做题记录

感觉一直把一些做的其他题放在复健里也不太对，所以新开了一篇。

[CF1368 F]

solution

题面：这是一道交互题。

Alice 和 Bob 正在玩游戏，有 盏灯排成一圈，顺时针标号为 。起初所有的灯都处于关闭状态。

游戏由 Alice 先手，她每次可以选定任意一个正整数 并指定任意 盏灯，并将其打开 ( 如果原来就是开着的那么仍然是开着的 )，然后 Bob 可以选定任意连续 盏灯，并将其关闭 ( 如果原来就是关闭的那么仍然是关闭的 )，他需要保证他选择的 值和 Alice 的相同。

每一轮 Alice 操作后 Bob 再操作，被称为一个回合。Alice 想要在若干回合后让开着的灯的数量尽可能多，而 Bob 希望这个数尽可能少。

你需要写一个程序模拟 Alice，以帮助她完成最优策略，Bob 则由交互库来模拟。

设在最优策略下，若干个回合后开着的灯的数量的最大可能值为 ，你需要在不超过 回合内将开着的灯的数量达到这个值。

做法：发现 Alice 为了尽可能多，肯定要打开一些不连续的灯。打开到一定程度，使得灯被迫有 个相连时，接下来的操作就都是无效的了。

假设间隔是 ，可以算得答案最多是 ，这可以通过鸽巢原理证明。而取到这个的方法就像我前面所说的，以 个为一组了。

对答案式子进行上取整和根号的分类讨论，可得 时取到最大值 。

时间复杂度 。

//2021.10.19 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e3+10;
namespace MAIN{
    int a[N],swt[N];
    inline void MAIN(){
        res n=read();
        res k=int(sqrt(n));
        for(res i=k;i<=n;i+=k)a[i]=1;
        for(res T=1;T<=10000;T++){
            res ax=0;
            for(res i=1;i<=n;i++)ax+=((swt[i]==0)&&(a[i]==0));
            if(ax<k){puts("0");fflush(stdout);return;}
            ax=0,printf("%d ",k);
            for(res i=1;i<=n&&ax<k;i++)if(!a[i]&&!swt[i])swt[i]=1,printf("%d ",i),ax++;
            puts(""),fflush(stdout),ax=read();
            for(res i=1;i<=k;i++)swt[ax]=0,ax=ax%n+1;
        }
        puts("0");fflush(stdout);
    }
}

[CEOI 2016] kangaroo

solution

题面：固定第一个数和最后一个数的长度为 的排列，满足每个数要么是波谷，要么是波峰，问排列个数。

做法：考虑从每一个合法排列往前构造。假设现在有一个合法排列了，我们删去它的最大值，发现整个排列被分成两段，且端点要么是起点或终点，要么是波谷。不断进行这个操作，发现删去的顺序一定是唯一的，同时每一段的端点要么是起点或终点，要么是波谷，要么就是自己一个数。我们拿这个做 ，考虑从最小的数开始塞入排列，设 表示已经塞到了 ，同时有 个连续段的方案数。注意到这里的连续段是类似上述删除时那样构造的，即我们不管连续段之间的空格数。转移就是考虑删除的过程中，我们将 删除时怎么才会变到 这个状态。要么 是单独的一个连续段，即从 转移而来，那么要求 塞在了任意两段连续段之间，即 。要么它是两个连续段之间夹的波谷，即 。 是起点和终点特殊讨论，最终一定被塞成一段，即 。而这个 的正确性已经在删除的过程中被证明了。

时间复杂度 。

听说这被称作水淹笛卡尔树？不太懂。

//2021.10.28 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e3+10;
namespace MAIN{
    int n,s,t;
    int f[N][N];
    inline void MAIN(){
        f[0][0]=1,n=read(),s=read(),t=read();
        for(res i=1;i<=n;i++){
            for(res j=0;j<i;j++){
                if(i==s||i==t)add(f[i][j],f[i-1][j]),add(f[i][j+1],f[i-1][j]);
                else {
                    res c=(i>s)+(i>t);
                    add(f[i][j+1],mul(f[i-1][j],j+1-c));
                    if(j)add(f[i][j-1],mul(f[i-1][j],j-1));
                }
            }
        }
        printf("%d\n",f[n][1]);
    }
}

[SNOI 2020] 区间和

solution

题面：有一个长度为 的整数数列 （可能含有负数）。现在对其进行 次操作，每次操作是以下二者之一：

• 0 l r x 表示对于 ，将 赋值为 ；
• 1 l r 求区间 的最大子段和。即：。

做法：显然的 ，不过没那么容易直接上手。

分析一下，按照那套逻辑，我们还要维护前缀最大值中有几个最小值，后缀的，全局最大的，发现这也不够维护所有信息，于是还得维护个能改变区间结构的最小取 值，这样就差不多了。然后手推一下这一些信息倒还是容易的，于是就给我写麻了，好难写捏。

时间复杂度你冷静分析一下，大概是要 ？

//2021.11.9 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 TR{
        LL lm,rm,mx,sum;
        int lc,rc,mc,c,mn,laz,tg;
        inline void init(const res &x){
            sum=mn=x,c=1;
            if(x<=0)lm=rm=mx=lc=rc=mc=tg=0;
            else lm=rm=mx=x,lc=rc=mc=1,tg=inf;
        }
        inline void change(res val){
            laz=val,swap(mn,val),val=mn-val;
            sum+=(LL)val*c,lm+=(LL)val*lc,rm+=(LL)val*rc,mx+=(LL)val*mc;
        }
    }tr[N<<2];
    inline void pushup(const res &rt){
        tr[rt].sum=tr[rt<<1].sum+tr[rt<<1|1].sum;
        tr[rt].mn=min(tr[rt<<1].mn,tr[rt<<1|1].mn);
        res fl=(tr[rt<<1].mn==tr[rt].mn),fr=(tr[rt<<1|1].mn==tr[rt].mn);
        tr[rt].c=fl*tr[rt<<1].c+fr*tr[rt<<1|1].c;
        tr[rt].tg=min({tr[rt<<1].tg,tr[rt<<1|1].tg,fl?tr[rt<<1].tg:tr[rt<<1].mn-1,fr?tr[rt<<1|1].tg:tr[rt<<1|1].mn-1});
        res c1=fl*tr[rt<<1].lc,c2=fl*tr[rt<<1].c+fr*tr[rt<<1|1].lc;
        RG LL s1=tr[rt<<1].lm,s2=tr[rt<<1].sum+tr[rt<<1|1].lm;
        if(s2>s1)tr[rt].lm=s2,tr[rt].lc=c2;
        else {
            tr[rt].lm=s1,tr[rt].lc=c1;
            if(c2>c1)tr[rt].tg=(int)min((LL)tr[rt].tg,tr[rt].mn+(s1-s2)/(c2-c1));
        }
        c1=fr*tr[rt<<1|1].rc,c2=fr*tr[rt<<1|1].c+fl*tr[rt<<1].rc;
        s1=tr[rt<<1|1].rm,s2=tr[rt<<1|1].sum+tr[rt<<1].rm;
        if(s2>s1)tr[rt].rm=s2,tr[rt].rc=c2;
        else {
            tr[rt].rm=s1,tr[rt].rc=c1;
            if(c2>c1)tr[rt].tg=(int)min((LL)tr[rt].tg,tr[rt].mn+(s1-s2)/(c2-c1));
        }
        if(tr[rt<<1].rm+tr[rt<<1|1].lm>max(tr[rt<<1].mx,tr[rt<<1|1].mx))tr[rt].mx=tr[rt<<1].rm+tr[rt<<1|1].lm,tr[rt].mc=fl*tr[rt<<1].rc+fr*tr[rt<<1|1].lc;
        else if(tr[rt<<1].mx>tr[rt<<1|1].mx)tr[rt].mx=tr[rt<<1].mx,tr[rt].mc=fl*tr[rt<<1].mc;
        else tr[rt].mx=tr[rt<<1|1].mx,tr[rt].mc=fr*tr[rt<<1|1].mc;
    }
    void build(res rt,res l,res r){
        tr[rt].laz=inf;
        if(l==r){tr[rt].init(read());return;}
        res mid=(l+r)>>1;
        build(rt<<1,l,mid),build(rt<<1|1,mid+1,r),pushup(rt);
    }
    inline void pushdown(const res &rt){
        if(tr[rt].laz!=inf){
            if(tr[rt].laz>tr[rt<<1].mn)tr[rt<<1].change(tr[rt].laz);
            if(tr[rt].laz>tr[rt<<1|1].mn)tr[rt<<1|1].change(tr[rt].laz);
            tr[rt].laz=inf;
        }
    }
    void modify(res rt,res l,res r,const res &L,const res &R,const res &val){
        if(val<=tr[rt].mn)return;
        if(L<=l&&r<=R&&val<=tr[rt].tg){tr[rt].change(val);return;}
        if(l==r){tr[rt].init(val);return;}
        res mid=(l+r)>>1;
        pushdown(rt);
        if(L<=mid)modify(rt<<1,l,mid,L,R,val);
        if(R>mid)modify(rt<<1|1,mid+1,r,L,R,val);
        pushup(rt);
    }
    LL qmx,qrm;
    void query(res rt,res l,res r,const res &L,const res &R){
        if(L<=l&&r<=R){
            qmx=max({qmx,tr[rt].mx,qrm+tr[rt].lm}),qrm=max(qrm+tr[rt].sum,tr[rt].rm);
            return;
        }
        res mid=(l+r)>>1;
        pushdown(rt);
        if(L<=mid)query(rt<<1,l,mid,L,R);
        if(R>mid)query(rt<<1|1,mid+1,r,L,R);
    }
    inline void MAIN(){
        n=read(),q=read(),build(1,1,n);
        while(q--){
            res opt=read(),l=read(),r=read();
            if(opt==0)modify(1,1,n,l,r,read());
            else qmx=qrm=0,query(1,1,n,l,r),printf("%lld\n",qmx);
        }
    }
}

