2021“MINIEYE杯”中国大学生算法设计超级联赛（6）

还就那个没有思维，耶！

暂时没有想明白，等想懂了再补。

[1001 Yes, Prime Minister]

solution

题面：给出 ，求 使得 且 为正质数且该正质数最小。 可以为负数。​​

做法：先求个和，即 ​​。这个要为正质数，至少要求 或 或 或 ​​，后面两类可以手玩，前两类手玩后等价于找一个质数。可以二分，也可以直接暴力找。反正都能过。

时间复杂度 或 。

//2021.8.13 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=3e7+10;
namespace MAIN{
    int prim[N/10],tot,vis[N];
    int num;
    inline void ck(const res &nu){
        if(nu<num)num=nu;
    }
    inline int solve(res x){
        if(x>=1){
            if(!vis[x])return 1;
            if(!vis[2*x-1])return 2;
            if(!vis[x<<1|1])return 2;
        }
        res o=max(x,1-x),p=max(x,2-x);
        while(vis[o])o++;
        ck(o<<1);
        while(vis[2*p-1])p++;
        ck(2*p-1);
        return num;
    }
    inline void MAIN(){
        vis[1]=1;
        for(res i=2;i<=N-10;i++){
            if(!vis[i])prim[++tot]=i;
            for(res j=1;j<=tot&&prim[j]*i<=N-10;j++){
                vis[prim[j]*i]=1;
                if(i%prim[j]==0)break;
            }
        }
        res Case=read();
        while(Case--){
            num=inf,printf("%d\n",solve(read()));
        }
    }
}

[1002 Might and Magic]

solution

题面：两个人，每个人都有五个属性：​。还有两个参数 ​。第 ​ 个人对第 ​​ 个人物理攻击伤害为 ​，魔法伤害为 ​。​ 表示第 ​ 个人可以使用魔法攻击的次数。​ 是第 ​ 个人的生命值。​，现给出 ​，你可以将数值分配到 ​ 上， 已知。问最多可以打掉第二个人多少生命？​

做法：若分配之后物伤大于等于法伤，那我肯定全选择物伤，则让关于法伤的都为 ​。否则当法伤大于物理伤害时，我们枚举总攻击次数 ​ 和 ​，把 ​ 分配成 ​​​，算出此时的值，然后与 ​ 做比较，会发现此时的值一定大于其他值（敲公式太麻烦了，懒得敲了），也即最大值情况会在只分配物伤或只分配法伤时取到。分配物伤是直接的，分配法伤是个二次函数，取对称轴两边即可。而我们知道 ​ 只有 ​​​ 种​，所以枚举 后总复杂度就是 ​​ 了。

官方题解是注意物伤关于 是下凸函数，法伤关于 ​ 也是下凸函数，下凸函数的和仍然是下凸函数，所以答案一定在端点处取到。

坑：向上取整我们可以分子减一再整体加一变成向下取整。

//2021.8.14 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    int Cp,Cm,H0,A1,D1,N;
    inline LL solve(const res &o,const res &t){
        res now=N-(A1-o);
        if(A1-o<0)return 0;
        if(now<0)return 0;
        RG LL ret=1ll*Cp*max(1,now-D1)*t;
        RG LL p=(1ll*now*Cm-Cp)/(2*Cm);
        if(0<=p&&p<=t&&p<=now)ret=max(ret,1ll*Cm*(now-p)*p+1ll*Cp*(t-p));
        if(0<=p-1&&p-1<=t&&p-1<=now)p--,ret=max(ret,1ll*Cm*(now-p)*p+1ll*Cp*(t-p)),p++;
        if(0<=p+1&&p+1<=t&&p+1<=now)p++,ret=max(ret,1ll*Cm*(now-p)*p+1ll*Cp*(t-p)),p--;
        if(t<now)ret=max(ret,1ll*Cm*(now-t)*t);
        else ret=max(ret,1ll*Cp*(t-now));
        return ret;
    }
    inline void MAIN(){
        res Case=read();
        while(Case--){
            Cp=read(),Cm=read(),H0=read()-1,A1=read(),D1=read(),N=read();
            RG LL ans=0;
            for(res l=1,r;l<=H0;l=r+1){
                r=H0/(H0/l);
                res a=(l+Cp-1)/Cp,b=r/Cp;
                if(a<=b)ans=max(ans,solve(b,H0/l+1));
            }
            printf("%lld\n",max(ans,solve(A1,H0/(1ll*Cp*A1)+1)));
        }
    }
}

