冲刺省选2月14日第十五场
T1 开心消消乐
对于已经确定的 0/1 序列，考虑将操作转化使得可以增量构造
将每两个球看作 1 组，开一个栈保存前缀
此时要将当前组 （a,b） 加入栈中，只有两个操作
- 将 a,b 依次压入栈中
- 将 a 压入栈中并将栈中元素合并，然后将 b 压入栈中
使用一个函数 \(G[a,b](x)\) 保存这个栈，表示加入 0 返回 a，加入 1 返回 b
压栈操作转化为将 \(G[a,b](x)\) 改变为 \(G[a',b'](x)\)
所以就有了一个 dp，\(f_{i,j0,j1}\) 表示前 i 组是否能构成函数 \(G[j0,j1](x)\)
对于计数问题，dp套dp，\(f_{i,j}\)表示前 j 组恰好能构成的函数集合为 i 的方案数，复杂度 \(O(2^{2^2}n)\)
T2 树上的棋局
对于一棵有根树，一个节点的 SG 是其子树内到它的最远距离，一个棋子的 SG 是所在节点的 SG，一棵树的 SG 是所有棋子的异或和
考虑换根对节点 SG 的影响，设可重集合 \(dis_x\) 为以 x 为根时每个儿子的子树内最大深度的集合
然后发现集合内可能有贡献的只有最大值 (记为 \(f_x\)) 和次大值 （记为 \(g_x\)），因为 以 y 为根的 x 的子树就是整个联通块减去以 x 为根时 y 所在的子树，即每个节点最多只会有一个出点不能选
然后考虑 \(f_x,g_x\) 分别何时有贡献，当 x 为根时，最远点一定是直径的一个端点，且这条路径一定过树的中心(直径的中点)
当中心 md 为根时，所有点取 \(g_x\)，当 y 为根时，\(y->md\) 路径上所有点取 \(f_x\)，其他取 \(g_x\)
考虑到 \(f,g\) 交换和奇偶性改变对权值的影响，可以在线段树上维护 \(2* 2\) 的矩阵并支持行交换和列交换，然后链加和子树加就树剖+线段树就行了
(直径没中点？在中间硬塞一个)
T3 社会黄油飞
还没写，等填网络流的坑的时候再说吧，，，
这个数据就比较离谱，因为他大样例不知道用了什么方法构造了一下，我觉得他懒得多构造几种图了，然后他确实只有随的图和大样例的那种图
代码
T1
#include
#include
#include
#include
using namespace std;
#define il inline
#define int long long
const int N=1e5+11;
const int mod=998244353;
struct sta_{bool a,b;}sta[4];
char pot[N],tx[N];
int n;
int rle[2][2];
int st[N];
int f[16][N];
il void md(int &x){if(x>=mod)x-=mod;}
bool jud(int i,char b){return tx[i]==b;}
bool judi(int i,char j){return jud(i,'?')||jud(i,j);}
int mrg(int i,int j,int k){return (k<<2)+(j<<1)+i;}
bool get_ab(bool jd,int id){return !jd?sta[id].a:sta[id].b;}
il int read(){
int s=0;char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s;
}
int opt1(int id,int a,int b){
bool jd0=st[mrg(a,b,0)],jd1=st[mrg(a,b,1)];
jd0=get_ab(jd0,id);jd1=get_ab(jd1,id);
return rle[jd0][jd1];
}
int opt2(int id,int a,int b){
bool jd0=st[mrg(get_ab(a,id),b,0)],jd1=st[mrg(get_ab(a,id),b,1)];
return rle[jd0][jd1];
}
signed main(){
freopen("game.in","r",stdin);freopen("game.out","w",stdout);
for(int i=0;i<4;++i)sta[i]={(bool)(i&2),(bool)(i&1)},rle[sta[i].a][sta[i].b]=i;
int t=read();while(t--){
memset(f,0,sizeof(f));
scanf("%s",pot+1);scanf("%s",tx+1);n=strlen(tx+1);
for(int i=0;i<8;++i)st[i]=pot[i+1]-'0';
for(int i=0;i<2;++i)for(int j=0;j<2;++j){
if(!judi(1,i+'0')||!judi(2,j+'0'))continue;
++f[1< T2
#include
#include
#include
#include
#include
#include
using namespace std;
#define il inline
const int N=2e5+11;
int n,m,md;
int rt[2],now,ds;
int pg[N],sta[N],p;
int dfn[N],rle[N],tot;
int mxp[N],mxd[N],cmxd[N];
int top[N],son[N],f[N],siz[N],dep[N];
int st[20][N];
vectorvct[N];
vector::iterator it;
il int max_(int x,int y){return x>y?x:y;}
bool cmp(int a,int b){return mxd[a]>mxd[b];}
struct mat_{
bool c,r;
int a[2][2];mat_(){}
mat_(bool c_,bool r_,int a_[]){c=c_,r=r_;memcpy(a,a_,sizeof(a_));}
void revr(){swap(a[0][0],a[1][0]);swap(a[0][1],a[1][1]);r^=1;}
void revc(){swap(a[0][0],a[0][1]);swap(a[1][0],a[1][1]);c^=1;}
friend mat_ operator^(mat_ a,mat_ b){
a.c=a.r=0;
a.a[0][0]^=b.a[0][0];
a.a[0][1]^=b.a[0][1];
a.a[1][0]^=b.a[1][0];
a.a[1][1]^=b.a[1][1];
return a;
}
}tre[N*4];
il int read(){
int s=0;char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s;
}
void dfs1(int x,int fa){
for(int i=1;i<=pg[dep[x]];++i)st[i][x]=st[i-1][st[i-1][x]];
siz[x]=1;for(int v : vct[x]){
if(v==fa)continue;
dep[v]=dep[st[0][v]=f[v]=x]+1;
dfs1(v,x);siz[x]+=siz[v];
if(siz[son[x]]mxd[x])cmxd[x]=mxd[x],mxd[x]=mxd[v];
else if(mxd[v]==mxd[x])cmxd[x]=mxd[v];
else if(mxd[v]cmxd[x])cmxd[x]=mxd[v];
}
}
void get_out(int x,int fa,int dis){
vector s;mxp[x]=dis;
for(int v : vct[x])if(v!=fa)s.push_back(v);
sort(s.begin(),s.end(),cmp);
if(!s.size())return;
if(s.size()==1){get_out(s[0],x,dis+1);return;}
for(int v : s)get_out(v,x,max_(dis+1,(v==s[0]?mxd[s[1]]:mxd[s[0]])+2));
}
void get_rt(int x,int fa,int dis){
if(dis>ds)ds=dis,now=x;
for(int v : vct[x]){
if(v==fa)continue;
get_rt(v,x,dis+1);
}
}
void get_sta(){
int x=rt[0],y=rt[1];
if(dep[x]sx,sy;
while(dep[x]>dep[y])sx.push_back(x),x=f[x];
while(x!=y){
sx.push_back(x),sy.push_back(y);
x=f[x],y=f[y];
}sx.push_back(x);
for(int i=sy.size()-1;i>=0;--i)sx.push_back(sy[i]);
for(int i=0;idep[y]?y:x;
}
il void upd(int i){
if((i<<1)>8e5)return;
tre[i]=tre[i<<1]^tre[i<<1|1];
}
void build(int i,int l,int r){
if(l==r){
tre[i].a[0][0]=cmxd[rle[l]];
tre[i].a[1][0]=mxd[rle[l]];
return;
}int mid=(l+r)>>1;
build(i<<1,l,mid);build(i<<1|1,mid+1,r);upd(i);
}
il void pushdown(int i){
if((i<<1)>8e5)return;
if(tre[i].r)tre[i<<1].revr(),tre[i<<1|1].revr();
if(tre[i].c)tre[i<<1].revc(),tre[i<<1|1].revc();
tre[i].r=tre[i].c=0;
}
void chg(int i,int l,int r,int L,int R,bool jd){
if(L>R)return;pushdown(i);
if(l>=L&&r<=R){
if(jd)tre[i].revc();
else tre[i].revr();
return;
}int mid=(l+r)>>1;
if(L<=mid)chg(i<<1,l,mid,L,R,jd);
if(R>mid)chg(i<<1|1,mid+1,r,L,R,jd);upd(i);
}
void tre_rev(int x,int y,bool jd){
int fx=top[x],fy=top[y];
while(fx!=fy){
if(dep[fx]