考场

T1 没看懂

T4 一眼回滚莫队，但忘记怎么写了，小慌

模拟 T1 题意的时候教练让 zsy 澄清了一下，确定了我不会做。。。

T2 一看就是毒瘤题，T3 感觉比较可做

T4 确定了回滚的细节，除了板子不会写其他都会了

7.40 开写，1h 后写完前三题暴力

先回想了一下普通莫队和回滚的思想，结合题目具体确定了实现方法，9.00 开写，比想象中顺利多了，9.40 过样例，10.00 过拍

剩下的时间没事干，先把 T3 的两个部分分写了，然后给 T1 加了个记忆化，对着数据卡常（一开始要 7s），随机的极限数据能在 0.8~1.1s 内跑过，记忆化后有点像状压 DP，但没啥时间了，就没细想。（卡常期间想起 T4 就是区间 mex，貌似可以主席树，感觉要被全场切了）

交题的时候发现 T1 还有个地方可以卡，但想着不差这点，且最后 10min 不想再改，就放弃了

res

rk1 95+65+70+100

T1 真被卡了 5ms

rk2 gjy 50+100+50+50

rk3 付文暄 50+65+100+20

总结

学东西的时候一定要注重思想，并想清楚代码为什么这么实现，这样即使忘了也能现推

发现自己心态还是不太好，如果有会做的非一眼题就比较正常，该拼部分分拼部分分，该卡常卡常；但如果一个题都不会，就很烦，暴力懒得想优化，部分分稍微想想就丢了，然后肝题到快结束，最后打 tetris。

最近倒是不打 tetris 了，但还是会心态爆炸，考场不是自闭的地方，即使啥都不会也要打满暴力，想不出题就优化暴力，卡常，不要把考场的时间用来发呆。

改题时发现对于拼接 hash 这种细节很多的东西很容易调不出来，以后遇到这类问题先在草稿纸上列好，尤其是边界，不要写完之后再改，效率太低。

打表

考场做法：考虑先枚举出每次由哪个 CPU 决策（称为 CPU 的决策顺序），在 dfs 出它当前这位填 \(0\) 还是 \(1\)，记忆化未决策的 CPU 和当前已填位状态即可。

正确性：显然不论哪个 CPU 做决策，选择的是同一位，但填的数相反（可以用反证法证明），因此被选择的位的顺序是固定的（称为最优顺序）。先强制令每次决策时决策剩下的最高位，那么对于一个 CPU 的决策序列，可以将它的顺序掉换成最优顺序，由于所有 CPU 的决策顺序都会被枚举到，那么这么做是等价的。

（其实到这里就很接近正解了， 但考场上没多想）

code

const int mod = 1e9+7;
int n,m,a[1<<18];

int all,ans;
unordered_map<int,int> f[1<<19];

int Pow(int x,int y=mod-2)
    { int res=1; for(;y;y>>=1,x=(LL)x*x%mod)if(y&1)res=(LL)res*x%mod; return res; }

int dfs(int u,int cpu,int p) {
    if( u > n ) return abs(a[p]-a[m]);
    if( f[cpu].count(p) ) return f[cpu][p];
    int res0 = dfs(u+1,cpu>>1,p<<1), res1 = dfs(u+1,cpu>>1,p<<1|1);
    return f[cpu][p] = cpu&1 ? min(res0,res1) : max(res0,res1);
}

signed main() {
    read(n,m); all = (1<<n--)-1;
    For(i,0,all) read(a[i]);
    for(int i = 1<<n+1, ii = i|all; i <= ii; ++i) ans = (ans + dfs(0,i,0)) %mod;
    write((LL)ans*Pow(1<<n+1)%mod);
    return iocl();
} 

蛇

只考虑蛇向右的情况，它的路径一定是先向左走一段（可能为 \(0\)），再调头向右，然后上下扭动地走，最后再调头向左。

考虑 hash 求出路径的左右的部分，然后中间的路径数可以 DP。（需要特判 \(|S|\le2\) 的情况）

细节很多。

code

const int N = 2e3+5, mod = 1e9+7, dx[]={0,-1,0,1}, dy[]={-1,0,1,0};
char s[2][N],t[N];