[1003 0 tree]

solution

题面：一棵树，有点权 ​​​​ 和边权 ​​​​，每次可以选择一条从 ​​​​ 到 ​​​​ 的路径 ​ 和权值 ​，其中 ​，使 ​，​。现让你构造不超过 次操作使得所有点权和边权变为 。

做法：先将边权转为点权，即每个点的第二点权为连接它的边的权值和。那每次操作只与端点有关了。

注意到几件事，首先每次操作的总异或和不变，所以总异或和为 ​​ 是有解的充分条件。其次，每个点第一权值和第二权值的奇偶关系是始终不变的，所以奇偶相同也是一个充分条件。另一方面，我们发现加减的不同仅在两个点的相隔点数的奇偶，于是考虑黑白染色，即黑点与白点相邻。那么只有异色才是都加，同色是一加一减。那么同色点间的操作是不会改变这种颜色的第一与第二权值和，能改变只能来自异色操作。而 ，所以每种颜色的第一权值异或和小于等于第二权值和的负数也是一个充分条件。实际上，以上已经构成充要条件。接下来我们来构造方案。

考虑第一权值和第二权值分开来处理。

我们发现同色间进行 ​ 会使

。

同色间进行 ​ 会使

。

于是若同色层的第一权值异或和为 ​ 且每个点第一权值为偶数的话，按照第一种操作我们就可以让每个点的第一权值为 ​，那么就处理好第一权值了。若同色层的第二权值和为 ​​ 且每个点第二权值为偶数的话，按第二种操作我们就能处理好第二权值了。

于是问题变成如何让同色层的异或和以及权值和都为 ​​​ 且每个点的点权都是偶数呢？假设黑色异或和以及权值和分别为 ​​​，白色的分别为 ​​​​。我们根据充分条件，暂时得到的是 ​​​，以及 ​ 和 ​ 同奇偶，​ 和 ​​ 同奇偶。我们选择两个异色点，执行 ​ 三次操作，发现这样 ​​。好像 不符合我们预期？再冷静一下，一条边转成点权的时候，一部分是变成黑色，一部分是变成白色，于是 ，因此我们成功做到了权值和为 ​。那全是偶数的条件该怎么办呢？注意到每个点的两个权值的奇偶性是相同的，我们先对第二权值动刀，即每个点减去自己的第二权值。这样可以使每个点的第二权值变为 （因为总权值和为 ​，而这种操作不会改变总权值和），同时由于 是偶数，所以不知不觉第一权值也都是偶数了。于是就成功了。

计算一下操作次数，是 次，刚好通过。

另一方面，先处理第一权值的话，操作次数更少，只有 。

坑：由于 c++ 异或负数会出错，所以要每一次操作要注意一下。