[JOI Open 2016] 摩天大楼

solution

题面：将互不相同的 个整数 按照一定顺序排列。 假设排列为 ，要求：。 求满足题意的排列的方案数 。

做法：直接考虑从小到大插入似乎不太行，因为和不是单调的，所以 这一维那开到 ，过不了。

但如果考虑将 看成 ，那考虑算 的贡献就有搞头了。这个东西的系数显然是满足一个大于等于 ，一个小于等于 的相邻数对个数。那仍旧考虑从小到大插入， 分别表示当前插到了第 个数，形成了 个连续段，贡献和为 ，头尾用了 个的方案数。这里的贡献和我们考虑上面那个贡献，意思就是考虑 的贡献。这个利用连续段是可以直接算的，因为接下来插入的都会比 大，而之前的都小于等于 ，于是只要插在一个段的两边就可以了。转移都是类似的，时间复杂度 。

坑： 时头就是尾，需要特判。

//2021.11.12 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=100+10;
namespace MAIN{
    int n,l;
    int a[N];
    int f[N][N][1000+1][3];
    inline void MAIN(){
        n=read(),l=read();
        if(n==1){puts("1");return;}
        for(res i=1;i<=n;i++)a[i]=read();
        sort(a+1,a+n+1),f[0][0][0][0]=1;
        for(res i=0;i<n;i++){
            for(res j=0;j<=i;j++)
                for(res k=0;k<=l;k++)
                    for(res p=0;p<=2;p++){
                        if(!f[i][j][k][p])continue;
                        res val=k+(2*j-p)*(a[i+1]-a[i]);
                        if(val>l)continue;
                        add(f[i+1][j+1][val][p],mul(j+1-p,f[i][j][k][p]));
                        add(f[i+1][j][val][p],mul(2*j-p,f[i][j][k][p]));
                        if(p<2)add(f[i+1][j+1][val][p+1],mul(2-p,f[i][j][k][p]));
                        if(j)add(f[i+1][j-1][val][p],mul(j-1,f[i][j][k][p]));
                        if(p<2&&j)add(f[i+1][j][val][p+1],mul(2-p,f[i][j][k][p]));
                    }
        }
        res ans=0;
        for(res i=0;i<=l;i++)add(ans,f[n][1][i][2]);
        printf("%d\n",ans);
    }
}

[TC12336]

solution

题面：给你一张图，要求删去若干条边，让残余图无论以什么形态都不能有边相交。求可以得到的残余图数量。

做法：观察一下就只有三角形或者菊花是可以的。于是枚举哪个点作为菊花的中心点以及有几个三角线即可。注意只剩一条边的情况会被端点算重，减掉即可。时间复杂度 或者暴力点来个 之类的。

[CF674 F]

solution

题面：酒店中有 只熊和 张床，这些熊正在开晚会。

熊喜欢喝果汁，它们不喜欢喝葡萄酒。但是它们无法仅通过颜色和气味辨别果汁和葡萄酒。

一只熊可以一直在晚会上活动而不睡觉，除非它喝了葡萄酒。当一只熊喝完葡萄酒后，它立即会去睡觉，且在晚会期间不再醒来。

现在有若干个酒桶，每个酒桶中装填了果汁或葡萄酒，其中恰有一个桶中装了葡萄酒。酒桶的主人为了测试熊的智力，给它们一个如下挑战：

晚会会进行许多天。每天，会依次发生如下三件事情：

1. 每只熊需要选择一个桶的子集 (可以为空集)，多个熊可以同时选择一个桶。

2. 每只熊需要把它选择的桶中的所有饮料都喝一小杯 (假设桶足够大，够所有的熊喝)。

3. 对于所有喝到过酒的熊 (喝完饮料后它们自己能发现是否喝到过酒)，马上会上床睡觉，并在整个晚会期间不再醒来 (i.e. 即它们不能参与剩下几天的活动了)。

   每张床恰能容纳一只熊，如果有熊无床睡觉，则挑战失败。

如果晚会结束后，这些熊中至少有一只没睡觉，且没有无床睡觉，并且它们能推理出哪个桶中装了葡萄酒 (假设熊足够聪明)，则挑战成功。

容易证明，对于一个确定的 ，如果晚会开了 天，则存在非负整数 ，满足：这些熊可以在 个酒桶中确保挑战成功，但在 个酒桶中无法保证挑战成功。

给定正整数 ，你需要求出 ，其中 表示按位异或运算。

做法：通过手玩样例 ，容易意识到我们总想每一桶饮料喝的熊的集合不相同。

于是枚举每一桶饮料喝的熊的数量 ，那么共有 种熊去喝的情况。同时一桶饮料若没有熊去喝，那么也可以判断。

再加上熊不能全喝醉，所以答案就是

$$\sum_{i=0}^{\min(n-1,p)} \binom{n}{i}q^i$$

注意到 很小，所以暴力预处理组合数即可。组合数考虑将分子分母的 都先拿出来，最后再放回去。那分母就是奇数，利用欧拉定理就可以直接求逆元了。时间复杂度 。

//2021.11.18 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    uint inv[140];
    inline uint Qpow(uint x,uint y){
        uint ret=1;
        while(y){
            if(y&1)ret*=x;
            x*=x,y>>=1;
        }
        return ret;
    }
    uint C[140];
    int even[140];
    inline void MAIN(){
        for(res i=1;i<=130;i++)inv[i]=Qpow(i,(((uint)1)<<31)-1);
        res n=read(),p=read(),q=read();
        C[0]=1;
        for(res i=1;i<=min(p,n-1);i++){
            uint x=i,z=n-i+1;
            even[i]=even[i-1]+ctz(n-i+1)-ctz(i);
            x>>=ctz(i),z>>=ctz(n-i+1);
            C[i]=C[i-1]*z*inv[x];
        }
        for(res i=1;i<=min(p,n-1);i++)C[i]<<=even[i];
        uint ans=0;
        for(res i=1;i<=q;i++){
            uint X=0,r=1;
            for(res j=0;j<=min(p,n-1);j++)X+=C[j]*r,r*=i;
            ans^=X*i;
        }
        printf("%u\n",ans);
    }
}

