【考试总结】2022-03-27
博弈论
诈 骗 大 师
尝试计算每个棋子放在某个点最多能带来的等着数量，使用 \(\rm DAG\) 上面 \(\rm DP\) 即可实现，注意两个人都希望在同色联通块中走的路径最长，同时走到临界点的时候都可以选择不再继续移动
剩下的是一个 背包问题，如果选出的所有石子给 \(A,B\) 带来的收益满足 \(A\) 的等着数量大于 \(B\) 就胜利了
Code Display
const int N=310;
char s[N];
int dp[N];
int f[2][N*N*2],out[N],n,m,a[N];
vector G[N],revG[N];
signed main(){
freopen("game.in","r",stdin); freopen("game.out","w",stdout);
n=read(); m=read();
scanf("%s",s+1);
for(int i=1;i<=n;++i) a[i]=s[i]=='W';
for(int i=1;i<=m;++i){
int u=read(),v=read();
G[u].emplace_back(v);
revG[v].emplace_back(u);
out[u]++;
}
queue q;
for(int i=1;i<=n;++i) if(!out[i]) q.push(i);
while(q.size()){
int fr=q.front(); q.pop();
for(auto t:G[fr]){
if(a[fr]==a[t]) ckmax(dp[fr],dp[t]+1);
else ckmax(dp[fr],-dp[t]+1);
}
for(auto t:revG[fr]){
if(!(--out[t])) q.push(t);
}
}
for(int i=1;i<=n;++i) if(!a[i]) dp[i]=-dp[i];
int cur=0;
const int U=N*N;
f[cur][U]=1;
for(int i=1;i<=n;++i){
for(int j=0;j 排列
将排列中二元组 \((a,b)\) 视作有向图上 \(a\to b\) ，那么题目中的限制相当于排列合法当且仅当其每个区间形成的 \(\rm DAG\) 都具有传递性
这里传递性形式化表达为：记 \(S_i\) 表示 \(i\) 在 \(\rm DAG\) 上可以到达的点所构成的集合，对于 \(x\in S_i,S_x\subsetneq S_x\)
其实区间的传递性和同时满足 每个前缀具有传递性 \(\&\) 每个后缀具有传递性 是等价的，使用简单的反证法可以找到矛盾
由于整个排列构成了一个 \(1\sim n\) 的竞赛图，那么上述限制等价于某个 \(\rm DAG\) 和它的补图具有传递性
我们发现上述形式的传递性和 \((i,p_i)\) 对应的二维偏序是完全等价的，也就是可行的 \(\rm DAG\) 构造是且仅是找到一个排列 \(\rm P\)，找到其中所有 \(i
此时转化为将 \(\{1,\dots n\}\) 通过 冒泡排序（也就是只能交换相邻两个元素） 变成 \(\{n,\dots 1\}\) 的方案数，可以通过康拓展开给排列标号后进行拓扑排序得到答案
对于题目中涉及的 \(m\) 条限制，每次翻转相邻点对时进行合法性判定即可
Code Display
int n,lim;
vector > G,perm,pos;
vector > seq;
vector Fac,dp;
inline int dfs(int S){
if(~dp[S]) return dp[S];
if(S==Fac[n]) return 1;
int sum=0;
vector &cur=perm[S];
vector p(n+1);
for(int i=1;i<=n;++i) p[cur[i]]=i;
for(int i=1;ip[seq[t].sec]){leg=0; break;}
if(!leg) continue;
int New_S=S;
int o1=0,o2=1;
for(int j=i+1;j<=n;++j) o1+=cur[j] id(n+1);
for(int i=1;i<=n;++i) id[i]=i;
perm.resize(Fac[n]+1);
int CNT=0;
do perm[++CNT]=id; while(next_permutation(id.begin()+1,id.end()));
// Label Finished
for(int i=1;i<=lim;++i){
int a=read(),b=read(),c=read(),d=read();
G[pos[a][b]].emplace_back(pos[c][d]);
}
print(dfs(1)); putchar('\n');
return 0;
}
子段和
尝试计算将最大子段和减少到 \(k\) 的最少操作次数，设为 \(g(k)\)
进行判定时，维护变量 \(\lim\)，初值为 \(k\)，以及前缀和数组 \(s_i\) ：若 \(s_i>lim\) 则将后缀 \(s_i\) 都减小 \(s_i-lim\)；\(\lim\leftarrow \min(\lim,s_i+k)\)
这个过程和下述过程是等价的，仍然维护 \(\lim=k\) 和操作次数计数器 \(cnt=0\) 如果 \(\lim
正确性相对容易理解
使用二分答案来得到进行不超过 \(K\) 次操作后最大子段和的值域 \([L,R]\) 那么经过一些和式变换可以发现最终问题就是求最大子段和值域 \([L,R]\) 内所有 \(w\) 的 \(cnt(w)\) 的值，对所有 \(w\) 同时进行上面的过程：
使用动态开点线段树维护整个过程，每个叶子节点对应一个 \(\lim(w)\) 差为 \(0/1\) 的连续 \(w\)，同时需要维护最大最小值和区间 \(\lim(w)\) 的和
注意这个过程并不需要求出来 \(cnt(w)\) 的具体值，只用计算每次得到的权值对答案的贡献之和，形式为区间长度乘 \(s_i-\) 区间和
发现在整个过程中 \(\lim(w)\) 满足随 \(w\) 递增而不降同时 \(\lim(w)-w\) 满足不升，所以对于 ckmin,ckmax 操作可以进行线段树上二分得到需要修改的区间，那么在线段树上新建立一个叶子即可
当然可以直接使用单调栈来代替线段树
Code Display
inline int qmod(int x){return (x%mod+mod)%mod;}
const int N=2e5+10,M=100*N,Inf=2e13;
inline int S(int l,int r){
int v1=r-l+1,v2=l+r;
if(v1&1) return v2/2%mod*(v1%mod)%mod;
else return v1/2%mod*(v2%mod)%mod;
}
bool k[M];
signed ls[M],rs[M];
int sum[M],L[M],Mn[M],Mx[M],tot,rt;
int a[N],n,K,ans,Wl,Wr;
inline int estab(int sl,int b,int l,int r){
int now=++tot;
k[now]=sl; L[now]=b;
Mn[now]=sl*l+b; Mx[now]=sl*r+b;
sum[now]=k[now]?S(Mn[now],Mx[now]):mul(L[now]%mod,(r-l+1)%mod);
return now;
}
inline void push_up(int p){
L[p]=-Inf-1; k[p]=0;
sum[p]=add(sum[ls[p]],sum[rs[p]]);
Mn[p]=Inf; Mx[p]=-Inf;
if(ls[p]){
ckmax(Mx[p],Mx[ls[p]]);
ckmin(Mn[p],Mn[ls[p]]);
}
if(rs[p]){
ckmax(Mx[p],Mx[rs[p]]);
ckmin(Mn[p],Mn[rs[p]]);
}
return ;
}
inline void make_son(int p,int l,int r){
int mid=(l+r)>>1;
if(!ls[p]) ls[p]=estab(k[p],L[p],l,mid);
if(!rs[p]) rs[p]=estab(k[p],L[p],mid+1,r);
return ;
}
inline int query_leq(int val,int p=rt,int l=Wl,int r=Wr){
if(Mn[p]>val) return l-1;
if(Mx[p]<=val) return r;
if(l==r) return l;
if(!ls[p]){
if(k[p]) return val-L[p];
else return r;
}
int mid=(l+r)>>1;
if(Mx[ls[p]]>=val) return query_leq(val,ls[p],l,mid);
else return query_leq(val,rs[p],mid+1,r);
}
inline int query_sum(int st,int ed,int p=rt,int l=Wl,int r=Wr){
if(st<=l&&r<=ed) return sum[p];
if(!ls[p]){
if(!k[p]) return mul(L[p]%mod,(r-l+1)%mod);
else return S(L[p]+max(st,l),L[p]+min(ed,r));
}
int mid=(l+r)>>1,res=0;
if(st<=mid) ckadd(res,query_sum(st,ed,ls[p],l,mid));
if(ed>mid) ckadd(res,query_sum(st,ed,rs[p],mid+1,r));
return res;
}
inline int query_geq(int val,int p=rt,int l=Wl,int r=Wr){
if(!ls[p]){
if(!k[p]){
if(val+l>L[p]) return l-1;
if(val+r>1;
if(Mx[ls[p]]<=val+mid) return query_geq(val,ls[p],l,mid);
return query_geq(val,rs[p],mid+1,r);
}
inline void check_min(int st,int ed,int v,int p=rt,int l=Wl,int r=Wr){
if(st<=l&&r<=ed){
L[p]=v; Mn[p]=v+l; Mx[p]=v+r;
sum[p]=S(Mn[p],Mx[p]);
k[p]=!(ls[p]=rs[p]=0);
return ;
}
if(!ls[p]) make_son(p,l,r);
int mid=(l+r)>>1;
if(st<=mid) check_min(st,ed,v,ls[p],l,mid);
if(ed>mid) check_min(st,ed,v,rs[p],mid+1,r);
return push_up(p);
} // v + l
inline void check_max(int st,int ed,int v,int p=rt,int l=Wl,int r=Wr){
if(st<=l&&r<=ed){
L[p]=Mn[p]=Mx[p]=v;
sum[p]=mul(v%mod,(r-l+1)%mod);
k[p]=ls[p]=rs[p]=0;
return ;
}
if(!ls[p]) make_son(p,l,r);
int mid=(l+r)>>1;
if(st<=mid) check_max(st,ed,v,ls[p],l,mid);
if(ed>mid) check_max(st,ed,v,rs[p],mid+1,r);
return push_up(p);
} // v
inline int calc(int w){
int lim=w,Aw=0;
for(int i=1;i<=n;++i){
Aw+=max(0ll,a[i]-lim);
lim=max(lim,a[i]);
ckmin(lim,a[i]+w);
} return Aw;
}
signed main(){
freopen("seg.in","r",stdin); freopen("seg.out","w",stdout);
n=read();
int Mn=0,Mx=0;
rep(i,1,n){
a[i]=read()+a[i-1];
ckmax(Mx,a[i]-Mn);
ckmin(Mn,a[i]);
}
K=read();
int tar=-Inf,wl=-Inf,wr=Mx;
while(wl<=wr){
int mid=(wl+wr)>>1;
if(calc(mid)>K) wl=mid+1;
else wr=mid-1,tar=mid;
}
if(tar==Mx) print(mul(qmod(Mx),K)),exit(0);
ans=qmod(tar)*((K+1)%mod)%mod-Mx;
ans=qmod(ans);
Wr=Mx-1,Wl=tar;
rt=estab(1,0,Wl,Wr);
for(int i=1;i<=n;++i){
int pos=query_leq(a[i]);
if(pos>=Wl) ckdel(ans,query_sum(Wl,pos));
ckadd(ans,mul(a[i]%mod,(pos-Wl+1)%mod));
if(pos>=Wl) check_max(Wl,pos,a[i]);
pos=query_geq(a[i]);
if(pos>=Wl) check_min(Wl,pos,a[i]);
}
print(qmod(ans));
return 0;
}