20200704模拟赛

T1

$sub1$

没有问号的情况下，考虑如何线性判定。考虑每两位当作一组，对于每组有如下两种操作：

将两位依次压入栈中；将第一位与栈中全部元素合并后，再将第二位压入栈中。 可以发现栈中的情况可以看作是关于下一个压入元素的函数，即 $G[a,b](x)$，表示当 $x = 0 $时返回 $a$，$x=1$ 时返回 $b$。

假设当前栈中情况为 $G[a,b](x)$，考虑压入两位 $c,d$，容易根据上述两种操作合并出新的函数$G[a\prime ,b\prime ](x)$。

由于本质不同的函数只有 $4$ 种，用 $f[i][j_0][j_1]$ 表示前 $i$ 位能否得到 $G[j_0,j_1](x)$。

$sub2$

对于计数问题，$dp$ 套 $dp$ 即可，状态数是 $2^{4}n$。

$\mathcal{A}CCode$

#include<bits/stdc++.h> #define maxn 100005 #define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++) #define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--) #define pb push_back #define mp make_pair #define LL long long #define db double #define Ct const #define mod 998244353 using namespace std; char cb[1<<16],*cs=cb,*ct=cb; #define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<16,stdin),cs==ct)?0:*cs++) void read(int &res){ char ch; for(;!isdigit(ch=getc());); for(res=ch-'0';isdigit(ch=getc());res=res+ch-'0'); } char s[maxn]; int f[2][2][2],n; int g[2][1<<4]; void add(int &u,int v){ ((u+=v)>=mod) && (u -= mod); } int main(){ freopen("A.in","r",stdin); freopen("A.out","w",stdout); int T; for(scanf("%d",&T);T--;){ scanf("%s",s); int cnt = 0; rep(i,0,1) rep(j,0,1) rep(k,0,1) f[k][j][i] = s[cnt++] - '0'; memset(g,0,sizeof g); scanf("%s",s+1); n = strlen(s+1); int now = 1 , pre = 0; g[now][2] = 1; for(int i=1;i+2<=n;i+=2){ swap(now,pre); memset(g[now],0,sizeof g[now]); rep(sta,0,(1<<4)-1) if(g[pre][sta]) rep(a,s[i]=='?'?0:s[i]-'0',s[i]=='?'?1:s[i]-'0') rep(b,s[i+1]=='?'?0:s[i+1]-'0',s[i+1]=='?'?1:s[i+1]-'0') { int nsta = 0; rep(c,0,1) rep(d,0,1) if(sta >> (2*c+d) & 1) nsta |= 1 << 2 * (f[a][b][0] ? d : c) + (f[a][b][1] ? d : c), nsta |= 1 << 2 * (a ? f[d][b][0] : f[c][b][0]) + (a ? f[d][b][1] : f[c][b][1]); add(g[now][nsta],g[pre][sta]); } } int ans = 0; if(s[n] != '?'){ rep(sta,0,(1<<4)-1) if(g[now][sta]){ int f = 0; rep(c,0,1) rep(d,0,1) if(sta >> (2*c+d) & 1) if((s[n]-'0' ? d : c) == 1){ f = 1; break; } if(f) add(ans,g[now][sta]); } } else{ s[n] = '0'; rep(sta,0,(1<<4)-1) if(g[now][sta]){ int f = 0; rep(c,0,1) rep(d,0,1) if(sta >> (2*c+d) & 1) if((s[n]-'0' ? d : c) == 1){ f = 1; break; } if(f) add(ans,g[now][sta]); } s[n] = '1'; rep(sta,0,(1<<4)-1) if(g[now][sta]){ int f = 0; rep(c,0,1) rep(d,0,1) if(sta >> (2*c+d) & 1) if((s[n]-'0' ? d : c) == 1){ f = 1; break; } if(f) add(ans,g[now][sta]); } } printf("%d\n",ans); } }

T2

显然答案是 $s$ 的子串，所以可以把 $s$ 的后缀自动机建出来，在上面考虑。

对于 endpos 集合相同的串，显然 * 的个数随着串的长度单调递增，所以可以二分这个长度 $len$，然后 * 的个数就是每相邻两个 endpos 的距离和 $len$ 取 $\min$ 并求和。

这个东西也许可以线段树合并但没有必要，（大概）更好写的做法是在 fail 树上做树上启发式合并，并用 set 和树状数组维护相邻元素的距离。

最后为了比较哪一个串最优，求这两个串在后缀树上的$lcp$即可，所以一开始就反着建串即可。

$\mathcal{A}CCode$

