NOIP 模拟 13

A 草莓

直接贪。

B 三色

发现是有限制的动态规划问题，\(n^3\) 很简单，直接在不合法的时候不转移就行了，然后发现转移很普通，有 \(j,k\to j,k\ \ \ j,k\to i,j\ \ \ j,k\to i,k\)，把后面两维看做矩阵形式，然后发现第一种没变，第二种和第三种相当于新加了一行，第二种是加列，第三种是加行，所以维护一个 \(s_i=\sum_{j=1}^n f_{now,i,j}+f_{now,j,i}\) 就可以做到快速转移，但是转移有限制，所以要做到给一些位置清零，拿东西存一下有值的位置，遇到不合法的就删了。具体看代码吧。

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii std::pair<int,int>
#define eb emplace_back
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
std::mt19937 myrand(std::chrono::high_resolution_clock::now().time_since_epoch().count());
inline int R(int n){return myrand()%n+1;}
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=5e3+10,mod=1e9+7,inf=1e9,ny=500000004;
inline void Min(int &x,int y){if(x>y)x=y;}
inline void Max(int &x,int y){if(x<y)x=y;}
inline void W(int &x,int y){x=(x+y)%mod;}
inline bool check(int l,int i,int r){return i>=l&&i<r;}
int n,m,s[N],t[N];
std::vector<pii> v[N];
std::vector<int> f,p,q,A[N],B[N];// f存的是值，A，B 存的是相应行列的值的下标，s 就是上文所说。
inline void insert(int x,int y,int v){
    if(!v)return ;
    int b=f.size();f.eb(v),p.eb(x),q.eb(y);
    A[x].eb(b),B[y].eb(b);W(s[x],v),W(s[y],v);
}// insert 相当于 f[x][y]=v
signed main(){
    freopen("color.in","r",stdin);freopen("color.out","w",stdout);
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
    int T=read();while(T--){
        n=read(),m=read();
        for(int i=1;i<=m;++i){int l=read(),r=read(),x=read();v[r].pb({l,x});}
        insert(0,0,1);
        for(int i=0;i<=n;++i){
            int la=0,lb=0,ra=i,rb=i;
            for(auto it:v[i]){
                int p=it.fi,x=it.se;
                if(x==3)Max(la,p),Max(lb,p);
                if(x==2)Max(la,p),Min(rb,p-1);
                if(x==1)Min(ra,p-1),Min(rb,p-1);
            }
            for(int j=0;j<=i;++j){
                if(j>=la&&j<=ra)continue;
                for(int x:A[j])W(s[p[x]],-f[x]),W(s[q[x]],-f[x]),f[x]=0;
                A[j].clear();// 如果不满足限制，更新信息
            }
            for(int j=0;j<=i;++j){
                if(j>=lb&&j<=rb)continue;
                for(int x:B[j])W(s[p[x]],-f[x]),W(s[q[x]],-f[x]),f[x]=0;
                B[j].clear();
            }
            if(i==n)break;
            for(int j=0;j<=i;++j)t[j]=s[j];
            for(int j=0;j<=i;++j)insert(i,j,t[j]);//转移新的一行
        }int ans=0;
        for(int i=0;i<=n;++i)W(ans,s[i]),s[i]=0,A[i].clear(),B[i].clear(),v[i].clear();
        f.clear(),p.clear(),q.clear();            
        std::cout<<(ans*ny%mod+mod)%mod<<'\n';
    }
}

C 博弈

只有三个值，首先考虑都不相等的情况，在图上就是三个点。当两点关于一点对称时：

先手必胜，直接移到同一个位置即可，然后不对称的时候，可以移动 \(A,C\) 使他们中的一个与 \(B\) 重合，此时如果是必胜局面那么先手可以继续操作，否则可以直接停止，所以当三个数不同时一定是先手必胜。
对于两个数相同的情况，设差为 \(x\),一定是移动使两个数重合，每次 \(x=\frac{x}{2}\)，如果达不到一定必败，所以 \(f_i=!f_{i/2}\)，所以当 \(x\) 的 lowbit 在偶数位置上的时候先手必胜。
然后正难则反，对于 \(a_i\)，统计不合法的情况，首先选择两个 \(a_i\)，然后枚举 \(x\) 的 lowbit，这个本质上就是异或，直接在 trie 树上找就行了，这里的 trie 树要从低位插。

D 后缀数组

不会。

总结

没啥好说的，睡觉场，不过没接触过有限制的 DP 转移，没想到直接不转移就行了，然后博弈论打出表来居然不觉得互不相同就能必胜，太唐了。