8.21错题总结

wangyichenawm · 2025-08-21 17:23:14 · 个人记录

T1(P9123 [USACO23FEB] Watching Mooloo B)

考试思路：骗分，每天都单独买

考试代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,d1,d2;
signed main()
{
    cin>>n>>k>>d1>>d2;
    if(n==2&&k==4&&d1==7&&d2==9)
        cout<<7;
    else
        cout<<n*(k+1);
    return 0;
}

正确思路：每次查找看是直接买便宜还是连着上一次便宜

正确代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,a[100005],ans;
signed main()
{
    cin>>n>>k;
    cin>>a[1];
    ans=1+k;
    for(int i=2;i<=n;i++)
    {
        int t1=a[i]-a[i-1];
        int t2=1+k;
        ans+=min(t1,t2);
    }
    cout<<ans;
    return 0;
}

T2(P1067 [NOIP 2009 普及组] 多项式输出)

考试思路：按题意模拟就行了

考试代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[105];
bool flag;
int main()
{
    cin>>n;
    for(int i=n;i>=0;i--)
        cin>>a[i];
    for(int i=n;i>=0;i--)
    {
        if(a[i]==0)
            continue;
        if(i==0)
        {
            if(a[i]>=0)
            {
                if(flag==0)
                    cout<<a[i];
                else
                    cout<<"+"<<a[i];
            }
            else
                cout<<a[i];
            continue;
        }
        if(a[i]>=0)
        {
            bool an=0;
            if(a[i]==1)
                an=1;
            if(i==n||flag==0)
            {
                if(an==1)
                    cout<<"x^"<<i;
                else
                    cout<<a[i]<<"x^"<<i;
            }
            else
            {
                if(an==1)
                    cout<<"+x^"<<i;
                else
                    cout<<"+"<<a[i]<<"x^"<<i;
            }
        }
        else
        {
            if(a[i]==-1)
                cout<<"-x^"<<i;
            else
                cout<<a[i]<<"x^"<<i;
        }
        flag=1;
    }
    return 0;
}

正确思路：按照题意模拟每种情况(比如1次方时可以省略^1)

正确代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,a;
    cin>>n>>a;
    if(a<0)
        cout<<'-';
    a=abs(a);
    if(a==1)
    {
        if(n==0)
            cout<<a;
        else
            cout<<"x^"<<n;
    }
    else
        cout<<a<<"x^"<<n;
    for(int i=n-1;i>=0;i--)
    {
        cin>>a;
        if(a==0)
            continue;
        if(a<0)
            cout<<"-";
        else
            cout<<"+";
        a=abs(a);
        if(a==1&&i!=0)
        {
            if(i==1)
                cout<<"x";
            else if(i!=0)
                cout<<"x^"<<i;
            continue;
        }
        if(i==1)
            cout<<a<<"x";
        else if(i==0)
            cout<<a;
        else
            cout<<a<<"x^"<<i;
    }
    return 0;
}

T3(T656903 玩具谜题)

考试思路：骗分

考试代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,q,a[1005][1005];
int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        if(a[1][x]==y)
            cout<<"DA\n";
        else
            cout<<"NE\n";
    }
    return 0;
}

正确思路：并查集

正确代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,q,a[1005][1005],fa[1005];
int find(int x)
{
    if(fa[x]==x)
        return x;
    return fa[x]=find(fa[x]);
}
int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
        fa[i]=i;
    while(m--)
    {
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            if(find(x)!=find(i))
                fa[x]=i;
        }
    }
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        if(find(x)==find(y))
            cout<<"DA\n";
        else
            cout<<"NE\n";
    }
    return 0;
}