//2021.8.14 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e4+10;
namespace MAIN{
    int n;
    int a[N];
    LL b[N];
    int col[N];
    vector<int> G[N];
    int v[2][N],ax[2];
    void dfs(res x,res fax,res depx){
        col[x]=depx&1;
        for(auto tox:G[x]){
            if(tox==fax)continue;
            dfs(tox,x,depx+1);
        }
    }
    struct P{
        int x,y;
        LL w;
        P() {}
        P(res x,res y,RG LL w):x(x),y(y),w(w) {}
    }ans[N<<2];
    int ansx;
    inline void get(const res &x,const res &y,const RG LL &w){
        ans[++ansx]=P(x,y,w),a[x]^=w,a[y]^=w,b[x]+=w;
        if(col[x]!=col[y])b[y]+=w;
        else b[y]-=w;
    }
    inline void solve(){
        n=read();
        for(res i=1;i<=n;i++)a[i]=read(),b[i]=0,vector<int>().swap(G[i]);
        for(res i=1;i<n;i++){
            res u=read(),v=read(),w=read();
            b[u]+=w,b[v]+=w,G[u].pb(v),G[v].pb(u);
        }
        dfs(1,0,1),ax[0]=ax[1]=0;
        static int A[2];
        static LL B[2];
        A[0]=A[1]=B[0]=B[1]=0;
        for(res i=1;i<=n;i++){
            res c=col[i];
            v[c][++ax[c]]=i,A[c]^=a[i],B[c]+=b[i];
            if((a[i]^b[i])&1){puts("NO");return;}
        }
        if(A[0]^A[1]){puts("NO");return;}
        if(-B[0]<A[0]){puts("NO");return;}
        ansx=0;
        if(ax[0]&&ax[1])get(v[0][1],v[1][1],A[0]),get(v[0][1],v[1][1],(-B[0]-A[0])/2),get(v[0][1],v[1][1],(-B[0]-A[0])/2);
        for(res c=0;c<=1;c++){
            if(ax[c]<=1)continue;
            for(res i=1;i<ax[c];i++)get(v[c][i],v[c][i+1],a[v[c][i]]);
            res i=1,j=2;
            while(233){
                while((!b[v[c][i]]||i==j)&&i<=ax[c])i++;
                if(i>ax[c])break;
                while((!b[v[c][j]]||i==j)&&j<=ax[c])j++;
                if(j>ax[c])break;
                res ni=v[c][i],nj=v[c][j];
                RG LL tmp;
                if(b[ni]<0)tmp=(-b[ni])/2;
                else tmp=b[ni]/2,swap(ni,nj);
                get(ni,nj,tmp),get(ni,nj,tmp);
            }
        }
        puts("YES");
        printf("%d\n",ansx);
        for(res i=1;i<=ansx;i++)printf("%d %d %lld\n",ans[i].x,ans[i].y,ans[i].w);
    }
    inline void MAIN(){
        res Case=read();
        while(Case--)solve();
    }
}

[1004 Decomposition]

solution

题面：一张 ​ 个点的无向完全图，你需要找出 条无重复点的路径使每条路径长度分别等于给出的长度 ，保证 为总边数且 。

做法：直接构造出一组解，别问我是怎么构造的。设 。

​

感觉这种比 要强？​​

如果还有看不懂的就看代码吧。

//2021.8.5 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=5e5+10;
namespace MAIN{
    int m,k;
    int a[N],b[N];
    inline void MAIN(){
        res T=read();
        for(res Case=1;Case<=T;Case++){
            m=read(),k=read();
            res n=(m-1)>>1;
            res ax=0;
            for(res i=1;i<m;i++)if(i&1)b[i]=i/2+1;else b[i]=m-i/2;
            for(res o=0;o<n;o++){
                a[++ax]=m;
                for(res i=1;i<m;i++){
                    a[++ax]=(b[i]+o-1)%(2*n)+1;
                }
            }
            a[++ax]=m;
            res now=0;
            printf("Case #%d:\n",Case);
            for(res i=1;i<=k;i++){
                res l=read();
                for(res j=1;j<=l;j++)printf("%d ",a[++now]);
                printf("%d\n",a[now+1]);
            }
        }
    }
}

[1005 Median]

solution

题面：给出 ，现希望你将 的排列分成 组，使得每一组的中位数为 ​。

做法：先分析下中位数条件。假设一组里大于中位数的个数是 ，小于是 ，则 。

然后再来思考限制中位数意味着什么。我们将 的排列用 ​​ 隔开，分成 组别（空的也算）。那么选择两个数加入同一组里就等价于选择不同组别的数。注意到 ，这意味着越后面的组别就有更大的机动性，它们可以插入到前面那些组里。即第 组别的数的个数至少要小于等于 。于是我们就设计了一个贪心思路。我们把所有大于 的部分拿出来互相消除，这样除非有一组的个数大于其他组的和，不然就只剩 个或 ​ 个（考虑总数的奇偶）。剩 个肯定有解了，剩 个我们希望把这个 放在最后面（这是可以做到的），然后就看前面不大于 的部分有没有可以消除的。剩余多个也是这个道理。

如果还没看懂就看代码吧，感觉有点难以讲明白。

