链接
传送门
题意
给出一个\(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;
}
|