abc262

https://atcoder.jp/contests/abc262

D:首先看数据范围,很明显是个$n^3$或$n^4$的题.首先枚举当前要用的数k,考虑到k的同余系下答案相等,先对序列取模,再更新背包.枚举k需要$O(n)$,序列中有n个数,每次更新背包需要$O(n^2)$,总复杂度$O(n^4)$.

For(id,1,n){
        ri v=ar[id]%M;
        //dp[i][j] 选用i个数,拼成剩余系下的j 
        iFor(i,n,1)
        For(j,0,M-1){
            dp[i][j]=(dp[i][j]+dp[i-1][(j-v+M)%M])%MOD;
        }
    }
    ans=(ans+dp[M][0])%MOD; //最后答案为用M个数拼成0

E:考虑所有标记过点的出度总和S,与标记过点相连的同色的边数R,不同色的边数D,满足$S=D+2R$,即若D为偶数,则S必为偶数.于是原问题可转化为从原图中选出若干点,使其出度总和为偶数,求方案数.此时点的出度可直接分为奇偶,组合数求和即可

for(ri i=0;i*2<=k;++i) ans=(ans+C(c[0],k-i*2)*C(c[1],i*2)%MOD)%MOD;

F:根据字典序,找出k能到达的范围内最小值lead.如果选择转动操作,需要转动的点仅在lead后方.这样仅用分两种情况讨论,直接删和转后再删.对于直接删的情况,维护一个单调栈,每次更新时执行删除操作.

For(i,1,n){
        while(p&&ar[i]<ar[sta1[p]]&&r)--r,--p;
        ++p,sta1[p]=i;
    }

如果旋转,旋转后的点删除不需要花费

while(p&&ar[i]<ar[sta2[p]]&&(r>=(sta2[p]<ld)))r-=(sta2[p]<ld),--p;
        ++p,sta2[p]=i;

最后比较两个答案的大小即可