#include<bits/stdc++.h> #define maxn 40005 #define S 131 #define rep(i,j,k) for(register int i=(j),LIM=(k);i<=LIM;i++) #define per(i,j,k) for(register int i=(j),LIM=(k);i>=LIM;i--) #define pb push_back #define mp make_pair #define LL long long #define db double #define Ct const #define maxc 26 using namespace std; char s[maxn]; int n,K; int tr[maxn][maxc],fa[maxn],len[maxn],pos[maxn],tot,last; LL hs[maxn],pw[maxn]; inline LL calc(int a,int b){ return (hs[b] - hs[a-1] * pw[b-a+1]); } int info[maxn],Prev[maxn],to[maxn],cnt_e; inline void Node(int u,int v){ Prev[++cnt_e]=info[u],to[cnt_e]=v,info[u]=cnt_e; } void ins(int c){ int u = ++tot , p = last , q; len[last = u] = len[p] + 1; for(;p != -1 && tr[p][c] == 0;p=fa[p]) tr[p][c] = u; if(p == -1) fa[u] = 0; else if(len[q = tr[p][c]] == len[p] + 1) fa[u] = q; else{ int v = ++tot; memcpy(tr[v],tr[q],sizeof tr[q]),fa[v]=fa[q],len[v]=len[p]+1; for(;p!=-1 && tr[p][c] == q;p=fa[p]) tr[p][c] = v; fa[q] = fa[u] = v; } } int sz[maxn] , son[maxn]; void dfs0(int u){ son[u] = -1 , sz[u] = 1; for(int i=info[u];i;i=Prev[i]){ int v = to[i]; dfs0(v); if(son[u] == -1 || sz[v] > sz[son[u]]) son[u] = v; sz[u] += sz[v]; } } LL tri[maxn],trx[maxn]; inline void upd(int u,LL v){ LL p = v * (1 - u);for(;u<=n;u+=u&-u) tri[u] += v , trx[u] += p; } inline LL qry(int u){ LL r=0,I=u;for(;u;u-=u&-u) r+=tri[u] * 1ll * I + trx[u];return r; } int ansl,ansr; set<int>st; void dfs2(int u){ if(pos[u]){ set<int>::iterator it = st.insert(pos[u]).first , it2 = it; it2 ++ , it --; upd(1,1) , upd(pos[u] - (*it) + 1 , -1); if(it2 != st.end()) upd((*it2)-pos[u]+1,-1),upd((*it2)-(*it)+1,1); } for(int i=info[u];i;i=Prev[i]){ int v = to[i]; dfs2(v); } } void dfs1(int u){ for(int i=info[u];i;i=Prev[i]){ int v = to[i]; if(v == son[u]) continue; dfs1(v); set<int>::iterator it = st.end() , it2 = st.end(); it--; for(;it != st.begin();){ it2 = it , it2--; upd(1,-1) , upd((*it)-(*it2)+1,1); it--; } st.clear(); st.insert(0); } if(son[u] != -1) dfs1(son[u]); if(!u) return; if(pos[u]){ set<int>::iterator it = st.insert(pos[u]).first , it2 = it; it2 ++ , it --; upd(1,1) , upd(pos[u] - (*it) + 1 , -1); if(it2 != st.end()) upd((*it2)-pos[u]+1,-1),upd((*it2)-(*it)+1,1); } for(int i=info[u];i;i=Prev[i]){ int v = to[i]; if(v == son[u]) continue; dfs2(v); } int L = len[fa[u]]+1 , R = len[u] , mid; for(;L<R;){ mid = L+R >> 1; if(qry(mid) < K) L = mid + 1; else R = mid; } if(qry(L) == K){ int sr = (*st.rbegin()) , sl = sr - L + 1; if(sr - sl < ansr - ansl) ansl = sl , ansr = sr; else if(sr - sl == ansr - ansl){ L = 0 , R = sr - sl; for(;L<R;){ mid = L+R+1 >> 1; if(calc(sl,sl+mid-1) != calc(ansl,ansl+mid-1)) R = mid - 1; else L = mid; } if(s[sl+L] < s[ansl+L]) ansl = sl , ansr = sr; } } } int main(){ freopen("B.in","r",stdin); freopen("B.out","w",stdout); int T;fa[0] = -1; pw[0] = 1; rep(i,1,maxn-1) pw[i] = pw[i-1] * S; for(scanf("%d",&T);T--;){ last = 0 , ansr = 0x3f3f3f3f , ansl = 0; memset(trx,0,sizeof trx); memset(tri,0,sizeof tri); memset(pos,0,sizeof pos); memset(tr,0,sizeof tr); st.clear(); scanf("%s",s+1); scanf("%d",&K); n = strlen(s+1); rep(i,1,n) hs[i] = (hs[i-1] * S + s[i]) , ins(s[i] - 'a') , pos[last] = i; rep(i,1,tot) Node(fa[i],i); dfs0(0); st.insert(0); dfs1(0); if(ansr > n) puts("NOTFOUND!"); else{ rep(i,ansl,ansr) putchar(s[i]); putchar('\n'); } rep(i,0,tot) info[i] = 0; cnt_e = 0; tot = 0; } }

T3

首先，考虑到区间异或可以前缀和。我们把分割序列的断点取出来，那么就会得到一个分割方案的必要条件，即每个断点处的前缀和必须是给出的集合能够线性组合出来的数。