复杂度 ​ 或 ，瓶颈在分成 组别的过程。

//2021.8.15 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    int n,m;
    int b[N];
    int a[N],c[N];
    inline void solve(){
        n=read(),m=read();
        for(res i=1;i<=m;i++)b[i]=read();
        sort(b+1,b+m+1),b[m+1]=n+1;
        a[1]=b[1]-1;
        for(res i=2;i<=m+1;i++)a[i]=b[i]-b[i-1]-1;
        for(res i=1;i<=m+1;i++)if(a[i]>i-1)c[i]=a[i]-i+1,a[i]=i-1;else c[i]=0;
        res id=0,sum=0;
        for(res i=1;i<=m+1;i++){
            sum+=c[i];
            if(c[id]<=c[i])id=i;
        }
        if(c[id]<=sum-c[id]){
            res o=sum&1;
            if(!o)puts("YES");
            else {
                for(res i=1;i<=m;i++)if(a[i]){puts("YES");return;}
                puts("NO");
            }
        }
        else {
            res s=0;
            for(res i=1;i<=m+1;i++)if(i!=id)s+=a[i];
            if(s>=(c[id]-(sum-c[id])))puts("YES");
            else puts("NO");
        }
    }
    inline void MAIN(){
        res Case=read();
        while(Case--)solve();
    }
}

[1006 The Struggle]

solution

题面：给出 ，。

求 。​

做法：容易考虑枚举 ，那后面的东西就是个卷积的东西， 即可。

但是呢，每一个 对应的 都是不同的，那直接全部卷起来肯定是不太行的。

然后接下来还没想出来，之后再补。

[1007 Power Station of Art]

solution

题面：给你一个有标号无向图，每个点有黑或白的颜色以及它自己的标号，每次可以选一条边并交换上面两个点的标号，但是如果两个点的颜色相同，这两个点的颜色会同时改变。现在给你两个形态一致的图，问第一张图经过操作之后能否变为第二张图。

做法：注意到交换操作的等价形式是交换标号和颜色，再反转颜色。于是我们的交换就可以去掉 if 条件了。

那么对于一个标号而言，交换次数的奇偶就代表了它的颜色。这让我们想了二分图。

如果是一张二分图，一个标号在哪一边就意味着它的颜色了。所以只要标号数量和颜色是对应的，那我们一个个按类似拓扑序的顺序来交换点，就保证能构造出方案了。

如果不是二分图，那每个标号的颜色就可以任意换了。于是我们只要标号数量是对应的，利用奇环让每个标号的颜色对应，就可以转成二分图时的构造了。

时间复杂度 。

坑：1. 图未必连通，要一个个连通块处理。

​ 2. 标号不唯一，可能重复，所以要按数量算。

//2021.8.16 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e6+10;
namespace MAIN{
    int n,m;
    int a[2][N],b[2][N];
    char str[N];
    vector<int> A[N],G[N];
    int col[N],fl[N];
    int cnt;
    void dfs(res x,res c){
        if(col[x]!=-1){if(c!=col[x])fl[cnt]=1;}
        else {
            col[x]=c,A[cnt].pb(x);
            for(auto tox:G[x])dfs(tox,c^1);
        }
    }
    int Fl[N][2];
    int s[N];
    inline void solve(){
        n=read(),m=read();
        for(res i=1;i<=n;i++)vector<int>().swap(G[i]),col[i]=-1;
        for(res i=1;i<=m;i++){
            res u=read(),v=read();
            G[u].pb(v),G[v].pb(u);
        }
        cnt=0;
        for(res x=1;x<=n;x++)if(col[x]==-1)cnt++,vector<int>().swap(A[cnt]),fl[cnt]=0,dfs(x,0);
        for(res i=1;i<=n;i++)a[0][i]=read();
        scanf("%s",str+1);
        for(res i=1;i<=n;i++)b[0][i]=(str[i]=='R');
        for(res i=1;i<=n;i++)a[1][i]=read();
        scanf("%s",str+1);
        for(res i=1;i<=n;i++)b[1][i]=(str[i]=='R');
        for(res i=1;i<=cnt;i++){
            if(!fl[i]){
                res FL=0;
                for(auto x:A[i])Fl[a[0][x]][col[x]^b[0][x]]++,Fl[a[1][x]][col[x]^b[1][x]]--;
                for(auto x:A[i])if(Fl[a[0][x]][col[x]^b[0][x]]||Fl[a[1][x]][col[x]^b[1][x]])FL=1;
                for(auto x:A[i])Fl[a[0][x]][col[x]^b[0][x]]=Fl[a[1][x]][col[x]^b[1][x]]=0;
                if(FL){puts("NO");return;}
            }
            else {
                res sum=0,FL=0;
                for(auto x:A[i])s[a[0][x]]++,sum^=b[0][x],s[a[1][x]]--,sum^=b[1][x];
                if(sum)FL=1;
                for(auto x:A[i])if(s[a[0][x]]||s[a[1][x]])FL=1;
                for(auto x:A[i])s[a[0][x]]=s[a[1][x]]=0;
                if(FL){puts("NO");return;}
            }
        }
        puts("YES");
    }
    inline void MAIN(){
        res Case=read();
        while(Case--){
            solve();
        }
    }
}

