2024 年 11 月杂题
前言
模拟赛其实是在保护地球，因为少考一场模拟赛地球就爆炸了，同理晚自习训练是在保护银河系，因为少做一次晚自习训练银河系就毁灭了。
P4352 [CERC2015] Greenhouse Growth
题意
- 给定一个长度为 $n$ 的序列 $a$，现在有 $m$ 个操作，每个操作如下：
- 从左到右枚举 $i$，若 $a_i < a_{i-1}$ 则 $a_i\gets a_i+1$，否则不进行任何操作。
- 从右到左枚举 $i$，若 $a_i < a_{i+1}$ 则 $a_i\gets a_i+1$，否则不进行任何操作。
- 求 $m$ 个操作后的最终序列。
题解
首先容易想到相同数字的连续段会同时增加，所以我们可以把相同数字的连续段视为一个点。不难发现，这样的连续段会依次合并。注意到合并次数显然是 $O(m)$ 的，于是考虑能不能维护段的合并。
一段在操作一中会加一当且仅当其左侧相邻的段严格大于它，操作二同理，于是我们可以对每一段维护一个二元组 $(a,b)(a,b\in\begin{Bmatrix}0,1\end{Bmatrix})$。自己手玩一下就能发现，若相邻的两段 $u,v$ 合并，那么除去合并得到的新一段外，每一段的 $(a,b)$ 是不变的，我们发现，修改的信息量是 $O(1)$ 的，那么我们只要能快速找出合并点即可。
考虑相邻两段的间隔，容易发现这两段只有在某个操作对这两段的影响不同时才可能合并，那么我们不妨对每个分界点再维护一个二元组 $(l,r)$ 表示操作 $1/2$ 是否会让这两段的差减小，再加上一些前缀和之类的操作我们就能 $O(1)$ 计算合并时间了，并且根据刚才的结论，显然需要修改的 $(l,r)$ 也是 $O(1)$ 的。
注意到经过多次合并，某一段的变化量应该是一个分段函数，但是显然我们只需要保留当前时刻最后一段，因为无论是计算合并还是计算最终答案，必然都只和最后一段有关。
那么我们只需要每次找出最早合并的两段，将其合并后更新其他段即可，段的合并可以使用双向链表维护。“找出最早合并的两段”可以使用堆做到 $O((n+m)\log m)$ 或者直接存下每个时刻的合并点做到 $O(n+m)$，但因为要用 std::vector 之类的东西我感觉不见得会比带 $\log$ 的快。所以我写的带 $\log$ 的。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=3e5+5,inf=0x3f3f3f3f;
int n,m,a[N],b[N];
char str[N];
int cntn=0;
struct Node{
int pre,nxt,lf,rt,l,r,st,be;
}s[N];
int val[N];
priority_queue<pii,vector<pii>,greater<pii> > q;
int posl[N],posr[N];
int sumb[N];
int get(int u,int t){
int len=t-s[u].be,ca=sumb[t]-sumb[s[u].be];
return ca*s[u].lf+(len-ca)*s[u].rt;
}
int calc(int u,int t){
if(!u) return 0;
return s[u].st+get(u,t);
}
void work(int u){
int v=s[u].pre;
int l=s[u].lf^s[v].lf,r=s[u].rt^s[v].rt,hu=s[u].st,hv=s[v].st;
int t=max(s[u].be,s[v].be),len=m-t,ca=sumb[m]-sumb[t];
if(s[u].be<t){
hu+=get(u,t);
}
if(s[v].be<t){
hv+=get(v,t);
}
int sub=abs(hu-hv);
val[u]=inf;
if(l&&r){
if(sub<=len){
val[u]=sub+t;
q.push(mkp(val[u],u));
}
}else if(l){
if(sub<=ca){
val[u]=posl[sub+sumb[t]];
q.push(mkp(val[u],u));
}
}else if(r){
if(sub<=len-ca){
val[u]=posr[sub+t-sumb[t]];
q.push(mkp(val[u],u));
}
}
}
signed main(){
n=read();m=read();
forup(i,1,n){
a[i]=read();
}
scanf(" %s",str+1);
forup(i,1,m){
b[i]=(str[i]=='A');
sumb[i]=sumb[i-1]+b[i];
if(b[i]){
posl[sumb[i]]=i;
}else{
posr[i-sumb[i]]=i;
}
}
int lst=1;
forup(i,1,n){
if(a[i]!=a[lst]){
++cntn;
s[cntn].l=lst;s[cntn].r=i-1;
s[cntn].pre=cntn-1;
s[cntn].st=a[lst];
s[cntn].be=0;
s[cntn].lf=a[lst-1]>a[lst];
s[cntn-1].nxt=cntn;
s[cntn-1].rt=a[lst]>a[lst-1];
lst=i;
}
}
if(lst==1){
forup(i,1,n){
printf("%d ",a[i]);
}
return 0;
}
++cntn;
s[cntn].l=lst;s[cntn].r=n;
s[cntn].pre=cntn-1;
s[cntn].st=a[lst];
s[cntn].lf=a[lst-1]>a[lst];
s[cntn-1].nxt=cntn;
s[cntn-1].rt=a[lst]>a[lst-1];
s[0].pre=cntn;
forup(i,2,cntn){
work(i);
}
while(q.size()){
int u=q.top().se,vv=q.top().fi;q.pop();
if(val[u]!=vv) continue;
int v=s[u].pre,pp=s[v].pre,nn=s[u].nxt,t=val[u];
val[u]=inf;
int hp=calc(pp,t),hn=calc(nn,t),hh=calc(u,t);
s[v].r=s[u].r;
s[v].nxt=nn;s[nn].pre=v;
s[v].lf=hp>hh;s[v].rt=hn>hh;
s[v].st=hh;s[v].be=t;
if(pp){
s[pp].rt=hh>hp;s[pp].st=hp;s[pp].be=t;
work(v);
}
if(nn){
s[nn].lf=hh>hn;s[nn].st=hn;s[nn].be=t;
work(nn);
}
}
for(int i=s[0].nxt;i;i=s[i].nxt){
int val=calc(i,m);
forup(j,s[i].l,s[i].r){
printf("%d ",val);
}
}
puts("");
}
P4006 小 Y 和二叉树
题意
- 给定一棵二叉树，但是我们不知道哪个点是根，也不知道每个点的左右儿子分别是哪一个。
- 现在需要你定一个根，并且为每个点确定左右儿子，使得这棵树的中序遍历的字典序最小。
- $1\le n\le 10^6$，每个点的度数不超过 $3$。
题解
最小化字典序，很难不想到贪心。
考虑中序遍历第一个点 $k$ 肯定是确定的，即编号最小的度数小于等于 $2$ 的点。
于是考虑逐个往上确定父亲，对于每个点，若（除去上一个点到这个点的连边以外，下同）只连了一条边，那么要么这个点就是根，要么下一个点是这个点的父亲，取决于下一个点作为子树能得到的字典序最小值的第一个点是否小于它，同样地，若连了两条边，则要考虑哪个是父亲，显然是作为子树能得到的字典序最小值的第一个点更大的那个。
那么我们需要确定这个值，显然只需要以 $k$ 为根简单 DP 就行了。
复杂度 $O(n)$，常数略大。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e6+5;
int n;
vector<int> e[N];
int rt,dp[N];
void dfs(int x,int fa){
dp[x]=n+1;
int cnt=0;
for(auto i:e[x]){
if(i==fa) continue;
++cnt;
dfs(i,x);
dp[x]=min(dp[x],dp[i]);
}
if(cnt<2){
dp[x]=min(dp[x],x);
}
}
void print(int x,int fa){
vector<int> son;
for(auto i:e[x]){
if(i==fa) continue;
son.push_back(i);
}
if(son.empty()){
printf("%d ",x);
}else if(son.size()==2){
if(dp[son[0]]>dp[son[1]]) swap(son[0],son[1]);
print(son[0],x);
printf("%d ",x);
print(son[1],x);
}else{
if(dp[son[0]]>x){
printf("%d ",x);
print(son[0],x);
}else{
print(son[0],x);
printf("%d ",x);
}
}
}
void work(int x,int fa){
vector<int> son;
for(auto i:e[x]){
if(i==fa) continue;
son.push_back(i);
}
printf("%d ",x);
if(son.empty()){
return;
}else if(son.size()==1){
int v=son[0];
if(v>dp[v]){
print(v,x);
}else{
work(v,x);
}
}else{
if(dp[son[0]]>dp[son[1]]) swap(son[0],son[1]);
print(son[0],x);
work(son[1],x);
}
}
signed main(){
n=read();
forup(u,1,n){
int k=read();
if(k<=2&&!rt){
rt=u;
}
forup(j,1,k){
int v=read();
e[u].push_back(v);
}
}
dfs(rt,0);
work(rt,0);
}
模拟赛神秘题目【1031 B组】D 后缀数组
题意
- 我们称一个由数字构成的序列是字符串当且仅当不存在某个小于序列最大值的正整数没在序列中出现过。
- 给定长度为 $n$ 的后缀数组 $sa_i$，即 $\forall 1\le i < j\le n,s[i:n] < s[j:n]$，其中这个小于表示字典序比较，我们认为空字符小于一切字符。
- 求符合后缀数组 $sa$ 的字符串 $s$ 的数量。
- 但我们不直接给出 $a$，我们初始化 $a_i=i$，然后有以下操作共 $m$ 次：
- $0\;l\;r$：将 $sa$ 中区间 $[l,r]$ 平移到序列开头。
- $1\;l\;r$：将 $sa$ 中区间 $[l,r]$ 左右翻转。
- $1\le n\le 10^9,1\le m\le 10^5$
题解
我去，$1\le n\le 10^9$，这怎么做。
为方便叙述设 $rk$ 是 $sa$ 的逆排列，即任意 $i$ 满足 $rk_{sa_i}=sa_{rk_i}=i$，考虑固定 $sa$ 后怎么做。
显然 $s_{sa_i}\le s_{sa_{i+1}}$，并且不难想到 $s_{sa_{i+1}}$ 要么等于 $s_{sa_i}$，要么等于 $s_{sa_i}+1$，否则就不满足值域连续的条件了。容易发现 $s_{sa_i}= s_{sa_{i+1}}$ 仅当 $rk_{sa_i+1} < rk_{sa_{i+1}+1}$，而由于 $rk$ 是固定的，所以每个 $s_{sa_i+1}$ 有一种还是两种填法也是固定的，那么答案大致是 $2^p$ 的形式，其中 $p$ 是满足 $rk_{sa_i+1} < rk_{sa_{i+1}+1}$ 的位置数。
容易想到，满足 $|sa_i-sa_{i+1}|=1$ 的连续段除去首尾外全都满足条件，而两个操作都是容易用平衡树维护的，那么用平衡树维护连续段（每个结点维护一段，这时候又能体现 FHQ 的优越了，分裂结点的实现是自然的），每一段的首尾再额外考虑一下就行了。
代码较为难写，复杂度 $O(n\log n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=3e5+5,inf=0x3f3f3f3f,mod=998244353;
int n,m,p2[N];
mt19937 mr(time(0));
vector<int> pos;
vector<pii> cor;
int ans;
map<int,int> rk;
struct Treap{
struct Node{
int l,r,ls,rs,hv;
}tr[N];
int cntn,mark[N],sum[N],root;
vector<int> stk;
int New(int l,int r){
int nw;
if(stk.size()){
nw=stk.back();stk.pop_back();
}else{
nw=++cntn;
}
tr[nw]=Node{l,r,0,0,(int)mr()};
mark[nw]=0;
sum[nw]=abs(r-l)+1;
return nw;
}
void Modi(int id){
swap(tr[id].ls,tr[id].rs);
swap(tr[id].l,tr[id].r);
mark[id]^=1;
}
void PushDown(int id){
if(!mark[id]) return;
if(tr[id].ls) Modi(tr[id].ls);
if(tr[id].rs) Modi(tr[id].rs);
mark[id]=0;
}
void PushUp(int id){
sum[id]=abs(tr[id].r-tr[id].l)+1;
if(tr[id].ls) sum[id]+=sum[tr[id].ls];
if(tr[id].rs) sum[id]+=sum[tr[id].rs];
}
int Merge(int u,int v){
if(!u||!v) return u|v;
PushDown(u);PushDown(v);
if(tr[u].hv>tr[v].hv){
tr[u].rs=Merge(tr[u].rs,v);
PushUp(u);
return u;
}else{
tr[v].ls=Merge(u,tr[v].ls);
PushUp(v);
return v;
}
}
void Split(int id,int key,int &x,int &y){
if(!id){
x=y=0;
return;
}
PushDown(id);
int len=abs(tr[id].r-tr[id].l)+1;
if(tr[id].ls&&sum[tr[id].ls]>=key){
y=id;
Split(tr[id].ls,key,x,tr[y].ls);
PushUp(y);
}else if(sum[tr[id].ls]+len<=key){
x=id;
int p=sum[tr[id].ls]+len;
Split(tr[id].rs,key-p,tr[x].rs,y);
PushUp(x);
}else{
if(tr[id].ls) key-=sum[tr[id].ls];
int l=tr[id].l,r=tr[id].r,ls=tr[id].ls,rs=tr[id].rs;
stk.push_back(id);
if(l<r){
int mid=l+key-1;
if(l<=mid){
x=Merge(ls,New(l,mid));
}else{
x=ls;
}
if(mid<r){
y=Merge(New(mid+1,r),rs);
}else{
y=rs;
}
}else{
int mid=l-key+1;
if(l>=mid){
x=Merge(ls,New(l,mid));
}else{
x=ls;
}
if(mid>r){
y=Merge(New(mid-1,r),rs);
}else{
y=rs;
}
}
return;
}
}
void Insert(int l,int r){
root=Merge(root,New(l,r));
}
void Reverse(int l,int r){
int x,y,z;
Split(root,l-1,x,y);Split(y,r-l+1,y,z);
Modi(y);
root=Merge(Merge(x,y),z);
}
void Move(int l,int r){
int x,y,z;
Split(root,l-1,x,y);Split(y,r-l+1,y,z);
root=Merge(Merge(y,x),z);
}
void get(int id,int len){
PushDown(id);
if(tr[id].ls){
get(tr[id].ls,len);
len+=sum[tr[id].ls];
}
int l=tr[id].l,r=tr[id].r,plen=abs(r-l)+1;
if(plen>2){
ans=1ll*ans*p2[plen-2]%mod;
}
if(l!=r){
if(l<r){
cor.push_back(mkp(r-1,r));
}else{
cor.push_back(mkp(l,l-1));
}
}
rk[l]=len+1;
rk[r]=len+plen;
if(l+1<r){
rk[l+1]=len+2;
}else if(r+1<l){
rk[r+1]=len+plen-1;
}
pos.push_back(l);
pos.push_back(r);
if(tr[id].rs) get(tr[id].rs,len+plen);
}
}mt;
signed main(){
n=read();m=read();
ans=1;
p2[0]=1;
forup(i,1,m*3){
p2[i]=2ll*p2[i-1]%mod;
}
mt.Insert(1,n);
forup(i,1,m){
int op=read(),l=read(),r=read();
if(op==0){
mt.Move(l,r);
}else{
mt.Reverse(l,r);
}
}
rk[n+1]=0;
mt.get(mt.root,0);
for(int i=2;i<(int)pos.size();i+=2){
if(rk[pos[i-1]+1]<rk[pos[i]+1]){
ans=2ll*ans%mod;
}
}
for(auto i:cor){
if(rk[i.fi+1]<rk[i.se+1]){
ans=2ll*ans%mod;
}
}
printf("%d\n",ans);
}
P10764 [BalticOI 2024] Wall
题意
- 有一堵长度为 $n$ 的墙，点 $i$ 位置墙的高度 $h_i$ 可能是 $a_i$ 或者 $b_i$（二选一）。
- 下了一场水量充分多的雨，每个地方可能会积水，点 $i$ 的积水高度为 $H_i$。形式化地，$H_i$ 为最大的整数满足存在两整数 $l,r(1\le l\le i\le r\le n)$，使得 $h_l\ge H_i$ 并且 $h_r\ge H_i$，我们认为积水量为 $\sum_{i=1}^nH_i-h_i$。
- 求总共 $2^n$ 种修墙策略的积水量之和。
- $1\le n\le 5\times 10^5,1\le a_i,b_i\le 10^9,a_i\ne b_i$，答案对 $998244353$ 取模。
题解
一个显然的想法是把贡献拆成 $\sum H_i-\sum h_i$，容易发现 $\sum\sum h_i=\sum_{i=1}^n(a_i+b_i)2^{n-1}$，于是只考虑前者。
我想过一个矩阵维护 DP 的做法，设 $f_{i,j,0/1}$ 表示从左到右考虑前 $i$ 个，前缀最大值为 $j$ 的方案数/积水量之和 $g$ 表示从右到左，转移可以线段树维护矩阵做，然后枚举全局最大值，这样左侧就只和前缀有关，右侧只和后缀有关，于是后将前后缀合在一起，复杂度 $O(n\log n 2^3)$，但是太难写了没写完，而且很多实现细节没搞清楚。
考虑 $H_i$ 有多少种情况恰好等于 $p$，设这个数是 $cnt_{p,i}$，那么答案就是 $\sum_{p}p\sum_{i=1}^ncnt_{p,i}=\sum_{p}\sum_{i=1}^n\sum_{q\ge p}cnt_{q,i}$，即 $H_i$ 大于等于 $p$ 的情况数之和，设 $\sum_{q\ge p}cnt_{q,i}=ans_{p,i}$。
关于求 $ans_p$，不难想到一个简单容斥，设 $s_i=[a_i < p]+[b_i < p]$。那么 $ans_{p,i}=2^n-2^{i-1}\prod_{j=i}^ns_j-2^{n-i}\prod_{j=1}^is_j+\prod_{j=1}^ns_j$，即总的减去某一边不合法的加上两边都不合法的。
考虑枚举 $p$，容易发现随着 $p$ 的改变，$2^n+\prod_{j=1}^ns_j$ 是容易维护的，注意到每个 $s_i$ 的修改对 $2^{i-1}\prod_{j=i}^ns_j$ 和 $2^{n-i}\prod_{j=1}^is_j$ 的影响是一段前缀/后缀，那么可以线段树维护。
然后我们发现从小到大枚举是不可维护的，于是考虑从大到小枚举。
于是做完了，复杂度 $O(n\log n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=5e5+5,inf=0x3f3f3f3f,mod=1e9+7,inv2=5e8+4;
int n,a[N],b[N],s[N],p2[N];
vector<int> lsh;
vector<int> pos[N*2];
int sz,sum1,sum2;
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
int sum[N<<2],mark[N<<2];
void PushUp(int id){
sum[id]=(sum[id<<1]+sum[id<<1|1])%mod;
}
void Modi(int id,int X){
mark[id]=1ll*mark[id]*X%mod;
sum[id]=1ll*sum[id]*X%mod;
}
void PushDown(int id){
Modi(id<<1,mark[id]);
Modi(id<<1|1,mark[id]);
mark[id]=1;
}
void Build(int l=1,int r=n,int id=1){
mark[id]=1;
if(l==r){
sum[id]=p2[n];
return;
}
Build(lson);Build(rson);
PushUp(id);
}
void Update(int L,int R,int X,int l=1,int r=n,int id=1){
if(L<=l&&r<=R){
Modi(id,X);
return;
}
if(mark[id]!=1) PushDown(id);
if(L<=mid) Update(L,R,X,lson);
if(mid< R) Update(L,R,X,rson);
PushUp(id);
}
}t1,t2;
int ans=0;
signed main(){
n=read();
p2[0]=1;
forup(i,1,n) p2[i]=2ll*p2[i-1]%mod;
forup(i,1,n){
a[i]=read();
lsh.push_back(a[i]);
}
forup(i,1,n){
b[i]=read();
lsh.push_back(b[i]);
if(a[i]>b[i]) swap(a[i],b[i]);
}
sort(lsh.begin(),lsh.end());
lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
sz=lsh.size();
forup(i,1,n){
int pa=lower_bound(lsh.begin(),lsh.end(),a[i])-lsh.begin(),pb=lower_bound(lsh.begin(),lsh.end(),b[i])-lsh.begin();
pos[pa].push_back(i);pos[pb].push_back(i);
s[i]=2;
}
sum1=sum2=p2[n];
t1.Build();t2.Build();
fordown(i,sz-1,0){
for(auto j:pos[i]){
--s[j];
if(s[j]==1){
sum2=1ll*sum2*inv2%mod;
t1.Update(1,j,inv2);t2.Update(j,n,inv2);
}else{
sum2=0;
t1.Update(1,j,0);t2.Update(j,n,0);
}
}
int del=(t1.sum[1]+t2.sum[1])%mod,pval=1ll*(sum1+sum2)*n%mod;
int val=(pval+mod-del)%mod,cnt=(i?lsh[i]-lsh[i-1]:lsh[i]);
(ans+=1ll*val*cnt%mod)%=mod;
}
forup(i,1,n){
ans=(ans+mod-1ll*(a[i]+b[i])*p2[n-1]%mod)%mod;
}
printf("%d\n",ans);
}
[ABC155F] Perils in Parallel
题意
- 有一条路，上面有 $n$ 盏路灯。第 $i$ 盏路灯在 $a_i$ 位置，现在状态是 $b_i$（$b=1/0$ 表示明灭）。
- 有 $m$ 个开关，每个开关可以将一个区间 $[l_i,r_i]$ 内所有路灯的状态反转。
- 问是否能把所有路灯灭掉，若能，输出方案（将要操作的开关的编号从小到大输出），否则输出
-1。 - $1\le n\le 10^5,1\le m\le 2\times 10^5,1\le a_i,l_i,r_i\le 10^9,l_i\le r_i$
题解
首先显然可以不管 $a_i$，将灯看作连续的序列，然后每个开关控制一个区间的灯。
显然区间修是不好做的，不妨差分一下（异或差分，设差分数组为 $c_i$）变成两个单点修，容易想到将每个修改 $[l,r)$（这里的 $l,r$ 指的是从左到右的路灯编号而非坐标，注意这里是左闭右开）视作一条无向边 $(l,r)$，显然每个连通块是独立的。
注意到会有 $r > n$ 的情况，此时就相当于点 $l$ 可以单点修改，称这样的点为特殊点。
容易发现有解当且仅当每个连通块都有偶数个 $c_i=1$（必要性显然，充分性考虑构造，一个想法是两两配对随便找条连接两点的路径将其上的边全部操作一次，具体构造考虑找棵生成树用树上路径），若有奇数个就尝试使用特殊点调整。
然后做完了，复杂度 $O(n)$，但我写的比较丑，用了并查集。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e5+5,M=2e5+5,inf=0x3f3f3f3f;
int n,m,co[N];
pii s[N];
vector<int> seq;
vector<int> ans;
vector<pii> e[N];
int a[N];
int fa[N];
int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
bool merge(int u,int v){
u=getfa(u);v=getfa(v);
if(u==v) return false;
fa[u]=v;
return true;
}
int cnt,pp,pf[N],dp[N];
void dfs1(int x,int fa){
cnt+=a[x];
if(!pp&&co[x]) pp=x;
for(auto i:e[x]){
int v=i.fi;
if(v==fa) continue;
pf[v]=i.se;
dfs1(v,x);
}
}
void dfs2(int x,int fa){
dp[x]=a[x];
for(auto i:e[x]){
int v=i.fi;
if(v==fa) continue;
dfs2(v,x);
dp[x]^=dp[v];
}
if(dp[x]) ans.push_back(pf[x]);
}
void work(int rt){
pp=cnt=0;
dfs1(rt,0);
if(cnt&1){
if(pp){
a[pp]^=1;
ans.push_back(co[pp]);
}else{
puts("-1");
exit(0);
}
}
dfs2(rt,0);
}
signed main(){
n=read();m=read();
forup(i,1,n){
s[i].fi=read();s[i].se=read();
seq.push_back(s[i].fi);
fa[i]=i;
}
sort(seq.begin(),seq.end());
sort(s+1,s+n+1);
forup(i,1,n){
a[i]=s[i].se;
}
fordown(i,n,1){
a[i]^=a[i-1];
}
forup(i,1,n){
msg("%d ",a[i]);
}msg("|\n");
forup(i,1,m){
int l=read(),r=read();
l=lower_bound(seq.begin(),seq.end(),l)-seq.begin()+1;
r=upper_bound(seq.begin(),seq.end(),r)-seq.begin()+1;
msg("%d %d|\n",l,r);
if(l>n||l==r) continue;
if(r>n){
co[l]=i;
}else{
if(merge(l,r)){
e[l].push_back(mkp(r,i));
e[r].push_back(mkp(l,i));
}
}
}
forup(i,1,n){
if(fa[i]==i){
work(i);
}
}
printf("%d\n",(int)ans.size());
sort(ans.begin(),ans.end());
for(auto i:ans){
printf("%d ",i);
}puts("");
}
[ABC163F] path pass i
题意
- 有一棵 $n$ 个点的树，每个点有颜色 $c_i$。
- 对于每个颜色 $1\le i\le n$，求出包含至少一个颜色为 $i$ 的点的简单路径数。
- $1\le n\le 2\times 10^5,1\le c_i\le n$
题解
简单题。
容易想到容斥，一条简单路径没有包含颜色 $i$ 当且仅当删掉所有颜色 $i$ 的点形成若干连通块，这条简单路径两端点在同一连通块内。称这样的连通块为“$i$ 的关键连通块”
于是对每个点的所有连通块计算大小即可。首先，全树的根节点是所有颜色关键连通块的根，此外每个点是其父亲颜色连通块的根，每个关键连通块的大小是容易计算的，而显然关键连通块总数是 $O(n)$ 的。
于是复杂度 $O(n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=2e5+5;
i64 n,c[N];
vector<i64> e[N];
vector<i64> pos[N];
i64 sz[N];
void dfs1(i64 x,i64 fa){
sz[x]=1;
if(fa){
pos[c[fa]].push_back(x);
}
for(auto i:e[x]){
if(i==fa) continue;
dfs1(i,x);
sz[x]+=sz[i];
}
}
i64 ans,cc,cnt[N],crt[N];
int pre[N];
void dfs2(i64 x,i64 fa){
if(pre[c[x]]!=1){
cnt[pre[c[x]]]-=sz[x];
}else{
crt[c[x]]-=sz[x];
}
int sv=pre[c[x]];
for(auto i:e[x]){
if(i==fa) continue;
pre[c[x]]=i;
dfs2(i,x);
}
pre[c[x]]=sv;
}
signed main(){
n=read();
forup(i,1,n){
c[i]=read();
}
forup(i,1,n-1){
i64 u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
dfs1(1,0);
forup(i,1,n){
cnt[i]=sz[i];
pre[i]=1;
crt[i]=n;
}
dfs2(1,0);
forup(i,1,n){
ans=n*(n+1)/2;
cnt[1]=n;
cc=i;
for(auto j:pos[i]){
ans-=cnt[j]*(cnt[j]+1)/2;
}
ans-=crt[i]*(crt[i]+1)/2;
printf("%lld\n",ans);
}
}
P9039 [PA2021] Drzewo czerwono-czarne
题意
- 给定一棵 $n$ 个点的树，每个点是黑色或者白色。
- 你可以进行以下操作若干次：
- 选择一条边，将其一端点改成另一端点的颜色。
- 给定两个序列 $a_i,b_i$，表示每个点的起始颜色和终止颜色，求能否通过操作使得每个点从起始颜色变为终止颜色。
- $1\le n\le 10^5$，带多测，$\sum n\le 10^6$
题解
我是猜结论高手。
首先如果图是一条链是好做的，（假设链是 $1,2,3,\dots,n$）有解当且仅当将相邻的相同颜色合为一个点后得到序列 $a',b'$，$b'$ 序列是 $a'$ 序列的子序列。因为元素只有 $0/1$ 就是说 $b'$ 的序列长度小于 $a'$ 或者两序列完全相同。
如果不是链呢？我们大胆猜测，不是链的必定有解，因为我们可以看作有一个分叉的链，如果需要将链上某个连续段断开那么挪到分叉点即可。
显然是不对的，注意到一个反例：
那么我们再限制一下 $b$ 至少有一个连通块大小大于 $1$ 即可。
然后就随便做了复杂度 $O(n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)){if(c=='-')f=-1;}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e5+5,inf=0x3f3f3f3f;
int n,a[N],b[N],pa[2],pb[2];
char str[N];
struct edge{
int v,nxt;
}e[N<<1];
int head[N],cnte,deg[N];
void adde(int u,int v){
e[++cnte]=edge{v,head[u]};head[u]=cnte;
e[++cnte]=edge{u,head[v]};head[v]=cnte;
++deg[u];++deg[v];
}
bool chk0(){
forup(u,1,n){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(b[v]==b[u]) return true;
}
}
return false;
}
bool chk(){
forup(u,1,n){
if(deg[u]>2) return true;
}
return false;
}
int prea,cnta,preb,cntb;
int cnt;
void dfs(int x,int fa){
if(!cnta||prea!=a[x]){prea=a[x];++cnta;}
if(!cntb||preb!=b[x]){preb=b[x];++cntb;}
if(fa==0) cnt=0;
++cnt;
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
if(v==fa) continue;
dfs(v,x);
}
}
void solve(){
n=read();
cnte=0;
pa[0]=pb[0]=pa[1]=pb[1]=0;
forup(i,1,n){
head[i]=deg[i]=0;
}
scanf(" %s",str+1);
forup(i,1,n){
a[i]=(str[i]=='1');
pa[a[i]]=1;
}
scanf(" %s",str+1);
bool flag=true;
forup(i,1,n){
b[i]=(str[i]=='1');
pb[b[i]]=1;
if(a[i]!=b[i]) flag=false;
}
forup(i,1,n-1){
int u=read(),v=read();
adde(u,v);
}
if(flag){
puts("TAK");
return;
}
if(!chk0()){
puts("NIE");
return;
}
if((pb[0]&&!pa[0])||(pb[1]&&!pa[1])){
puts("NIE");
return;
}
if(chk()){
puts("TAK");
return;
}
prea=preb=0;
cnta=cntb=0;
forup(i,1,n){
if(deg[i]==1){
dfs(i,0);
break;
}
}
if(cnta>cntb||(cnta==cntb&&prea==preb)){
puts("TAK");
}else{
puts("NIE");
}
}
signed main(){
int t=read();
while(t--){
solve();
}
}
黑暗爆炸-4770 图样
题意
- 有一张 $n$ 个点的完全图，点有点权 $a_i$，边 $(u,v)$ 的边权为 $a_u\oplus a_v$。其中 $\oplus$ 表示按位异或。
- 现在每个点的点权在 $[0,2^m)$ 中随机取值，求最小生成树的期望边权和。
- $1\le n\le 50,0\le m\le 8$，答案对 $258280327$ 取模（这是质数）
题解
神秘。
考虑固定点权怎么做，从小到大枚举位数 $i$，显然任意时刻更高位全部相同的点应该连成了连通块，每一层都只会将所有更高位全部相同，但这一层不同的连通块二元组两两合并。
容易想到设 $dp_{i,x}$ 表示考虑到前 $i$ 层，所有合并出一个大小为 $x$ 的连通块的方案的代价之和。转移就枚举这一位全为 $1$ 的连通块大小，然后合并。
考虑这一次合并的代价，容易发现除去必定在 $[2^{i-1},2^i)$ 之间我们啥都不知道，但是因为 DP 概括了所有方案，那么我们只要求出所有方案的代价和即可，转移形如：
$$ dp_{i,j}=2dp_{i-1,j}+\sum_{p=1}^{(j-1)(i-1)}\binom{j}{p}(dp_{i-1,p}2^{j-p}+dp_{i-1,j-p}2^{p(i-1)}+g(i-1,p,j-p)+2^{i-1}\times 2^{j(i-1)}) $$
其中 $g(i,l,r)$ 表示所有将两大小分别为 $l,r$，并且大于 $i$ 的二进制位全都相同（就是不考虑大于 $i$ 的位）的连通块合并的情况的贡献和。
考虑怎么算 $g$，显然不好算，考虑设 $f(i,l,r,v)$ 表示只考虑前 $i$ 位，将两连通块合并的代价为 $v$ 的方案数。$f$ 是能 DP 求出的，具体来说，枚举左右连通块这一位 $1$ 的个数，显然除去一边全 $0$ 另一边全 $1$ 以外，必定是两 $0$ 合并或者两 $1$ 合并，实现细节自己考虑。
直接算复杂度是 $O(n^4m2^m)$ 的，但是注意到本质不同询问只有 $400$ 种，打表即可。
参考打表代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=55,M=2e4+5,mod=258280327,inv2=(mod+1)/2;
int n=50,m=8,f[9][N][N][1<<8|5],suf[9][N][N][1<<8|5],g[9][N][N],dp[9][N];
int p2[M],ip2[M],binom[N][N];
signed main(){
p2[0]=ip2[0]=1;
forup(i,1,2e4){
p2[i]=2ll*p2[i-1]%mod;
ip2[i]=1ll*ip2[i-1]*inv2%mod;
}
forup(i,0,n){
binom[i][0]=1;
forup(j,1,i){
binom[i][j]=(binom[i-1][j]+binom[i-1][j-1])%mod;
}
}
forup(i,1,n){
forup(j,1,n-i){
f[0][i][j][0]=suf[0][i][j][0]=1;
g[0][i][j]=0;
}
}
forup(i,1,m){
forup(l,1,n){
forup(r,1,n-l){
forup(v,0,(1<<(i-1))-1){
forup(p,1,l-1){
forup(q,1,r-1){
int val=1ll*binom[l][p]*binom[r][q]%mod;
(f[i][l][r][v]+=1ll*f[i-1][p][q][v]*suf[i-1][l-p][r-q][v]%mod*val%mod)%=mod;
(f[i][l][r][v]+=1ll*f[i-1][l-p][r-q][v]*suf[i-1][p][q][v+1]%mod*val%mod)%=mod;
}
}
forup(q,1,r){
(f[i][l][r][v]+=2ll*f[i-1][l][q][v]*binom[r][q]%mod*p2[(i-1)*(r-q)]%mod)%=mod;
}
forup(p,1,l-1){
(f[i][l][r][v]+=2ll*f[i-1][p][r][v]*binom[l][p]%mod*p2[(i-1)*(l-p)]%mod)%=mod;
}
(f[i][l][r][v+(1<<(i-1))]+=2ll*f[i-1][l][r][v]%mod)%=mod;
}
fordown(v,(1<<i)-1,0){
suf[i][l][r][v]=(suf[i][l][r][v+1]+f[i][l][r][v])%mod;
(g[i][l][r]+=1ll*f[i][l][r][v]*v%mod)%=mod;
}
}
}
msg("%d|\n",i);
}
forup(v,0,3){
msg("%d ",f[2][1][2][v]);
}msg("|\n");
forup(i,1,n){
dp[0][i]=0;
}
forup(i,1,m){
forup(j,1,n){
dp[i][j]=(dp[i-1][j]+dp[i-1][j])%mod;
forup(p,1,j-1){
int val=(1ll*p2[(j-p)*(i-1)]*dp[i-1][p]%mod+1ll*p2[p*(i-1)]*dp[i-1][j-p]%mod)%mod;
(val+=g[i-1][p][j-p]+1ll*p2[j*(i-1)]*p2[i-1]%mod)%=mod;
(dp[i][j]+=1ll*binom[j][p]*val%mod)%=mod;
}
}
}
msg("%lld %lld||\n",1ll*dp[2][2]*ip2[4]%mod,1ll*dp[3][10]*ip2[30]%mod);
forup(i,0,m){
msg("{");
forup(j,0,n){
msg("%lld",1ll*dp[i][j]*ip2[i*j]%mod);
// msg("%d",dp[i][j]);
if(j<n)msg(",");
}
msg("},\n");
}
}
QOJ-1870 Command and Conquer: Red Alert 2
题意
- 有一个三维坐标系，一个人从三个维度坐标都充分小的点出发，要到达三个维度坐标都充分大的点，每一步只能让三个坐标其中一个 $+1$。
- 坐标系中有 $n$ 个敌人，第 $i$ 个敌人的坐标是 $(x_i,y_i,z_i)$，这个人有一杆猎枪，子弹充分多，射程为 $k$，从坐标 $(x_0,y_0,z_0)$ 能击杀坐标 $(x_1,y_1,z_1)$ 的敌人当且仅当 $\max(|x_0-x_1|,|y_0-y_1|,|z_0-z_1|)\le k$。
- 求要击杀所有敌人的最小射程 $k$。
- $1\le n\le 5\times 10^5,0\le x_i,y_i,z_i\le 10^9$ 带多测，$\sum n\le 2\times 10^6$
题解
神秘，全 CW 竟无一人场切。
考虑攻击范围是个正方体，我们不妨认为这个人攻击距离是 $2k$，但是只能往正方向打。设这样得到的答案是 $K$，那么实际答案就是 $\left\lceil\frac{K}{2}\right\rceil$。
容易发现啊，如果我们走到了某个点 $(x_1,y_1,z_1)$，那么任意满足 $x' < x\lor y' < y\lor z' < z$ 的点 $(x',y',z')$，都必须被干掉，不然就永远干不掉了。设 $x$ 最小的点为 $A(x_a,y_a,z_a)$，$y$ 最小的为 $B(x_b,y_b,z_b)$，$z$ 最小的为 $C(x_c,y_c,z_c)$，那么我们必须在走到 $(x_a,y_b,z_c)$ 之前干掉 $A,B,C$ 其中一个。不难想到恰好从 $(x_a,y_b,z_c)$ 开枪是不劣的（在必须干掉三者前能得到的最大坐标），这时候我们贪心地把距离最小的击杀，更新 $K$，然后将这个点删掉。
这个贪心显然是正确的，复杂度 $O(n\log n)$，瓶颈在排序。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=5e5+5,inf=0x3f3f3f3f;
int n;
int a[N],b[N],c[N],vis[N];
int sa[N],sb[N],sc[N];
int pa,pb,pc;
void solve(){
n=read();
forup(i,1,n){
a[i]=read();b[i]=read();c[i]=read();
sa[i]=sb[i]=sc[i]=i;
vis[i]=0;
}
sort(sa+1,sa+n+1,[&](int l,int r){return a[l]<a[r];});
sort(sb+1,sb+n+1,[&](int l,int r){return b[l]<b[r];});
sort(sc+1,sc+n+1,[&](int l,int r){return c[l]<c[r];});
int ans=0;
pa=pb=pc=1;
forup(i,1,n){
while(vis[sa[pa]]) ++pa;
while(vis[sb[pb]]) ++pb;
while(vis[sc[pc]]) ++pc;
int na=sa[pa],nb=sb[pb],nc=sc[pc];
int va=max(abs(b[nb]-b[na]),abs(c[nc]-c[na]));
int vb=max(abs(a[na]-a[nb]),abs(c[nc]-c[nb]));
int vc=max(abs(a[na]-a[nc]),abs(b[nb]-b[nc]));
if(va<=vb&&va<=vc){
ans=max(ans,va);
vis[na]=1;
}else if(vb<=vc){
ans=max(ans,vb);
vis[nb]=1;
}else{
ans=max(ans,vc);
vis[nc]=1;
}
}
printf("%d\n",(ans+1)/2);
}
signed main(){
int t=read();
while(t--){
solve();
}
}
QOJ-2549 King's Palace
题意
- 有 $n$ 个点，每个点可能是红色，绿色，蓝色。
- 有 $m$ 个限制，每个限制形如 $(u,x,v,y)$，表示点 $u$ 的颜色不是 $x$ 或者点 $v$ 的颜色不是 $y$（就是说 $u$ 的颜色是 $x$ 和 $v$ 的颜色是 $y$ 不能同时成立）。
- 求合法染色数。
- $1\le n\le 22,0\le m\le 9\binom{n}{2}$。
题解
也很厉害吧，赛时一车人爆搜过了。
首先爆搜剪枝可过（而且是已知做法里面最快的）。
然后有个折半搜索，按 $1:2$ 分成两半，设小的那半大小为 $p$，用一个 $2^{3p}$ 二进制数表示这一半每个点可以是哪种颜色，复杂度大致是 $O(p2^{3p}+3^{n-p}+3^{p})$，跑的比下面的这个做法快，但是需要玄学剪枝，我不是很喜欢。
用 $0,1,2$ 表示三种颜色。
考虑先确定哪些点是 $2$，可以 $2^n$ 枚举，那么我们就能确定一部分点是 $0$ 还是 $1$ 了，剩下没确定的点就和这些无关了，设 $f(S)$ 表示只考虑 $S$ 中的点，只能填 $0,1$ 的方案数。
$f(S)$ 求法也类似，先枚举一个点，将有关的找出来，剩下 $S'$，从 $S'$ 转移。
复杂度 $O(2^n(n+m))$，跑的比较慢，但是时限 6s。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=25;
int n,m;
struct edge{
int v,w,nxt;
}e[N*N*20];
int head[N][3],cnte;
void adde(int u,int p,int v,int w){
e[++cnte]=edge{v,w,head[u][p]};head[u][p]=cnte;
}
i64 f[1<<22];
int val[N];
int chk(int msk,int p){
int u=__builtin_ctz(msk)+1;
val[u]=p;
queue<int> q;q.push(u);
int res=msk;
res^=(1<<(u-1));
while(q.size()){
int u=q.front();q.pop();
for(int i=head[u][val[u]];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(!(msk&(1<<(v-1)))||w==2) continue;
if(res&(1<<(v-1))){
val[v]=w^1;
q.push(v);
res^=(1<<(v-1));
}else{
if(val[v]==w){
return -1;
}
}
}
}
return res;
}
i64 ans;
void work(int msk){
mem(val,-1);
queue<int> q;
int nxt=(1<<n)-1;
forup(i,1,n){
if(msk&(1<<(i-1))){
q.push(i);
val[i]=2;
}
}
while(q.size()){
int u=q.front();q.pop();
nxt^=(1<<(u-1));
for(int i=head[u][val[u]];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(val[v]==w) return;
if(~val[v]||w==2) continue;
w^=1;
val[v]=w;
q.push(v);
}
}
ans+=f[nxt];
}
signed main(){
n=read();m=read();
forup(i,1,m){
int u,x,v,y;char c;
u=read();scanf(" %1c",&c);
x=(c=='R'?0:c=='G'?1:2);
v=read();scanf(" %1c",&c);
y=(c=='R'?0:c=='G'?1:2);
adde(u,x,v,y);
adde(v,y,u,x);
}
f[0]=1;
forup(i,1,(1<<n)-1){
if(__builtin_popcount(i)==1){
f[i]=2;
continue;
}
int res=chk(i,0);
if(res!=-1) f[i]+=f[res];
res=chk(i,1);
if(res!=-1) f[i]+=f[res];
}
forup(msk,0,(1<<n)-1){
work(msk);
}
printf("%lld\n",ans);
}
QOJ-7509 01tree
题意
- 有一棵 $n$ 个点的树，每个点是黑色或者白色。
- 你可以进行以下操作任意次：
- 选择一条边 $(u,v)$ 满足 $u,v$ 颜色相同，将两点的颜色反转。
- 初始每个点 $i$ 的颜色分别 $a_i$，求至少多少次操作才能把颜色序列变成 $b_i$，无解则为 $0$。
- 但是 $a,b$ 中都有一些点没确定，即 $a,b$ 均是由
0,1,?构成的字符串，其中?可以随意替换成0,1，求所有替换方案的贡献和。 - $1\le n\le 10^5$，带多测，$\sum n\le 10^5$，答案对 $10^9+7$ 取模。
题解
神秘题。但是赛时因为数据问题一车人 $30\to 50$ 或者 $50\to 100$。
不妨设 $1$ 为根。
先考虑没有 ? 的情况。有神秘构造（或许是套路？）设 $s_i=a_i\oplus (dpt_i\bmod 2)$（其中 $dpt_i$ 表示点 $i$ 的深度，$\oplus$ 表示按位异或），$t_i=b_i\oplus(dpt_i\bmod 2)$，那么一次操作就是选择一条 $s_u\ne s_v$ 的边 $(u,v)$，将两点颜色互换。
显然地，$s_i$ 和 $a_i$ 是一一对应的，那么我们只需要关注 $s,t$ 了。不妨认为 $s_i=1$ 的点上有一个黑色棋子，$t_i=1$ 的点上有一个白色棋子，那么我们的目的就是将黑白棋子一一配对，设 $z_i$ 表示点 $i$ 子树中黑色棋子个数减去白色棋子个数，容易发现有解当且仅当 $z_1=0$，并且最小代价为 $\sum |z_i|$（考虑有多少个棋子会经过这个点，可以认为黑白棋子都只会向上移动，在 $\mathrm{lca}$ 处相遇）。
接下来处理 ?，首先容易发现 $a$ 中的 ? 在 $s$ 中也是 $0,1$ 任选的，$t$ 里面的也是一样，于是考虑推一下组合数。
设 $A$ 表示 $s$ 中的 ? 数量，$B$ 表示 $t$ 中的 ? 数量，已知部分的权值和为 $C$（$s_i=1$ 提供 $+1$ 权值，$t_i=1$ 提供 $-1$ 权值）。点 $i$ 子树中 $s$ 的 ? 数量为 $x$，$t$ 的 ? 数量为 $y$，点 $i$ 子树已知部分的权值和为 $z$，则点 $i$ 的贡献为：
$$ \sum_{i=0}^x\sum_{j=0}^y\sum_{k=0}^{A-x}\sum_{l=0}^{B-y}[C+i-j+k-l=0]|z+i-j|\binom{x}{i}\binom{y}{j}\binom{A-x}{k}\binom{B-y}{l} $$
即枚举子树内 $s,t$ 分别有多少个 ? 变成了 $1$，后面那坨组合数就是对应个数的方案数。我去，这么一大坨怎么做。
注意到我们只关注 $i-j$ 和 $k-l$，设 $p=i-j,q=k-l$，注意到 $\sum_{i=p}^x\binom{x}{i}\binom{y}{i-p}=\sum_{i=p}^x\binom{x}{x-i}\binom{y}{i-p}=\binom{x+y}{x-p}$（考虑组合意义），同理有 $\sum_{k=q}^{A-x}\binom{A-x}{k}\binom{B-y}{k-q}=\binom{A+B-x-y}{A-x-q}$。于是上式等于：
$$ \begin{aligned} &\sum_{p}\sum_{q}[C+p+q=0]|z+p|\binom{x+y}{x-p}\binom{A+B-x-y}{A-x-q}\\ =&\sum_{p}|z+p|\binom{x+y}{x-p}\binom{A+B-x-y}{A-x+C+p} \end{aligned} $$
然后就能 $O(n^2)$ 计算了，注意枚举的上下界，不要搞出没有意义的组合数。
然后我们只看式子了，为了让式子好看一点，不妨令 $p:=x-p$，则上式等于 $\sum_{p}|z+x-p|\binom{x+y}{p}\binom{A+B-x-y}{A+C-p}$，设 $f(x,y)=\sum_{i}|y-i|\binom{x}{i}\binom{X-x}{Y-i}$，其中 $X=A+B,Y=A+C$，那么上式就是 $f(x+y,x+z)$，于是我们只关注 $f(x,y)$ 如何计算了。
接下来的思路非常神奇，注意到重链剖分后，对于一条重链，链尾到链顶的过程中 $x,y$ 的变化量和链顶的子树大小是一个级别的（分别乘个至多两倍的常数），那么假如我们能从 $f(x,y)$ 低复杂度（比如 $O(1)$）推到 $f(x,y+1),f(x,y-1)$ 和 $f(x+1,y)$ 就能 $O(n\log n)$ 计算了。
那么怎么做呢？先把绝对值拆了，于是 $f(x,y)=\left(\sum_i\binom{x}{i}\binom{X-x}{Y-i}(i-y)\right)+2\left(\sum_{i\le y}\binom{x}{i}\binom{X-x}{Y-i}(y-i)\right)$，注意到：
$$ \begin{aligned} \sum_i\binom{x}{i}\binom{X-x}{Y-i}(i-y)&=\sum_i\binom{x}{i}\binom{X-x}{Y-i}i-y\sum_i\binom{x}{i}\binom{X-x}{Y-i}\\ &=-y\binom{X}{Y}+\sum_{i}\frac{x!}{i!(x-i)!}\binom{X-x}{Y-i}i\\ &=-y\binom{X}{Y}+\sum_{i}x\frac{(x-1)!}{(i-1)!((x-1)-(i-1))!}\binom{X-x}{Y-i}\\ &=-y\binom{X}{Y}+x\sum_{i}\binom{x-1}{i-1}\binom{X-x}{Y-i}\\ &=-y\binom{X}{Y}+x\sum_{i}\binom{x-1}{i}\binom{X-x}{Y-1-i}\\ &=-y\binom{X}{Y}+x\binom{X-1}{Y-1}\\ \end{aligned} $$
倒数第二步就是 $i:=i-1$。
那么就能 $O(1)$ 计算了。考虑 $\sum_{i\le y}\binom{x}{i}\binom{X-x}{Y-i}(y-i)$，就是 $y\sum_{i\le y}\binom{x}{i}\binom{X-x}{Y-i}-\sum_{i\le y}\binom{x}{i}\binom{X-x}{Y-i}i$，于是只考虑 $\sum_{i\le y}\binom{x}{i}\binom{X-x}{Y-i}i$，把 $\binom{x}{i}$ 和上面类似地，可以发现这个等于 $x\sum_{i\le y}\binom{x-1}{i-1}\binom{X-x}{Y-i}=x\sum_{i\le y-1}\binom{x-1}{i}\binom{X-x}{Y-(i+1)}$。
于是我们只需要关注 $g(x,y)=\sum_{i\le y}\binom{x}{i}\binom{X-x}{Y-i}$（和 $g'(x,y)=\sum_{i\le y}\binom{x}{i}\binom{P-x}{Q-i}$，其中 $P=X-1,Q=Y-1$，上面的 $x\sum_{i\le y-1}\binom{x-1}{i}\binom{X-x}{Y-(i+1)}$ 就等于 $x\cdot g'(x-1,y-1)$）。
于是考虑怎么从 $g(x,y)$ 推到 $g(x+1,y)$ 和 $g(x,y\pm 1)$。
从 $g(x,y)$ 推到 $g(x,y+1)$ 是容易的，加上 $\binom{x}{y+1}\binom{X-x}{Y-(y+1)}$ 即可。考虑如何从 $g(x,y)$ 推到 $g(x+1,y)$。有组合意义：$g(x,y)$ 相当于从 $X$ 个球中选 $Y$ 个染色，前 $x$ 个球中至多 $y$ 个被染了。于是 $g(x,y)-g(x+1,y)$ 就是前 $x$ 个球被染了 $y$ 个，且第 $x+1$ 个球必须被染的方案数（因为某个方案不属于后者仅当前 $x+1$ 个球中有超过 $y$ 个，又属于前者就说明第 $x+1$ 个就是被染的），那么就是 $\binom{x}{y}\binom{X-x-1}{Y-y-1}$。这个在一堆边界情况需要特判。
$g'$ 也是类似的，然后我们能得到：
$$ f(x,y)=-y\binom{X}{Y}+x\binom{X-1}{Y-1}+2y\cdot g(x,y)-2x\cdot g'(x-1,y-1) $$
于是就能做了，复杂度 $O(n\log n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=5e5+5,mod=1e9+7;
int ksm(int a,int b){
int c=1;
while(b){
if(b&1) c=1ll*a*c%mod;
a=1ll*a*a%mod;
b>>=1;
}
return c;
}
int n,s[N],t[N];
vector<int> e[N];
char str[N];
int A,B,C,dpt[N];
int z[N],x[N],y[N];
int fact[N<<1],finv[N<<1];
void init(int n){
fact[0]=1;
forup(i,1,n) fact[i]=1ll*fact[i-1]*i%mod;
finv[n]=ksm(fact[n],mod-2);
fordown(i,n-1,0) finv[i]=1ll*finv[i+1]*(i+1)%mod;
}
int binom(int n,int m){
if(n<m||n<0||m<0) return 0;
return 1ll*fact[n]*finv[m]%mod*finv[n-m]%mod;
}
int sz[N],son[N],hig[N],dfn[N],Tm,ff[N];
void dfs(int u,int fa){
dpt[u]=dpt[fa]+1;
ff[u]=fa;sz[u]=1;
if(s[u]!=2){
s[u]^=(dpt[u]&1);
z[u]+=s[u];
}else{
++x[u];
}
if(t[u]!=2){
t[u]^=(dpt[u]&1);
z[u]-=t[u];
}else{
++y[u];
}
for(auto i:e[u]){
if(i==fa) continue;
dfs(i,u);
sz[u]+=sz[i];
if(!son[u]||sz[son[u]]<sz[i]) son[u]=i;
z[u]+=z[i];
x[u]+=x[i];
y[u]+=y[i];
}
}
int X,Y;
struct Caclg{
int gv,gx,gy,P,Q;
void initg(int x,int y){
gv=0;
gx=x;gy=y;
forup(i,max(Q-(P-gx),0),min(gy,gx)){
(gv+=1ll*binom(gx,i)*binom(P-gx,Q-i)%mod)%=mod;
}
}
void workg(int x,int y){
y=min(y,x);
while(gx<x){
if(gy<0){
gv=0;
}else if(gy<Q){
gv=(gv+mod-1ll*binom(gx,gy)*binom(P-1-gx,Q-1-gy)%mod)%mod;
}else{
gv=binom(P,Q);
}
++gx;
}
if(y<0){
gy=y;
gv=0;
}else{
if(gy<=0){
gy=0;
gv=binom(P-x,Q);
}
while(gy<y){
(gv+=1ll*binom(gx,gy+1)*binom(P-x,Q-(gy+1))%mod)%=mod;
++gy;
}
while(gy>y){
gv=(gv+mod-1ll*binom(gx,gy)*binom(P-x,Q-gy)%mod)%mod;
--gy;
}
}
}
}g1,g2;
vector<int> lf;
void dfs2(int x,int fa,int hh){
hig[x]=hh;dfn[x]=++Tm;
if(son[x]){
dfs2(son[x],x,hh);
}else{
lf.push_back(x);
}
for(auto i:e[x]){
if(i==fa||i==son[x]) continue;
dfs2(i,x,i);
}
}
int ans;
int calcf(int x,int y){
int res=0;
res=(res+mod-1ll*y*binom(X,Y)%mod)%mod;
(res+=1ll*x*binom(X-1,Y-1)%mod)%=mod;
(res+=2ll*y*g1.gv%mod)%=mod;
res=(res+mod-2ll*x*g2.gv%mod)%mod;
return res;
}
void work(int u){
int nx=x[u]+y[u],ny=x[u]+z[u];
g2.initg(nx-1,ny-1);
g1.initg(nx,ny);
while(1){
nx=x[u]+y[u];ny=x[u]+z[u];
g2.workg(nx-1,ny-1);
g1.workg(nx,ny);
int val=calcf(nx,ny);
(ans+=val)%=mod;
if(u==hig[u]) break;
u=ff[u];
}
}
void solve(){
n=read();
lf.clear();
forup(i,1,n){
e[i].clear();
son[i]=0;ff[i]=0;
z[i]=x[i]=y[i]=0;
}
ans=0;
forup(i,1,n-1){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
scanf(" %s",str+1);
forup(i,1,n){
if(str[i]=='?'){
s[i]=2;
}else{
s[i]=(str[i]-'0');
}
}
scanf(" %s",str+1);
forup(i,1,n){
if(str[i]=='?'){
t[i]=2;
}else{
t[i]=(str[i]-'0');
}
}
dfs(1,0);
A=x[1];B=y[1];C=z[1];
X=A+B;Y=A+C;
g1.P=X;g1.Q=Y;
g2.P=X-1;g2.Q=Y-1;
dfs2(1,0,1);
for(auto u:lf){
work(u);
}
printf("%d\n",ans);
}
signed main(){
init(1e6);
int t=read();
while(t--){
solve();
}
}
P2048 [NOI2010] 超级钢琴
题意
- 有一个长度为 $n$ 的整数序列 $a_i$，代表钢琴上的键，称一个“和弦”为一个长度在 $[L,R]$ 之间的区间，其权值为区间内的整数之和。
- 选出 $m$ 个和弦，最大化权值和，保证至少有 $m$ 个和弦。
- $1\le n\le 5\times 10^5,-1000\le a_i\le 1000$
题解
感觉想到了就挺简单的。
首先这道题就是要求前 $m$ 大的和弦。
考虑前缀和一下，这样可以很方便地求出以每个点为右端点的最大和弦。
然后发现最大值把左端点区间分成两半后，次大值必定是两边其中一个区间的最大值。这个可以用 ST 表简单维护。
那么对每个右端点用堆维护最优的左端点，然后类似于 shopping plans，每次将全局最大值拎出来（还是用堆维护），更新对应右端点的答案，显然也只需要更新最大值的区间。
注意 ST 表需要预处理 $[0,n]$ 的区间。
复杂度 $O((n+m)\log n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=5e5+5,inf=0x3f3f3f3f;
int n,m,L,R;
int a[N],sum[N];
priority_queue<pii> mx;
struct Node{
int l,r,mn;
bool operator <(const Node &p)const{return sum[mn]>sum[p.mn];}
};
priority_queue<Node> q[N];
int st[19][N];
int Query(int l,int r){
int len=31^__builtin_clz(r-l+1);
return sum[st[len][l]]<sum[st[len][r-(1<<len)+1]]?st[len][l]:st[len][r-(1<<len)+1];
}
void work(int u){
Node nw=q[u].top();q[u].pop();
int l=nw.l,r=nw.r,mm=nw.mn;
if(l<mm) q[u].push(Node{l,mm-1,Query(l,mm-1)});
if(mm<r) q[u].push(Node{mm+1,r,Query(mm+1,r)});
if(q[u].size()) mx.push(mkp(sum[u]-sum[q[u].top().mn],u));
}
signed main(){
n=read();m=read();L=read();R=read();
st[0][0]=0;
forup(i,1,n){
a[i]=read();
sum[i]=sum[i-1]+a[i];
st[0][i]=i;
}
forup(i,0,17){
forup(j,0,n-(1<<(i+1))+1){
st[i+1][j]=(sum[st[i][j]]<sum[st[i][j+(1<<i)]]?st[i][j]:st[i][j+(1<<i)]);
}
}
forup(i,L,n){
int ll=max(i-R,0),rr=i-L;
int gt=Query(ll,rr);
q[i].push(Node{ll,rr,gt});
mx.push(mkp(sum[i]-sum[gt],i));
}
i64 res=0;
forup(i,1,m){
pii nw=mx.top();mx.pop();
res+=nw.fi;
work(nw.se);
}
printf("%lld\n",res);
}
Gym-104120H Homework
题意
- 给定一张 $n$ 个点 $m$ 条边的图，其中一些边已经定向了，另一些边没有定向。
- 给每条边定向，使得这张图能被划分为若干个不共用边的有向环。
- $1\le n\le 300,1\le m\le \binom{n}{2}$，保证两个点之间至多有一条连边。
题解
挺套路的。
首先一个图能被划分为若干个不共用边的有向环当且仅当它的每个极大连通子图都有欧拉回路。
这个又当且仅当每个点的出度等于入度。
那么我们就能判掉一堆无解情况（度数是奇数，或者已经确定的入度/出度过大），转化成一个类似二分图匹配的问题，只不过第 $i$ 个右部点要匹配 $a_i$ 条边。
dinic 解决，复杂度 $O(m\sqrt{m})=O(n^3)$，用的是“dinic 复杂度不会超过 $O(C\sqrt{C})$，其中 $C$ 是网络流图容量和”的结论。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=305,inf=0x3f3f3f3f;
int n,m,cntn;
namespace flow{
struct edge{
int v,rst,nxt;
}e[N*N*8];
int head[N*N+N],cur[N*N+N],dpt[N*N+N],cnte=1,s,t;
void adde(int u,int v,int rst){
e[++cnte]=edge{v,rst,head[u]};head[u]=cnte;
e[++cnte]=edge{u,rst,head[v]};head[v]=cnte;
}
bool bfs(){
forup(i,1,cntn){
cur[i]=head[i];
dpt[i]=-1;
}
dpt[s]=0;
queue<int> q;
q.push(s);
while(q.size()){
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,rst=e[i].rst;
if((~dpt[v])||!rst) continue;
dpt[v]=dpt[u]+1;
q.push(v);
}
}
return ~dpt[t];
}
int dfs(int x,int flow){
if(x==t||!flow) return flow;
int res=0;
for(int i=cur[x];i;i=e[i].nxt){
cur[x]=i;
int v=e[i].v,rst=e[i].rst;
if(dpt[v]!=dpt[x]+1||!rst) continue;
int gt=dfs(v,min(flow-res,rst));
if(gt){
e[i].rst-=gt;
e[i^1].rst+=gt;
res+=gt;
if(res==flow) break;
}
}
return res;
}
int dinic(){
int ans=0;
while(bfs()){
ans+=dfs(s,inf);
}
return ans;
}
}
int rd[N],cd[N],deg[N];
signed main(){
n=read();m=read();
flow::s=n+1;flow::t=n+2;
cntn=flow::t;
forup(i,1,m){
int u=read(),v=read(),d=read();
if(d){
++cd[u];++rd[v];
}else{
int nd=++cntn;
flow::adde(nd,u,1);flow::adde(nd,v,1);
flow::adde(flow::s,nd,1);
++deg[u];++deg[v];
}
}
int sum=0;
forup(i,1,n){
if((cd[i]+rd[i]+deg[i])&1){
puts("NO");
return 0;
}
int v=(cd[i]+rd[i]+deg[i])/2;
if(rd[i]>v||cd[i]>v){
puts("NO");
return 0;
}
flow::adde(i,flow::t,v-rd[i]);
sum+=v-rd[i];
}
int res=flow::dinic();
puts(res==sum?"YES":"NO");
}
[AGC003F] Fraction of Fractal
题意
- 给定一个 $n\times m$ 的 $01$ 矩阵 $a$，有一个矩阵 $s$，初始为大小 $1\times 1$，并且 $s_{1,1}=1$，进行 $k$ 次以下操作：
- 将 $s$ 中所有 $1$ 替换成矩阵 $a$，所有 $0$ 替换成 $n\times m$ 的全 $0$ 矩阵。
- 称操作 $p$ 次得到的矩阵是 $2^p$ 求 $s^k$ 中有多少 $1$ 的四连通块。
- $1\le n,m\le 1000,0\le k\le 10^{18}$，保证 $a$ 中的所有 $1$ 形成一个四连通块，答案对 $10^9+7$ 取模。
题解
一开始想复杂了。
先手玩一下，可以发现：
- 如果 $\exists i,a_{1,i}=a_{n,i}=1$，那么将两个 $a$ 上下放置，会连在一起，称这样的 $a$ 是“上下连通的”。
- 如果 $\exists i,a_{i,1}=a_{i,m}=1$，那么将两个 $a$ 左右放置，会连在一起，称这样的 $a$ 是“左右连通的”。
容易发现，若 $a$ 既上下连通又左右连通，那么最终必定只有一个连通块，同理，若既不上下连通，又不左右连通，那么最终必定有 $c^{k-1}$ 个连通块（其中 $c$ 是 $a$ 中 $1$ 的个数，就是最终图中有多少个 $a$）。
于是只需要考虑一边连通一边不连的情况了，不妨认为是左右连通的。
不难想到点边容斥，即“$a$ 的数量”减去“与左侧矩阵连通的 $a$ 的数量”，前者是好算的，快速幂即可。考虑后者。
$k=0$ 特判，考虑从 $s^1$ 开始，容易发现 $a$ 中每有一个形如 $11$ 的结构，就会产生一次贡献，但是 $s_2$ 时，需要考虑 $s^2$ 左边缘的所有 $a$ 和右边缘的 $a$ 的贡献，其实就是 $a_{i,1}=a_{i,m}=1$ 的 $i$ 的数量。
于是我们需要维护“左右边缘的匹配数量”和“总匹配数量”，不难想到用矩阵乘法概括，具体略。
复杂度 $O(2^3\log k)$。
另外 $a$ 不连通貌似也能做（我一开始就没考虑 $a$ 连通），大概要平面图欧拉定理，感觉巨复杂无比。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=1005,mod=1e9+7;
struct Matrix{
i64 c[2][2];
void init(bool p=0){
mem(c,0);
if(p){
forup(i,0,1){
c[i][i]=1;
}
}
}
Matrix operator*(const Matrix &r){
Matrix res;res.init();
forup(i,0,1){
forup(j,0,1){
forup(k,0,1){
(res.c[i][j]+=1ll*c[i][k]*r.c[k][j]%mod)%=mod;
}
}
}
return res;
}
void print(){
msg("=====\n");
forup(i,0,1){
forup(j,0,1){
msg("%lld ",c[i][j]);
}msg("|\n");
}msg("=====\n");
}
}tr;
Matrix ksm(Matrix a,i64 b){
Matrix c;c.init(1);
while(b){
if(b&1) c=a*c;
a=a*a;
b>>=1;
}
return c;
}
i64 ksm(i64 a,i64 b){
i64 c=1;
while(b){
if(b&1) c=1ll*a*c%mod;
a=1ll*a*a%mod;
b>>=1;
}
return c;
}
i64 n,m,k,a[N][N],cnt0,cntc,cntr;
char str[N];
signed main(){
n=read();m=read();k=read();
if(k==0){
puts("1");
return 0;
}
forup(i,1,n){
scanf(" %s",str+1);
forup(j,1,m){
a[i][j]=(str[j]=='#');
cnt0+=a[i][j];
if(i>1) cntr+=(a[i][j]&a[i-1][j]);
if(j>1) cntc+=(a[i][j]&a[i][j-1]);
}
}
tr.init();
i64 c0=0,c1=0;
forup(i,1,n){
if(a[i][1]&&a[i][m]){
++c0;
}
}
forup(i,1,m){
if(a[1][i]&&a[n][i]){
++c1;
}
}
if(c0==0&&c1==0){
printf("%lld\n",ksm(cnt0,k-1));
}else if(c0&&c1){
puts("1");
}else{
if(c1){swap(c0,c1);swap(cntc,cntr);}
tr.c[0][0]=c0;
tr.c[0][1]=cntc;
tr.c[1][1]=cnt0;
tr.print();
Matrix res=ksm(tr,k-1);
res.print();
i64 cntn=0,cnte=0;
cntn=res.c[1][1];
cnte=res.c[0][1];
printf("%lld\n",(cntn+mod-cnte)%mod);
}
}
QOJ#1288 Tokens on the Tree
题意
- 有一棵 $n$ 树，上面有 $w$ 个白色棋子和 $b$ 个黑色棋子，称一个摆放方式是合法的当且仅当白色棋子和黑色棋子均连成了连通块，并且每个格子上至多有一个棋子。
- 现在你可以进行任意次以下操作：
- 选择一个棋子，满足至少一个与它相邻的点上没有和它同色的棋子或它所在点的度数为 $1$，将其移动到与某和它同色的棋子相邻的空格。
- 显然无论怎么操作这个摆放方式都是合法的。
- 称两摆放方式等价，当且仅当两摆放方式可以通过若干上述操作互相转化。
-
给定一棵 $n$ 个点的树，设 $f(w,b)$ 表示 $w$ 个白子和 $b$ 个黑子摆放方式的等价类个数，求：
$$ \left(\sum_{w=1}^{n-1}\sum_{b=1}^{n-w}f(w,b)\times w\times b\right)\bmod (10^9+7) $$
-
$1\le n\le 2\times 10^5$
题解
神秘构造。
不妨设 $w\ge b$，将 $w > b$ 的贡献乘以二即可。
设 $mx_i$ 表示将点 $i$ 删掉后得到的连通块里面最大的那个。容易发现若 $w > mx_i$，则点 $i$ 上面必定有一颗白子，将所有满足上述条件的点删掉，此时 $f(w,b)$ 就是剩下的连通块里面大小大于等于 $b$ 的个数。
若不存在这样的点，容易发现答案只可能是 $1,2$，并且是一当且仅当存在一个点 $u$，将其删掉后连通块的前两大值都大于等于 $w$，并且第三大值大于等于 $b$。
那么我们找到 $mx_i$ 的最小值 $m$，小于等于 $m$ 的 $w$ 和大于 $w$ 的分开维护，具体实现细节略，可以做到 $O(n)$，但是我求前三大值用了排序，是 $O(n\log n)$ 的。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5,mod=1e9+7;
int n;
vector<int> e[N],vec[N];
int sz[N],mx[N];
int rt;
int pmx[N];
void dfs(int x,int fa){
sz[x]=1;mx[x]=0;
for(auto i:e[x]){
if(i==fa) continue;
dfs(i,x);
mx[x]=max(mx[x],sz[i]);
sz[x]+=sz[i];
vec[x].push_back(sz[i]);
}
mx[x]=max(mx[x],n-sz[x]);
vec[x].push_back(n-sz[x]);
sort(vec[x].begin(),vec[x].end(),greater<int>());
if(mx[x]<=n/2){
rt=x;
}
}
int calc(int l,int r){
if(l>r) return 0;
return (1ll*(r-l+1)*(l+r)/2)%mod;
}
vector<int> add[N],del[N];
int ff[N];
void dfs2(int x,int fa){
ff[x]=fa;sz[x]=1;
for(auto i:e[x]){
if(i==fa) continue;
dfs2(i,x);
sz[x]+=sz[i];
}
}
void solve(){
n=read();
forup(i,1,n+1){
e[i].clear();vec[i].clear();
add[i].clear();del[i].clear();
pmx[i]=ff[i]=0;
}
forup(i,2,n){
int f=read();
e[i].push_back(f);
e[f].push_back(i);
}
if(n==2){
puts("2");
return;
}
rt=0;
dfs(1,0);
dfs2(rt,0);
int m=vec[rt][0];
forup(u,1,n){
if(vec[u].size()>=3){
pmx[vec[u][1]]=max(pmx[vec[u][1]],vec[u][2]);
}
if(mx[u]==m) continue;
add[mx[ff[u]]+1].push_back(sz[u]);
del[mx[u]+1].push_back(sz[u]);
}
int ans=0;
fordown(i,n,1){
pmx[i]=max(pmx[i],pmx[i+1]);
}
forup(w,1,m){
(ans+=2ll*calc(1,min(w-1,pmx[w]))%mod*w%mod)%=mod;
(ans+=4ll*calc(pmx[w]+1,w-1)%mod*w%mod)%=mod;
if(w<=pmx[w]) (ans+=1ll*w*w%mod)%=mod;
else (ans+=2ll*w*w%mod)%=mod;
}
int val=0;
for(auto i:add[m]){
(val+=calc(1,i))%=mod;
}
for(auto i:del[m]){
val=(val+mod-calc(1,i))%mod;
}
forup(w,m+1,n-1){
for(auto i:add[w]){
(val+=calc(1,i))%=mod;
}
for(auto i:del[w]){
val=(val+mod-calc(1,i))%mod;
}
(ans+=2ll*w*val%mod)%=mod;
}
printf("%d\n",ans);
}
signed main(){
int t=read();
while(t--){
solve();
}
}
QOJ#5020 举办乘凉州喵，举办乘凉州谢谢喵
题意
- 给定一棵 $n$ 个点的树，有 $m$ 次查询，每次查询与链 $x\to y$ 距离小于等于 $d$ 的点个数。
- 点和链的距离定义如下：
- 设这条链占据点集 $S$，定义点 $u$ 和这条链的距离为 $\min_{v\in S}dist(u,v)$，其中 $dist(u,v)$ 表示 $u,v$ 之间简单路径上的边数。
- $1\le n,q\le 2\times 10^5$
题解
很 cool 的一道题。
考虑链上询问常见做法是用差分转化成若干个 $1\to u$ 的问题，考虑这道题怎么做。
不妨用 $f(x,y,d)$ 表示“与链 $x\to y$ 距离小于等于 $d$ 的点个数”，不难发现：
$$ f(x,y,d)=f(1,x,d)+f(1,y,d)-2f(1,p,d)+f(p,p,d) $$
其中 $p=\mathrm{lca}(x,y)$。
发现 $f(p,p,d)$ 可以点分治求出，于是只关注 $f(1,u,d)$ 怎么求。
处理链信息不难想到重链剖分，容易发现整链我们只需要算轻儿子的贡献，而两链之间的轻边简单容斥即可，不妨设 $g(x,d)$ 表示 $x$ 所有轻儿子中距离 $x$ 小于等于 $d$ 的点数，$h(x,d)$ 表示以 $x$ 为根的子树中距离 $x$ 小于等于 $d$ 的点数 $son_u$ 表示 $u$ 的重儿子。设从 $u$ 到根经过了 $m$ 条重链，其中第 $i$ 条重链是从 $s_i$ 进入到 $t_i$（即重链链顶）走出，有：
$$ f(1,u,d)=dpt_u+h(son_u,d-1)+\sum_{i=1}^m\left(\sum_{j\in(s_i,t_i)}g(j,d)\right)+h(son_{s_i},d-1)-h(t_i,d-1) $$
其中 $j\in(s_i,t_i)$ 表示 $j$ 枚举 $s_i\to t_i$ 路径上所有点。
由于每个点轻儿子的个数总和是 $O(n\log n)$ 级别的，那么可以在进行 dfs 的途中暴力遍历轻儿子用树状数组维护 $g$，而 $h$ 可以 DSU on tree $+$ 树状数组解决，因为 $m$ 是 $O(\log n)$ 级别的，所以要进行 $O(q\log n)$ 次查询，复杂度 $O(n\log^2 n)$。
注意树状数组边界情况。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)){if(c=='-')f=-1;}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5,inf=0x3f3f3f3f;
int n,m;
vector<int> e[N];
int ans[N];
vector<pii> q[N];
int sz[N],mx[N],als,rt;
int vis[N];
void dfs1(int x,int fa){
sz[x]=1;mx[x]=0;
for(auto i:e[x]){
if(i==fa||vis[i]) continue;
dfs1(i,x);
sz[x]+=sz[i];
mx[x]=max(mx[x],sz[i]);
}
mx[x]=max(mx[x],als-sz[x]);
if(mx[x]<=als/2) rt=x;
}
int cnt[N];
void dfs2(int x,int fa,int dis){
++cnt[dis];
for(auto i:e[x]){
if(i==fa||vis[i]) continue;
dfs2(i,x,dis+1);
}
}
vector<pii> qu;
void dfs3(int x,int fa,int dis){
--cnt[dis];
for(auto i:q[x]){
if(i.fi>=dis){
qu.push_back(mkp(i.fi-dis,i.se));
}
}
for(auto i:e[x]){
if(i==fa||vis[i]) continue;
dfs3(i,x,dis+1);
}
}
void dfz(int x,int ps){
dfs2(x,0,0);
vis[x]=1;
sort(q[x].begin(),q[x].end());
int pl=0,sum=0;
for(auto i:q[x]){
while(pl<=i.fi&&pl<=ps){
sum+=cnt[pl];++pl;
}
ans[i.se]+=sum;
}
for(auto i:e[x]){
if(vis[i]) continue;
qu.clear();
dfs3(i,x,1);
sort(qu.begin(),qu.end());
int pl=0,sum=0;
for(auto i:qu){
while(pl<=i.fi&&pl<=ps){
sum+=cnt[pl];++pl;
}
ans[i.se]+=sum;
}
dfs2(i,x,1);
}
forup(i,0,ps) cnt[i]=0;
for(auto i:e[x]){
if(vis[i]) continue;
rt=0;als=(sz[i]<sz[x]?sz[i]:ps-sz[x]);
dfs1(i,x);
dfz(rt,als);
}
}
int dfn[N],Tm,siz[N],son[N],hig[N],dpt[N],ff[N],mp[N];
void _0dfs(int x,int fa){
siz[x]=1;dpt[x]=dpt[fa]+1;
ff[x]=fa;
for(auto i:e[x]){
if(i==fa) continue;
_0dfs(i,x);
siz[x]+=siz[i];
if(!son[x]||siz[i]>siz[son[x]]) son[x]=i;
}
}
void _1dfs(int x,int fa,int hh){
dfn[x]=++Tm;hig[x]=hh;
mp[dfn[x]]=x;
if(son[x]){
_1dfs(son[x],x,hh);
}
for(auto i:e[x]){
if(i==fa||i==son[x]) continue;
_1dfs(i,x,i);
}
}
int lca(int u,int v){
while(hig[u]!=hig[v]){
if(dpt[hig[u]]<dpt[hig[v]]) swap(u,v);
u=ff[hig[u]];
}
if(dpt[u]<dpt[v]) swap(u,v);
return v;
}
struct Node{
int d,val,pos;
};
vector<Node> q1[N],q2[N];
void getqu(int x,int d,int i,int v){
ans[i]+=v*dpt[x];
q1[x].push_back(Node{d,v,i});
while(x){
if(son[x]) q2[son[x]].push_back(Node{d-1,v,i});
q2[hig[x]].push_back(Node{d-1,-v,i});
x=ff[hig[x]];
}
}
struct BIT{
int c[N];
void upd(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;}
int sum(int x){int res=0;for(;x>0;x-=x&-x)res+=c[x];return res;}
}t1,t2;
void dfs4(int x,int fa){
for(auto i:e[x]){
if(i==fa||i==son[x]) continue;
forup(j,dfn[i],dfn[i]+siz[i]-1){
int u=mp[j];
t1.upd(dpt[u]-dpt[x],1);
}
}
for(auto i:q1[x]){
msg("A %d %d %d|\n",x,i.d,t1.sum(i.d));
ans[i.pos]+=i.val*t1.sum(i.d);
}
for(auto i:e[x]){
if(i==fa||i==son[x]) continue;
dfs4(i,x);
forup(j,dfn[i],dfn[i]+siz[i]-1){
int u=mp[j];
t2.upd(dpt[u],-1);
}
}
if(son[x]){
dfs4(son[x],x);
}
for(auto i:e[x]){
if(i==fa||i==son[x]) continue;
forup(j,dfn[i],dfn[i]+siz[i]-1){
int u=mp[j];
t2.upd(dpt[u],1);
}
}
t2.upd(dpt[x],1);
for(auto i:q2[x]){
msg("B %d %d %d|\n",x,i.d,t2.sum(min(n,dpt[x]+i.d)));
ans[i.pos]+=i.val*t2.sum(min(n,dpt[x]+i.d));
}
for(auto i:e[x]){
if(i==fa||i==son[x]) continue;
forup(j,dfn[i],dfn[i]+siz[i]-1){
int u=mp[j];
t1.upd(dpt[u]-dpt[x],-1);
}
}
}
signed main(){
n=read();
forup(i,1,n-1){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
_0dfs(1,0);
_1dfs(1,0,1);
forup(i,1,n){
msg("%d ",hig[i]);
}msg("|\n");
m=read();
forup(i,1,m){
int x=read(),y=read(),d=read();
if(x!=y){
int p=lca(x,y);
q[p].push_back(mkp(d,i));
getqu(x,d,i,1);getqu(y,d,i,1);
getqu(p,d,i,-2);
}else{
q[x].push_back(mkp(d,i));
}
msg("%d|\n",ans[i]);
}
rt=0;als=n;
dfs1(1,0);
dfz(rt,als);
dfs4(1,0);
forup(i,1,m){
printf("%d\n",ans[i]);
}
}
P8863 「KDOI-03」构造数组
题意
- 给定一个数组 $b$，你可以进行若干次以下操作：
- 选择两个数 $i,j$ 满足 $b_i > 0,b_j > 0,i < j$，$b_i\gets b_i-1,b_j\gets b_j-1$，这个操作记为二元组 $(i,j)$。
- 问有多少种操作方式能让 $b$ 变为全 $0$，我们认为两操作方式不同当且仅当存在一个 $x$，使得两操作方式中第 $x$ 步选择的二元组不同。
- $1\le n\le 5000,1\le b_i\le 30000,\sum b_i\le 30000$，答案对 $998244353$ 取模。时限 4s。
题解
其实这道题很简单，但是赛时放模拟赛 T4，然后 T3 因为本地机子太慢一直在卡常就没认真想，唉。
设 $m=\sum b_i$，首先显而易见的，若 $m\bmod 2=1$ 则显然无解，否则相当于把 $m$ 个小球放进若干个盒子里，每个盒子都要放两个不同颜色的小球，盒子有标号小球无标号。
发现这其实是经典的 DP，设 $f_{i,j,k,l}$ 表示考虑前 $i$ 种颜色的小球，现在有 $j$ 个盒子放了两颗，$k$ 个放了一个，$l$ 个空盒子。转移就枚举这 $b_i$ 个小球有多少放进有一个小球的，多少放进空盒，乘一个组合数即可。
不难发现 $j,k,l$ 只要确定了 $i$ 和其中一个就能确定剩下两个，那么状态数是 $O(nm)$ 的，又注意到转移时需要枚举 $b_i$，但是 $b_i$ 的总和是 $m$，所以复杂度 $O(m^2)$，然后滚动数组优化一下空间就能过了。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=5005,M=30005,mod=998244353;
int ksm(int a,int b){
int c=1;
while(b){
if(b&1) c=1ll*a*c%mod;
a=1ll*a*a%mod;
b>>=1;
}
return c;
}
int n,m,a[N],sum;
int dp[2][M];
int fact[M],finv[M];
int binom(int n,int m){
if(n<m) return 0;
return 1ll*fact[n]*finv[m]%mod*finv[n-m]%mod;
}
signed main(){
n=read();
forup(i,1,n){
a[i]=read();
sum+=a[i];
}
if(n==1||(sum&1)){
puts("0");
return 0;
}
if(n==2){
if(a[1]==a[2]){
puts("1");
}else{
puts("0");
}
return 0;
}
fact[0]=1;
forup(i,1,sum) fact[i]=1ll*fact[i-1]*i%mod;
finv[sum]=ksm(fact[sum],mod-2);
fordown(i,sum-1,0) finv[i]=1ll*finv[i+1]*(i+1)%mod;
m=sum/2;
sum=0;
dp[0][0]=1;
forup(i,1,n){
int p=i&1,q=p^1;
mem(dp[p],0);
sum+=a[i];
forup(j,max(sum-m,0),sum/2){
int k=sum-j*2,l=m-j-k;
forup(c1,max(0,a[i]-k),min(a[i],j)){
int c2=a[i]-c1;
int j1=j-c1,k1=k+c1-c2;
if(j1*2+k1!=sum-a[i]) continue;
(dp[p][j]+=1ll*dp[q][j-c1]*binom(k+c1-c2,c1)%mod*binom(l+c2,c2)%mod)%=mod;
}
}
}
printf("%d\n",dp[n&1][m]);
}
模拟赛神秘题目 【1112 B组】D 逃脱
《》
题意
- 有一棵树，每个度数为 $1$ 的点视为出口，上面有一个逃脱者和若干个围堵者，围堵者初始只能从某出口出发。
- 每回合逃脱者和所有围堵者同时移动到相邻的格子（可以不动），当逃脱者和任意围堵者处于同一格时逃脱者胜利，否则，若逃脱者处于任意出口，则逃脱者胜利。
- 现在对于逃脱者的所有 $n$ 个起点，求至少需要多少个围堵者才能让逃脱者必败。
- $1\le n\le 7\times 10^4$
题解
首先若逃脱者出生就在出口则只需要一个，因为可以在这个出口安排一个围堵者。
否则我们将逃脱者出生点视为根，不难发现围堵者一直往上走是不劣的。
因为我们需要让逃脱者往任意方向走都会被堵住，假设逃脱者看准了一个叶子直着冲过去，那么它就会在根和叶子的中点被拦下。
那么我们可以认为所有叶子和根的中点会对这个根产生一次贡献，但是显然若某个点的祖先中已经有贡献点了就不会再产生一次贡献，那么不妨把限制放宽一点，一个点产生贡献当且仅当它和最近的叶子的距离比和根的距离进，且祖先中没有贡献点。
然后我们不认为出生点是根，限制就变成了出生点到这个点的路径上没有贡献点，预处理每个点和最近叶子的距离后不难用点分治维护（每个连通块考虑从点到根和从根到点的两段都不能有），复杂度 $O(n\log n)$，注意特判在叶子出生的情况。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=7e4+5,inf=0x3f3f3f3f;
int n,ans[N];
vector<int> e[N];
int mn[N];
void dfs(int x,int fa){
mn[x]=inf;
if(e[x].size()==1) mn[x]=0;
for(auto i:e[x]){
if(i==fa) continue;
dfs(i,x);
mn[x]=min(mn[x],mn[i]+1);
}
}
void dfs0(int x,int fa){
for(auto i:e[x]){
if(i==fa) continue;
mn[i]=min(mn[i],mn[x]+1);
dfs0(i,x);
}
}
int sz[N],mx[N],vis[N],als,rt;
void dfs1(int x,int fa){
sz[x]=1;mx[x]=0;
for(auto i:e[x]){
if(i==fa||vis[i]) continue;
dfs1(i,x);
sz[x]+=sz[i];
mx[x]=max(mx[x],sz[i]);
}
mx[x]=max(mx[x],als-sz[x]);
if(mx[x]<=als/2) rt=x;
}
int val[N],vv[N],dd[N];
void dfs2(int x,int fa,int p){
int pl=max(mn[x]-dd[x],0),pr=pl-1;
for(int i=max(mn[x]-dd[x],0);i<=als;++i){
if(vv[i]) break;
vv[i]=1;pr=i;
val[i]+=p;
}
for(auto i:e[x]){
if(i==fa||vis[i]) continue;
dd[i]=dd[x]+1;
dfs2(i,x,p);
}
forup(i,pl,pr){
vv[i]=0;
}
}
void dfs3(int x,int fa,int mxd){
mxd=min(mxd,dd[x]+mn[x]);
if(dd[x]>=mxd) return;
ans[x]+=val[dd[x]];
for(auto i:e[x]){
if(i==fa||vis[i]) continue;
dfs3(i,x,mxd);
}
}
void dfz(int x,int ps){
dd[x]=0;
dfs2(x,0,1);
msg("[%d]",x);
forup(i,0,ps){
msg("%d ",val[i]);
}msg("|\n");
ans[x]+=val[0];
for(int i=max(mn[x]-dd[x],0);i<=als;++i){
vv[i]=1;
}
for(auto i:e[x]){
if(vis[i]) continue;
dfs2(i,x,-1);
dfs3(i,x,als);
dfs2(i,x,1);
}
forup(i,0,ps){
val[i]=vv[i]=0;
}
vis[x]=1;
for(auto i:e[x]){
if(vis[i]) continue;
rt=0;als=sz[i]<sz[x]?sz[i]:ps-sz[x];
dfs1(i,x);
dfz(rt,als);
}
}
signed main(){
n=read();
forup(i,1,n-1){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1,0);
dfs0(1,0);
als=n;rt=0;
dfs1(1,0);
dfz(rt,als);
forup(i,1,n){
if(e[i].size()==1){
printf("1 ");
}else{
printf("%d ",ans[i]);
}
}
}
[AGC018C] Coins
题意
- 有 $x+y+z$ 个人，每个人手上有 $a_i$ 个金币，$b_i$ 个银币，$c_i$ 个铜币。
- 现在你要选 $x$ 个人把金币给你，从剩下的里面选 $y$ 个人把银币给你，剩下 $z$ 个人把铜币给你。
- 问你最多能拿到多少个钱币。
- $1\le x,y,z\le 10^5,x+y+z\le 10^5,1\le a_i,b_i,c_i\le 10^9$
题解
容易想到模拟网络流，但是过于难写了，调了好久调破防了遂看题解。
考虑假设每个人最初把铜币给你，然后选 $x$ 个人获得 $a_i-c_i$ 的贡献，从剩下的人里面选择 $y$ 个获得 $b_i-c_i$ 的贡献，不妨设 $e_i=a_i-c_i,f_i=b_i-c_i$。
考虑一个类似邻项交换法的东西，若 $e_i+f_j\ge e_j+f_i$，则 $e_i-f_i\ge e_j-f_j$，那么按这个排序就能发现应是一个前缀前 $x$ 大的 $e$ 和后缀前 $y$ 大的 $f$ 贡献，随便维护一下即可。
用堆复杂度是 $O(n\log n)$，其中 $n=x+y+z$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=1e5+5,inf=1e18;
i64 x,y,z,n,a[N],b[N],c[N],ans;
struct Node{
i64 a,b;
}s[N];
i64 pre[N],suf[N];
priority_queue<i64,vector<i64>,greater<i64>> q;
signed main(){
x=read();y=read();z=read();
n=x+y+z;
forup(i,1,n){
a[i]=read();b[i]=read();c[i]=read();
ans+=c[i];
s[i]=Node{a[i]-c[i],b[i]-c[i]};
}
sort(s+1,s+n+1,[&](Node a,Node b){return a.a-a.b>b.a-b.b;});
i64 sum=0;
forup(i,1,x){
q.push(s[i].a);
sum+=s[i].a;
}
pre[x]=sum;
forup(i,x+1,n){
sum+=s[i].a;q.push(s[i].a);
sum-=q.top();q.pop();
pre[i]=sum;
}
while(q.size()) q.pop();
sum=0;
fordown(i,n,n-y+1){
q.push(s[i].b);
sum+=s[i].b;
}
suf[n-y+1]=sum;
fordown(i,n-y,1){
sum+=s[i].b;q.push(s[i].b);
sum-=q.top();q.pop();
suf[i]=sum;
}
i64 mx=-inf;
forup(i,x,n-y){
mx=max(mx,pre[i]+suf[i+1]);
}
printf("%lld\n",ans+mx);
}
[AGC007F] Shik and Copying String
题意
- 给定两个长度为 $n$ 的字符串 $s^0,t$，定义 $s^k$ 为一个字符串满足 $s^k_i$ 不等于 $s^{k-1}i$ 就等于 $s^k{i-1}$，求让 $s^k=t$ 的最小的 $k$，无解输出 $-1$。
- $1\le n\le 10^6$
题解
贪心。
把每种字符视为一种颜色，不难找到每个颜色最终需要覆盖到哪个位置，从右往左贪心向右匹配即可。
注意到任意时刻这个颜色的连续段都不能跨过右侧下一个颜色，不难发现尽量往右走是最优的，那么我们可以维护每个时刻下个颜色的左端点。
又注意到颜色的左端点在时刻上其实是若干连续段的形式，那么我们只需要维护连续段交界点即可。然后显然地，若这个颜色始终紧贴下一颜色，那么每个连续段必定左右端点都是下个颜色的向右平移一个时刻，可以打懒标记维护。
那么何时不会紧贴呢？首先开头时可能不紧贴，其次是末尾某段假如已经到了自己的匹配点，那么一直向下即可。
答案就是匹配过程中找到的连续段最大的连续段右端点，复杂度 $O(n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e6+5;
int n;
char s[N],t[N];
int pr[N];
signed main(){
n=read();
scanf(" %s",s+1);
scanf(" %s",t+1);
queue<int> q;
fordown(i,n,1){
q.push(i);
if(t[q.front()]==s[i]){
pr[i]=q.front();
while(q.size()&&t[q.front()]==s[i]) q.pop();
}
}
if(q.size()){
puts("-1");
return 0;
}
deque<pii> vec;
int ans=0,pre=n+1,adx=0,ady=0;
fordown(i,n,1){
if(!pr[i]) continue;
if(pr[i]==i){
vec.clear();adx=ady=0;
}
adx+=1;ady-=1;
while(vec.size()&&vec.back().se+ady>=pr[i]) vec.pop_back();
if(vec.empty()) adx=ady=0;
if(pre>i+1) vec.push_front(mkp(1-adx,i-ady));
if(vec.size()) ans=max(ans,vec.back().fi+adx);
pre=i;
}
printf("%d\n",ans);
}
[AGC009D] Uninity
题意
- 定义一棵 $0$ 阶树为一个点的无根树，一棵 $i$ 阶树为一个点上连了 $x\ge 0$ 棵 $i-1$ 阶树的无根树。
- 显然任意 $k$ 阶树也是 $k+1,k+2,\dots$ 阶树，给定一棵 $n$ 个点的树，求这棵树至少是多少阶树。
- $1\le n\le 10^5$
题解
妙妙贪心题。
首先第一眼看过去哇塞这不是点分治板题吗，然后仔细想一下发现不对，因为一棵树可能有俩重心，从两个地方分开答案可能不同。
然后假如顺着这个思路想就寄了。发现点分治求最优点分树并不好做，考虑能不能丢弃题目原有的限制，抽象出一个相对独立的充要条件。
《容易》发现相当于给每个点赋一个 $d$ 表示这个点是第几阶树的根，满足任意两相等的 $d_u,d_v$ 之间的简单路径上都有至少一个 $d_x > d_u$。设 $d$ 的最大值为 $k$，显然可以直接从这个编号构造出 $k$ 阶树，并且任意 $k$ 阶树都能由这样的编号概括，于是就充分必要了。
那么怎么求答案呢？随便定一个根，然后 dfs 的过程中维护每个点都在不与子树冲突的情况下取最小值，因为你容易发现一个较大值对全局最大值的影响必定大于任意多个较小值，于是贪心地最小化每个点是正确的。
具体实现考虑一些位运算，对每个点维护一个 $msk_u$ 表示子树内和 $u$ 之间路径上没有更大值的 $d$ 的集合，注意到 $d$ 的上界是 $\left\lfloor\log_2 n\right\rfloor$，所以直接用一个整数状压即可。每个 $u$ 的限制就能不能取儿子 $msk$ 的并集中的点，并且必须大于最大的 $d'$ 满足至少两儿子的 $msk$ 中含有这个数。然后对 $msk_u$ 小于 $d_u$ 的部分推平即可，用一些位运算复杂度能做到 $O(n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e5+5,inf=0x3f3f3f3f;
int n,p,ans;
vector<int> e[N];
int msk[N],dp[N];
void dfs(int x,int fa){
int OR=0;
int cnt=0;
dp[x]=0;
for(auto i:e[x]){
if(i==fa) continue;
++cnt;
dfs(i,x);
if(OR&msk[i]){
dp[x]=max(dp[x],(31^__builtin_clz(OR&msk[i]))+1);
}
OR|=msk[i];
}
while(OR&(1<<dp[x])) ++dp[x];
OR=OR&((1<<p)-(1<<dp[x]));
OR|=(1<<dp[x]);
msk[x]=OR;
ans=max(ans,dp[x]);
}
signed main(){
n=read();
p=(31^__builtin_clz(n))+1;
forup(i,1,n-1){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1,0);
printf("%d\n",ans);
}
NIKKEI Programming Contest 2019 F-Jewels
题意
- 有 $n$ 个物品，每个物品有一个颜色 $c_i(1\le c_i\le m)$ 和一个价值 $v_i$。
- 对于任意一种颜色，都不能恰好只选 $1$ 个该颜色的物品（即要么不选要么至少选两个）。
- 对于 $i=1\sim n$，求选恰好 $i$ 个物品的最大价值，无解输出 $-1$。
- $1\le n\le 2\times 10^5,1\le m\le \frac{n}{2},1\le v_i\le 10^9$，保证每种颜色至少出现两次。
题解
很趣味的一道题。
首先 $i=1$ 无解，然后若每种颜色都出现恰好两次则奇数无解，否则对于 $i=2\sim n$ 必定有解。
一个显然的观察是每个颜色必定是选择价值最大的若干个。考虑如何从选 $i$ 个推到 $i+1$ 个。假设我们已经求出了选 $i$ 个的最优答案。
首先最多只会增加一个已有颜色，假如增加超过一个，那么需要对其它位置进行一些操作使得总物品数减少一个。设减少的权值为 $v$，增加的两个分别为 $u_1,u_2$（不妨设 $u_1\ge u_2$），因为 $u_1+u_2-v > u_1$，则 $u_2 > v$，那么 $u_1 > v$，则从选 $p$ 个的情况中去掉 $v$ 再加上 $u_1$ 是更优的，并且显然无论 $u_1,u_2$ 颜色是否相同这个操作都合法，与先前的“最优”矛盾。
然后最多只会减少一个已有颜色（除去减掉之后这个颜色消失的情况），首先当减少时，其它增加的必定只能增加原先没有的颜色，否则可以简单调整得到更优解（即与最优矛盾），那么假设我们减少了两个，则必定是某个原先没有的颜色增加三个，设增加的是 $v_1,v_2,v_3$，减少的是 $u_1,u_2$（同理不一定同色，钦定 $u_1\ge u_2$），因为这个比减一增二优（减去 $u_2$，增加 $v_1,v_2$），则 $v_3 > u_1$，于是 $v_1 \ge v_2 \ge v_3 > u_1 ge u_2$，则 $v_1+v_2 > u_1+u_2$，调整过去更优，与“最优”矛盾。减三增四就更简单了，因为只能新增两对同颜色的（直接增加四个同色的等价于减二增三加上情况一），那么较小的那对必定大于减去的三个里面较小的两个，于是调整过去更优。
然后任意情况下，每次都最多减少三个，超过三个的时候必定是减去若干个 $2$ 和至多一个 $1$（注意 $1$ 能和某个 $2$ 颜色相同），增加的时候也只能是若干个 $2$ 和至多一个 $1$（同理）。因为减去的至少有四个，则必然有至少一个颜色原本就只有两个，增加的也是同理，可以直接调整过去。
于是综合下来，不难发现只有以下四种情况：
- 增加一个已有颜色。
- 减少一个已有（$\ge 3$）颜色，增加一对原先没有的。
- 减去一个选了且只选了 $3$ 个的颜色，增加两对原先没有的。
- 减去一个选了且只选了 $2$ 个的颜色，新增 $3$ 个某种没选的颜色。
用若干个堆或者 set 维护一下即可。复杂度 $O(n\log n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=2e5+5,inf=1e18;
i64 n,m,ans[N],pl[N];
vector<i64> vec[N];
set<pii> s02,s03,s2,s3,sdl,sad;
void add(i64 u){
if(pl[u]==0){
if(vec[u].size()>=2) s02.insert(mkp(vec[u][0]+vec[u][1],u));
if(vec[u].size()>=3) s03.insert(mkp(vec[u][0]+vec[u][1]+vec[u][2],u));
}else{
if(pl[u]>2) sdl.insert(mkp(vec[u][pl[u]-1],u));
if(2<=pl[u]&&pl[u]<=vec[u].size()-1) sad.insert(mkp(vec[u][pl[u]],u));
if(pl[u]==2) s2.insert(mkp(vec[u][0]+vec[u][1],u));
if(pl[u]==3) s3.insert(mkp(vec[u][0]+vec[u][1]+vec[u][2],u));
}
}
void del(i64 u){
if(pl[u]==0){
if(vec[u].size()>=2) s02.erase(mkp(vec[u][0]+vec[u][1],u));
if(vec[u].size()>=3) s03.erase(mkp(vec[u][0]+vec[u][1]+vec[u][2],u));
}else{
if(pl[u]>2) sdl.erase(mkp(vec[u][pl[u]-1],u));
if(2<=pl[u]&&pl[u]<=vec[u].size()-1) sad.erase(mkp(vec[u][pl[u]],u));
if(pl[u]==2) s2.erase(mkp(vec[u][0]+vec[u][1],u));
if(pl[u]==3) s3.erase(mkp(vec[u][0]+vec[u][1]+vec[u][2],u));
}
}
signed main(){
n=read();m=read();
forup(i,1,n){
i64 c=read(),v=read();
vec[c].push_back(v);
}
bool flag=true;
forup(i,1,m){
sort(vec[i].begin(),vec[i].end(),greater<i64>());
add(i);
if(vec[i].size()>2) flag=false;
}
if(flag){
vector<i64> seq;
forup(i,1,m){
if(vec[i].size()==2){
seq.push_back(vec[i][0]+vec[i][1]);
}
}
sort(seq.begin(),seq.end(),greater<i64>());
i64 sum=0;
forup(i,1,n){
if(i&1){
puts("-1");
}else{
sum+=seq[i/2-1];
printf("%lld\n",sum);
}
}
return 0;
}
ans[1]=-1;
ans[2]=prev(s02.end())->fi;
i64 u=prev(s02.end())->se;
del(u);
pl[u]=2;
add(u);
forup(i,3,n){
ans[i]=ans[i-1];
i64 val0=-inf,val1=-inf,val2=-inf,val3=-inf;
if(sad.size()) val0=prev(sad.end())->fi;
if(s2.size()&&s03.size()) val1=(prev(s03.end())->fi)-(s2.begin()->fi);
if(s02.size()>1&&s3.size()) val2=(prev(s02.end())->fi)+(prev(prev(s02.end()))->fi)-(s3.begin()->fi);
if(s02.size()&&sdl.size()) val3=(prev(s02.end())->fi)-(sdl.begin()->fi);
if(val0>=val1&&val0>=val2&&val0>=val3){
ans[i]+=val0;
i64 u=prev(sad.end())->se;
del(u);
++pl[u];
add(u);
}else if(val1>=val2&&val1>=val3){
ans[i]+=val1;
i64 u=(prev(s03.end()))->se,v=s2.begin()->se;
del(u);del(v);
pl[v]=0;pl[u]=3;
add(u);add(v);
}else if(val2>=val3){
ans[i]+=val2;
i64 a=prev(s02.end())->se,b=prev(prev(s02.end()))->se,c=s3.begin()->se;
del(a);del(b);del(c);
pl[a]=pl[b]=2;pl[c]=0;
add(a);add(b);add(c);
}else{
ans[i]+=val3;
i64 u=prev(s02.end())->se,v=sdl.begin()->se;
del(u);del(v);
pl[u]=2;--pl[v];
add(u);add(v);
}
}
forup(i,1,n){
printf("%lld\n",ans[i]);
}
}
模拟赛神秘题目 【1116 B组】C 异或
题意
- 有一个集合 $S$，所有数在 $[0,2^n)$ 之间，满足 $\forall a,b\in S$ 有 $a\oplus b\in S$，其中 $\oplus$ 表示按位异或，下同。
- 现在给定 $m$ 个限制，形如“集合中第 $x$ 小的数是 $y$”（题目要求最小的数是第 $1$ 小），求合法的集合数。
- $1\le n\le 120,1\le m\le 10^5,0\le x,y < 2^n$
题解
妙妙题。
考虑这个集合相当于是一个张成空间，而张成空间第 $i$ 小有经典套路。
具体来说，我们求出该线性空间的线性基，对线性基消元成为行最简型矩阵，得到 $p$ 个代表元。然后第 $k$ 小（注意到题设中若 $S$ 非空最小的数必定是 $0$，我们认为 $0$ 是第 $0$ 小的，即对题目给的 $x$ 全部 $-1$）就是 $k$ 二进制中 $1$ 的位置上的代表元异或起来，证明考虑按位贪心。
那么不难发现，假设第 $x_1$ 小的数为 $y_1$，第 $x_2$ 小的数为 $y_2$，则第 $x_1\oplus x_2$ 小的数为 $y_1\oplus y_2$（注意这里往后的 $x$ 都是题目给的 $x-1$）。
于是我们可以先对 $x$ 维护线性基来简化问题，同时额外维护每一个代表元对应的 $y$，若 $x$ 与之前的代表元已经线性相关，那么对应的 $y'$ 异或起来必定等于 $x$，否则无解，具体实现考虑插入时同时对 $x,y$ 进行异或，大概这样：
参考代码
这个函数返回 $\mathrm{false}$ 就说明无解。
然后我们就能求出 $O(n)$ 个有用的限制了（即只保留这个线性基求出的代表元）。接着我们用这些限制来构造另一个线性基，每个限制形如“线性基中若干个（就是 $x$ 中二进制为 $1$ 的那些位）代表元异或起来等于 $y$”，并且要求该线性基是行最简的。
考虑从小到大确定线性基中第 $i$ 小的代表元，若存在一个 $x$ 最高位是 $i$，不难发现该代表元是唯一确定的，因为我们需要 $x$ 中 $1$ 的位置异或起来是 $y$，而其余的 $1$ 全都被确定了（注意是从小到大确定的），想要得到 $y$ 这个代表元就只有一种填法。并且第 $i$ 位代表元的位数已经被确定了。
但是有一些问题，因为我们要求线性基行最简，那么若第 $p$ 位存在一个代表元，则这一列就只有 $p$ 可以是 $1$。放到题目里就是若 $k\in x$（就是说 $x$ 这一位为 $1$），那么若第 $k$ 小的代表元对应位置是 $p$，则 $y$ 的第 $p$ 为必定是 $1$。同理若 $k\notin x$，则 $y$ 的第 $p$ 位必定是 $0$。
于是我们就又能知道若干个“第 $i$ 小的代表元不能是 $j$”的限制，容易发现在这两个限制后，剩下的位就能随便乱填了。于是设 $dp_{i,j}$ 表示第 $i$ 小的代表元最高位为 $j$ 的方案数，若存在 $x$ 最高位为 $i$ 就只有一种填法，否则转移系数形如 $2^w$。
复杂度 $O(nm+n^3)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using i128=__int128;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i128 read(){
i128 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e5+5,inf=0x3f3f3f3f,mod=998244353;
int n,m,p2[130],mxb=-1;
i128 a[130],b[130];
bool insert(i128 x,i128 y){
fordown(i,n-1,0){
if((x>>i)&1){
if(a[i]){
x^=a[i];y^=b[i];
if(!x) break;
}else{
a[i]=x;b[i]=y;
return true;
}
}
}
return y==0;
}
int my_log2(i128 a){
int res=-1;
while(a){
a>>=1;++res;
}
return res;
}
bool ava[130][130];
void work(){
forup(i,0,n-1){
if(a[i]){
mxb=i;
int p=my_log2(b[i]);
ava[i][p]=1;
forup(j,0,i-1){
if((a[i]>>j)&1){
forup(k,0,p-1){
if(!((b[i]>>k)&1)){
ava[j][k]=0;
}
}
}else{
forup(k,0,p-1){
if((b[i]>>k)&1){
ava[j][k]=0;
}
}
}
}
}else{
forup(j,i,n-1){
ava[i][j]=1;
}
}
}
}
int get(int i,int j){
return a[i]?1:p2[j-i];
}
int dp[130][130];
signed main(){
n=read();m=read();
p2[0]=1;
forup(i,1,n) p2[i]=2ll*p2[i-1]%mod;
forup(i,1,m){
i128 x=read(),y=read();
--x;
if(!insert(x,y)){
puts("0");
return 0;
}
}
work();
forup(i,0,n-1) if(ava[0][i]) dp[0][i]=get(0,i);
forup(i,1,n-1){
forup(j,i,n-1){
if(!ava[i][j]) continue;
int f=get(i,j);
forup(k,0,j-1){
(dp[i][j]+=1ll*dp[i-1][k]*f%mod)%=mod;
}
}
}
int ans=0;
if(mxb==-1) ans=1,mxb=0;
forup(i,mxb,n-1){
forup(j,i,n-1){
(ans+=dp[i][j])%=mod;
}
}
printf("%d\n",ans);
}
[ARC126E] Infinite Operations
题意
- 给定一个长度为 $n$ 的序列 $a$，我们这样计算序列的权值：
- 选择 $i,j$ 满足 $a_i\ne a_j$，钦定 $a_i < a_j$。
- 选择一个实数 $x$ 满足 $a_i+x \le a_j-x$，$a_i\gets a_i+x,a_j\gets a_j-x$，并将 $x$ 累加进权值。
- 进行上述操作直至无法操作为止。
- 设这样能得到的最大权值为 $f(a)$，有 $m$ 次 $a$ 的单点修改，每次修改后输出 $f(a)$，注意计算权值并不会真正改变序列。
- $1\le n,m\le 3\times 10^5,1\le a_i\le 10^9$
题解
妙妙题，一开始想简单了，写完了才发现，最后还是看了题解。
钦定 $a$ 是单调不降的，即升序排列。
显然最后所有数都会变成全局平均数 $\bar{a}$。考虑怎样最大化权值。
如果你要从 $a_j$ 向 $a_i$ 扔 $x$，那么最优的必定是每次传给 $j-1$，这样能产生 $x(i-j)$ 的贡献。
那么每个 $i$ 能产生的贡献就是有多少数需要经过它运送，不难发现这个就等于 $\sum_{j=i}^na_i-\bar{a}$，然后随便推一推容易发现，答案就是：
$$ \begin{aligned} &\sum_{i=1}^ni\cdot a_i-\frac{n(n+1)}{2}\bar{a}\\ =&\sum_{i=1}^ni\cdot a_i-\frac{(n+1)}{2}\sum_{i=1}^n a \end{aligned} $$
后面的是好算的，前面的就是排名乘值，为了避免重复问题我们需要钦定相同数的排名不同，然后就变成了 $\sum x_iy_i$ 的问题了，其中 $x$ 单点修改，$y$ 区间修改，可以直接线段树维护，复杂度 $O((n+m)\log(n+m))$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=3e5+5,mod=998244353,inv2=(mod+1)/2;
int ksm(int a,int b){
int c=1;
while(b){
if(b&1) c=1ll*a*c%mod;
a=1ll*a*a%mod;
b>>=1;
}
return c;
}
int n,m,a[N],nd[N],sum,cnt[N<<1];;
vector<int> lsh;
int sz;
struct opr{
int x,y;
}s[N];
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
int sum[N<<3],num[N<<3],mark[N<<3];
void PushUp(int id){
sum[id]=(sum[id<<1]+sum[id<<1|1])%mod;
num[id]=(num[id<<1]+num[id<<1|1])%mod;
}
void PushDown(int id){
sum[id<<1]=(sum[id<<1]+1ll*num[id<<1]*mark[id]%mod)%mod;
sum[id<<1|1]=(sum[id<<1|1]+1ll*num[id<<1|1]*mark[id]%mod)%mod;
(mark[id<<1]+=mark[id])%=mod;
(mark[id<<1|1]+=mark[id])%=mod;
mark[id]=0;
}
void Modify(int L,int R,int X,int l=1,int r=n+m,int id=1){
if(L<=l&&r<=R){
(mark[id]+=X)%=mod;
(sum[id]+=1ll*X*num[id]%mod)%=mod;
return;
}
if(mark[id]) PushDown(id);
if(L<=mid) Modify(L,R,X,lson);
if(mid< R) Modify(L,R,X,rson);
PushUp(id);
}
void Update(int P,int X,int l=1,int r=n+m,int id=1){
if(l==r){
(num[id]+=X)%=mod;
(sum[id]+=1ll*X*mark[id]%mod)%=mod;
return;
}
if(mark[id]) PushDown(id);
if(P<=mid) Update(P,X,lson);
else Update(P,X,rson);
PushUp(id);
}
}mt;
signed main(){
n=read();m=read();
forup(i,1,n){
a[i]=read();
lsh.push_back(a[i]);
}
forup(i,1,m){
s[i].x=read();s[i].y=read();
lsh.push_back(s[i].y);
}
sort(lsh.begin(),lsh.end());
lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
sz=lsh.size();
forup(i,1,n){
int p=lower_bound(lsh.begin(),lsh.end(),a[i])-lsh.begin()+1;
(sum+=a[i])%=mod;
++cnt[p];
}
forup(i,1,m){
int p=lower_bound(lsh.begin(),lsh.end(),s[i].y)-lsh.begin()+1;
++cnt[p];
}
forup(i,1,sz) cnt[i]+=cnt[i-1];
forup(i,1,n){
int p=lower_bound(lsh.begin(),lsh.end(),a[i])-lsh.begin()+1;
nd[i]=cnt[p]--;
mt.Update(nd[i],a[i]);mt.Modify(nd[i],n+m,1);
}
forup(i,1,m){
int x=s[i].x,y=s[i].y;
mt.Update(nd[x],mod-a[x]);mt.Modify(nd[x],n+m,mod-1);
sum=(sum+mod-a[x])%mod;
a[x]=y;
int p=lower_bound(lsh.begin(),lsh.end(),a[x])-lsh.begin()+1;
nd[x]=cnt[p]--;
mt.Update(nd[x],a[x]);mt.Modify(nd[x],n+m,1);
(sum+=a[x])%=mod;
int res=mt.sum[1];
res=(res+mod-1ll*(n+1)*inv2%mod*sum%mod)%mod;
printf("%d\n",res);
}
}
P8978 「DTOI-4」中位数
题意
- 给定长度为 $n$ 的序列 $a$。你可以进行以下操作至多 $k$ 次：
- 选择一个区间 $[l,r]$，将区间内所有值替换为区间中位数。
- 此处对长度为 $len$ 的区间中位数的定义是排序后第 $\left\lceil\frac{len}{2}\right\rceil$ 小的数。
- 求 $k$ 次操作后全局最小值最大是多少。
- $1\le n\le 4\times 10^5$
题解
趣味妙妙题，只会抄题解。
首先不难想到二分答案，于是转化为判断答案能否大于等于 $mid$，将大于等于 $mid$ 的数置为 $1$，小于 $mid$ 的置为 $0$，每次选择一个 $1$ 严格多于 $0$ 的区间全变成 $1$，目标是将整个序列变为 $1$。
为了让这个操作更符合直觉，我们可以把所有 $0$ 赋值成 $-1$，每次就是选择一个区间和大于 $0$ 的区间全变成 $1$，为方便叙述，称这个序列的前缀和为 $s_i$。
不难发现，除去最后一次操作必定操作 $[1,n]$ 之外，必定每次操作的区间和都恰好是 $1$，否则拓展一下区间是不劣的，称这样的区间是“合法”的。
那么不难发现，每次操作消去 $0$ 的数量应是区间内 $1$ 的数量 $-1$，并且应恰好是 $\left\lfloor\frac{len}{2}\right\rfloor$。
然后一个想法是每次操作的区间应是互相包含的，即设每次操作的区间分别是 $I_1,I_2,\dots I_e$，有 $I_1\subseteq I_2\subseteq I_3\dots \subseteq I_e$，感性理解的话，因为第一次操作后最长的合法区间应该是包含它的，感觉上来说每次选最长的不会劣，但是怎么证呢？
证明
首先显然若两区间相交则必定包含，因为把后面的那个调整到包含前面的不会劣，于是证必定两两相交。
那么不妨设 $j$ 为最大的编号满足 $I_j$ 和 $I_{j+1}$ 不交则后面的必定有 $I_{j+1}\subseteq I_{j+2}\subseteq I_{j+3}\cdots\subseteq I_e$，又因为 $I_e=[1,n]$，则必定存在一个 $j+1\le p< e$ 满足 $I_{j}\cap I_p= \varnothing$ 且 $I_j\subseteq I_{p+1}$。
若 $|I_j|\ge |I_p|$，则我们可以把 $I_{j+1}\sim I_{p}$ 的区间全部删掉替换成一个区间 $I'$ 满足 $I_j\subseteq I'\subseteq I_{p+1}$，区间 $I'$ 至少能消去 $|I_j|-1$ 个 $0$，因为 $I_j$ 操作后里面全是 $1$，而因为 $I_{j+1}\subseteq I_{j+2}\cdots \subseteq I_{p}$，所以这一段至多只能消去 $|I_p|-1$ 个 $0$（区间 $I_p$ 内至少得有一个 $1$ 吧，事实上我们会发现他也不会多于 $|I_p|-2$），$|I_p|-1\le |I_j|-1$，那么显然这样做操作 $I_{p+1}$ 也是合法的。与之前的操作效果是相同的，并且操作数不会变多。
若 $|I_j| < |I_p|$，我们可以取消操作 $I$ 在 $I_p$ 后插入 $I_p\subseteq I'\subseteq I_{p+1}$，证明是类似的。
那么我们就可以每次将最后不交的调整为相交，必定能调整到两两包含。
然后我们不难发现，若有解至多只需要操作大约 $\log n$ 次，因为每次可以将连续 $1$ 的个数大致翻倍。并且不难发现有解当且仅当初始情况有子串 11 或 101。
于是考虑一个 DP，设 $dp_{i,l,r}$ 表示第 $i$ 次操作有没有可能是 $[l,r]$，转移可以找到区间内最大的 $[l',r']\subseteq [l,r]$ 满足 $dp_{i-1,l',r'}=1$，然后计算 $0,1$ 个数，大概能做到 $O(n^4\log n)$ check 吧。
注意到我们只关心最长的区间，不难想到我们可以改为 $f_{i,l}$ 表示最大的 $r$ 满足 $dp_{i,l,r}=1$ 是多少。考虑设 $c_i(l)=f_{i,l}-l+1-(s_{f_{i,l}}-s_{l-1})$，即操作 $[l,f_{i,l}]$ 消去了多少 $0$。于是转移就变成了找到最大的 $r$，满足存在 $p$ 使得 $s_r-s_{l-1}+c_{i-1}(p)\ge 1$，且 $r\ge f_{i-1,p}$，于是 $f_{i,l}=r$。不难发现若 $q < p$ 且 $f_{i-1,p} < f_{i-1,q}$，则 $f_{i-1,p}$ 就没用了，于是有用的转移区间是两两偏序的。
思考一下 $s_r-s_{l-1}+c_{i-1}(p)\ge 1$ 的限制，即 $s_{l-1}+1-c_{i-1}(p)\le s_r$，因为转移合法的条件是 $r\ge f_{i-1,p}$，而且其实我们也只需要找到最大的合法 $r$，所以我们可以维护 $g(i)$ 表示最大的 $r$ 满足 $s_r\ge i$，可以 $O(n)$ 预处理。
显然这个 $g(i)$ 是随着 $i$ 变小单调不降的，那么容易发现若 $a < b$ 且 $s_a\le s_b$，那么我们就不需要管 $f_{i,b}$ 了，因为 $f_{i,a}$ 必定能从 $f_{i,b}$ 相同的转移点转移过来，于是 $f_{i,a}$ 的区间必定包含 $f_{i,b}$ 的区间，根据上文显然 $f_{i,b}$ 就不可能往后转移。所以我们只需要关注取到 $s$ 前缀最小值的点了。
于是我们发现，随着 $l$ 往左移动，$s_{l-1}+1-c_{i-1}(p)$ 是单调不降的，则 $g(s_{l-1}+1-c_{i-1}(p))$ 也是单调左移的。又容易发现，若 $p < p'$ 并且 $c_{i-1}(p)\ge c_{i-1}(p')$，那么 $p'$ 的转移也是不优的，于是可以用单调队列维护 $p$，然后从右往左扫 $l$ 进行转移，check 的复杂度为 $O(n\log n)$，总复杂度 $O(n\log^2 n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=4e5+5,inf=0x3f3f3f3f;
int n,k,a[N];
int c[N],s[N];
int f[N],mxp[N<<1];
bool chk(int val){
bool flag=false;
mem(mxp,0);
int mn=n+1;
vector<int> seq;
forup(i,1,n){
c[i]=(a[i]>=val?1:-1);
s[i]=s[i-1]+c[i];
if(i>1&&c[i]==1&&c[i-1]==1) flag=true;
if(i>2&&c[i]==1&&c[i-2]==1) flag=true;
mxp[s[i]+n]=i;
if(s[i-1]<mn){
mn=s[i-1];
seq.push_back(i);
}
}
if(!flag) return false;
fordown(i,n*2,0){
mxp[i]=max(mxp[i],mxp[i+1]);
}
deque<pii> q;
reverse(seq.begin(),seq.end());
mem(f,0);
forup(p,1,k){
while(q.size()) q.pop_back();
for(auto i:seq){
if(f[i]){
int vv=f[i]-i+1-(s[f[i]]-s[i-1]);
while(q.size()&&vv>=q.back().se) q.pop_back();
q.push_back(mkp(f[i],vv));
}
while(q.size()){
int p=mxp[max(-n,s[i-1]+1-q.front().se)+n];
if(p>=q.front().fi){
f[i]=p;break;
}
q.pop_front();
}
if(q.empty()){
int p=mxp[max(-n,s[i-1]+1)+n];
f[i]=p;
}
}
if(f[1]==n) return true;
}
return false;
}
signed main(){
n=read();k=read();
forup(i,1,n){
a[i]=read();
}
if(k==0){
int mn=inf;
forup(i,1,n) mn=min(mn,a[i]);
printf("%d\n",mn);
return 0;
}
int ll=0,rr=1e9,mm;
while(ll<rr){
mm=(ll+rr+1)>>1;
if(chk(mm)) ll=mm;
else rr=mm-1;
}
printf("%d\n",ll);
}
[ABC230G] GCD Permutation
题意
-
给定长度为 $n$ 的排列 $a$，求：
$$ \sum_{i=1}^n\sum_{j=i}^n[\gcd(i,j)\ne 1\land \gcd(a_i,a_j)\ne 1] $$
-
其中中括号是艾佛森括号，若内部表达式为真值为 $1$，否则为 $0$，下同。
- $1\le n\le 2\times 10^5$
题解
简单题。
注意到两个 $\gcd$ 同时不为 $1$ 不太好搞，不妨先解决其中一个。
考虑设 $f(k)$ 表示将下标为 $k$ 倍数的数拎出来，所得到的不互质的数对数。
显然直接算 $\sum_{k=2}^nf(k)$ 是不对的，会算重，于是考虑何时会算重。容易发现只要 $k\mid \gcd(i,j)$，那么 $i,j$ 之间的答案就会在 $k$ 处被统计一遍，于是我们希望找到一个容斥系数 $g(i)$，使得对于 $p\ge 2$ 有 $\sum_{k\mid p}^{k\ge 2}g(k)=1$，注意到其实就是 $(g\ast I)(p)-g(1)=1$，一眼瞪出 $g(i)$ 可以取 $-\mu(i)$。于是答案就是 $\sum_{k=2}^n-\mu(k)f(k)$，那么考虑如何计算 $f$。
相当于给定一个长度为 $L=\left\lfloor\frac{n}{k}\right\rfloor$ 的序列 $b$，求出 $\sum_{i=1}^L\sum_{j=i}^L[\gcd(b_i,b_j)\ne 1]=\frac{L(L+1)}{2}-\sum_{i=1}^L\sum_{j=i}^L[\gcd(b_i,b_j)=1]$，于是只看后者，考虑很经典地推一推式子：
$$ \begin{aligned} &\sum_{i=1}^L\sum_{j=i}^L[\gcd(b_i,b_j)= 1]\\ &\sum_{i=1}^L\sum_{j=i}^L\sum_{d\mid \gcd(b_i,b_j)}\mu(d)\\ &\sum_{d}\mu(d)\frac{cnt_d(cnt_d+1)}{2}\\ \end{aligned} $$
其中 $cnt_d=\sum_{i=1}^L[d\mid b_i]$，即 $b$ 中 $d$ 倍数的数量。
发现 $cnt_d$ 的总和大致是 $O(L\max\tau(b_i))\approx O(L\sqrt[3]{n})$ 级别的（其中 $\tau$ 表示因数个数），而我们枚举的 $d$ 也只需要枚举 $b$ 的因数。根据经典结论，$\sum L$ 是 $O(n\log n)$ 级别的，于是总复杂度大约是 $O(n\log n\sqrt[3]{n})$，实际上因为 $\tau$ 取满上界的点并不多，应该会略小于这个数。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=2e5+5;
i64 n,a[N],ans;
i64 vv[N],mu[N];
vector<i64> pri;
vector<i64> fct[N];
void init(i64 n){
mu[1]=1;
forup(i,2,n){
if(!vv[i]){
mu[i]=-1;
pri.push_back(i);
}
for(auto j:pri){
if(1ll*i*j>n) break;
if(i%j){
mu[i*j]=-mu[i];
vv[i*j]=1;
}else{
mu[i*j]=0;
vv[i*j]=1;
break;
}
}
}
}
vector<i64> vec;
i64 cnt[N];
i64 work(){
i64 sz=vec.size();
i64 res=sz*(sz+1)/2;
vector<i64> seq;
for(auto i:vec){
for(auto j:fct[i]){
seq.push_back(j);
++cnt[j];
}
}
sort(seq.begin(),seq.end());
seq.erase(unique(seq.begin(),seq.end()),seq.end());
for(auto i:seq){
res-=mu[i]*cnt[i]*(cnt[i]+1)/2;
cnt[i]=0;
}
return res;
}
signed main(){
n=read();
init(n);
forup(i,1,n){
for(i64 j=i;j<=n;j+=i){
fct[j].push_back(i);
}
}
forup(i,1,n){
a[i]=read();
}
forup(i,2,n){
if(!mu[i]) continue;
vec.clear();
for(i64 j=i;j<=n;j+=i){
vec.push_back(a[j]);
}
ans-=mu[i]*work();
}
printf("%lld\n",ans);
}
[ABC225F] String Cards
题意
- 给定 $n$ 个字符串，求从其中选 $k$ 个任意排序拼起来能得到的字典序最小的字符串。
- $1\le k\le n\le 50,1\le |S_i|\le 50$
题解
套路题。
字符串拼接的最小字典序有经典邻项交换法确认顺序的套路，具体来说，我们按 $a+b < b+a$ 的顺序将字符串排列即可，其中 $+$ 代表连接字符串，$<$ 指字典序比较。
为什么呢？考虑将字符串视为一个 $p$ 进制数，$a,b$ 的长度分别是 $la,lb$，于是：
$$ \begin{aligned} a\times p^{lb}+b &< b\times p^{la}+a\\ a\times (p^{lb}-1) &< b\times (p^{la}-1)\\ \frac{a}{p^{la}-1} &< \frac{b}{p^{lb}-1}\\ \end{aligned} $$
显然是具有传递性的。
然后就变成从字符串序列中选一个长度为 $k$ 的子序列连起来最小化字典序了。套路是倒着 DP，设 $f_{i,j}$ 表示考虑 $[i,n]$ 的字符串，选择 $j$ 个的字典序，转移是简单的。
复杂度 $O(n^4)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=55,inf=0x3f3f3f3f;
int n,k;
string str[N];
string dp[N];
signed main(){
n=read();k=read();
forup(i,1,n){
cin>>str[i];
}
sort(str+1,str+n+1,[&](string a,string b){return a+b<b+a;});
forup(i,1,k){
dp[i]="{";
}
dp[0]="";
fordown(i,n,1){
fordown(j,k,1){
if(str[i]+dp[j-1]<dp[j]) dp[j]=str[i]+dp[j-1];
}
}
cout<<dp[k];
}
[AGC016D] XOR Replace
题意
- 给定两长度为 $n$ 的序列 $a,b$，你可以进行任意次以下操作：
- 将 $a$ 的某个位置赋值为 $a$ 整个序列的异或和。
- 求将 $a$ 变成 $b$ 至少需要操作多少次，无解输出 $-1$。
- $1\le n\le 1\times 10^5,0\le a_i < 2^{30}$
题解
趣味题。
考虑手思考一下“赋值为 $a$ 整个序列的异或和”这个操作，假设我们对 $a_i$ 操作，原序列异或和为 $s$，那么新的异或和就变为了 $s\oplus a_i\oplus s=a_i$，相当于将 $a_i$ 和 $s$ 互换。
那么相当于有 $n+1$ 个小球和 $n$ 个盒子，每个小球有颜色，初始为序列 $a$，每次将不在盒子里的那个小球与另一小球交换，问至少需要交换多少次才能让颜色序列变为 $b$。
显然无解当且仅当某种颜色的小球数量对不上，可以直接判掉，考虑怎么求最小操作数。
不难想到对颜色进行图论建模，连边 $(a_i,b_i)$，首先所有不是自环的边需要一次操作，其次除去多出的那个小球所在的连通块以外，每个大小大于 $1$ 的连通块还需要额外一次操作。
具体考虑每个连通块都是一个欧拉回路，唯独多出来的那个小球如果在某个连通块，那么这个连通块是一个不是回路的欧拉路，其余每个连通块都需要在离开的时候将原来的小球换回去，只有他自己不需要。
复杂度 $O(n\log n)$，瓶颈在离散化。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e5+5,inf=0x3f3f3f3f;
int n,a[N],b[N],ans;
map<int,int> cnt;
vector<int> lsh;
int sz;
vector<int> e[N];
bool vis[N];
int cc=0;
void dfs(int x){
vis[x]=1;++cc;
for(auto i:e[x]){
if(vis[i]) continue;
dfs(i);
}
}
signed main(){
n=read();
int sum=0;
forup(i,1,n){
a[i]=read();
sum^=a[i];
++cnt[a[i]];
lsh.push_back(a[i]);
}
++cnt[sum];
lsh.push_back(sum);
sort(lsh.begin(),lsh.end());
lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
sz=lsh.size();
forup(i,1,n){
b[i]=read();
--cnt[b[i]];
if(cnt[b[i]]<0){
puts("-1");
return 0;
}
}
ans=0;
forup(i,1,n){
a[i]=lower_bound(lsh.begin(),lsh.end(),a[i])-lsh.begin();
b[i]=lower_bound(lsh.begin(),lsh.end(),b[i])-lsh.begin();
if(a[i]!=b[i]){
e[b[i]].push_back(a[i]);
e[a[i]].push_back(b[i]);
++ans;
}
}
sum=lower_bound(lsh.begin(),lsh.end(),sum)-lsh.begin();
dfs(sum);
forup(i,0,sz-1){
if(!vis[i]){
int pc=cc;
dfs(i);
ans+=(cc-pc>1);
}
}
printf("%d\n",ans);
}
[AGC017D] Game on Tree
题意
- 给定一棵 $n$ 个点的树，Alice 和 Bob 在这棵树上玩一个游戏。
- Alice 先手，两人轮流选择一条边断掉，然后保留点 $1$ 所在连通块。
- 不能操作者输，求谁必胜。
- $1\le n\le 10^5$
题解
唉，博弈论太牛了，完全做不来。
首先显然这是个有向图博弈，考虑 SG 函数，又因为是树上问题，思考能否将每个子树的信息独立开，这样就能直接树形 DP 了。
首先不难发现，对于某个点，它每个儿子的游戏是两两无关的，如果是每个儿子都是链就是裸 Nim 游戏了。
那么考虑如果将一个这样的游戏从树根 $u$ 处往上再连一个结点 $v$，SG 函数的值会如何变化。不难发现就是原游戏所有状态新增一个后继 $0$，然后原游戏获胜状态 SG 函数值变为 $1$，那么对于原游戏为 $sg=0$ 的状态，新增唯一后继 $0$ 后 SG 值就变为 $1$ 了，于是原游戏 $sg=1$ 的状态值就变为二了，那么不难发现新游戏的 SG 值就等于原游戏 SG 值 $+1$。
于是设 $sg_i$ 表示以 $i$ 为根的子树的 $sg$ 值，dfs 直接 DP 求出即可，复杂度 $O(n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e5+5,inf=0x3f3f3f3f;
int n,sg[N];
vector<int> e[N];
void dfs(int x,int fa){
sg[x]=0;
for(auto i:e[x]){
if(i==fa) continue;
dfs(i,x);
sg[x]^=(sg[i]+1);
}
}
signed main(){
n=read();
forup(i,1,n-1){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1,0);
puts(sg[1]?"Alice":"Bob");
}
[AGC016F] Games on DAG
题意
- 给定一张 $n$ 个点 $m$ 条边的 DAG，点 $1$ 和点 $2$ 各有一颗棋子，两人轮流移动棋子，可以将任意一颗棋子移到相邻的点上（注意边有向），两棋子可以放在同一格。
- 问 $2^m$ 种保留边的方案中，有多少种能使先手必胜。
- $1\le n\le 15$，无重边。
题解
博弈论趣味题。
显然两棋子相当于两独立的有向图博弈，那么先手必胜当且仅当 $sg_1\oplus sg_2\ne 0$，其中 $\oplus$ 表示按位异或，下同。
显然求 $sg_1\oplus sg_2= 0$ 的情况更简单，相当于要求两点 $sg$ 值相同。
考虑一个很妙的性质：对于一个有向图博弈游戏，若在保留该游戏原图的基础上新增若干 $0$ 状态，且原游戏所有点均向任意 $0$ 状态连边，则原本的所有点有 $sg_i'\gets sg_i+1$，证明可以数学归纳法，原本为 $0$ 的显然变为 $1$，那么原本为 $1$ 的就变成 $2$，依此类推。
又看到 $n$ 的范围很小，那么不难想到 DP，设 $dp_{msk}$ 表示仅考虑点集 $msk$ 的导出子图（显然 $1,2\in msk$ 才有用），有多少种方案使得点 $1,2$ 在同一层，转移就枚举 $S$ 表示集合 $S$ 内均有 $sg_i=0$，设 $T=msk\setminus S$，显然 $S$ 之内不能互相连边（否则后继的 $\mathrm{mex}$ 就不是 $0$ 了），$T$ 内每个点必须向 $S$ 连边（根据先前的性质）。容易发现 $1,2$ 要么都在 $S$ 内要么都在 $T$ 内，否则两点 $sg$ 值就不可能相等了。若 $1,2\in S$，则除去上面的限制以外，$T$ 内部可以随便乱连。若 $1,2\in T$，则从 $dp_T$ 转移过来，然后按上面的限制计算容斥系数即可。
因为需要枚举子集，复杂度 $O(3^nn)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=20,inf=0x3f3f3f3f,mod=1e9+7;
int n,m,p2[N*N],al;
int grp[N];
int dp[1<<15];
int calc(int i,int msk){
return p2[__builtin_popcount(grp[i]&msk)];
}
signed main(){
n=read();m=read();
al=(1<<n)-1;
p2[0]=1;
forup(i,1,m) p2[i]=2ll*p2[i-1]%mod;
forup(i,1,m){
int u=read(),v=read();
--u;--v;
grp[u]|=(1<<v);
}
dp[0]=1;
for(int msk=3;msk<=al;msk=(msk+1)|3){
for(int t=msk;t;t=(t-1)&msk){
if((t&1)!=((t>>1)&1)) continue;
if((t&1)){
int s=msk^t,val=1;
forup(i,0,n-1){
if(!((msk>>i)&1)) continue;
if((s>>i)&1){
val=1ll*val*(calc(i,t)-1)%mod*calc(i,s)%mod;
}else{
val=1ll*val*calc(i,s)%mod;
}
}
(dp[msk]+=val)%=mod;
}else{
int s=msk^t,val=dp[s];
forup(i,0,n-1){
if(!((msk>>i)&1)) continue;
if((s>>i)&1){
val=1ll*val*(calc(i,t)-1)%mod;
}else{
val=1ll*val*calc(i,s)%mod;
}
}
(dp[msk]+=val)%=mod;
}
}
}
printf("%d\n",(p2[m]+mod-dp[al])%mod);
}
P6631 [ZJOI2020] 序列
题意
- 给定一个长度为 $n$ 的正整数序列 $a$，你可以进行以下三种操作任意次：
- 选择一个区间，将区间内每个数 $-1$。
- 选择一个区间，将区间内下标为奇数的数全部 $-1$。
- 选择一个区间，将区间内下标为偶数的数全部 $-1$。
- 问最少需要多少次操作才能让整个序列全部变为 $0$。
- $1\le n\le 10^5$，带多测，$1\le T\le 10$。
题解
好像是线性规划版题，但是我不会线性规划。但是可以贪心。
对于 $a_1$，不难发现尽量进行操作一是不劣的，可以考虑一些调整法，若不进行操作一后面就需要用另外两种操作补齐，一个操作二加一个操作三个贡献显然不优于单个操作一。
那么贪心地进行操作一，然后剩下的用操作二/三解决后，$a_1$ 就变成 $0$ 了，后面的怎么办呢？
考虑从 $i-1$ 和 $i-2$ 处分别传来了 $X$ 个操作一和 $Y$ 个操作二/三，若 $X+Y\le a_i$ 则保留这些所有操作必定必定不劣，否则我们发现除去必须保留 $a_i-\min(a_i,X)$ 个操作二和 $a_i-\min(a_i,Y)$ 个操作一以外，剩下的 $X+Y-a_i$ 个操作都是自由的，即可以随便选择操作一二。
那么我们不考虑这些操作，把 $a_i$ 当成 $a_1$ 来做，显然任意从 $a_i$ 开始的操作都能用这些替换，那么我们尽量多地使用这些操作即可，这样就不会对答案产生贡献了。
复杂度 $O(n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=2e5+5,inf=0x3f3f3f3f;
i64 n,a[N];
void solve(){
n=read();
forup(i,1,n){
a[i]=read();
}
i64 X=0,Y=0,PY=0,ans=0;
a[n+1]=0;
forup(i,1,n){
X=min(X,a[i]);Y=min(Y,a[i]);
i64 W=0;
if(X+Y>a[i]){
i64 ny=a[i]-X,nx=a[i]-Y;
X=nx,Y=ny;
W=a[i]-X-Y;
}
a[i]-=(X+Y);
i64 nv=a[i+1]-X-PY;
if(a[i]){
if(nv>0){
i64 cc=min(a[i],nv);
ans+=max(cc-W,0ll);W=max(W-cc,0ll);
X+=cc;a[i]-=cc;
}
i64 cc=a[i];
ans+=max(cc-W,0ll);W=max(W-cc,0ll);
Y+=cc;a[i]-=cc;
}
swap(Y,PY);
}
printf("%lld\n",ans);
}
signed main(){
i64 t=read();
while(t--){
solve();
}
}
CF2039E Shohag Loves Inversions
题意
- 称一个正整数序列是合法的当且仅当该序列可以通过序列 $a=[0,1]$ 进行若干次如下操作得到：
- 将 $a$ 的逆序对数量 $x$ 插入 $a$ 中，如序列 $[3,1,2]$ 的逆序对数为 $2$，那么操作一次可能得到 $[2,3,1,2],[3,2,1,2],[3,1,2,2]$。
- 求有多少个本质不同的长度为 $n$ 的合法序列。
- $1\le n\le 10^6$，带多测，$\sum n\le 10^6$
题解
细心想一想就能过的简单题。据说能用 OEIS 做。
但是我这场没打，哎哟能上分的场没一场打了。
不难发现对于一个合法序列，每次插入的数是单调不减的（逆序对数显然不会随着插入减小），那么考虑插入的数相同的操作段有什么特点，注意到除去 $0，1$ 的情况外，插入的数必定大于它之前的区间最大值（毕竟是单调不减的），那么这样的操作段除了最后一次之外，必定是每次都插在区间末尾，只有最后一次放在前面的。为方便叙述，称这最后一次操作为“转折操作”。
不难发现，最终序列和转折操作（包括在操作时间轴上的位置和在序列上的位置）构成的序列是一一对应的，于是对转折操作进行 DP，设 $f_i$ 表示长度为 $i$，且上一次操作为转折操作（但是不考虑这次操作是 $0$ 或 $1$ 的情况）的合法序列数，转移就枚举上一次转折操作 $j$，有转移：
$$ f_{i}=\sum_{j=2}^{i-1}f_j\times j+j-1 $$
其中 $f_j\times j$ 是因为这最后一次转折操作有 $i-1$ 种插法（举个例子，$1,0,1,0$ 这个序列进行若干次非转折操作可能变成了 $1,0,1,0,3,3\dots$，但是最后一次转折操作只能插在前四个数的前面），后面的 $j-1$ 表示 $1$ 转折到更大的数的情况，容易发现 $1$ 转折到更大的数的序列必定形如 $0,0,\dots ,0,1,0$ 加上若干非转折的 $1$，于是转折操作 $1$ 只有 $j-1$ 种插入方法，因为 $1$ 的前后插入得到的序列是相同的。
转移可以前缀和优化，那么答案就是 $f$ 的前缀和加上只有 $0,1$，并且逆序对数也是 $0$ 或 $1$ 的合法序列数，可以在算前缀和时一并统计，复杂度 $O(n+t)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e6+5,inf=0x3f3f3f3f,mod=998244353;
int n,f[N],g[N];
void solve(){
n=read();
printf("%d\n",g[n]);
}
signed main(){
int n=1e6,sum=0;
forup(i,2,n){
f[i]=sum;
g[i]=(g[i-1]+f[i]+1)%mod;
(sum+=1ll*f[i]*i%mod)%=mod;
if(i>=3) (sum+=i-1)%=mod;
}
int t=read();
while(t--){
solve();
}
}
[AGC004E] Salvage Robots
题意
- 有一个 $n\times m$ 的地图，上面有一些机器人和一个出口。
- 你可以命令所有机器人向某个方向移动，若机器人走出地图边缘就会消失，若进入出口就会被解救。
- 问你最多能解救多少个机器人。
- $1\le n,m\le 100$
题解
细心想一想就能过的简单题，但是经典唐诗错误之 $m:=n$ 给我挂了一发。
考虑以出口为原点的四个象限，容易发现除去最大的那个以外，对于剩下的三个象限，都存在能全部取完的方案。
思考一下为什么，不妨设最大的象限是第二象限（进行若干翻转操作即可，另外这样下来最小的象限就是第四象限），对于第一象限，可以每次取完一行，然后整体向下平移，这样就不会有要取的机器人走出地图了。
那么推广到一般情况，设出口距离左右边界的距离分别是 $sx,px$，距上下边界的距离分别是 $sy,py$。首先任意方案能取到的所有机器人必定能用一个 $sx\times sy$ 的矩形框起来，那么不妨把要取的矩形（显然只有 $O(nm)$ 种）先挪到第二象限，不难发现，我们只要向下平移超过 $py$ 步最下面的一行就会消失（另一边同理），在保证另一边不消失的情况下，我们这一行最多只能取最后 $px$ 个点里面的机器人。
不妨对消失的行列进行 DP，设 $dp_{i,j}$ 表示大于 $i$ 的行，大于 $j$ 的列全都消失，剩下最多能解救多少个机器人。转移就考虑下一次是行消失还是列消失，若行消失，则从 $dp_{i-1,j}$ 转移过来，并且加上这一行最多产生多少贡献。具体转移方程略。
复杂度 $O(n^4)$，但是常数极小。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=105,inf=0x3f3f3f3f;
int n,m,a[N][N];
int sum[N][N];
int calc(int xl,int xr,int yl,int yr){
return sum[xr][yr]-sum[xl-1][yr]-sum[xr][yl-1]+sum[xl-1][yl-1];
}
char str[N];
int sx,sy,dp[N][N];
signed main(){
n=read();m=read();
forup(i,1,n){
scanf(" %s",str+1);
forup(j,1,m){
a[i][j]=(str[j]=='o');
if(str[j]=='E'){
sx=i;sy=j;
}
}
}
if(sx<n-sx+1){
sx=n-sx+1;
forup(i,1,n/2){
forup(j,1,m){
swap(a[i][j],a[n-i+1][j]);
}
}
}
if(sy<m-sy+1){
sy=m-sy+1;
forup(i,1,n){
forup(j,1,m/2){
swap(a[i][j],a[i][m-j+1]);
}
}
}
msg("%d %d|\n",sx,sy);
forup(i,1,n){
forup(j,1,m){
msg("%d ",a[i][j]);
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
}
msg("|\n");
}
int px=n-sx+1,py=m-sy+1;
int ans=0;
forup(x,1,px){
forup(y,1,py){
forup(i,px,sx){
forup(j,py,sy){
dp[i][j]=0;
}
}
dp[px][py]=calc(x,x+px-1,y,y+py-1);
forup(i,px,sx){
forup(j,py,sy){
if(i==px&&j==py) continue;
dp[i][j]=max(dp[i-1][j]+calc(x+i-1,x+i-1,y+j-py,y+j-1),dp[i][j-1]+calc(x+i-px,x+i-1,y+j-1,y+j-1));
}
}
ans=max(ans,dp[sx][sy]);
}
}
printf("%d\n",ans);
}
P4403 [BJWC2008] 秦腾与教学评估
题意
- 有一个序列 $a$，初始全为 $0$，进行 $n$ 次以下操作：
- 给定 $s,e,d$，将所有满足 $s\le i\le e$ 且 $(i-s)\bmod d=0$ 的 $a_i$ 加一。
- 保证操作后序列上至多有一个点值为奇数，找出这个点（输出下标和值），或报告不存在。
- $1\le n\le 2\times 10^5$
题解
其实挺妙的。
因为只有至多一个点是奇数，那么包含这个点的前缀的前缀和必定是奇数，不包含的必定是偶数。
而我们可以 $O(n)$ 计算一个前缀的和，于是 $O(n\log V)$ 二分即可。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=2e5+5,inf=0x3f3f3f3f;
i64 n,s[N],e[N],d[N];
bool chk(i64 pos){
i64 sum=0;
forup(i,1,n){
if(pos>=s[i]) sum+=(min(pos,e[i])-s[i])/d[i]+1;
}
return sum%2==0;
}
i64 calc(i64 pos){
i64 res=0;
forup(i,1,n){
if(s[i]<=pos&&pos<=e[i]&&(pos-s[i])%d[i]==0){
++res;
}
}
return res;
}
void solve(){
n=read();
i64 mx=0;
forup(i,1,n){
s[i]=read();e[i]=read();d[i]=read();
mx=max(mx,e[i]);
}
i64 ll=0,rr=mx+1,mm;
while(ll<rr){
mm=(ll+rr)>>1;
if(chk(mm)) ll=mm+1;
else rr=mm;
}
if(ll>mx){
puts("Poor QIN Teng:(");
}else{
printf("%lld %lld\n",ll,calc(ll));
}
}
signed main(){
i64 t=read();
while(t--){
solve();
}
}
P5211 [ZJOI2017] 字符串
题意
- 有一个长度为 $n$ 的字符串 $s$，字符集是整数集。
- 有两个操作共 $m$ 次：
- 区间加某个整数 $d$。
- 查询区间字典序最小的后缀的下标（假如答案是 $s[p:r]$，应输出 $p$）。
- $1\le n\le 2\times 10^5,1\le m\le 2\times 10^4,|s_i|\le 10^8,|d|\le 1000$
题解
显然我们不可避免地需要维护两区间的合并。
考虑一个区间“可能成为某超区间最小后缀”的 $p$（即存在 $d$ 使得 $s[p:r]+d$ 是区间最小后缀）具有什么性质。不难发现所有可能的后缀必定是最长的那个的 Border。但是仍然不好做。
继续观察性质，注意到任意两后缀 $u,v$ 满足 $|u| < |v|$ 必定有 $2|u| < |v|$，根据 Border 循环的性质，若 $2|u| \ge |v|$，则 $v-u$ 是一个循环节，于是设 $u=t+w$，其中 $t$ 是循环节，那么 $v=t+t+w$，设后面接上了字符串 $d$，设 $u+d < v+d$，即 $t+w+d < t+t+w+d$，根据字典序的定义有 $w+d < t+w+d$，那么 $w+d < u+d$，说明 $u$ 后面无论怎么加都不可能同时小于 $u+d$ 和 $w+d$，不可能是最小后缀。
于是长度为 $len$ 的区间中“可能的 $p$”至多只有 $O(\log len)$ 个。考虑使用线段树维护区间合并，由于左右两区间长度差不超过 $1$（并且通常写法中右边的更长），所以左边区间至多贡献一个 $p$，合并时两两比较字典序即可。但是这个字典序比较因为要支持修改所以需要哈希加二分。注意到哈希值修改次数是 $O(m)$ 的，查询次数是 $O(n\log n+m\log^2 n)$ 的，那么可以使用 $O(\sqrt{n})-O(1)$ 的分块维护，总复杂度 $O(n\log^2n+m\log^3n+m\sqrt{n})$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using u32=unsigned int;
using u64=unsigned long long;
using u128=__uint128_t;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5;
int n,m,a[N];
const int B=450;
const u64 P=1e9+7,M=(1ull<<61)-1;
int L[N/B+10],R[N/B+10],blg[N],T;
struct modint61{//哈希使用了模 2^61-1 的科技
u64 v;
modint61():v(0ull){}
modint61(int _v):v(_v<0?_v+M:_v){}
modint61(u64 _v):v(_v){}
modint61 operator +(const modint61 &r){
u64 t=v+r.v;
if(t>=M) t-=M;
return modint61(t);
}
modint61 operator -(const modint61 &r){
u64 t=v-r.v;
if(t>=M) t+=M;
return modint61(t);
}
modint61 operator *(const modint61 &r){
u128 t=(u128)v*r.v;
t=(t>>61)+(t&M);
if(t>=M) t-=M;
return modint61((u64)t);
}
bool operator ==(const modint61 &r){
return v==r.v;
}
}pw[N],pv[N],preb[N/B+10],prec[N/B+10][B+10];
int tag[N/B+10];
void initb(){
T=n/B;
forup(i,1,T){
L[i]=R[i-1]+1;R[i]=i*B;
forup(j,L[i],R[i]){
blg[j]=i;
}
}
if(R[T]<n){
++T;
L[T]=R[T-1]+1;R[T]=n;
forup(j,L[T],R[T]){
blg[j]=T;
}
}
forup(b,1,T){
forup(i,L[b],R[b]){
prec[b][i-L[b]+1]=(prec[b][i-L[b]]*P+(u64)a[i]);
}
preb[b]=(preb[b-1]*pw[R[b]-L[b]+1]+prec[b][R[b]-L[b]+1]);
}
}
void pushblk(int p){
if(!tag[p]) return;
forup(i,L[p],R[p]){
a[i]+=tag[p];
}
tag[p]=0;
forup(i,L[p],R[p]){
prec[p][i-L[p]+1]=(prec[p][i-L[p]]*P+(u64)a[i]);
}
}
void modify(int l,int r,int v){
if(blg[l]==blg[r]){
int p=blg[l];
pushblk(p);
forup(i,l,r) a[i]+=v;
forup(i,L[p],R[p]) prec[p][i-L[p]+1]=(prec[p][i-L[p]]*P+(u64)a[i]);
}else{
int pl=blg[l],pr=blg[r];
pushblk(pl);
forup(i,l,R[pl]) a[i]+=v;
forup(i,L[pl],R[pl]) prec[pl][i-L[pl]+1]=(prec[pl][i-L[pl]]*P+(u64)a[i]);
pushblk(pr);
forup(i,L[pr],r) a[i]+=v;
forup(i,L[pr],R[pr]) prec[pr][i-L[pr]+1]=(prec[pr][i-L[pr]]*P+(u64)a[i]);
forup(i,pl+1,pr-1){
tag[i]+=v;
}
}
forup(b,1,T){
modint61 vb=(prec[b][R[b]-L[b]+1]+pv[R[b]-L[b]]*tag[b]);
preb[b]=(preb[b-1]*pw[R[b]-L[b]+1]+vb);
}
}
modint61 getpre(int l){
int p=blg[l];
modint61 vb=(prec[p][l-L[p]+1]+pv[l-L[p]]*tag[p]);
return (preb[p-1]*pw[l-L[p]+1]+vb);
}
modint61 getval(int l,int r){
if(l>r) return 0;
return (getpre(r)-getpre(l-1)*pw[r-l+1]);
}
int cmp(int l1,int l2,int r){
int len=min(r-l1,r-l2);
if(getval(l1,l1+len)==getval(l2,l2+len)) return 0;
int ll=0,rr=len,mm;
while(ll<rr){
mm=(ll+rr)>>1;
if(getval(l1,l1+mm)==getval(l2,l2+mm)) ll=mm+1;
else rr=mm;
}
// msg("[%d]\n",ll);
return a[l2+ll]+tag[blg[l2+ll]]<a[l1+ll]+tag[blg[l1+ll]]?1:-1;
}
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
vector<int> vec[N<<2];
void PushUp(int id,int rr){
int mx=vec[id<<1].front();
for(auto i:vec[id<<1]){
int res=cmp(mx,i,rr);
if(res==1) mx=i;
}
int val=cmp(mx,vec[id<<1|1].front(),rr);
vec[id].clear();
if(val==1){
vec[id]=vec[id<<1|1];
}else{
vec[id].push_back(mx);
for(auto i:vec[id<<1|1]){
if(cmp(mx,i,rr)!=-1) vec[id].push_back(i);
}
}
}
void Build(int l=1,int r=n,int id=1){
if(l==r){
vec[id].push_back(l);
return;
}
Build(lson);Build(rson);
PushUp(id,r);
}
void Modify(int L,int R,int l=1,int r=n,int id=1){
if(L<=l&&r<=R){
return;
}
if(L<=mid) Modify(L,R,lson);
if(mid< R) Modify(L,R,rson);
PushUp(id,r);
}
int Query(int L,int R,int l=1,int r=n,int id=1){
if(L<=l&&r<=R){
int mn=vec[id].front();
for(auto i:vec[id]){
int res=cmp(mn,i,R);
if(res!=-1) mn=i;
}
return mn;
}
if(R<=mid){
return Query(L,R,lson);
}else if(mid<L){
return Query(L,R,rson);
}else{
int rl=Query(L,R,lson),rr=Query(L,R,rson);
if(cmp(rl,rr,R)==-1) return rl;
else return rr;
}
}
}mt;
signed main(){
n=read();m=read();
pw[0]=pv[0]=1;
forup(i,1,n){
pw[i]=pw[i-1]*P;
pv[i]=pv[i-1]*P+1;
}
forup(i,1,n){
a[i]=read();
a[i]+=5e8;
}
initb();
mt.Build();
forup(i,1,m){
int op=read();
if(op==1){
int l=read(),r=read(),d=read();
modify(l,r,d);
mt.Modify(l,r);
}else{
int l=read(),r=read();
printf("%d\n",mt.Query(l,r));
}
}
}