死亡回放模考过程：
【8:30~8:45】看T1，直接爆搜！
【8:45~9:00】看T2，推规律ing…
【9:00~9:10】写T2代码，短得不可思议！一看就是错解。
【9:10~9:30】T3不会先放着，去写T4的暴力。
【9:30~10:00】尝试T3的暴力…
【10:00~11:30】挂机ing…
预计得分：100+50+50+50=250
实际得分：10+0+0+50=60
订正得分：100+100+100+100=400
死亡原因失分原因：
1.T1不用dijkstra写最短路，用了dfs。
2.T2明知错误，就是不改。
3.T3暴力打错了
正确解法：
T1 最短路计数
考场错误写法：
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
vector<int>a[1000005];
int cnt[1000005];
int dis[1000005];
bool vis[1000005];
void dfs(int k,int num){
if(dis[k]==num){
cnt[k]++;
cnt[k]%=100003;
}else if(dis[k]>num){
cnt[k]=1;
dis[k]=num;
}
for(int i = 0;i<a[k].size();i++){
dfs(a[k][i],num+1);
}
}
signed main(){
memset(dis,0x3f,sizeof dis);
cin>>n>>m;
for(int i = 1;i<=m;i++){
int u,v;
cin>>u>>v;
a[u].push_back(v);
}
dfs(1,0);
for(int i = 1;i<=n;i++){
cout<<cnt[i]<<'\n';
}
return 0;
}
爆搜。
正解：
使用dijkstra求最短路径。
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct e{
int u,v;
};
struct node{
int p,d;
bool operator < (const node & a)const{return a.d<d;}
};
vector<e>mp[2000005];
int n,m;
int dis[1000005];
bool vis[1000005];
int cnt[1000005];
priority_queue<node>q;
void init(){
memset(dis,0x3f,sizeof dis);
cin>>n>>m;
for(int i = 1;i<=m;i++){
int a,b;
cin>>a>>b;
mp[a].push_back({b,1});
mp[b].push_back({a,1});
}
}
void dijkstra(){
dis[1]=0;
cnt[1]=1;
q.push( (node){1,0} );
while(!q.empty()){
node temp = q.top();
q.pop();
int x = temp.p,d = temp.d;
if(vis[x])continue;
vis[x]=1;
for(int i = 0;i<mp[x].size();i++){
int tt = mp[x][i].u,ww=mp[x][i].v;
if(dis[tt]>dis[x]+ww){
dis[tt]=dis[x]+ww;
cnt[tt]=cnt[x];
q.push( (node){tt,dis[tt]} );
}else if(dis[tt]==dis[x]+ww){
cnt[tt]+=cnt[x];
cnt[tt]%=100003;
}
}
}
}
void write(){
for(int i = 1;i<=n;i++){
cout<<cnt[i]<<'\n';
}
}
void solve(){
init();
dijkstra();
write();
}
signed main() {
solve();
return 0;
}
难度：\color{lightgreen}普及+/提高。
T2 frog
考场错解：
计算两只青蛙分别能走多少个来回，取最大值。如果走到另外一边则将值减少1。然后取最大值。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int l,v1,v2,t,num,x1,x2;
signed main(){
cin>>num;
while(num--){
cin>>l>>v1>>v2>>t;
if(v1!=0)x1 = (v1*t)/l;
if((v1*t)*1.0/l==x1)x1--;
if(v2!=0)x2 = (v2*t)/l;
if((v2*t)*1.0/l==x2)x2--;
cout<<max(x1,x2)<<"\n";
}
return 0;
}
正解：
对于测试点3,4,5,6特殊判断。
对于其他测试点：先将 v_1,v_2 从大到小排序，接下来求 gcd = \gcd(v_1,v_2)，然后求 l_1 = \frac{v_{1}}{gcd},l_2 = \frac{v_2}{gcd}，如果 l_1 和 l_2 奇偶性相同，那么它们在游的过程中不会出现多计算的情况，否则他们重叠的部分就是 ((v_2\times t\div l_2 \div l)+1)/2
接着：
算出最后一个来回两只青蛙游的距离，看他们有没有相遇，如果相遇了，那么答案增加1。
最后输出 就是快的青蛙游的来回数减去多算的部分再加回多减去的部分就行了。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int l,v1,v2,t,num;
int ans1,ans2;
signed main(){
cin>>num;
while(num--){
cin>>l>>v1>>v2>>t;
if(v1==v2||v1==0||v2==0){
cout<<((v1+v2)*t/l+1)/2<<'\n';
continue;
}
if(v1<v2)swap(v1,v2);
int gcd = __gcd(v1,v2);
int l1 = v1/gcd;
int l2 = v2/gcd;
if((l1-l2)%2==0||gcd==-1){
ans1 = 0;
}else{
ans1 = ((v2*t/l2/l)+1)/2;
}
int lh1 = v1*t/l;
int lh2 = v2*t/l;
int c1 = v1*t-lh1*l;
int c2 = v2*t-lh2*l;
if(lh1%2==lh2%2){
if(c1+c2>=l)ans2=1;
else ans2 = 0;
}else{
if(c1>=c2)ans2=1;
else ans2 = 0;
}
cout<<v1*t/l-ans1+ans2<<'\n';
}
return 0;
}
难度：\color{lightgreen}普及+/提高 ~ \color{blue}提高/省选-。
T3 奇怪的矩阵
考场错解：
建立一个桶存储已经有的部分，再从 l 到 r 去更新桶。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[100005];
int n,q;
int t[10000005];//
signed main(){
cin>>n;
for(int i = 1;i<=n;i++)cin>>a[i];
cin>>q;
while(q--){
memset(t,0,sizeof t);
int l,r;cin>>l>>r;
for(int i = l;i<=r;i++){
for(int j = 1;j<=n;j++){
if(i==1){
//cout<<a[j]<<" ";
t[a[j]]++;
}else{
//cout<<a[j]+i-1<<" ";
t[a[j]+i-1]++;
}
}
}
int cnt = 0;
for(int i = 0;i<=100005;i++){
if(t[i]>0){
cnt++;
}
}
cout<<cnt<<"\n";
}
return 0;
}
正解：
不难证明，求矩阵中从第 l 列到第 r 列有多少个不同的数字其实就是求矩阵中从第 0 列到第 r-l 列有多少个不同的数字。
先给 a 数组排序。
建立差分数组 d ，存储 a_i 和 a_{i-1} 之间有多少个数（不含 a_i 和 a_{i-1} ）。
再给 d 数组排序。
询问中，使用二分查找在 d 中找第一个大于 r-l 的数，输出这个 d_1 到 d_{\text{这个数}} 的和加 (n-k)*(r-l)+n。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[100005];
int d[100005];
int s[100005];
int n,q;
signed main(){
cin>>n;
for(int i = 1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
int tt = 0;
for(int i = 2;i<=n;i++)d[i-1]=a[i]-a[i-1]-1;
sort(d+1,d+n);
for(int i = 1;i<=n;i++){
s[i]=s[i-1]+d[i];
}
cin>>q;
while(q--){
int l,r;cin>>l>>r;
r = r-l,l = 0;
int k=upper_bound(d+1,d+n,r)-d-1;
cout<<s[k]+(n-k)*r+n<<' ';
}
return 0;
}
难度：\color{lightgreen}普及+/提高。
T4 jxcakak
赛时错解：
暴力枚举左上角。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[2005][2005];
//int mx[2005][2005];
//int mn[2005][2005];
int w,h,n;
signed main(){
cin>>w>>h>>n;
for(int i = 1;i<=w;i++){
for(int j = 1;j<=h;j++){
cin>>a[i][j];
}
}
int ans = LLONG_MAX;
for(int i = n;i<=w;i++){
for(int j = n;j<=h;j++){
int x1 = i-n+1;
int y1 = j-n+1;
int x2 = i;
int y2 = j;
int mx = 0;
int mn = LLONG_MAX;
for(int l = x1;l<=x2;l++){
for(int r = y1;r<=y2;r++){
mx = max(mx,a[l][r]);
mn = min(mn,a[l][r]);
}
}
ans = min(ans,mx+mn);
}
}
cout<<ans;
return 0;
}
正解：
先用单调队列维护每一行的最大值与最小值，再用单调队列维护每一列的最大值与最小值，再枚举每一个正方形即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int w,h,n;
int a[2005][2005];
int mxx[2005][2005];
int mxy[2005][2005];
int mnx[2005][2005];
int mny[2005][2005];
deque<int>qmn,qmx;
signed main(){
cin>>w>>h>>n;
for(int i = 1;i<=w;i++)for(int j = 1;j<=h;j++)cin>>a[i][j];
for(int i = 1;i<=w;i++){
qmn.clear();qmx.clear();
for(int j = 1;j<=h;j++){
while(qmx.size()&&j-qmx.front()>=n)qmx.pop_front();
while(qmx.size()&&a[i][j]>=a[i][qmx.back()])qmx.pop_back();
qmx.push_back(j);
while(qmn.size()&&j-qmn.front()>=n)qmn.pop_front();
while(qmn.size()&&a[i][j]<=a[i][qmn.back()])qmn.pop_back();
qmn.push_back(j);
if(j>=n){
mxx[i][j-n+1]=a[i][qmx.front()];
mnx[i][j-n+1]=a[i][qmn.front()];
}
}
}
for(int j = 1;j<=h-n+1;j++){
qmn.clear();qmx.clear();
for(int i = 1;i<=w;i++){
while(qmx.size()&&i-qmx.front()>=n)qmx.pop_front();
while(qmx.size()&&mxx[i][j]>=mxx[qmx.back()][j])qmx.pop_back();
qmx.push_back(i);
while(qmn.size()&&i-qmn.front()>=n)qmn.pop_front();
while(qmn.size()&&mnx[i][j]<=mnx[qmn.back()][j])qmn.pop_back();
qmn.push_back(i);
if(i>=n){
mxy[i-n+1][j]=mxx[qmx.front()][j];
mny[i-n+1][j]=mnx[qmn.front()][j];
}
}
}
int ans = LLONG_MAX;
for(int i = 1;i<=w-n+1;i++){
for(int j = 1;j<=h-n+1;j++){
//cout<<mxy[i][j]<<" "<<mny[i][j]<<'\n';
ans = min(ans,mxy[i][j]+mny[i][j]);
}
}
cout<<ans;
return 0;
}
难度：\color{lightgreen}普及+/提高。