const LL P = 999999001;
int n,m;
LL ans,f[2][N][N];
LL base[N],hs[4][N],ht[2][N];

void ckadd(LL &x,LL y) { x+=y; if(x>=mod) x-=mod; }

namespace sub {
bool vis[2][N];
void dfs(int x,int y,int u) {
    if( u == m ) return ++ans, void();
    For(i,0,3) {
        int xx = x+dx[i], yy = y+dy[i];
        if( xx<0||xx>1||yy<1||yy>n || vis[xx][yy] || s[xx][yy] != t[u+1] )
            continue;
        vis[xx][yy] = 1, dfs(xx,yy,u+1), vis[xx][yy] = 0;
    }
}
void main() {
    if( m > 2 ) return; cerr<<"sub"<<endl;
    For(i,0,1) For(j,1,n) if( s[i][j] == t[1] )
        vis[i][j] = 1, dfs(i,j,1), vis[i][j] = 0;
    write(ans%mod);
    iocl(), exit(0);
}
}

LL hsh(LL *h,int l,int r) { return (h[r] - h[l-1]*base[r-l+1] %P+P)%P; }
LL rhsh(LL *h,int l,int r) { return (h[l] - h[r+1]*base[r-l+1] %P+P)%P; }
void work() {
    memset(f,0,sizeof f);
    For(i,1,n) hs[0][i] = (hs[0][i-1] * 997 + s[0][i]) %P, // 1为高位
               hs[1][i] = (hs[1][i-1] * 997 + s[1][i]) %P;
    rFor(i,n,1) hs[2][i] = (hs[2][i+1] * 997 + s[0][i]) %P, // n为高位
                hs[3][i] = (hs[3][i+1] * 997 + s[1][i]) %P;
    For(i,1,m) ht[0][i] = (ht[0][i-1] + t[i] * base[i-1]) %P;
    rFor(i,m,1) ht[1][i] = (ht[1][i+1] * 997 + t[i]) %P;
    For(i,1,n) {
        f[0][i][1] = s[0][i]==t[1], f[1][i][1] = s[1][i]==t[1];
        For(j,1,i) {
            int len = i-j+1;
            f[1][i][len*2] =
                    (hsh(hs[0],j,i)+rhsh(hs[3],j,i)*base[len])%P == ht[0][len*2];
            f[0][i][len*2] =
                    (hsh(hs[1],j,i)+rhsh(hs[2],j,i)*base[len])%P == ht[0][len*2];
        }
    }
    For(i,1,n) For(j,2,m) {
        if( s[0][i] == t[j] ) {
            ckadd(f[0][i][j],f[0][i-1][j-1]);
            if( s[1][i] == t[j-1] ) ckadd(f[0][i][j],f[1][i-1][j-2]);
        }
        if( s[1][i] == t[j] ) {
            ckadd(f[1][i][j],f[1][i-1][j-1]);
            if( s[0][i] == t[j-1] ) ckadd(f[1][i][j],f[0][i-1][j-2]);
        }
    }
    For(i,1,n) ckadd(ans,f[0][i][m]), ckadd(ans,f[1][i][m]);
    For(i,1,n) rFor(j,i-1,1) {
        int len = i-j+1; if( len*2 > m ) break;
        if( (hsh(hs[0],j,i)*base[len]+rhsh(hs[3],j,i))%P == ht[1][m-len*2+1] )
            ckadd(ans,f[1][j-1][m-len*2]);
        if( (hsh(hs[1],j,i)*base[len]+rhsh(hs[2],j,i))%P == ht[1][m-len*2+1] )
            ckadd(ans,f[0][j-1][m-len*2]);
    }
}

signed main() {
    base[0] = 1; For(i,1,2e3) base[i] = base[i-1] * 997 %P;
    scanf("%s%s%s",s[0]+1,s[1]+1,t+1); n = strlen(s[0]+1), m = strlen(t+1);
    sub::main();
    work(), reverse(s[0]+1,s[0]+n+1), reverse(s[1]+1,s[1]+n+1), work();
    write(ans);
    return iocl();
} 

购物

显然如果 \(a_i\) 能凑出 \(x\)，那么区间 \([\lceil\frac x2\rceil,x]\) 中的 \(k\) 都合法。

