题目链接：http://codeforces.com/problemset/problem/352/B
题目意思：给出一个长度为n的序列 a1, a2, ..., an（序号i，1 <= i <= n）。需要从这个序列中，找出符合这两个条件的数：1、这个数在序列 a1, a2, ..., an 中； 2、该数的所有位置（也就是序号i）构成等差数列。一旦有一个位置不满足（此时和上一个位置所求出的公差就与之前的公差不相等），这个数就不符合条件，不应该输出。找完之后，输出所有满足这两个条件的数的总数，还有这些数以及对应的公差。
值得注意的地方有：当这个数在序列中只出现一次的时候，也属于可输出的，此时它的公差为0，也就是ST 1的情况； 还有，整个序列一个都找不到这样的数，要输出0。
这条是我赛中第一次提交的，因为一下子就看懂题目了。不过赛中是没过到啦，以为很简单...赛后，修改，调试，整整两天多，终于AC了。方法比较笨，还是那句话，自己写的特别有感觉。后来看了别人用vector来做，代码长度缩短了很多。看来还是需要学一下容器啊～～～
方法一：
| Time | Memory |
|---|
| 92 ms | 2000 KB |
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std; const int maxn = 1e5 + ; struct pairs
{
int index; // 保存位置的编号i
int num; // 保存序列的数，即题目中的a[i]
}p[maxn]; int cmp(pairs a, pairs b)
{
if (a.num != b.num)
return a.num < b.num;
return a.index < b.index; // 关键！！！保证公差是正数，否则过不了test 10
} int c[maxn], b[maxn];
int f[maxn]; int main()
{
int i, j, k, n, sum;
while (scanf("%d", &n) != EOF)
{
memset(c, , sizeof(c));
for (j = i = ; i <= n; i++)
{
scanf("%d", &p[i].num);
c[p[i].num]++; // 统计a[i]在序列中出现多少次
if (c[p[i].num] == )
{
b[j++] = p[i].num; // 保存a[i]
}
p[i].index = i;
}
k = j;
sort(p+, p+n+, cmp); // 序列a的数从小到大排序，如果相同，则按具体的位置从小到大排序
sort(b+, b+j); // 保证输出的序列是递增的
/* for (i = 1; i <= n; i++)
{
printf("p[%d].index = %d, p[%d].num = %d\n", i, p[i].index, i, p[i].num);
}
*/
memset(f, , sizeof(f)); // 保存公差
int tmp, j, flag, minus;
sum = ;
for (i = ; i <= n; i += c[p[i].num])
{
// printf("i = %d\n", i);
// printf("c[%d] = %d\n", p[i].num, c[p[i].num]);
if (c[p[i].num] == ) // 在序列中只出现一次的数，公差设为0
{
f[p[i].num] = ;
sum++; // 也属于可输出的
}
else
{
flag = ;
for (j = i; j < c[p[i].num]+i-; j++) // 检测相同数字的公差是否相等
{
// printf("j = %d\n", j);
if (j == i) // 用第一、二个的位置算出公差即可，下面用这个公差来检查其他位置的公差是否和这个公差相等
{
tmp = p[j+].index - p[j].index;
// printf("tmp = %d\n", tmp);
}
minus = p[j+].index - p[j].index;
// printf("minus = %d\n\n", minus);
if (tmp != minus)
{
f[p[i].num] = -; // 发现有一个位置不等于之前算出的公差
flag = ;
// printf("error !!!!\n\n"); }
}
if (j == c[p[i].num]+i- && !flag) // 相同的数的所有位置算出的公差都相等
{
sum++;
// printf("success!!!\n");
f[p[i].num] = tmp; // 保存公差
}
}
}
if (sum)
{
printf("%d\n", sum); // 符合条件的总数
for (i = ; i < k; i++)
{
if (f[b[i]] != -)
{
printf("%d %d\n", b[i], f[b[i]]);
}
}
}
else
printf("0\n");
}
return ;
}
方法二：
| Time | Memory |
|---|
| 92 ms | 4900 KB |
用vector方法写的，记得每次都要清空。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
using namespace std; const int maxn = 1e5 + ;
const int maxm = ; vector <int> s[maxn];
int ans[maxn][maxm]; int main()
{
int i, j, n, tmp, flag;
while (scanf("%d", &n) != EOF)
{
memset(s, , sizeof(s));
for (i = ; i <= n; i++)
{
scanf("%d", &tmp);
s[tmp].push_back(i);
}
int d, len, cnt = ;
for (i = ; i <= maxn; i++)
{
flag = ;
len = s[i].size();
if (len == )
continue;
else if (len == )
{
ans[cnt][] = i;
ans[cnt][] = ;
cnt++;
}
else
{
d = s[i][] - s[i][];
if (len == )
{
ans[cnt][] = i;
ans[cnt][] = d;
flag = ;
cnt++;
}
// printf("d = %d\n", d);
if (!flag)
{
for (j = ; j < len; j++)
{
if (s[i][j] - s[i][j-] != d)
break;
}
if (j == len)
{
ans[cnt][] = i;
ans[cnt][] = d;
cnt++;
}
}
}
}
printf("%d\n", cnt);
for (i = ; i < cnt; i++)
{
printf("%d %d\n", ans[i][], ans[i][]);
}
}
return ;
}