3561. 数螃蟹

楼上确定公差的方法都错了，只不过这道题测试数据没有测出来。

给定数据 1, 4, 5, 6, 9, 10, 13, 15, 找出差为 3, 1, 1, 3, 1, 3, 2, 按其它人的做法得出 3 或 1。事实上，公差是 2。

正确的做法是按差频数降序排序，依次检查是否有合适的答案。

这个问题不是我发现的，而是一个同学发现的

//总体思路:确定公差，然后模拟结果

include

using namespace std;

int main(void) {
int n;
cin >> n;
int d;
int max = 0;
vector vec, res;
map hash;
while (n–) {
int num;
cin >> num;
vec.push_back(num);
}
//利用map找到公差
int len = vec.size()
for (int i = 1; i < len; i++) {
hash[vec[i] - vec[i - 1]]++;
}
for (map :: iterator it = hash.begin(); it != hash.end(); it++) {
if (it -> second > max) {
max = it -> second;
d = it -> first;
}
}
//确定首项
int i;
for (i = 1; i < len; i++) {
if (vec[i] - vec[i - 1] == d) {
long long one = vec[i] - i * d;
res.push_back(one);
for (int j = 1; j < vec.size(); j++) {
res.push_back(array1 + j * d);
}
//比较选取这个i后，是否满足不同数最多只有三个的要求
int cnt = 0;
for (int k = 0; k < len; k++) {
if (vec[k] != res[k]) {
cnt++;
}
}
if (cnt > 3) {
res.clear();
continue;
} else {
break;
}
}
}
输出结果
long long one = vec[i] - i * d;
for (int i = 0; i < len; i++) {
cout << one + i * d << ” “;
}
cout << endl;
return 0;
}

include

include

define ll long long

using namespace std;
const int M = 1e5+1;
ll flag[M];
ll g[M];
mapm;
int main() {
int n;
cin>>n;
for(int i = 0; i < n; i++) {
cin>>flag[i];
if(i>0)
m[flag[i]-flag[i-1]]++;
}
int M=0;
int d;
//找公差
for(map::iterator it=m.begin(); it!=m.end(); it++) {
if(it->second>M) {
M=it->second;
d=it->first;
}
}
int count=0;
int i = 0;
while(i=0; j–) { //先前枚举使其公差为d 1 2 3 5 6 7 8 9 10
g[j]=flag[j];
if(g[j+1]-g[j]!=d) {
g[j]=g[j+1]-d;
count++;
}
if(count>3)
break;
}
for(int j = i+1; j < n; j++) {//向后枚举使其公差为d
g[j]=flag[j];
if(g[j]-g[j-1]!=d) {
g[j]=g[j-1]+d;
count++;
}
if(count>3)
break;
}
if(count<=3) {
break;
}
i++;
}
for(int i = 0 ; i < n; i++)
cout<<g[i]<<” “;
}

include

const int maxn = 100005;
int n;

long long A[maxn],B[maxn];

int main(){
// freopen(“3561.txt”,”r”,stdin);
scanf(“%d”,&n);
for(int i=0;i=0;j--){ B[j] = B[j+1] - d; if(B[j] != A[j]){ k++; if(k>=4){
flag = false;
break;
}
}
}
if(flag){
for(int j=i+2;j=4){
flag = false;
break;
}
}
}
}
if(flag){
break;
};
}
for(int i=0;i<n;i++){
printf(“%lld “, B[i]);
}

return 0;

}