本文迁移自洛谷原文。
赛时看到“误差修复”就一直往随机化方面想了
假设对于时刻 ， 第 个人的位置为 。 本文统一用 表示人，用 表示时刻
那么我们令 ，
再令，
令
观察发现，由于在求和后，顺序就变得无关紧要了，故在没有改动数据的情况下， 就等于 。同样，可以发现，如果第 个时刻都没有被改动，那么， 。
根据这个性质，我们就可以求出哪一个时刻进行了更改。令更改的时刻为 。
如果第 个时刻进行了更改，那么就会有；但是又因为有 ，故有 ，更进一步的，有其中一个小于 ，另一个大于 。
所以，我们可以求出所有的 ，并对它们进行排序。在没有改动数据的情况下， 都等于 。故经过排序后， 与 就自然的排到了头和尾。
现在，我们求出了那个时刻进行了更改。然后我们需要求出哪个数值需要更改。
观察 。
由于累加后顺序不重要，故可以展开，得到
在没有改动数据的情况下，又
看到这里可能没有什么发现
但是如果我们再进一步，令
就有
所以，在不改动数据的情况下， 都是相等的。也就是说， 是一个等差数列！
根据这个性质，我们就可以轻易推断出，在更改数据前，的值。
最后我们就可以求出那个值了。
令更改数据前的 ，
令，。
观察更改前后 的变化。没有更改的那些值是不会带来贡献的，带来贡献的只有更改的那个值。
令更改后那个值为。
故
答案就是
完结~~~
Code:
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include<bits/stdc++.h>
#define ll long long
#define mp make_pair
using namespace std;
const int mxn=1e3+3;
ll a[mxn][mxn],n,m;
ll sum[mxn],squsum[mxn];
pair<int,int> delta[mxn];
int err;
ll sumdelta,squsumdelta;
ll orgsum,orgsqusum;
ll sumchange,squsumchange;
ll deltasqusumchange,basesqusumchange;
ll ans;
inline void solve(){
cin>>n>>m;
for(int i=1;i<=m;++i)for(int j=1;j<=n;++j)cin>>a[i][j],sum[i]+=a[i][j],squsum[i]+=a[i][j]*a[i][j];
for(int i=1;i<m;++i)delta[i].first=sum[i+1]-sum[i],delta[i].second=i;
sort(delta+1,delta+m);
sumdelta=delta[2].first;
if(delta[1].second<delta[m-1].second)err=delta[m-1].second;
else err=delta[1].second;
if(err==2){
deltasqusumchange=((squsum[5]-squsum[4])-(squsum[4]-squsum[3]));
basesqusumchange=(squsum[5]-squsum[4])-deltasqusumchange*3;
}else{
basesqusumchange=squsum[2]-squsum[1];
if(err==3)deltasqusumchange=((squsum[5]-squsum[4])-(squsum[2]-squsum[1]))/3;
else deltasqusumchange=((squsum[3]-squsum[2])-(squsum[2]-squsum[1]));
}
orgsum=sum[err-1]+sumdelta;
sumchange=orgsum-sum[err];
orgsqusum=squsum[err-1]+basesqusumchange+deltasqusumchange*(err-2);
squsumchange=orgsqusum-squsum[err];
ans=(squsumchange-sumchange*sumchange)/2/sumchange;
cout<<err-1<<' '<<ans+sumchange<<'\n';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;T=1;
for(;T--;)solve();
}
|