CQUPT 2025级 数据科学与大数据技术英才班 周测#02
A Trifecta
找出序列中最小的三个数所对应的位置。
推荐使用 方法 2，如果你还不会 结构体+sort 排序，请认真学习 方法 2 的写法！！！
- 解法1：
三次 \(for\) 循环，依次找到最小、次小、第三小的数即可。
int pos1,pos2,pos3;
int minn1,minn2,minn3;
minn1=minn2=minn3=INF;
for(int i=1;i<=n;i++)
{if(minn1>t[i]){minn1=t[i];pos1=i;}
}
for(int i=1;i<=n;i++)
{if(i==pos1) continue;if(minn2>t[i]){minn2=t[i];pos2=i;}
}
for(int i=1;i<=n;i++)
{if(i==pos1||i==pos2) continue;if(minn3>t[i]){minn3=t[i];pos3=i; }
}printf("%d %d %d\n",pos1,pos2,pos3);
- 解法 2：
找最小的数，可以将原数组从小到大排序，输出前三项即可。
题目要求输出下标，所以不能直接排序。
可以将数据与位置合并成为一个结构体，将结构体按照数据从小到大排序，输出前三个位置即可。
这里使用 \(sort\) 对结构体进行排序，需要自定义函数规定排序方式。
struct node
{int id,val;
}t[N]; bool mycmp(node x,node y)
{return x.val<y.val;
}
scanf("%d",&n);
for(int i=1;i<=n;i++)
{int x;scanf("%d",&x);t[i]={i,x};
}
sort(t+1,t+1+n,mycmp);
printf("%d %d %d\n",t[1].id,t[2].id,t[3].id);
B 前缀和的逆
一维前缀和+差分模板题，前缀和数组求差分即为原数组。
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)printf("%d ",a[i]-a[i-1]);
C 地毯
二维前缀和模板题
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);a[x1][y1]++; a[x2+1][y2+1]++;a[x1][y2+1]--; a[x2+1][y1]--;
} for(int i=1;i<=n;i++)
{for(int j=1;j<=n;j++){a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];printf("%d ",a[i][j]); }puts("");
}
本题存在加强版，考察内容仍为二维前缀和，可以尝试一下。
P13787 地毯 加强版
D 最大正方形
二维前缀和
三重循环，前两重枚举正方形左上角的坐标，第三重枚举正方形的边长
然后判断正方形内数值之和是否等于面积即可
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];}
}for(int i=1;i<=n;i++)
{for(int j=1;j<=m;j++){for(int k=1;k<=min(n-i+1,m-j+1);k++){int x1=i, y1=j, x2=i+k-1, y2=j+k-1; int sum=(a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1]);if(sum==k*k) ans=max(ans,k);}}
}printf("%d\n",ans);
E Swap and Range Sum
看到统计 \(\sum\limits_{l\leq i\leq r} A_i\)，想到前缀和，设前 \(i\) 个数的和为 \(s[i]\)
每次进行交换 \(A_x,A_{x+1}\) 的操作，只有前 \(x\) 个数的和发生变化
将 \(s[x]\) 变为 \(s[x]-a[x]+a[x+1]\)，交换 \(s[x],s[x+1]\) 即可
while(q--)
{int k,x,l,r;scanf("%d",&k);if(k==1){scanf("%d",&x);s[x]-=a[x];s[x]+=a[x+1];swap(a[x],a[x+1]);}else{scanf("%d%d",&l,&r);printf("%d\n",s[r]-s[l-1]); }
}
F Many Repunit Sum
把题意换种说法，\(B_i\) 就是一个 \(A_i\) 位整数，每一位都是 \(1\)，然后求出 \(\sum\limits_{i=1}^N B_i\) 即可。
从数据范围可以看出（样例 \(2\) 也提示了），答案可能非常大，用 int, long long 都不行。
这就需要一些 高精度加法 的思想。
先把每一位上的数字相加，再依次进位（类似于列竖式算加法）。
那么，如何处理 \(B_i\) 呢？直接枚举每一位就会 \(\text{TLE}\)。
因为 \(B_i\) 每一位都是 \(1\)，可以转换为区间加法，联想到 差分。
每次输入 \(A_i\)，对于差分数组 \(d\)，\(d[A_i+1]-1,d[1]+1\)，最后对差分数组求前缀和就能得到原数组。
scanf("%d",&n);
for(int i=1;i<=n;i++)
{int x;scanf("%d",&x);m=max(m,x);d[x+1]--;d[1]++;
}
for(int i=1;i<=m+1;i++)d[i]+=d[i-1];
然后，从低到高依次进位即可。最后按位输出最终数字。
for(int i=1;i<=m;i++)
{if(d[i]>=10) d[i+1]+=d[i]/10,d[i]%=10;if(i==m&&d[i+1]>0) m++;
}
for(int i=m;i>=1;i--)printf("%d",d[i]);
puts("");