[1008 Command and Conquer: Red Alert 2]

solution

题面：给出三维空间里若干个点，你从任意点出发，每次只能向坐标递增的方向走，路径由你自己构造。问你走的路径到这若干个点的切比雪夫距离的最小值。

做法：考虑二分答案。那么那就等于在一堆正方体中找出一条路径满足每个正方体都被碰到。一个贪心就是找到一个 ​​ 坐标最小的正方体，然后走到这个最小的 ​​ 坐标。这显然是最优的，因为不走白不走，一定是不劣的。于是我们已经得到了 的做法。

再冷静一下，发现也没必要二分答案了。考虑直接将所有点平移到正方体的左前下角，那么我们每次贪心想找的点就是这些点本身了，直接找就行了。时间复杂度也是 ​​​，瓶颈在排序。

坑：实现下面那个做法的时候，注意到所有点平移了，所以这里求得的 是平移后的 。而正方体中心平移到一个端点是边长乘 ，那么 即可。

//2021.8.16 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=5e5+10;
namespace MAIN{
    int n;
    struct P{
        int x,y,z;
        P() {}
        P(res x,res y,res z):x(x),y(y),z(z) {}
    }h[N];
    Pair x[N],y[N],z[N];
    int fl[N];
    inline int get(const RG P &I,const res &x,const res &y,const res &z){
        return max({(I.x-x),(I.y-y),(I.z-z)});
    }
    inline void MAIN(){
        res Case=read();
        while(Case--){
            n=read();
            for(res i=1;i<=n;i++){
                res a=read(),b=read(),c=read();
                x[i]=mp(a,i),y[i]=mp(b,i),z[i]=mp(c,i),h[i]=P(a,b,c);
            }
            sort(x+1,x+n+1),sort(y+1,y+n+1),sort(z+1,z+n+1);
            res ans=0;
            for(res i=1;i<=n;i++)fl[i]=0;
            res i=1,j=1,k=1;
            while(i<=n&&j<=n&&k<=n){
                res a=x[i].fi,b=y[j].fi,c=z[k].fi;
                RG Pair o=min({mp(get(h[x[i].se],a,b,c),x[i].se),mp(get(h[y[j].se],a,b,c),y[j].se),mp(get(h[z[k].se],a,b,c),z[k].se)});
                fl[o.se]=1,ans=max(ans,o.fi);
                while(fl[x[i].se]&&i<=n)i++;
                while(fl[y[j].se]&&j<=n)j++;
                while(fl[z[k].se]&&k<=n)k++;
            }
            printf("%d\n",(ans+1)>>1);
        }
    }
}

[1009 Typing Contest]

solution

题面：每个人有两个数值 ，现让你挑出若干个人，使得 最大。​

做法：稍微做一些化简，即

$$ans=\sum s_i(1-f_i(-f_i+\sum f_j))\\\\ =\sum s_i+\sum s_if_i^2-(\sum s_if_i)(\sum f_i)$$