例如$[1,1,4,5,1,4]$ 的前缀和为$[1,0,4,1,0,4]$。则对于集合 $\{1,4\}$ 和分割方案$[1],[1],[4,5],[1],[4]$，则有前缀和 $1,0,1,0,4$。于是，能够马上得到一个结论：总是存在一种方案，使得最后构造出来的序列段数 $m\le 2^k$ 。

证明就是考虑到如果最终方案中有两个断点前缀和相同，例如 $[5,3,2,5]$，那么显然后三段的异或和为$0$，显然是可以和前面的 $5$ 并起来变成单个 $5$。从最简单的 $dp$ 开始考虑。 $f_i$ 表示最后一个断点在 $i$ 是否可行。根据上面的结论，注意到如果有前缀和 $p_j=p_i(j<i)$，且有 $f_j=1$，那么显然 $f_i $ 能贡献到的状态， $f_j$ 都能贡献到。

于是实际上我们只需要记录在所有的可行分割方案中，一个前缀和的出现位置的最小值 $f_v$ ，如果不存在则设为 $n+1$。容易证明最终的可行性就是 $f_{p_n}\le n$ 。一个值分别异或上查询集合里所有的数，可以得到这个数的转移目标的集合。

我们把序列前缀和的每种数单独提出来写成若干个位置集合，如果可以支持查询后继，就能转移：注意到对一个值 $v$ 如果有 $i<j$，且在 $i$ 处查询过，如果没有后继，则在 $j$处没有后继；如果有后继，显然 $ j$ 处的没有 $i$ 处的优。于是可以用类似最短路的写法，用一个优先队列 $bfs$，每种能线性组合出的数最多访问一次，所以单次询问最多调用 $O(k{2}^k)$ 次查询后继操作。

剩下的问题是区间异或，查询一个值在序列中下一次出现位置。可以使用分块的技巧处理。对于每一块里，维护一个 $bitset$ 记录哪些数出现过，和一个异或标记。这样修改和询问的时候都暴力即可。

虽然复杂度 $O(nk{2}^k\sqrt{n})$ 有点爆炸，但出题人很菜，肯定卡不满，所以就可以跑过去了。

$\mathcal{A}CCode$

#include<bits/stdc++.h> #define maxn 100005 #define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++) #define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--) #define pb push_back #define mp make_pair #define LL long long #define db double #define Ct const #define mp make_pair using namespace std; char cb[1<<16],*cs=cb,*ct=cb; #define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<16,stdin),cs==ct)?0:*cs++) void read(int &res){ char ch; for(;!isdigit(ch=getc());); for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0'); } char Start; #define S 355 int n,Q,A[maxn],sm[maxn],id[maxn],st[S],ed[S]; bitset< 1<<20 >B[S]; int tg[S],f[1<<20]; int findnxt(int u,int v){ rep(i,u,ed[id[u]]) if((sm[i] ^ tg[id[i]]) == v) return i; rep(i,id[u]+1,id[n]) if(B[i][v ^ tg[i]]) rep(j,st[i],ed[i]) if((sm[j] ^ tg[i]) == v) return j; return n+1; } int main(){ freopen("C.in","r",stdin); freopen("C.out","w",stdout); read(n),read(Q); rep(i,1,n) read(A[i]),sm[i] = sm[i-1] ^ A[i],id[i] = (i-1)/S , st[id[i]] = st[id[i]] ? st[id[i]] : i , ed[id[i]] = i; rep(i,1,n) B[id[i]][sm[i]] = 1; for(int op,x,y;Q--;){ read(op),read(x); if(op == 1){ read(y);int t = A[x] ^ y; rep(i,id[x]+1,id[n]) tg[i] ^= t; int p = tg[id[x]];tg[id[x]] = 0; B[id[x]].reset();A[x] = y; rep(i,st[id[x]],ed[id[x]]) sm[i] ^= p ^ (i >= x ? t : 0), B[id[x]][sm[i]] = 1; } else{ static int ar[10],st[1<<5]; rep(i,0,x-1) read(ar[i]); rep(i,0,(1<<x)-1){ st[i] = 0; rep(j,0,x-1) if(i >> j & 1) st[i] ^= ar[j]; f[st[i]] = n+1; } static priority_queue<pair<int,int> >q; rep(i,0,x-1){ int t; if((t = findnxt(0,ar[i])) <= n) f[ar[i]] = t , q.push(mp(-f[ar[i]],ar[i])); } for(int u,w;!q.empty();){ w = q.top().first , u = q.top().second;q.pop(); if(-w != f[u]) continue; int t ; rep(j,0,x-1) if((t = findnxt(-w , ar[j] ^ u)) < f[ar[j] ^ u]){ f[ar[j]^u] = t; q.push(mp(-f[ar[j]^u],ar[j]^u)); } } bool flg = 0; rep(i,0,(1<<x)-1) if(st[i] == (sm[n] ^ tg[id[n]]) && f[st[i]] <= n){ flg = 1; break; } if(flg) puts("yes"); else puts("no"); } } }