结论：将 \(a\) 排序，记 \(s_i\) 为 \(a_i\) 前缀和，那么 \((1,s_n)\) 中不合法的 \(k\) 就是 \([s_{i-1},\frac{a_i}2]\)（这个区间如果为空则不考虑）的并集。

证明：

已处理完了 \([1,s_{i-1}]\)，当前处理的区间 \((s_{i-1},\frac{a_i}2)\)。如果这个区间为空显然正确；如果不为空，则前 \(i-1\) 个数最多只能凑到 \(s_{i-1}\)，而第 \(i\) 个数之后的数都 \(\ge a_i\)，最少也是 \(\frac{a_i}2\)，因此这个区间是不可能被补上的。

再考虑证明 \([\frac{a_i}2,s_i]\) 一定合法。如果前面没有空隙显然合法；如果有，那么空隙大小一定 \(\le\frac{a_i}2\)（前面的总长只有 \(\frac{a_i}2\)），设空隙为 \((l,r)\)，则将 \(l\) 左边、\(r\) 右边的区间加 \(a_i\) （总和加 \(a_i\)，左端点加 \(\frac{a_i}2\)，右端点加 \(a_i\)）后这个区间变为 \((l+a_i,r+\frac{a_i}2)\)，一定为空。

code

const int N = 1e5+5;
int n,a[N];

LL ans,s[N];

signed main() {
    read(n);
    For(i,1,n) read(a[i]); sort(a+1,a+n+1);
    For(i,1,n) {
        s[i] = s[i-1] + a[i];
        ans -= max((a[i]+1)/2-s[i-1]-1,0ll);
    }
    write(ans+s[n]);
    return iocl();
} 

ants

裸的回滚莫队

值域上每个点维护它向左、向右能连续到哪，插入 \(x\) 时与 \(x-1,x+1\) 合并，每次有三个点需要回滚。

考场代码

const int N = 1e5+5;
int n,m,a[N];
struct Q { int l,r,id; } q[N];

int size,mm,now,be[N],le[N],ri[N],ans[N];
bool vis[N];
int tp; struct Node { int p,v,l,r; } stk[N*3];

bool operator < (const Q &x,const Q &y)
    { return be[x.l]!=be[y.l] ? x.l<y.l : x.r<y.r; }

void push(int x) { stk[++tp] = Node{x,vis[x],le[x],ri[x]}; }
void add(int x,bool op) {
    int l = le[x-1], r = ri[x+1];
    if( vis[x-1] ) { if( op ) push(l); } else l = x;
    if( vis[x+1] ) { if( op ) push(r); } else r = x;
    if( op ) push(x);
    vis[x] = 1, le[x] = l, ri[x] = r, ri[l] = r, le[r] = l;
    ckmax(now,ri[x]-le[x]+1);
}
void clear() {
    while( tp ) {
        auto u = stk[tp--];
        vis[u.p] = u.v, le[u.p] = u.l, ri[u.p] = u.r;
    }
}
int bf(int l,int r) {
    For(i,l,r) add(a[i],1);
    int res = now;
    now = 0, clear();
    return res;
}

signed main() {
//    freopen("d.in","r",stdin);
//    freopen("d.out","w",stdout);
    read(n,m); size = sqrt(n);
    For(i,1,n) read(a[i]), be[i] = (i-1)/size+1, le[i] = ri[i] = i;
    For(i,1,m) {
        int l,r; read(l,r);
        if( be[l] == be[r] ) ans[i] = bf(l,r);
        else q[++mm] = Q{l,r,i};
    }
    sort(q+1,q+mm+1);
    for(int i = 1, r; i <= mm; ++i) {
        if( be[q[i].l] != be[q[i-1].l] ) {
            now = 0, r = size * be[q[i].l];
            For(i,1,n) vis[i] = 0, le[i] = ri[i] = i;
        }
        while( r < q[i].r ) add(a[++r],0);
        int l = size * be[q[i].l] + 1, old = now;
        while( l > q[i].l ) add(a[--l],1);
        ans[q[i].id] = now;
        now = old, clear();
    }
    For(i,1,m) write(ans[i]);
    return iocl();
}