2023.7信友队暑假集训第2次测试复盘

信友队暑假集训第2次测试总结：

本次比赛都出的以前做过的题，但本蒟蒻确只写了320（悲

第一题：排行榜
一道水题，秒A

#include <bits/stdc++.h>
using namespace std;
string ans[105],s[105],t[105];
int vis[105];
int main(){
    int n;
    cin >> n;
    memset(vis,0,sizeof vis);
    for(int i = 1;i <= n;i++){
        cin >> s[i] >> t[i];
        if(t[i]=="SAME"){
            ans[i] = s[i];
            vis[i]=1;
        }
    }

    for(int i = 1;i <= n;i++){
        if(t[i]=="DOWN"){
            for(int j = 1;j <= i-1;j++){
                if(!vis[j]){
                    ans[j] = s[i];
                    vis[j]=1;
                    break;
                }
            }
        }
    }

    for(int i = n;i >= 1;i--){
        if(t[i]=="UP"){
            for(int j = n;j >= i+1;j--){
                if(!vis[j]){
                    vis[j]=1;
                    ans[j] = s[i];
                    break;
                }
            }
        }
    }

    for(int i = 1;i <= n;i++){
        cout << ans[i] << "\n";
    }

    return 0;
}

第二题：小信吃甜筒
一道水题：秒A

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,x,y,z;
int a[100005],b[100005],c[100005],d[200005];
bool cmp(int a,int b){
    return a>b;
}
signed main(){
    cin >>n>>m>>x>>y>>z;
    for(int i = 1;i <=x;i++){
        scanf("%lld",&a[i]);
    }
    for(int i = 1;i <=y;i++){
        scanf("%lld",&b[i]);
    }
    for(int i = 1;i <= z;i++){
        scanf("%lld",&c[i]);
    }
    sort(a+1,a+1+x,cmp);
    sort(b+1,b+1+y,cmp);
    sort(c+1,c+1+z,cmp);

    for(int i=1;i<=n;i++){
        d[i]=a[i];
    }
    for(int i=1;i<=m;i++){
        d[i+n]=b[i];
    }

    sort(d+1,d+1+n+m);
    for(int i =1;i<=min(z,n+m);i++){
        if(c[i]>=d[i]) d[i]=c[i];
    }
    int ans=0;
    for(int i = 1;i <= n+m;i++){
        ans+=d[i];
    }
    cout<<ans;


    return 0;
}

第三题：替换字母
本来是一道贪心水题，但是想错了贪心策略，WA20

#include <bits/stdc++.h>
using namespace std;
int n,m;
string s,ss;
int main(){
    cin >>n>> m;
    cin >> ss;
    int ans = 1e9;
    for(char a='a';a<='z';a++){
        int j = -1;
        int cnt=0;
        string s;
        s=ss+a;
        for(int i = 0 ;i < s.size();i++){
            if(i==0 && s[i] == a){
                j=i;
            }else if(s[i]==a && i - j >1){
                j=i;
                cnt++;
            }else if(i-j > m){
                j=i;
                cnt++;
            }
        }    
        ans=min(ans,cnt);    
    }
    cout << ans;

    return 0;
}

第四题：泽泽在巴西
调了很久，考试时都快崩溃了，考完才发现，球门到人的速度是距离×2，忘记了这个×2，不要读题太马虎，虽然改了×2只有70分，但是还要检查，需要更细心。