发现前面两个东西和 ​​​ 无关，只有最后一个东西有关。考虑枚举 ​​，容易想到背包，即设 ​​ 表示当前 ​​​​ 的最大价值，那么求的就是 ​。注意到 ​ 是两位小数，那么直接枚举的复杂度就是 ​，轻而易举地过不去。

然后考场上 ljc 迅速发现 实际上不用枚举那么多，而且是容易证明的。

我们还是考虑对每一个人进行计算，那么对一个人而言的贡献就是 。贪心地想，肯定要系数大于 ，即 。把 直接放到 ，那么 。假设我们选了 个人，两边同乘 ​，则 。而必然存在一个人的 是最大的，所以 ，也即 ，于是 。

这样的话，复杂度就变成了 ​，这大概是可以跑过去的，不行就再剪剪枝，毕竟上面的放缩是比较松的。​

坑：1. 注意 ​ 后，​ 也要乘 ​​​。​

​ 2. 虽然他题面是让你输出九位小数，但他让你输出的小数是在 还是两位小数的时候，所以最后五位一定是 。如果直接除以 ​​ 会产生精度损失，所以建议取模来拿到小数部分。

​ 3. 乘上 时注意是有精度损失的，浮点数存到 位，那损失的量大致是 ，所以要加上 差不多避免精度损失。​​

//2021.8.16 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=100+10;
const int M=1414+10;
namespace MAIN{
    int n;
    LL s[N];
    int f[N];
    LL g[M];
    inline void MAIN(){
        res Case=read();
        while(Case--){
            n=read();
            res m=0;
            for(res i=1;i<=n;i++){
                s[i]=Read();
                RG db t;
                cin>>t,f[i]=int(t*100++0.004),m+=f[i];
            }
            m=min(m,int(100*sqrt(2*n)));
            RG LL ans=0;
            for(res F=0;F<=m;F++){
                for(res i=0;i<=F;i++)g[i]=0;
                for(res i=1;i<=n;i++){
                    RG LL v=s[i]*(f[i]*f[i]+10000-f[i]*F);
                    if(v<=0)continue;
                    for(res j=F;j>=f[i];j--)if(j==f[i]||g[j-f[i]])g[j]=max(g[j],g[j-f[i]]+v);
                }
                ans=max(ans,g[F]);
            }
            printf("%lld.%04lld00000\n",ans/10000,ans%10000);
        }
    }
}

[1010 Array]

solution

题面：给出一个 ​ 数组，满足 ​ 数组单调不减。设 ​ 表示有多少个不同的数在 ​ 集合里，询问是否存在一个数组 ​，使得对任意的 ​，​ 是 ​​ ​的充要条件？

做法：我们刚开始肯定是想直接构造 数组，可惜想了一圈之后头皮发麻，只感觉限制之间非常难以处理。而比较好的做法则是构造 数组，其中 表示最前的在 之后与 颜色一致的 ，即 ，为了方便，不存在 则设为 。如果我们构造出了一个 数组，则很容易就能构造出 数组。事实上，这个 数组要比 数组容易构造许多。

我们考虑 与 的关系。经过分类讨论，我们发现 ，这是相当容易证明的。而且通过证明它的过程，我们发现，满足这个条件的 ，一定就是合法的 ，也一定能构造出 。而利用这个条件就直观许多。若 ，则 。若 ，则 。但仅有这样的不等式是不容易确定 间的矛盾的，我们细化这个构造的过程。

首先， 的 一定都不是第一次出现的，这可以由 这个区间限制来证明，而无法证明的情况则是 ，那就特判掉。一个位置的数不是第一次出现这个条件转到 上，就是存在一个 ，且 是这个位置。于是， 是构造 使必选的，剩余的数包括 是可选可不选的，且所有数（除了 ）都只能选一次。

接下来我们看那个不等式的限制，即 ，我们发现这个不等式的左端点与右端点都是单调的。这给我们一定的贪心启示。我们设必选数的集合为 ，其余为 ，每选出一个就将其删去（除了 ）。 从小到大扫过去，设当前 中最小值为 ， 中最小的大于 的为 ，接下来开始基于贪心着讨论。