[CF674 G]

solution

题面：给定一个长度为 的序列和一个整数 。有 个操作，操作要么是区间赋值，要么是询问区间内出现次数至少占 的数。输出询问的答案时，可以包含错的数，也可以重复输出，但对的数一定要在答案中，且输出的数的个数不超过 。

做法：考虑摩根（ 忘记名字了 ）投票法，就那个加一个就删一个的。注意到 ，所以最多维护五个数。所以线段树每个节点维护个五元组就好了，时间复杂度 。

//2021.11.19 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=150000+10;
namespace MAIN{
    int n,m,p;
    struct P{
        int num,tag,a[5],b[5];
    }tr[N<<2];
    int len[N<<2];
    inline P merge(const RG P &A,const RG P &B){
        RG P ret=A;
        ret.tag=0;
        for(res i=0;i<B.num;i++){
            RG bool fl=0;
            for(res j=0;j<ret.num&&!fl;j++)if(B.a[i]==ret.a[j])ret.b[j]+=B.b[i],fl=1;
            if(fl)continue;
            if(ret.num<p){ret.a[ret.num]=B.a[i],ret.b[ret.num]=B.b[i],ret.num++;continue;}
            res mnid=0;
            for(res j=1;j<ret.num;j++)if(ret.b[j]<ret.b[mnid])mnid=j;
            if(B.b[i]<ret.b[mnid]){
                for(res j=0;j<ret.num;j++)ret.b[j]-=B.b[i];
            }
            else {
                res tmp=ret.b[mnid];
                ret.a[mnid]=B.a[i],ret.b[mnid]=B.b[i];
                for(res j=0;j<ret.num;j++)ret.b[j]-=tmp;
            }
        }
        return ret;
    }
    void build(res rt,res l,res r){
        len[rt]=r-l+1;
        if(l==r){
            res x=read();
            tr[rt].num=tr[rt].b[0]=1,tr[rt].a[0]=x;
            return;
        }
        res mid=(l+r)>>1;
        build(rt<<1,l,mid),build(rt<<1|1,mid+1,r),tr[rt]=merge(tr[rt<<1],tr[rt<<1|1]);
    }
    inline void change(const res &rt,const res &val){
        tr[rt].num=1,tr[rt].b[0]=len[rt],tr[rt].a[0]=val,tr[rt].tag=val;
    }
    inline void pushdown(const res &rt){
        if(!tr[rt].tag)return;
        change(rt<<1,tr[rt].tag),change(rt<<1|1,tr[rt].tag),tr[rt].tag=0;
    }
    void modify(res rt,res l,res r,const res &L,const res &R,const res &val){
        if(L<=l&&r<=R){change(rt,val);return;}
        pushdown(rt);
        res mid=(l+r)>>1;
        if(L<=mid)modify(rt<<1,l,mid,L,R,val);
        if(R>mid)modify(rt<<1|1,mid+1,r,L,R,val);
        tr[rt]=merge(tr[rt<<1],tr[rt<<1|1]);
    }
    P query(res rt,res l,res r,const res &L,const res &R){
        if(L<=l&&r<=R)return tr[rt];
        pushdown(rt);
        res mid=(l+r)>>1;
        if(L<=mid&&R>mid)return merge(query(rt<<1,l,mid,L,R),query(rt<<1|1,mid+1,r,L,R));
        if(L<=mid)return query(rt<<1,l,mid,L,R);
        return query(rt<<1|1,mid+1,r,L,R);
    }
    inline void MAIN(){
        n=read(),m=read(),p=100/read(),build(1,1,n);
        while(m--){
            res opt=read(),l=read(),r=read();
            if(opt==1)modify(1,1,n,l,r,read());
            else {
                RG P ret=query(1,1,n,l,r);
                printf("%d ",ret.num);
                for(res i=0;i<ret.num;i++)printf("%d ",ret.a[i]);
                puts("");
            }
        }
    }
}

[Code Festival Final 17 C]

solution

题面：来自世界各地的 名选手参加了比赛，A 调查并计算出第 名选手所在城市与他自己所在城市的时差 。时差如下定义：对于城市 A 和城市 B，当 A 为 点时，B 为 点，此时时差为 （24小时制）。例如，当 A 所在城市为 点时，第 名选手所在城市的时间要么是 ，要么是 。
记 为 A 所在城市为 点时，每两个城市间的时差的最小值。求出尽可能大的 。

做法：首先注意到鸽巢原理， 直接就是 ，因为必有两个城市重复了。剩下来的直接暴搜。时间复杂度 。

//2021.11.21 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    int n;
    int h[30];
    int ans;
    int fl[30];
    void dfs(res dep){
        if(dep==n+1){
            res mn=30,las=0;
            for(res i=1;i<24;i++)if(fl[i])mn=min(mn,i-las),las=i;
            mn=min(mn,24-las),ans=max(ans,mn);
            return;
        }
        if(!fl[h[dep]])fl[h[dep]]=1,dfs(dep+1),fl[h[dep]]=0;
        if(!fl[(24-h[dep])%24])fl[(24-h[dep])%24]=1,dfs(dep+1),fl[(24-h[dep])%24]=0;
    }
    inline void MAIN(){
        n=read()+1;
        if(n>24){puts("0");return;}
        for(res i=1;i<n;i++)h[i]=read();
        dfs(1),printf("%d\n",ans);
    }
}

[TC12118]

solution

题面：有两个由 构成的字符串，将某个位置的 变成 的代价为 ， 变成 为 ， 变成 为 ，最大代价为 ，问将第一个串变成第二个的方案数。

做法：注意到记录代价无意义，因为一个合法方案一定是有将第一个串变成第二个串，然后在每个位置循环变化，所以实际上记录代价可以被记录变化次数所代替。

令 表示当前已经动了 步，还有 个位置差一步， 个位置差两步的方案数。转移就是 。观察一下就知道这个可以矩乘优化了，时间复杂度 ，其中 为字符串长， 为步数。

[Code Festival Final 17 F]

solution

题面：有 张纸，每张纸上要写 个数，要求这 个数都在 内，且 中的每个数恰好出现 次。还要求每张纸不能写相同的数，且任意两张纸的数字交集大小为 ，让你构造 和 以及染色方案。

做法：首先根据每两个相同数字都要在不同的纸张，以及不同纸张之间都要有相同的数字，可以得到 ，即 。然后我们手动玩一下 的情况，会得到一个这样的构造：

第一张到第 张都是 ，然后接下来是以 打头，剩下来的取一排。然后是以 打头，然后隔一格取。类似这样，可以证明 是质数时大概是有解的，然后就构造完了。

//2022.2.26 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    int k=42,n=k*k-k+1;
    int a[100][100];
    inline void MAIN(){
        printf("%d %d\n",n,k);
        for(res i=1;i<=k;i++){
            printf("1 ");
            for(res j=(i-1)*(k-1)+2;j<=i*(k-1)+1;j++)printf("%d ",j),a[i][j-(i-1)*(k-1)-2]=j;
            puts("");
        }
        for(res i=0;i<k-1;i++)for(res j=0;j<k-1;j++){
            printf("%d ",i+2);
            for(res l=2,cur=j;l<=k;l++,cur=(cur+i)%(k-1))printf("%d ",a[l][cur]);
            puts("");
        }
    }
}

[TC12161]

solution

题面：有 个数 ，一个排列的价值为 ，求价值最小且字典序最小的排列。

做法：肯定想要越大的越少出现，那么除了最小的，其他都是出现一次，即一个 V 字形。剩下来的直接贪心就可以了。时间复杂度 。

[LG6327]

solution

题面：中文不会自己看？

做法：考虑那个啥公式，就 ，那么线段树上每个结点只用维护 和 了。时间复杂度 。

