4.22错题总结

wangyichenawm · 2025-04-24 13:57:14 · 个人记录

T2(P1055 [NOIP 2008 普及组] ISBN 号码)

考试思路：直接按题意模拟

考试代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s;
    int ans=0,cnt=0;
    cin>>s;
    for(int i=0;i<s.size()-1;i++)
    {
        if(s[i]>='0'&&s[i]<='9')
        {
            ans++;
            cnt+=(s[i]-'0')*ans;
        }
    }
    cnt%=11;
    int a=s[s.size()-1]-'0';
    if(cnt!=a)
    {
        for(int i=0;i<s.size()-1;i++)
            cout<<s[i];
        if(cnt==10)
            cout<<"X\n";
        else    
            cout<<cnt<<'\n'; 
    }
    else
        cout<<"Right\n";
    return 0;
}

错误原因：忘了X这个情况

正确思路：同上

正确代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s;
    int ans=0,cnt=0;
    cin>>s;
    for(int i=0;i<s.size()-1;i++)
    {
        if(s[i]>='0'&&s[i]<='9')
        {
            ans++;
            cnt+=(s[i]-'0')*ans;
        }
    }
    cnt%=11;
    char a=s[s.size()-1];
    if(a!=cnt+'0'&&!(a=='X'&&cnt==10))
    {
        for(int i=0;i<s.size()-1;i++)
            cout<<s[i];
        if(cnt==10)
            cout<<"X\n";
        else    
            cout<<cnt<<'\n'; 
    }
    else
        cout<<"Right\n";
    return 0;
}

T3(P4826 [USACO15FEB] Superbull S)

考试思路：骗分

考试代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    cout<<37;
    return 0;
}

错误原因：没时间

正确思路：最小生成树

正确代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
int const N=2e3+10;
int n,m,an[N],f[N],sum,ans;
struct pc
{
    int x,y,v;
}g[N*N];
int find(int x)
{
    if(f[x]==x)
        return x;
    return f[x]=find(f[x]);
}
void unionn(int x,int y)
{
    x=find(x),y=find(y);
    if(x!=y)
        f[x]=y;
    return;
}
bool cmp(pc a,pc b)
{
    return a.v>b.v;
}
void kruskal()
{
    for(int i=1;i<=n;i++)
        f[i]=i;
    sort(g+1,g+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        int x=find(g[i].x),y=find(g[i].y);
        if(x==y)
            continue;
        unionn(x,y);
        sum++,ans+=g[i].v;
        if(sum==n-1)
            return;
    }
    return;
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>an[i];
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            g[++m]={i,j,an[i]^an[j]};
    kruskal();
    cout<<ans;
    return 0;
}

T5(P1582 倒水)

考试思路：把只剩1个到n个，都算一遍，求最小值

考试代码：

#include<bits/stdc++.h>
using namespace std;
long long n,mb=1,mn=1e9;
int k;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    k--;
    while(k!=0)
    {
        int z=mb;
        while(z<n)
            z*=2;
        mn=min(mn,z-n);
        mb*=2;
        mb++;
        k--;
    }
    while(mb<n)
        mb*=2;
    mn=min(mn,mb-n);
    cout<<mn<<'\n';
    return 0;
}

错误原因：没想拿满分

正确思路：这个东西可以看成二进制的形式，其实就是瓶数在二进制下1的个数

正确代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+1;
long long n,k,ans;
int f(int x)
{
    int t=0;
    while(x>0)
    {
        t+=(x%2);
        x/=2;
    }
    return t;
}
int main()
{
    cin>>n>>k;
    while(f(n)>k)
        ans+=n&-n,n+=n&-n;
    cout<<ans;
    return 0;
}