1. 。这一定不合法了，因为无处放 。
2. 。这也一定不合法了，因为 不合法。
3. 和 只有一个不合法。那就只能选合法的那个了。
4. 和 都合法，但 。注意到扫描到后面时，若可以放 就一定可以放 ，所以我们选择更不劣的方案，这里放 。
5. 和 都合法，但 。我们暂时的方案是放 ，但同时从 中去掉 ，在 中加入 。若最终构造方案有了 ，那这种方案无问题。若没有，我们将 变成 即可。而且，这种暂时的方案是不会影响到其他构造的，理由同上。

于是，我们就成功做到了最优的构造。实现上，维护这两个集合可以用 set 或者 list，做到时间复杂度 或 。为了方便，我写的是 。

//2021.8.22 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e5+10;
namespace MAIN{
    int n;
    int b[N];
    set<int> A,B;
    set<int>::iterator it;
    inline void solve(){
        n=read();
        set<int>().swap(A),set<int>().swap(B);
        for(res i=1;i<=n;i++)b[i]=read();
        if(b[1]==n+1){puts("NO");return;}
        for(res i=1;i<=n;i++){
            if(b[i]==i){
                if(i>1){puts("NO");return;}
                for(res j=i+1;j<=n;j++)if(b[j]!=j){puts("NO");return;}
                puts("YES");return;
            }
            if(b[i]<i){puts("NO");return;}
        }
        for(res i=1;i<b[1];i++)B.insert(i);
        for(res i=b[1]+1;i<=n;i++)A.insert(i);
        B.insert(n+1);
        for(res i=1;i<n;i++){
            if(b[i]<b[i+1]){
                if(b[i+1]==n+1)continue;
                it=A.find(b[i+1]);
                if(it==A.end())B.erase(B.find(b[i+1]));
                else A.erase(it);
            }
            else {
                //i<x<=b[i]
                while(!B.empty()&&*B.begin()<=i)B.erase(B.begin());
                if(!A.empty()){
                    res x=*A.begin();
                    if(x<=i){puts("NO");return;}
                    if(B.empty()){
                        if(x>b[i]){puts("NO");return;}
                        A.erase(A.begin());
                        continue;
                    }
                    res y=*B.begin();
                    if(x>b[i]){
                        if(y>b[i]){puts("NO");return;}
                        if(y!=n+1)B.erase(B.begin());
                        continue;
                    }
                    if(y>b[i]){A.erase(A.begin());continue;}
                    if(x>y){
                        A.erase(A.begin());
                        if(y!=n+1)B.erase(B.begin());
                        B.insert(x);continue;
                    }
                    else A.erase(A.begin());
                }
                else {
                    if(B.empty()){puts("NO");return;}
                    res y=*B.begin();
                    if(y>b[i]){puts("NO");return;}
                    if(y!=n+1)B.erase(B.begin());
                }
            }
        }
        puts(A.empty()?"YES":"NO");
    }
    inline void MAIN(){
        res Case=read();
        while(Case--){
            solve();
        }
    }
}

[1011 Game]

solution

题面：两个人在博弈，设当前区间为 ，两个人的操作为使区间变成 或 ，一个人面对的区间是 时输，再给出若干个区间 以及对应的参数 ，表示当一个人面对的区间是 时这个人直接判胜或判负。若干组询问，每次询问一个初始区间 ，问谁胜？

做法：说下我考场的思路。我们先将状态转移图写出来，发现如果没有那些特殊区间，​​ 与 ​​ 的情况是一致。也就是胜负取决于 ​​ 的奇偶。如果有那些特殊区间应该怎么办呢？我们会发现只要离那些特殊区间两步之远的都不会受影响。这是容易证明的（​ 表示先手必负态）。若 ​ 是 ​，那么 ​ 和 ​ 必须是 ​，那么 ​ 就必须是 ​ 了。​若 ​ 是 ​，这说明 ​ 与 ​ 中至少有一个是 ​ ，那么 ​ 和 ​ 中也至少有一个是 ​，这又可以导出 ​ 和 ​ 中至少有一个是 ​，于是 也是 了。

有了这个性质，我们考虑按 分组维护。特殊区间以及与它在两步之内的区间直接暴力计算。