//2021.11.25 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
#define ld long db
const int N=2e5+10;
namespace MAIN{
    int n;
    ld si[N<<2],cs[N<<2];
    LL tag[N<<2];
    void build(res rt,res l,res r){
        if(l==r){
            res x=read();
            si[rt]=sin(x),cs[rt]=cos(x);
            return;
        }
        res mid=(l+r)>>1;
        build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);
        si[rt]=si[rt<<1]+si[rt<<1|1];
        cs[rt]=cs[rt<<1]+cs[rt<<1|1];
    }
    inline void change(const res &rt,const RG LL &val){
        RG ld vs=si[rt],vc=cs[rt];
        si[rt]=vs*cos(val)+vc*sin(val);
        cs[rt]=vc*cos(val)-vs*sin(val);
        tag[rt]+=val;
    }
    inline void pushdown(const res &rt){
        if(!tag[rt])return;
        change(rt<<1,tag[rt]),change(rt<<1|1,tag[rt]),tag[rt]=0;
    }
    void modify(res rt,res l,res r,const res &L,const res &R,const res &val){
        if(L<=l&&r<=R){
            change(rt,val);
            return;
        }
        pushdown(rt);
        res mid=(l+r)>>1;
        if(L<=mid)modify(rt<<1,l,mid,L,R,val);
        if(R>mid)modify(rt<<1|1,mid+1,r,L,R,val);
        si[rt=si[rt<<1]+si[rt<<1|1];
        cs[rt]=cs[rt<<1]+cs[rt<<1|1];
    }
    ld query(res rt,res l,res r,const res &L,const res &R){
        if(L<=l&&r<=R)return si[rt];
        pushdown(rt);
        res mid=(l+r)>>1;
        RG ld ret=0;
        if(L<=mid)ret=query(rt<<1,l,mid,L,R);
        if(R>mid)ret+=query(rt<<1|1,mid+1,r,L,R);
        return ret;
    }
    inline void MAIN(){
        n=read(),build(1,1,n);
        res q=read();
        while(q--){
            res opt=read(),l=read(),r=read();
            if(opt==1){
                res v=read();
                modify(1,1,n,l,r,v);
            }
            else printf("%.1Lf\n",query(1,1,n,l,r));
        }
    }
}

[CF453 E]

solution

题面：你有 只小马（ 编号从 到 ）。每只小马有三种属性。

：时间为 时这只小马拥有的法力值。

：这只小马可以拥有的最大法力值。

：这只小马单位时间内回复的法力值。

提雷克会给出 条指令，每一条都可以被描述为 个整数：。表示在时间为 时，提雷克会从区间 的小马中吸取魔力，指令保证 升序，计算每一条指令之后提雷克可以吸取多少点魔力。

做法：考虑 那一套逻辑，把上次修改时间一致的连续点连成一个区间，发现这样的区间个数是 的。于是可以暴力处理这些区间，注意到一共就两类情况，即 与否，可以容易注意到这东西是二维数点，离线下来可以一维数点，不过直接可持久化线段树挺好写的捏。时间复杂度 。当然可以注意到这是分段函数，所以可以上闵科夫斯基凸包和。

坑：这题实现上一车细节。比如就 的这些点你要怎么安排的小细节，因为此时直接用乘法会遇到 的情况导致无序而 RE。（ 我不会说我写了一个半小时的 ）

//2021.11.30 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;
#define tup tuple<int,int,int>
    set<tup> S;
    int s[N],m[N],u[N];
    set<int> T;
    int ls[N*30],rs[N*30],tot;
    pair<LL,LL> su[N*30];
    inline pair<LL,LL> operator + (pair<LL,LL> a,pair<LL,LL> b){
        return mp(a.fi+b.fi,a.se+b.se);
    }
    void build(res &rt,res l,res r){
        rt=++tot;
        if(l==r){su[rt]=mp(u[l],0ll);return;}
        res mid=(l+r)>>1;
        build(ls[rt],l,mid),build(rs[rt],mid+1,r),su[rt]=su[ls[rt]]+su[rs[rt]];
    }
    void insert(res &rt,res RT,res l,res r,const res &p){
        rt=++tot;
        ls[rt]=ls[RT],rs[rt]=rs[RT],su[rt]=su[RT];
        if(l==r){if(u[l])su[rt]=mp(0ll,m[l]);return;}
        res mid=(l+r)>>1;
        if(p<=mid)insert(ls[rt],ls[RT],l,mid,p);
        else insert(rs[rt],rs[RT],mid+1,r,p);
        su[rt]=su[ls[rt]]+su[rs[rt]];
    }
    pair<LL,LL> query(res rt,res l,res r,const res &L,const res &R){
        if(!rt)return su[rt];
        if(L<=l&&r<=R)return su[rt];
        res mid=(l+r)>>1;
        RG pair<LL,LL> ret=mp(0ll,0ll);
        if(L<=mid)ret=query(ls[rt],l,mid,L,R);
        if(R>mid)ret=ret+query(rs[rt],mid+1,r,L,R);
        return ret;
    }
    int rt[N];
    int id[N];
    inline bool cmp(const res &A,const res &B){
        if(!u[A])return 0;
        if(!u[B])return 1;
        return (LL)m[A]*u[B]-(LL)m[B]*u[A]<0;
    }
    inline pair<LL,LL> calc(const res &L,const res &R,const res &t){
        res l=0,r=n,ret=0;
        while(l<=r){
            res mid=(l+r)>>1;
            if(m[id[mid]]<=(LL)t*u[id[mid]])l=mid+1,ret=mid;
            else r=mid-1;
        }
        return query(rt[ret],1,n,L,R);
    }
    set<tup>::iterator L,R;
    inline void MAIN(){
        n=read();
        for(res i=1;i<=n;i++)s[i]=read(),m[i]=read(),u[i]=read(),T.insert(i),id[i]=i;
        S.insert(tup(0,0,0));
        build(rt[0],1,n),sort(id+1,id+n+1,cmp);
        for(res i=1;i<=n;i++)insert(rt[i],rt[i-1],1,n,id[i]);
        res q=read();
        while(q--){
            res t=read(),l=read(),r=read();
            LL ans=0;
            auto IT=T.lower_bound(l);
            while(IT!=T.end()&&(*IT)<=r){
                res i=(*IT);
                ans+=min((LL)m[i],(LL)u[i]*t+s[i]),T.erase(IT),IT=T.lower_bound(l);
            }
            if(S.empty())L=R=S.end();
            else {
                if(r==n)R=S.end();
                else {
                    auto it=(--S.upper_bound(tup(r+1,0,0)));
                    tup tmp=(*it);
                    if(r>=get<1>(tmp))R=(++it);
                    else S.erase(it),S.insert(tup(get<0>(tmp),r,get<2>(tmp))),R=S.insert(tup(r+1,get<1>(tmp),get<2>(tmp))).fi;
                }
                auto it=(--S.upper_bound(tup(l+1,0,0)));
                tup tmp=(*it);
                if(l>get<1>(tmp))L=(++it);
                else if(l>get<0>(tmp))S.erase(it),S.insert(tup(get<0>(tmp),l-1,get<2>(tmp))),L=S.insert(tup(l,get<1>(tmp),get<2>(tmp))).fi;
                else {
                    if(l==get<0>(tmp))L=it;
                }
            }
            auto nL=L;
            for(;L!=R;L++){
                pair<LL,LL> ret=calc(get<0>(*L),get<1>(*L),t-get<2>(*L));
                ans+=ret.fi*(t-get<2>(*L))+ret.se;
            }
            S.erase(nL,R),S.insert(tup(l,r,t)),printf("%lld\n",ans);
        }
    }
}

[Wannafly 6 E]

solution

题面：中文题面不会自己看？

做法：所以说构造题千万不能看样例和数据范围啊。

时，显然不能找到两组使得右边的数大于左边，所以都无解。而其它的 ， 可以找到 ， 可以找到 ，然后你发现这样往后每次添加两个 ，只要第二位和第三位处划分就可以了。时间复杂度 。

//2021.12.1 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    inline void MAIN(){
        res n=read();
        if(n<=3)puts("-1");
        else {
            if(n&1){
                printf("16400");
                for(res i=n-5;i;i--)printf("0");
                puts("");
            }
            else {
                printf("1144");
                for(res i=n-4;i;i--)printf("0");
                puts("");
            }
        }
    }
}

