UVa 10730 - Antiarithmetic?

链接

传送门

题意

给出一个$0$到$n-1$的排列,若其中没有子数列为等差数列,输出”yes”,否则,输出”no”。

思路

记录每个数字出现的位置,枚举公差验证。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 10010;
int pos[maxn];
int main() {
int n;
while (~scanf("%d:", &n) && n) {
for (int i = 0; i < n; ++i) {
int x;
scanf("%d", &x);
pos[x] = i;
}
bool flag = true;
for (int i = 0; flag && i < n; ++i) {
for (int j = 1; flag && i + j * 2 < n; ++j) {
flag = !((pos[i] < pos[i + j]) ^ (pos[i + j] > pos[i + 2 * j]));
}
}
puts(flag ? "yes" : "no");
}
return 0;
}

支付宝扫码领红包