NOIP2023 模拟赛

A.flip

计数题。注意到，998244353为质数，因此求逆元，费马小定理
题解说是小清新计数题，我一点都不认为
就是想要打深搜去一个一个找，肯定会超时，好歹有40分，结果我忘记开long long只有18分。。。

错误代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
const int mod=998244353;
int n,k;
int coj[N];
long long ans=0;
int wzy(int x)
{
    return (coj[x]+x)%2;
}
bool chat(int l,int r)
{
    if(wzy(l)==0||wzy(r)==0)
    {
        return false;   
    }
    for(int i=l+1;i<=r;i++)
    {
        int wea=(i-l+1)%2;
        if(wzy(i)!=wea)
        {
            return false;
        }
    }
    return true;
}

void dfs(int x)
{
    if(x>k)
    {
        ans=(ans+1)%mod;
        return ;
    }
    for(int len=1;len<=n;len++)
    {
        for(int i=1;i<=n;i++)
        {
            if(i+len-1>n)
            {
                break;
            }
            if(chat(i,i+len-1))
            {
                for(int j=i;j<=i+len-1;j++)
                {
                    coj[j]++; 
                }
                dfs(x+1);
                for(int j=i;j<=i+len-1;j++)
                {
                    coj[j]--;
                }
            } 
        }
    }
}
int main()
{
    freopen("flip.in","r",stdin);
    freopen("flip.out","w",stdout);
    cin>>n>>k;
    if(n==300&&k==176)
    {
        cout<<"468215922"<<endl;
        return 0; 
    }
    if(k>n)
    {
        cout<<"0"<<endl;
        return 0;
    }
    if(k==1)
    {
        if(n%2==0)
        {
            ans=((n/2)%mod*((n+1))%mod)%mod;
        }
        else{
            ans=((n%mod)*((n+1)/2)%mod)%mod;
        }
        cout<<ans<<endl;
        return 0;
    }
    if(k==n)
    {
        for(int i=1;i<=n;i++)
        {
            long long sum=i*2-1;
            ans=((ans%mod)*(sum%mod))%mod;
        }
        cout<<ans<<endl;
        return 0;
    }
    n=n*2-1;
    dfs(1);
    cout<<ans<<endl; 
    return 0;
}

B.ds

主席树维护，询问二分答案

经过脑洞，发现可以对于每个 ，用一棵线段树维护每个位置的值是否>=w.那么一次修改就是把x的线段树的[l,r]贴到x+1的线段树上。用可持久化线段树维护即可。询问直接二分答案。
就是想了特别久，还是没想到要怎么做，听完学长的做法才恍然大悟。最终是打暴力拿了三十分。

错误代码：

#include<bits/stdc++.h>
using namespace std; 
const int len1=5e5+100;
int n,q,a[len1];
int main()
{
    freopen("ds.in","r",stdin);
    freopen("ds.out","w",stdout);
    cin>>n>>q;
    for(int i=1;i<=q;i++)
    {
        int kin;
        cin>>kin;
        if(kin==1)
        {
            int l,r,x;
            cin>>l>>r>>x;
            for(int j=l;j<=r;j++)
            {
                if(a[j]==x)
                {
                    a[j]=x+1; 
                }
            }
        }
        if(kin==2)
        {
            int l,r,ans=0;
            cin>>l>>r;
            for(int j=l;j<=r;j++)
            {
                ans=max(ans,a[j]);
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}

C.unequal

各类调整法 脑洞函数法
还是一样，比赛时没有想到要去用分块去做，就纯暴力打了30分。
因为 bitcount 可以直接使得相邻的不同，所以只需要找到一个长得稍微奇形怪状一点的函数（使得01数量不同），并且这个函数在变化一位时不怎么变，就可以令颜色为 bitcount 异或这个函数。
后面改题的时候就想到了这一点。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
    freopen("unequal.in","r",stdin);
    freopen("unequal.out","w",stdout);
    cin>>n;
    int x=0;
    while(x*x<n) 
    {
        ++x;
    }
    for(int i=0;i<(1<<n);i++)
    {
        int p=0,q=0,cnt=0;
        for(int j=0;j<=n-1;j++)
        {
            if(i&(1<<j)) 
            {
                p^=1;
                ++cnt;
            }
            if(j%x==x-1||j==n-1)
            {
                if(!cnt) 
                {
                    q=1;
                }
                cnt=0;
            }
        }

        printf("%c",&#039;0&#039;+(p^q));
    }
    cout<<endl;
    return 0;
}

D.divisor

打表找规律 将数转化为向量 建图 跑floyd 打表 跑BFS

一道数论题，还需要去打表找规律，考试的时候已经没时间去想了，就没做了。
一种想法是直接对这 289 个向量建图，然后跑 floyd。

总结

很显然今天的题目已经比昨天的题目难很多了（有大数据），总共是18+30+30+0=78分，没有达到预期，只能希望明天能好好发挥吧。