[Ynoi2007] rgxsxrs

solution

题面：中文题面不会自己看？

做法：整体或树上操作都类同于 年暑假 多校第三场的那道 ，即考虑到以 分段考虑，中间那一段暴力，后面那一段直接打标记。然后分块，之后再写好了。

[CF739 A]

solution

题面：长度为 的序列，有 个区间限制，要求构造这个序列，使得这 个区间的最小 最大。

做法：注意到最大值不能超过最短区间的长度，考虑构造这个下界。发现循环 构造就行了，其中 为最短区间长度。时间复杂度 。

//2021.12.6 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    inline void MAIN(){
        res n=read(),m=read(),L=n;
        for(res i=1;i<=m;i++){
            res l=read(),r=read();
            L=min(L,r-l+1);
        }
        res now=0;
        printf("%d\n",L);
        for(res i=1;i<=n;i++)printf("%d ",now),now=(now==L-1?0:now+1);
    }
}

[CF733 C]

solution

题面：有 个怪兽，第 个的重量是 。

一秒钟内，能让恰好一个怪兽吃掉相邻的比它重量小的怪兽。重量大的重量加上重量小的的重量；重量小的怪兽死掉。死后重新靠拢。

求一种顺序，变成：共 个怪兽，第 个的重量是 。

做法：注意每次合并的一定是一个区间，那么就可以逐个确定是否能构造出 。另一方面一个区间能能否构造，当且仅当和等于 且不全部相等。因为如果全部相等则没得吃，若有一个不等，那么一定存在一个最大的数能吃相邻的一个。于是只要每次拿最大的那个来吃就好了。时间复杂度 。

//2021.12.7 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=500+10;
namespace MAIN{
    int n;
    int a[N];
    int k,b[N];
    vector<pair<int,char> > ans;
    inline void MAIN(){
        n=read();
        for(res i=1;i<=n;i++)a[i]=read();
        k=read();
        for(res i=1;i<=k;i++)b[i]=read();
        res now=1,cur=1,ret=0,st=0,sum=0;
        while(now<=n+1){
            if(now>n&&ret!=b[cur]){puts("NO");return;}
            if(!ret){st=now,ret=a[now++];continue;}
            if(ret<b[cur]){ret+=a[now++];continue;}
            if(ret>b[cur]){puts("NO");return;}
            res fl=0,mx=0;
            if(st+1==now){ret=0,cur++;continue;}
            for(res i=st+1;i<now;i++)if(a[i]!=a[st]){fl=1;break;}
            if(!fl){puts("NO");return;}
            for(res i=st;i<now;i++)if(a[mx]<a[i])mx=i;
            if(mx==st&&a[mx]==a[mx+1]){
                for(res i=st;i<now-1;i++)if(a[mx]==a[i]&&a[i]>a[i+1]){mx=i;break;}
                for(res i=mx+1;i<now;i++)ans.pb(mp(mx-sum,'R'));
                for(res i=st;i<mx;i++)ans.pb(mp(mx-sum-(i-st),'L'));
                sum+=now-st-1;
            }
            else {
                for(res i=st;i<mx;i++)ans.pb(mp(mx-sum-(i-st),'L'));
                sum+=mx-st;
                for(res i=mx+1;i<now;i++)ans.pb(mp(mx-sum,'R'));
                sum+=now-1-mx;
            }
            ret=0,cur++;
            if(now>n&&cur<=k){puts("NO");return;}
            if(now>n&&cur>k)break;
        }
        puts("YES");
        for(auto x:ans)printf("%d %c\n",x.fi,x.se);
    }
}

[CF429 E]

solution

题面：给定 条线段 ，然后给这些线段红蓝染色，要求最后直线上任意一个点被蓝色及红色线段覆盖次数之差的绝对值之差小于等于 。

做法：绝对值之差小于等于 实际都是可以用欧拉回路解决的。差分后考虑区间端点处连边，然后把相邻的点度为奇数的点连边，这样保证了每个点的度数为偶数。接下来跑个欧拉回路，给无向图边定向，这样顺时针为红，逆时针为蓝，即可保证每个点的红蓝染色次数相等。时间复杂度 。

坑：因为相邻点连边了，所以空间要乘 。

//2021.12.7 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=4e5+10;
namespace MAIN{
    int n,m;
#define tup tuple<int,int,int>
    tup a[N];
    struct E{
        int next,to;
        E() {}
        E(res next,res to):next(next),to(to) {}
    }edge[N];
    int head[N],cnt=-1;
    inline void addedge(const res &u,const res &v){
        edge[++cnt]=E(head[u],v),head[u]=cnt;
        edge[++cnt]=E(head[v],u),head[v]=cnt;
    }
    int pos[N];
    int vis[N],ans[N];
    void dfs(res x){
        vis[x]=1;
        for(res &i=head[x];~i;i=edge[i].next)if(!ans[i])ans[i]=1,ans[i^1]=2,dfs(edge[i].to);
    }
    inline void MAIN(){
        n=read(),memset(head,-1,sizeof(head));
        for(res i=1;i<=n;i++){
            res l=read(),r=read();
            a[i]=tup(l,1,i),a[i+n]=tup(r+1,-1,i);
        }
        sort(a+1,a+2*n+1);
        for(res i=1;i<=2*n;i++){
            if(get<0>(a[i])>get<0>(a[i-1])){
                m++;
                if(!(i&1))addedge(m-1,m);
            }
            if(get<1>(a[i])==1)pos[get<2>(a[i])]=m;
            else addedge(pos[get<2>(a[i])],m),pos[get<2>(a[i])]=cnt;
        }
        for(res i=1;i<=m;i++)if(!vis[i])dfs(i);
        for(res i=1;i<=n;i++)printf("%d ",ans[pos[i]]&1);
    }
}

[CF725 C]

solution

题面：给一个长度为 的大写字母串，其中除了一个字符出现两次，其他都出现一次。要求构造出 的字符网格，使得每个字符都出现一次，且原字符串中相邻的字母在网格中八连通。

做法：注意到若我们按原字符串直接塞入网格中（ 即第二行处的末尾和第一行的末尾相连 ），我们不断向前旋转这个网格，相邻的字符仍然是相邻的。那么只用考虑那个出现两次的字符。出现两次的字符我们保留一个即可，设另一个相邻的字符是 ，那么不断旋转，这个字符一定会和 相遇。这是小学二年级的相遇问题，而且因为删去这个字符后 就在网格中相邻了，所以是对的。除非当这个出现两次的字符相邻了，那么显然无解。

时间复杂度 ，当然可以更优。

