8.26测试总结

Luck_Deepsea · 2025-08-26 18:12:36 · 算法·理论

8.21测试总结

T639104 信奥大联赛

得分:21

应得:100

考点:字典序

错误原因:错误使用手写string类型的排序

正确思路:

C：所有数相加%n

S:建立一个string类型的数组，进行排序

完整代码:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
string s[105];
int n,sum;
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x=0;
        cin>>s[i]>>x;
        sum+=x;
        sum%=n;
    }
    sort(s+1,s+n+1);
    cout<<s[sum+1];
    return 0;
}

T660516 来追梦运动会之慢跑赛

得分:90

应得:100

考点:模拟

错误原因:莫名其妙的WA，也许是没考虑完全？

思路:模拟过程

完整代码:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int a,b,c,d,e,f,x;
int sum1,sum2;
bool check(int a,int c,int t){
    while(t>(a+c))t-=(a+c);
    if(t>a)return 0;
    else return 1;
}
signed main()
{
    cin>>a>>b>>c>>d>>e>>f>>x;
    for(int i=1;i<=x;i++)
    {
        if(check(a,c,i))
        {
            sum1+=b;
        }
        if(check(d,f,i))
        {
            sum2+=e;
        }
    }
    if(sum1>sum2)
    {
        cout<<"Takahashi";
    }
    else if(sum1<sum2)
    {
        cout<<"Aoki";
    }
    else
    {
        cout<<"Draw";
    }
    return 0;
}

T642548 引爆炸弹

得分:10

应得:100

考点:dfs(深度优先搜索)

错误原因:没有转变数组类型（char->bool）

思路:很容易发现没有最少的引爆次数（每种方式都一样），因此只要用dfs(深度优先搜索)，模拟一遍即可

完整代码:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
struct node{
    int x,y;
};
int n,m,sum;
bool a[1005][1005];
queue<node>q;
void dfs(int x,int y){
    a[x][y]=0;
    for(int i=1;i<=m;i++)if(a[x][i]==1)dfs(x,i);
    for(int i=1;i<=n;i++)if(a[i][y]==1)dfs(i,y);
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            char x;
            cin>>x;
            a[i][j]=bool(x-'0');
            if(a[i][j]==1)
            {
                q.push({i,j});
            }
        }
    }
    while(q.size())
    {
        node f=q.front();
        q.pop();
        if(a[f.x][f.y]==1)
        {
            dfs(f.x,f.y);
            sum++;
        }
    }
    cout<<sum;
    return 0;
}

T642551 卡牌

得分:0

应得:100

考点:map

错误思路:模拟（这是错误的，而且代码还写错了QAQ）

正确思路:使用map进行模拟

完整代码:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int t;
signed main()
{
    cin>>t;
    while(t--)
    {
        int n,cnt=0;
        map<int,int>mp;
        cin>>n;
        while(n--)
        {
            int x;
            cin>>x;
            mp[x]++;
        }
        while(mp.size())
        {
            cnt++;
            int x=0;
            for(auto xx : mp)
            {
                x=xx.first;
                break;
            }
            mp[x]--;
            if(mp[x]==0)
            {
                mp.erase(x);
            }
            while(1)
            {
                x++;
                if(mp.count(x)==0)break;
                mp[x]--;
                if(mp[x]==0)mp.erase(x);
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}