2020-2021:teams:legal_string:jxm2001:contest:cf_732_div._1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:legal_string:jxm2001:contest:cf_732_div._1 [2021/07/12 16:42] jxm2001 创建 |
2020-2021:teams:legal_string:jxm2001:contest:cf_732_div._1 [2021/07/12 17:12] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 113: | 行 113: | ||
| </hidden> | </hidden> | ||
| + | ===== D. AquaMoon and Wrong Coordinate ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 初始有 $n$ 个人，第 $i$ 个人第 $t$ 秒的位置为 $x_i+v_it$。 | ||
| + | |||
| + | 接下来给定 $k$ 行，第 $i$ 行表示 $n$ 个人在第 $i-1$ 秒的位置，其中这 $n$ 个人的坐标顺序是打乱的。 | ||
| + | |||
| + | 这 $n\times k$ 个数据中有一个数据是错误的。求错误数据所在行号和正确的值。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 构造函数 $s1(t)=\sum_{i=1}^n x_i+v_it,s2(t)=\sum_{i=1}^n (x_i+v_it)^2$。 | ||
| + | |||
| + | 于是有 $s1(t+1)-s1(t)=\sum_{i=1}^n v_i$ 是固定值，利用该性质可以确定错误数据的行号。 | ||
| + | |||
| + | 接下来枚举错误数据的位置，根据 $s1$ 性质可以得到假定这个位置是错误的前提下的数据正确值。 | ||
| + | |||
| + | 由于 $s2(i+2)+s2(i)-s2(i+1)=\sum_{i=1}^n 2v_i$ 为确定值，利用该性质可以验证假设的正确性。总时间复杂度 $O(nk)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=1005; | ||
| + | int p[MAXN][MAXN]; | ||
| + | LL s1[MAXN],s2[MAXN]; | ||
| + | int main() | ||
| + | { | ||
| + | int n,k,row; | ||
| + | scanf("%d%d",&n,&k); | ||
| + | _for(i,0,k){ | ||
| + | _for(j,0,n){ | ||
| + | scanf("%d",&p[i][j]); | ||
| + | s1[i]+=p[i][j]; | ||
| + | s2[i]+=1LL*p[i][j]*p[i][j]; | ||
| + | } | ||
| + | } | ||
| + | _for(i,1,k){ | ||
| + | if((s1[k-1]-s1[0])*i!=(s1[i]-s1[0])*(k-1)){ | ||
| + | row=i; | ||
| + | break; | ||
| + | } | ||
| + | } | ||
| + | _for(i,0,n){ | ||
| + | LL v=p[row][i]+(s1[k-1]-s1[0])/(k-1)*row-(s1[row]-s1[0]); | ||
| + | LL v2=s2[row]-1LL*p[row][i]*p[row][i]+v*v; | ||
| + | if(row>=3){ | ||
| + | if(s2[2]+s2[0]-s2[1]*2==v2+s2[row-2]-s2[row-1]*2){ | ||
| + | printf("%d %d\n",row,v); | ||
| + | fflush(stdout); | ||
| + | return 0; | ||
| + | } | ||
| + | } | ||
| + | else{ | ||
| + | if(s2[k-1]+s2[k-3]-s2[k-2]*2==s2[row+2]+v2-s2[row+1]*2){ | ||
| + | printf("%d %d\n",row,v); | ||
| + | fflush(stdout); | ||
| + | return 0; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/contest/cf_732_div._1.1626079340.txt.gz · 最后更改: 2021/07/12 16:42 由 jxm2001