//2021.12.8 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    char str[30];
    int vis[26];
    int id1,id2;
    char p[4],q[8],a[5][15],b[5][15];
    int fl[4];
    inline void MAIN(){
        str[0]='!',str[28]='!';
        scanf("%s",str+1);
        res n=int(strlen(str+1));
        for(res i=1;i<=n;i++){
            if(!vis[str[i]-'A'])vis[str[i]-'A']=i;
            else {
                id1=i,id2=vis[str[i]-'A'];break;
            }
        }
        for(res i=1;i<=n;i++){
            if(i==id1)p[0]=str[i-1],p[1]=str[i+1];
            if(i==id2)p[2]=str[i-1],p[3]=str[i+1];
        }
        if(abs(id1-id2)==1){puts("Impossible");return;}
        res now=1,ni,nj;
        for(res j=1;j<=13;j++){
            if(now==id2)now++;
            if(now==id1)ni=1,nj=j;
            a[1][j]=str[now],now++;
        }
        for(res j=13;j;j--){
            if(now==id2)now++;
            if(now==id1)ni=2,nj=j;
            a[2][j]=str[now],now++;
        }
        for(res T=1;T<=26;T++){
            q[0]=a[ni][nj-1],q[1]=a[ni][nj+1],q[2]=a[ni-1][nj],q[3]=a[ni+1][nj];
            q[4]=a[ni-1][nj-1],q[5]=a[ni-1][nj+1],q[6]=a[ni+1][nj-1],q[7]=a[ni+1][nj+1];
            fl[0]=fl[1]=fl[2]=fl[3]=0;
            for(res k=0;k<4;k++){
                for(res i=0;i<8;i++){
                    if(q[i]==p[k]||p[k]=='!')fl[k]=1;
                }
            }
            if(fl[0]==1&&fl[1]==1&&fl[2]==1&&fl[3]==1){
                for(res i=1;i<=2;i++){
                    for(res j=1;j<=13;j++)putchar(a[i][j]);
                    puts("");
                }
                return;
            }
            if(nj<13&&ni==1)nj++;
            else if(ni==1&&nj==13)ni=2;
            else if(ni==2&&nj==1)ni=1;
            else nj--;
            for(res j=1;j<13;j++)b[1][j+1]=a[1][j];
            b[2][13]=a[1][13];
            for(res j=2;j<=13;j++)b[2][j-1]=a[2][j];
            b[1][1]=a[2][1];
            for(res i=1;i<=2;i++)for(res j=1;j<=13;j++)a[i][j]=b[i][j];
        }
        now=1;
        for(res j=1;j<=13;j++){
            if(now==id1)now++;
            if(now==id2)ni=1,nj=j;
            a[1][j]=str[now],now++;
        }
        for(res j=13;j;j--){
            if(now==id1)now++;
            if(now==id2)ni=2,nj=j;
            a[2][j]=str[now],now++;
        }
        for(res T=1;T<=26;T++){
            q[0]=a[ni][nj-1],q[1]=a[ni][nj+1],q[2]=a[ni-1][nj],q[3]=a[ni+1][nj];
            q[4]=a[ni-1][nj-1],q[5]=a[ni-1][nj+1],q[6]=a[ni+1][nj-1],q[7]=a[ni+1][nj+1];
            fl[0]=fl[1]=fl[2]=fl[3]=0;
            for(res k=0;k<4;k++){
                for(res i=0;i<8;i++){
                    if(q[i]==p[k]||p[k]=='!')fl[k]=1;
                }
            }
            if(fl[0]==1&&fl[1]==1&&fl[2]==1&&fl[3]==1){
                for(res i=1;i<=2;i++){
                    for(res j=1;j<=13;j++)putchar(a[i][j]);
                    puts("");
                }
                return;
            }
            if(nj<13&&ni==1)nj++;
            else if(ni==1&&nj==13)ni=2;
            else if(ni==2&&nj==1)ni=1;
            else nj--;
            for(res j=1;j<13;j++)b[1][j+1]=a[1][j];
            b[2][13]=a[1][13];
            for(res j=2;j<=13;j++)b[2][j-1]=a[2][j];
            b[1][1]=a[2][1];
            for(res i=1;i<=2;i++)for(res j=1;j<=13;j++)a[i][j]=b[i][j];
        }
        puts("Impossible");
    }
}

[ARC093 D]

solution

题面：构造 的网格染黑白色，使得白连通块个数为 ，黑为 ，。

做法：注意到 不大，考虑将 的网格分成上下两个部分，分别染全黑全白，然后在其中一些小空处染另一种颜色。比如一行行隔一个染一个这样子。具体可以看代码。

//2021.12.10 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=100+10;
namespace MAIN{
    int a[N][N];
    inline void MAIN(){
        res A=read()-1,B=read()-1;
        res x=1,y=1;
        for(res i=1;i<=A;i++){
            a[x][y]=1,y+=2;
            if(y>100)x+=2,y=1;
        }
        for(res i=51;i<=100;i++)for(res j=1;j<=100;j++)a[i][j]=1;
        x=100,y=1;
        for(res i=1;i<=B;i++){
            a[x][y]=0,y+=2;
            if(y>100)x-=2,y=1;
        }
        puts("100 100");
        for(res i=1;i<=100;i++){
            for(res j=1;j<=100;j++){
                if(a[i][j])putchar('.');
                else putchar('#');
            }
            puts("");
        }
    }
}

[Code Festival Qual 17 A]

solution

题面：给定一个 的网格。一些人站在网格的边界上。一个人可以占据他面前的一行（列），过程是一直往前染色（每个人的颜色都不一样），直到下一个格子染上了颜色或者到达了边界。显然不同顺序会有不同的最终状态。求最终状态的方案数。

做法：

[POI 2011] IMP

solution

题面：给定一张 个点 条边的图 ，保证存在一个大小为 的团，要求输出一个大小为 的团。

做法：高中时就知道的题了，结果现在才第一次做啊。

注意若两个点之间没有连边则一定不会在一个团里。考虑每次删掉两个不在一个团里的点，那么最多删 次，因为存在一个大小为 的团。而剩下的 个点自然就是答案了。时间复杂度 。

//2021.12.14 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=3e3+10;
namespace MAIN{
    int n,m;
    int G[N][N];
    int vis[N];
    inline void MAIN(){
        n=read(),m=read();
        for(res i=1;i<=m;i++){
            res u=read(),v=read();
            G[u][v]=G[v][u]=1;
        }
        for(res i=1;i<=n;i++){
            if(vis[i])continue;
            for(res j=i+1;j<=n;j++){
                if(G[i][j]||vis[j])continue;
                vis[i]=vis[j]=1;break;
            }
        }
        for(res i=1,t=1;i<=n&&t<=n/3;i++)if(!vis[i])printf("%d ",i),t++;
        puts("");
    }
}

[CF765 F]

solution

题面： 个数， 次询问 ，问 区间内两数之差的最小值。

做法：一眼莫队，然后想把添加改成删除也去不掉 set 这一个 ，感受一下过不了，就不写了。

接下来先考虑一个大暴力，离线下来后，考虑每次添加一个 对所有右端点是 的询问的贡献。考虑在 中找到最靠右的大于 的数 ，那么 的答案就会更新个 。以此类推，暴力的话，我们只用一个升序数列就将其卡到 。再观察观察这个东西到底有什么性质，注意到有一部分贡献是一定无意义的。因为找到一个 时，一定要求 ，那么 。于是这样要不断递减下去，最多只会有 次，即合法的 只有 。那么用一棵线段树维护下值域，再用棵 维护答案更新就行了。总复杂度 。

//2021.12.21 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=3e5+10;
namespace MAIN{
    int n,m;
    int a[N];
    vector<Pair> que[N];
    int tr[N];
    inline void modify(const res &x,const res &y){
        for(res i=x;i;i-=lowbit(i))tr[i]=min(tr[i],y);
    }
    inline int query(const res &x){
        res ret=1000000000;
        for(res i=x;i<=n;i+=lowbit(i))ret=min(ret,tr[i]);
        return ret;
    }
    int mx[N*30],tot,ls[N*30],rs[N*30];
    void modify(res &rt,res l,res r,const res &p,const res &va){
        if(!rt)rt=++tot;
        mx[rt]=max(mx[rt],va);
        if(l==r)return;
        res mid=(l+r)>>1;
        if(p<=mid)modify(ls[rt],l,mid,p,va);
        else modify(rs[rt],mid+1,r,p,va);
    }
    int query(res rt,res l,res r,const res &L,const res &R){
        if(!rt)return 0;
        if(L<=l&&r<=R)return mx[rt];
        res mid=(l+r)>>1,ret=0;
        if(L<=mid)ret=query(ls[rt],l,mid,L,R);
        if(R>mid)ret=max(ret,query(rs[rt],mid+1,r,L,R));
        return ret;
    }
    int RT;
    int ans[N];
    inline void MAIN(){
        n=read();
        for(res i=1;i<=n;i++)a[i]=read(),tr[i]=1000000000;
        m=read();
        for(res i=1;i<=m;i++){
            res l=read(),r=read();
            que[r].pb(mp(l,i)),ans[i]=1000000000;
        }
        for(res i=1;i<=n;i++){
            res p=query(RT,0,1000000000,a[i],1000000000);
            while(p)modify(p,a[p]-a[i]),p=query(RT,0,1000000000,a[i],(a[i]+a[p])/2-(~(a[i]+a[p])&1));
            modify(RT,0,1000000000,a[i],i);
            for(auto [l,id]:que[i])ans[id]=min(ans[id],query(l));
        }
        for(res i=1;i<=n;i++)tr[i]=1000000000,a[i]=1000000000-a[i];
        for(res i=1;i<=tot;i++)ls[i]=rs[i]=mx[i]=0;
        tot=RT=0;
        for(res i=1;i<=n;i++){
            res p=query(RT,0,1000000000,a[i],1000000000);
            while(p)modify(p,a[p]-a[i]),p=query(RT,0,1000000000,a[i],(a[i]+a[p])/2-(~(a[i]+a[p])&1));
            modify(RT,0,1000000000,a[i],i);
            for(auto [l,id]:que[i])ans[id]=min(ans[id],query(l));
        }
        for(res i=1;i<=m;i++)printf("%d\n",ans[i]);
    }
}

