NOIP2024 解题报告

Graphcity · 2024-12-02 23:28:46 · 生活·游记

省流：没有上 400pts 的自行反思

总结：峰值难度不如 CSP2024，但整体难度比 CSP2024 和 NOIP2023 要难一些。

这套题最大的困难在于 时间。考察的都是基本功，既有 T4 这种比较朴素但是略复杂的数据结构，也有 T3 这样需要花一些心思去大力分类讨论的题目。这体现出了平时练习时需要重视基本功的锻炼。

Edit

贪心，从左往右能配对就配对，不配对就摆烂。O(n)。

这个贪心的正确性在于：

1. 这是第一题。我是位置学大师
2. 相信大家都会调整法吧？反正我不会

参考用时：10min

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=2e5;

int T,n,A[Maxn+5],B[Maxn+5],a[Maxn+5][2],b[Maxn+5][2],c[Maxn+5],d[Maxn+5];

inline void Solve()
{
    scanf("%d",&n);
    For(i,1,n) scanf("%1d",&A[i]);
    For(i,1,n) scanf("%1d",&B[i]);
    For(i,1,n) scanf("%1d",&c[i]);
    For(i,1,n) scanf("%1d",&d[i]);
    for(int i=1,j=Maxn;i<=n;++i) {if(c[i]) j=min(j,i),a[j][A[i]]++; else j=Maxn;}
    for(int i=1,j=Maxn;i<=n;++i) {if(d[i]) j=min(j,i),b[j][B[i]]++; else j=Maxn;}
    int xa[2],xb[2],ans=0;
    xa[0]=xa[1]=xb[0]=xb[1]=0;
    For(i,1,n)
    {
        // cerr<<xa[0]<<' '<<xa[1]<<' '<<xb[0]<<' '<<xb[1]<<endl;
        if(c[i]) For(j,0,1) xa[j]+=a[i][j];
        if(d[i]) For(j,0,1) xb[j]+=b[i][j];
        if(!c[i] && !d[i]) {ans+=(A[i]==B[i]); continue;}
        if(!c[i])
        {
            if(xb[A[i]]) xb[A[i]]--,ans++;
            else xb[A[i]^1]--; continue;
        }
        if(!d[i])
        {
            if(xa[B[i]]) xa[B[i]]--,ans++;
            else xa[B[i]^1]--; continue;
        }
        int flg=0;
        For(j,0,1) if(xa[j] && xb[j] && !flg) {xa[j]--,xb[j]--,ans++,flg=1;}
        For(j,0,1) if(xa[j] && xb[j^1] && !flg) {xa[j]--,xb[j^1]--,flg=1;}
    }
    printf("%d\n",ans);
    For(i,0,n+1) A[i]=B[i]=c[i]=d[i]=0;
    For(i,0,n+1) For(j,0,1) a[i][j]=b[i][j]=0;
}

int main()
{
    // freopen("1.in","r",stdin);

    scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

Assign

不会的可以退役了。

如果相邻的两个点不是一条链从首连到尾，而且尾部还不一样的话，那么肯定合法的。O(n\log V)。

参考用时：10min

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=2e5,Mod=1e9+7;

inline int Pow(int x,int y)
{
    int res=1;
    while(y)
    {
        if(y&1) res=1ll*res*x%Mod;
        x=1ll*x*x%Mod,y>>=1;
    }
    return res;
}

int T,n,m,K,ans=1;
pair<int,int> h[Maxn+5];

inline int F(int x) {return Pow(K,x*2);}

inline void Solve()
{
    cin>>n>>m>>K; ans=1;
    For(i,1,m) cin>>h[i].first>>h[i].second;
    sort(h+1,h+m+1);
    For(i,1,m-1) if(h[i].first==h[i+1].first && h[i].second!=h[i+1].second)
        {cout<<0<<endl; return;}
    ans=1ll*F(h[1].first-1)*F(n-h[m].first)%Mod;
    For(i,1,m-1) if(h[i].first!=h[i+1].first)
    {
        int s1=1ll*Pow(K,h[i+1].first-h[i].first-1)*(K-1)%Mod;
        int s2=F(h[i+1].first-h[i].first);
        ans=1ll*ans*(s2-s1+Mod)%Mod;
    }
    cout<<ans<<endl;
}

int main()
{
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);

    cin>>T;
    while(T--) Solve();
    return 0;
}

Traverse

本场最难题。需要耐心和一些观察力。

21 世纪最重要的品质——淡定。

如果把边看作方点，点看作圆点的话，我们实际上求的就是一棵仙人掌对应圆方树的生成树个数。