#include<bits/stdc++.h>
using namespace std;
int xz,yz,n,m;
int zx[305],zy[305];
double g[305][305];
int lx[305],ly[305];
bool check(int x,int y,int z){
    double a =sqrt((zx[x]-zx[y])*(zx[x]-zx[y]) +(zy[x]-zy[y])*(zy[x]-zy[y]));
    double b =sqrt((zx[x]-lx[z])*(zx[x]-lx[z]) +(zy[x]-ly[z])*(zy[x]-ly[z]));
    double c =sqrt((zx[y]-lx[z])*(zx[y]-lx[z]) +(zy[y]-ly[z])*(zy[y]-ly[z]));
    if(abs(a-b-c) > 1e-4) return true;
    return false;
}
int main(){
    cin >> xz >> yz >> n >>m;
    for(int i = 1;i <= n;i++){
        cin >> zx[i] >> zy[i];
    }
    for(int i = 1;i <= m;i++){
        cin >> lx[i] >> ly[i]; 
    }
    memset(g,0x3f,sizeof g);
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            for(int k = 1;k <= m;k++){
                if(i==j) continue;
                if(check(i,j,k)){
                    //可以建边
                    g[i][j]=sqrt((zx[i]-zx[j])*(zx[i]-zx[j])+(zy[i]-zy[j])*(zy[i]-zy[j]));
                    g[j][i]=sqrt((zx[i]-zx[j])*(zx[i]-zx[j])+(zy[i]-zy[j])*(zy[i]-zy[j]));
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        g[i][n+1] = sqrt((xz-zx[i])*(xz-zx[i])+(yz-zy[i])*(yz-zy[i]));
    }
    for(int k =1;k <= n+1;k++){
        for(int i = 1;i <= n+1;i++){
            if(i == k) continue;
            for(int j = 1;j <= n+1;j++){
                if(j == i || j == k) continue;
                g[i][j] = min(g[i][j],g[i][k]+g[k][j]);
            }
        }
    }
    printf("%.0lf",g[1][n+1]);
    return 0;
}

第五题：重要的城市
O（n^4),用弗洛伊德，秒A

#include <bits/stdc++.h>
using namespace std;
int n,m;
int u,v,w;
int dis[205][205];
int ans[205],ai;
int ids[205][205];
int vis[205][205];
int main(){
    cin >>n >>m;
    memset(dis,0x3f,sizeof dis);
    memset(ids,0x3f,sizeof ids);
    memset(vis,0x3f,sizeof ids);
    for(int i = 1;i <= m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        dis[u][v]=w;
        ids[u][v]=w;
        dis[v][u]=w;
        ids[v][u]=w;
        vis[v][u]=w;
        vis[u][v]=w;
    }

    for(int k = 1;k <= n;k++){
        for(int i = 1;i <= n;i++){
            if(k==i)continue;
            for(int j = 1;j <= n;j++){
                if(j==i||j==k)continue;
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }

    for(int x = 1 ; x <= n;x++){
        for(int i = 1;i <= n;i++){
            for(int j =1;j <= n;j++){
                ids[i][j]=vis[i][j];
            }
        }
        for(int k = 1;k <= n;k++){
            if(k==x)continue;
            for(int i = 1;i <= n;i++){
                if(i==x)continue;
                if(k==i)continue;
                for(int j = 1;j <= n;j++){
                    if(j==x)continue;
                    if(j==i||j==k)continue;
                    ids[i][j]=min(ids[i][j],ids[i][k]+ids[k][j]);
                }
            }
        }
        int flag=0;
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                if(i==j||i==x||j==x) continue;
                if(ids[i][j] > dis[i][j]) flag=1;
            }
        }
        if(flag){
            ans[++ai] = x;
        }
    }
    if(ai==0) cout<<"No important cities.";
    else for(int i = 1;i <= ai;i++){
        cout << ans[i] << " ";
    }
    return 0;
}

第六题：因为第四题没调出来，不想写，当时而且我很困，不想写，只想看着调

总结：下次比赛要合理安排时间，调试的时候不要仅仅静态调试，也要结合一些动态调试。实在调不出来的题放一放，写写其他题，换换思路，说不定回头再来就可以跳出来了。在调试的时候，如果样例小的话，试着手算一下，确保自己算法的正确性，这一次第四题没调出来的原因就是我一直死盯着屏幕，静态调试，没有动态去打数组，或者手算样例，如果手算样例就能发现其实我错在没有×2，就可以多拿70分。