[Gym102956 K]

solution

题面：有 块木板，第 块木板有稳定性 ，木板从高到低排列。在木板上放置果子，第 块木板被放了大于等于 个果子后会碎裂，有 会下坠到下一块木板上。求至少需要多少果子才可以砸碎前 块木板。

做法：注意到可以先用一些少的果子让下面的木板被破掉，然后上面的果子就不会被除二。于是会考虑区间 ， 表示破掉了 到 还剩 个果子的最小代价，转移就很显然了。注意到破掉一个区间最多只会剩 个果子，因为剩更多还无意义。总复杂度 ，因为跑不满，所以可以过。

//2021.12.23 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=70+10;
namespace MAIN{
    int n;
    int a[N];
    int f[N][N][150+10];
    inline void MAIN(){
        n=read(),memset(f,0x3f,sizeof(f));
        for(res i=1;i<=n;i++)a[i]=read(),f[i][i][a[i]/2]=a[i];
        for(res len=2;len<=n;len++){
            for(res l=1,r=l+len-1;r<=n;l++,r++){
                for(res x=a[r]>>1;x<=150;x++){
                    res &ret=f[l][r][x];
                    for(res k=l+1;k<r;k++){
                        for(res X=a[r-1]/2;X<=150;X++){
                            res c=max(a[r]-X,0);
                            if(x-(X+c)/2>=a[k-1]/2)ret=min(ret,f[l][k-1][x-(X+c)/2]+f[k][r-1][X]+c);
                            else break;
                        }
                    }
                    if(x==a[r]>>1){
                        for(res X=a[r-1]>>1;X<=a[r]+1;X++){
                            res c=max(a[r]-X,0);
                            if((c+X)/2!=a[r]/2)break;
                            ret=min(ret,f[l][r-1][X]+c);
                        }
                    }
                    for(res X=a[r-1]>>1;X<=150;X++){
                        if(X/2>x)break;
                        res c=max(x*2-X,0);
                        if(c+X>=a[r])ret=min(ret,f[l][r-1][X]+c);
                    }
                    ret=min(ret,f[l][r-1][x-a[r]/2]+a[r]);
                }
            }
        }
        for(res i=1;i<=n;i++){
            res ans=inf;
            for(res j=a[i]>>1;j<=150;j++)ans=min(ans,f[1][i][j]);
            printf("%d ",ans);
        }
    }
}

[统一省选2021 A卷] 矩阵游戏

solution

题面：中文不会自己看？

做法：

[TC12304]

solution

题面：给出一棵 个点的树和 ，问有多少个 的排列，满足按排列重标号后，对于每一个 ， 总是个连通块。

做法：

[CF708 E]

solution

题面：有一个 的网格。

除了第一行和最后一行，其他每一行每一天最左边和最右边的格子都有 的概率消失。

求 天后，网格始终保持连通的概率。

做法：纯高中数列题。

考虑一个暴力 ，即设 表示当前算到第 行，存在的是 的概率。转移就是

$$f(i,l,r)=p_{l-1}p_{m-r}\sum_{[l',r']\cap [l,r]} f(i-1,l',r')$$

其中 为有 次删除的概率，等于 。

发现这个转移正着有点难讨论，不如算不交，即

$$f(i,l,r)=p_{l-1}p_{m-r}(\sum_{l'<r'} f(i-1,l',r')-\sum_{l'\leq r'<l}f(i-1,l',r')-\sum_{r<l'\leq r'}f(i-1,l',r'))$$

写好看点，即设第一个 $\sum$ 为 $F(i-1)$，第二个为 $L(i-1,l)$，第三个为 $R(i-1,r)$，那么就得看看这三个咋求。

首先根据对称性，有 $L(i,x)=R(i,m-x+1)$。

可惜 $L,R$ 还是 $O(n^2)$，我们把它们拆解一下，即

$$L(i,x)=\sum_{l\leq r<x} f(i,l,r)=\sum_{r<x} \sum_{l\leq r} f(i,l,r)\\\\ =\sum_{r<x} F_L(i,r)$$

注意到 $F_L$ 的形式很类似 $F$，所以我们类似地去推一下式子

$$\begin{align*} &F_L(i,x)=\sum_{l<x} f(i,l,x)=\sum_{l<x} p_{l-1}p_{m-x}(F(i-1)-L(i-1,l)-R(i-1,x))\\ &=p_{m-x}(F(i-1)-R(i-1,x))\sum_{l<x}p_{l-1}-p_{m-x}\sum_{l<x}p_{l-1}L(i-1,l) &\end{align*}$$

于是就得到了一个递推过程，一共 层，每一层处理出 的前缀和，这样就可以 推出 ，再处理 的前缀和，这样就可以得到 和 。总时间复杂度 。

//2021.12.27 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
const int M=1500+10;
namespace MAIN{
    int n,m,p,k;
    int F[M][M],L[M][M],FL[M][M],P[N],q[N];
    int fac[N],inv[N];
    inline int C(const res &x,const res &y){
        return mul(fac[x],mul(inv[y],inv[x-y]));
    }
    inline void MAIN(){
        n=read(),m=read(),p=read(),p=mul(p,qpow(read())),k=read(),fac[0]=fac[1]=inv[0]=inv[1]=1;
        for(res i=2;i<=k;i++)fac[i]=mul(fac[i-1],i),inv[i]=mul(inv[kcz%i],kcz-kcz/i);
        for(res i=2;i<=k;i++)inv[i]=mul(inv[i-1],inv[i]);
        for(res i=0;i<=min(m,k);i++)P[i]=mul(C(k,i),mul(qpow(p,i),qpow(1+kcz-p,k-i)));
        for(res i=1;i<=m;i++)q[i]=Add(q[i-1],P[i-1]);
        F[0][m]=L[0][m]=1;
        for(res i=1;i<=n;i++)for(res j=1;j<=m;j++){
            F[i][j]=mul(P[m-j],Add(mul(Add(L[i-1][m],kcz-L[i-1][m-j]),q[j]),kcz-FL[i-1][j]));
            L[i][j]=Add(L[i][j-1],F[i][j]);
            FL[i][j]=Add(FL[i][j-1],mul(P[j-1],L[i][j-1]));
        }
        printf("%d\n",L[n][m]);
    }
}

[loj6215]

solution

题面：中文题面建议自己看。如果读不懂可以手玩下样例。

做法：完全不会，直接偷学 EI 和 xy 的做法。

次幂直接是不好算的，考虑用第二类斯特林数拆解，即最终要求的是

$$\sum_{T_n} \sum_{u,v\in \mathrm{leaf}} \sum_{i} \begin{Bmatrix}k\\i \end{Bmatrix}i!\binom{\mathrm{len(u,v)}}{i}\\\\ =\sum_i \begin{Bmatrix}k\\i \end{Bmatrix}i! \sum_{T_n} \sum_{u,v\in \mathrm{leaf}}\binom{\mathrm{len(u,v)}}{i}$$

我们想把后面对应每个 求出来，这里是个比较经典的做法，具体证明可以用范德蒙德卷积（ 我好像以前写过，或许也有其它理解 ）。