现考虑一个询问 ，如果它所在的组内没有元素，则说明它的胜负只与 的奇偶有关。若有元素，则找到比它小且最大的区间，按照之前的性质，​​ 的胜负一定与这个区间有关。而以上操作都是可以用 map 维护的，总时间复杂度 。

具体实现上，我们在暴力维护特殊区间相关区间时，是要按从小到大的顺序的，因为有可能相关区间之间会互相影响。具体处理手段可以看代码。

//2021.8.16 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    int n,q;
    struct P{
        int l,r,c;
        P() {}
        P(res l,res r,res c):l(l),r(r),c(c) {}
        inline void init(){
            l=read(),r=read(),c=read();
        }
        inline bool operator < (const RG P &A){
            return r-l+1<A.r-A.l+1;
        }
    }a[N];
    map<int,int> A[5*N],pos;
    map<int,int>::iterator it;
    int ax;
    inline void insert(const res &l,const res &r,const res &c){
        if(!pos.count(l+r)){
            map<int,int>().swap(A[++ax]);
            A[pos[l+r]=ax][l]=c;
        }
        else {
            res idx=pos[l+r];
            if(A[idx].count(l))return;
            A[idx][l]=c;
        }
    }
    inline int query(const res &l,const res &r){
        if(pos.count(l+r)){
            res idx=pos[l+r];
            if(A[idx].count(l))return A[idx][l];
            it=A[idx].upper_bound(l);
            if(it!=A[idx].end())return (*it).se;
            return (l+r)&1;
        }
        else return (l+r)&1;
    }
    inline bool ck(const res &l,const res &r){
        if(!pos.count(l+r))return 0;
        res idx=pos[l+r];
        return A[idx].count(l+r)>0;
    }
    int o[N],ox;
    inline void MAIN(){
        res Case=read();
        while(Case--){
            ax=0,n=read(),q=read(),map<int,int>().swap(pos);
            for(res i=1;i<=n;i++)a[i].init(),insert(a[i].l,a[i].r,a[i].c);
            sort(a+1,a+n+1);
            for(res i=1;i<=n;){
                res j=i;
                while(a[i].r-a[i].l+1==a[j].r-a[j].l+1&&j<=n)j++;
                for(res k=i;k<j;k++){
                    res l=a[k].l,r=a[k].r,c=a[k].c;
                    if(l>1){
                        if(ck(l-1,r))continue;
                        if(!c)insert(l-1,r,1);
                        else {
                            res x1=query(l-1,r-1);
                            if(!x1)insert(l-1,r,1);
                            else insert(l-1,r,0);
                        }
                    }
                    if(r<1000000000){
                        if(ck(l,r+1))continue;
                        if(!c)insert(l,r+1,1);
                        else {
                            res x1=query(l+1,r+1);
                            if(!x1)insert(l,r+1,1);
                            else insert(l,r+1,0);
                        }
                    }
                }
                for(res k=i;k<j;k++){
                    res l=a[k].l,r=a[k].r;
                    if(l>2){
                        if(ck(l-2,r))continue;
                        res c0=query(l-1,r);
                        if(!c0)insert(l-2,r,1);
                        else {
                            res x1=query(l-2,r-1);
                            if(!x1)insert(l-2,r,1);
                            else insert(l-2,r,0);
                        }
                    }
                    if(r<1000000000){
                        if(ck(l,r+2))continue;
                        res c0=query(l,r+1);
                        if(!c0)insert(l,r+2,1);
                        else {
                            res x1=query(l+1,r+2);
                            if(!x1)insert(l,r+2,1);
                            else insert(l,r+2,0);
                        }
                    }
                    if(l>1&&r<1000000000){
                        if(ck(l-1,r+1))continue;
                        res c0=query(l-1,r);
                        if(!c0)insert(l-1,r+1,1);
                        else {
                            res x1=query(l,r+1);
                            if(!x1)insert(l-1,r+1,1);
                            else insert(l-1,r+1,0);
                        }
                    }
                }
                i=j;
            }
            ox=0;
            while(q--){
                res l=read(),r=read();
                o[++ox]=query(l,r);
            }
            for(res i=1;i<=ox;i++)printf("%d",o[i]);
            puts("");
        }
    }
}