令二叉树数量的 为 ， 的 为 ， 为 。

为了方便起见，在 暂时不考虑路径端点和 的存在，这只用在最后的地方乘上 进行修正。

利用固定根，枚举左右子树来得到 的递推式，即

$$\begin{align*} &F=1+xF^2\\ &G=1+2x(y+1)FG\\ &H=G^2+2xFH\\ &\end{align*}$$

解释下最后一条式子，考虑到 要么是根的两个子树合并起来，那么 就是根，这样路径总长就是相加（ 因为不考虑路径端点和 ），按范德蒙德卷积那样，这样的组合数上标刚好是路径之和、 还可以是某个子树算好了，那另外一边就是任意树，由于可以翻转，所以乘个 。

最后算出 ，再乘上一个 ，即答案为 （ 令 ）

$$[x^ny^i] \frac{x^3(1+y)^3}{(y(t-1)+t)^2t}\\\\ =[x^{n-3}y^i]\frac{(1+y)^3}{t^3(1-(\frac{1}{t}-1)y)^2}$$

分子那个可以先不管，最后乘上组合数即可，那么求的就是

$$[x^{n-3}y^i] \frac{1}{t^3(1-(\frac{1}{t}-1)y)^2}\\\\ =[x^{n-3}]\frac{1}{t^3}(i+1)(\frac{1}{t}-1)^i$$

这样的话，我们只要求出 即可在 的时间内解决这道题了 。（ EI 写的那个理论复杂度我看不懂。。。水平太低了，呜呜呜 ）

这是比较容易的，用一个拉格朗日反演即可，即

$$\begin{align*} &[x^n] \frac{1}{(\sqrt{1-4x})^i}=\frac{1}{n} [x^{-1}] (\frac{1-\frac{1}{x^{\frac{2}{i}}}}{4})^{-n}\\ &=\frac{4^n}{n}[x](1-x^{\frac{2}{i}})^{-n}\\ &=\frac{4^n}{n}[x^{\frac{i}{2}}](1-x)^{-n}\\ &=\frac{4^n}{n} \binom{\frac{i}{2}+n-1}{n-1} &\end{align*}$$

这个二项式系数至少可以在 的时间复杂度内求出，于是总复杂度就是 了。

然后我们会发现自己忽略了 的情况，这个情况也是可以用 推的，可以推出这个的 是 ，于是 。所以这个情况的答案就是 。

//2022.1.1 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e7+300+10;
const int M=300+10;
namespace MAIN{
    int f[N],g[M],C[M][M],h[M];
    inline void pre(const res &n,const res &m){
        if(n<0)return;
        res inv2=qpow(2),ret=mul(inv2,3),fac=1;
        f[0]=1,f[1]=1;
        for(res i=1;i<=n;i++)f[1]=mul(f[1],i+n),fac=mul(fac,i);
        f[1]=mul(f[1],qpow(fac)),f[2]=qpow(4,n);
        if(n==0)for(res i=3;i<=m;i++)f[i]=1;
        else for(res i=3;i<=m;i++)f[i]=mul(f[i-2],qpow(ret-1)),f[i]=mul(f[i],Add(ret,n-1)),add(ret,inv2);
        C[0][0]=1;
        for(res i=1;i<=m;i++){
            C[i][0]=1;
            for(res j=1;j<=i;j++)C[i][j]=Add(C[i-1][j],C[i-1][j-1]);
        }
    }
    int S[M][M];
    int ans[M];
    inline void MAIN(){
        res n=read(),m=read();
        pre(n-3,m+3);
        for(res i=0;i<=m;i++){
            for(res j=0;j<=i;j++){
                if(j&1)add(g[i],kcz-mul(C[i][j],f[i-j+3]));
                else add(g[i],mul(C[i][j],f[i-j+3]));
            }
            g[i]=mul(g[i],i+1);
        }
        for(res i=0;i<=m;i++)add(h[i],g[i]),add(h[i+1],mul(g[i],3)),add(h[i+2],mul(g[i],3)),add(h[i+3],g[i]);
        //S=S_2(i,j)*j!
        S[0][0]=1;
        for(res i=1;i<=m;i++)for(res j=1;j<=i;j++)S[i][j]=mul(Add(S[i-1][j-1],S[i-1][j]),j);
        for(res i=0;i<=m;i++)for(res j=0;j<=i;j++)add(ans[i],mul(S[i][j],h[j]));
        res Fac=1;
        if(n>=3){
            Fac=f[1];
            for(res i=2;i<=5;i++)Fac=mul(Fac,2*n-i);
            for(res i=1;i<=2;i++)Fac=mul(Fac,qpow(mul(n-i,n-i)));
        }
        else {
            for(res i=1;i<n;i++)Fac=mul(Fac,mul(qpow(i),i+n-1));
        }
        for(res i=0;i<=m;i++)add(ans[i],Fac),printf("%d ",ans[i]);
        puts("");
    }
}

[CF891 B]

solution

题面：有一个长度为 且数互不相同的序列 ，现要求将 排列成 ，满足任何一个非空下标真子集的 和不等于 和。

做法：一道降智题。

不要被构造题的数据范围迷惑了。平凡地，我们认为 是递增的。那么将 位移一位就是 。证明也是容易的，若不包含 ，则下者一定大于上者；若包含，则考虑补集，于是下者一定小于上者。时间复杂度 。

//2022.1.10 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=100+10;
namespace MAIN{
    int n;
    int a[N];
    Pair b[N];
    int c[N];
    inline void MAIN(){
        n=read();
        for(res i=1;i<=n;i++)a[i]=read(),b[i]=mp(a[i],i);
        sort(b+1,b+n+1),b[n+1].fi=b[1].fi;
        for(res i=1;i<=n;i++){
            c[b[i].se]=b[i+1].fi;
        }
        for(res i=1;i<=n;i++)printf("%d ",c[i]);
        puts("");
    }
}

[CC NOV19A PBOXES/CF802 O]

solution

题面：不会有人不知道 codechef 有官方汉化吧，不会吧不会吧。

做法：典中典之模拟费用流，之前因为实在不想写代码所以一直没用这种做法。

首先建个费用流模型，方便起见，我们将以前习惯的四层图模型改成三层，因为这类题的边是单向的，CC 这题经过贪心后也是单向的，CF 那题本来就是要求单向的。即 向每个点连个权值 流量 ，每个点向 连个权值 流量 ，然后点与点之间的连边是单向的，所以只要 向 连个权值 流量 即可。

这种题的增广都有一个很好的贪心性质：不会退回已经增广过的有权值边。这个性质保证了我们的增广路径实际就两种，一种是从 到 ，其中 。一种是 到 ，但 ，那么这里就满足 之间的边的反边有流量了，即被增广过了。也可以发现流量改变是区间的，要么加一，要么减一，于是我们分别考虑如何维护这两种增广信息。

第一种增广是随意的，只要找到左边一个最小的 ，右边一个最小的 ，直接加起来就是答案。这东西完全可以用线段树在合并区间的时候维护下即可。第二种增广有要求，它要求 之间的反边流量不为 ，那要咋维护呢？如果我们已经想要用线段树的话，那就是要考虑两个区间合并要用哪些信息。发现这个东西其实挺类似最大区间和的，一个区间要维护连着左端点的最长反边流量不为 的位置以及这一段的最小 ，还有右端点类似的一段位置和最小 。发现如果没有修改的话，我们已经维护了答案。如果是区间加一，那等于直接包揽了整段区间；如果是区间减一，我们还需要知道哪些反边流量为 ，然后缩短那一段。实际上维护为 的这个信息是艰难的，不如维护从左边开始的最小反边流量的位置和值（ 说得有点绕，不过手画一下是可以理解的 ），右边同理（ 同时可以注意到最小值都是一样的 ），然后也要把之前维护的流量不为 的信息改成不跨过这个最小值点。发现这样的话区间减某个数可以直接从哪个最小反边流量处断开即可（ 因为每次能减就已经保证了反边流量减完后还大于等于