Contest Link
\(\text{By DaiRuiChen007}\)
*A. [CF2097F] Lost Luggage (7.5)
Problem Link
先建立网络流,每层的点 \(i\) 向下一层 \(i-1,i,i+1\) 分别连权值 \(a_i,b_i,c_i\) 的边,答案就是到每层的最大流。
最大流不好处理,考虑求最小割。
那么可以直接 dp,\(f_{i,s}\) 表示到第 \(i\) 层,源点可达的点集是 \(s\) 的最小割。
朴素转移 \(f_{i,s}\to f_{i+1,t}\) 是 \(4^n\) 的,但注意到转移代价之和 \(s,t\) 中相邻的位有关,因此可以逐步计算贡献、
具体来说,我们从前往后确定 \(t\) 的每一位并计算贡献,设当前已确定 \(t[0,x)\),那么只要维护 \(t[0,x-1],s[x-1,n]\) 以及 \(s_0\) 就行,状态数 \(\mathcal O(n2^n)\)。
时间复杂度 \(\mathcal O(nm2^n)\)。
#include<bits/stdc++.h>
using namespace std;
int a[12],b[12],c[12],dp[1<<12],h[1<<12],f[1<<12][2],g[1<<12][2];
inline void chkmin(int &x,const int &y) { x=y<x?y:x; }
void solve() {int n,m; cin>>n>>m;memset(dp,0,sizeof(dp));for(int i=0,x;i<n;++i) {cin>>x;for(int s=0;s<(1<<n);++s) if(!(s>>i&1)) dp[s]+=x;}for(int t=1;t<=m;++t) {for(int i=0;i<n;++i) cin>>a[i];for(int i=0;i<n;++i) cin>>b[i];for(int i=0;i<n;++i) cin>>c[i];memset(h,0x5f,sizeof(h));for(int e:{0,1}) {memset(f,0x5f,sizeof(f));for(int s=0;s<(1<<n);++s) if((s&1)==e) chkmin(f[s][s>>(n-1)&1],dp[s]);for(int i=0;i<n;++i) {int L=c[(i+n-1)%n],R=a[(i+1)%n];memset(g,0x5f,sizeof(g));for(int s=0;s<(1<<n);++s) for(int x:{0,1}) {chkmin(g[s|1<<i][s>>i&1],f[s][x]);chkmin(g[s&~(1<<i)][s>>i&1],f[s][x]+L*x+b[i]*(s>>i&1)+R*(i==n-1?e:s>>(i+1)&1));}memcpy(f,g,sizeof(f));}for(int s=0;s<(1<<n);++s) for(int x:{0,1}) chkmin(h[s],f[s][x]);}memcpy(dp,h,sizeof(h));cout<<dp[0]<<"\n";}
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}
*B. [CF2077G] RGB Walking (8)
Problem Link
分析每种颜色的权值,首先假设路径经过了所有边,那么可以在某条边上走来回增加 \(2w\),根据裴蜀定理,只要在 \(\bmod 2\gcd(w)\) 意义下考虑权值。
设三种颜色对应的模数为 \(p_1,p_2,p_3\),那么我们只要枚举每条路径权值取模后的余数 \(r_1,r_2,r_3\)。
注意到每条边权值都是 \(\frac p2\) 的倍数,因此 \(r_i\in\{0,\frac{p_i}2\}\),则本质不同的路径只有 \(2^3\) 种,直接 dfs 维护。
因此我们只要求 \(x_1,x_2,x_3\) 使得 \(x_i\bmod p_i=r_i\) 且 \(\{x\}\) 极差最小。
不妨设 \(x_1=\min(x)\),那么枚举 \(x_1=kp_1+r_1\),然后可以简单计算最小的 \(x_2-x_1,x_3-x_1\)。
注意到 \(\min(x_2-x_1)\) 关于 \(k\) 有长度为 \(p_2\) 的周期,\(\min(x_3-x_1)\) 关于 \(k\) 有长度为 \(p_3\) 的周期,那么可以 \(\mathcal O(p)\) 枚举并计算每个 \(k\) 的代价。
设 \(k_2=k\bmod p_2,k_3=k\bmod p_3\),只要 \(k_2\equiv k_3\pmod{\gcd(p_2,p_3)}\) 就存在这样的 \(k\),因此把每个 \(k\) 的贡献对 \(\gcd(p_2,p_3)\) 取模就能计算。
时间复杂度 \(\mathcal O(m+V)\)。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5,inf=1e9;
int f[MAXN][2];
int sol(int p,int x,int q,int y,int r,int z) {int g=__gcd(q,r),ans=inf;for(int i=0;i<g;++i) f[i][0]=f[i][1]=inf;for(int o=0;o<2;++o,swap(q,r),swap(y,z)) {for(int i=0;i<q;++i) f[i%g][o]=min(f[i%g][o],(int)(y+q-(1ll*i*p+x)%q)%q);}for(int i=0;i<g;++i) ans=min(ans,max(f[i][0],f[i][1]));return ans;
}
struct Edge { int v,w,c; };
vector <Edge> G[MAXN];
int n,m,V,p[3],vis[MAXN];
void dfs(int u,int s) {if(vis[u]>>s&1) return ;vis[u]|=1<<s;for(auto e:G[u]) dfs(e.v,e.w%p[e.c]?s^(1<<e.c):s);
}
void solve() {cin>>n>>m>>V,p[0]=p[1]=p[2]=0;for(int i=1;i<=n;++i) vis[i]=0,G[i].clear();for(int i=1,u,v,w,c;i<=m;++i) {char z; cin>>u>>v>>w>>z,c=(z=='r'?0:(z=='g'?1:2));p[c]=__gcd(p[c],2*w),G[u].push_back({v,w,c}),G[v].push_back({u,w,c});}dfs(1,0);int ans=inf;for(int s=0;s<8;++s) if(vis[n]>>s&1) {int r[3]={0,0,0};for(int i:{0,1,2}) if(s>>i&1) r[i]=p[i]/2;for(int i:{0,1,2}) {ans=min(ans,sol(p[0],r[0],p[1],r[1],p[2],r[2]));rotate(p,p+1,p+3),rotate(r,r+1,r+3);}}cout<<ans<<"\n";
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}
C. [CF2096F] Wonderful Impostors (4)
Problem Link
合法当且仅当所有 \(0\) 线段的并不能完全覆盖某个 \(1\) 线段。
可以双指针求每个 \(l\) 合法的最大 \(r\)。
只要判断增加 \(r\) 对应的线段是否会新增有矛盾的线段。
- 如果 \(r\) 对应 \(1\) 线段,判断该线段是否被 \(0\) 线段完全覆盖即可。
- 如果 \(r\) 对应 \(0\) 线段,二分出加入后所在的极长 \(0\) 连续段,判断内部是否完全包含 \(1\) 线段。
线段树维护。
时间复杂度 \(\mathcal O(m\log n+q)\)。
代码:
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5,inf=1e9,N=1<<18;
int n,m,q,op[MAXN],L[MAXN],R[MAXN],e[MAXN];
struct Heap {priority_queue <int> qi,qo;void ins(int x) { qi.push(x); }void ers(int x) { qo.push(x); }int top() {while(qo.size()&&qi.top()==qo.top()) qi.pop(),qo.pop();return qi.size()?qi.top():0;}
};
struct Segt1 {Heap f[MAXN]; int tr[N*2];void upd(int x,int v,int h) {(h>0?f[x].ins(v):f[x].ers(v)),tr[x+N]=f[x].top();for(x+=N;x>1;x>>=1) tr[x>>1]=max(tr[x],tr[x^1]);}int qry(int l,int r) {int s=0;for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1) {if(~l&1) s=max(s,tr[l^1]);if(r&1) s=max(s,tr[r^1]);}return s;}
} S;
struct Segt2 {int mn[N*2],ad[N*2];void psu(int p) { mn[p]=min(mn[p<<1],mn[p<<1|1]); }void adt(int p,int k) { mn[p]+=k,ad[p]+=k; }void psd(int p) { if(ad[p]) adt(p<<1,ad[p]),adt(p<<1|1,ad[p]),ad[p]=0; }void init(int l=1,int r=n,int p=1) {ad[p]=mn[p]=0;if(l==r) return ;int mid=(l+r)>>1;init(l,mid,p<<1),init(mid+1,r,p<<1|1);}void add(int ul,int ur,int k,int l=1,int r=n,int p=1) {if(ul<=l&&r<=ur) return adt(p,k);int mid=(l+r)>>1; psd(p);if(ul<=mid) add(ul,ur,k,l,mid,p<<1);if(mid<ur) add(ul,ur,k,mid+1,r,p<<1|1);psu(p);}int qmn(int ul,int ur,int l=1,int r=n,int p=1) {if(ul<=l&&r<=ur) return mn[p];int mid=(l+r)>>1,s=inf; psd(p);if(ul<=mid) s=min(s,qmn(ul,ur,l,mid,p<<1));if(mid<ur) s=min(s,qmn(ul,ur,mid+1,r,p<<1|1));return s;}int ql(int x,int l=1,int r=n,int p=1) {if(x<1||mn[p]) return 0;if(l==r) return l;int mid=(l+r)>>1; psd(p);int z=x>mid?ql(x,mid+1,r,p<<1|1):0;return z?z:ql(x,l,mid,p<<1);}int qr(int x,int l=1,int r=n,int p=1) {if(x>n||mn[p]) return n+1;if(l==r) return r;int mid=(l+r)>>1; psd(p);int z=x<=mid?qr(x,l,mid,p<<1):n+1;return z<=n?z:qr(x,mid+1,r,p<<1|1);}
} T;
bool qry(int x) {if(op[x]) return T.qmn(L[x],R[x])>0;else {int l=T.ql(L[x]-1)+1,r=T.qr(R[x]+1)-1;return S.qry(l,r)>=l;}
}
void add(int x,int k) {if(op[x]) S.upd(R[x],L[x],k);else T.add(L[x],R[x],k);
}
void solve() {cin>>n>>m,T.init();for(int i=1;i<=m;++i) cin>>op[i]>>L[i]>>R[i];for(int i=1,j=0;i<=m;++i) {while(j<m&&!qry(j+1)) add(++j,1);e[i]=j,add(i,-1);}cin>>q;for(int l,r;q--;) cin>>l>>r,cout<<(r<=e[l]?"YES\n":"NO\n");
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}
D. [CF2097E] Clearing the Snowdrift (2.5)
Problem Link
按最大值分段,想让最大值 \(v\) 减一相当于选择若干长度为 \(d\) 的线段覆盖所有 \(\ge v\) 的位置。
那么扫描线就是要在每次删点的情况下动态维护选出线段数的最小值。
考虑一个贪心,\(x\) 从 \(1\) 出发,如果 \(x\) 超过 \(v\) 就添加线段并令 \(x\gets x+d\),否则 \(x\gets x+1\)。
那么维护这个过程可以用 LCT,动态维护 \(1\to n+1\) 的路径点权和即可。
时间复杂度 \(\mathcal O(n\log n)\)。
代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5e5+5;
int n,m,ch[MAXN][2],fa[MAXN],su[MAXN],vl[MAXN];
bool rv[MAXN];
void psu(int p) { su[p]=su[ch[p][0]]+vl[p]+su[ch[p][1]]; }
void adt(int p) { if(p) rv[p]^=1,swap(ch[p][0],ch[p][1]); }
void psd(int p) { if(rv[p]) adt(ch[p][0]),adt(ch[p][1]),rv[p]=0; }
bool son(int p) { return p==ch[fa[p]][1]; }
bool isrt(int p) { return p!=ch[fa[p]][0]&&p!=ch[fa[p]][1]; }
void rot(int p) {int u=fa[p],v=fa[u],k=son(p);if(!isrt(u)) ch[v][son(u)]=p;ch[u][k]=ch[p][k^1],fa[ch[p][k^1]]=u;ch[p][k^1]=u,fa[u]=p,fa[p]=v;psu(u),psu(p);
}
void fls(int p) { if(!isrt(p)) fls(fa[p]); psd(p); }
void splay(int p) {for(fls(p);!isrt(p);rot(p)) if(!isrt(fa[p])) rot(son(p)==son(fa[p])?fa[p]:p);
}
int access(int p) {int u=0;for(;p;u=p,p=fa[p]) splay(p),ch[p][1]=u,psu(p);return u;
}
void mkrt(int p) { adt(access(p)); }
void link(int u,int v) { mkrt(u),splay(u),fa[u]=v; }
void cut(int u,int v) { mkrt(u),access(v),splay(v),ch[v][0]=fa[u]=0,psu(v); }
array<int,2> a[MAXN];
void solve() {cin>>n>>m;for(int i=1;i<=n;++i) cin>>a[i][0],a[i][1]=i,su[i]=vl[i]=1;for(int i=1;i<=n;++i) link(i,min(n+1,i+m));sort(a+1,a+n+1);ll ans=0;for(int i=1;i<=n;++i) {mkrt(n+1);int o=access(1);ans+=1ll*su[o]*(a[i][0]-a[i-1][0]);int x=a[i][1];cut(x,min(n+1,x+m)),link(x,x+1);access(x),splay(x),vl[x]=0,psu(x);}cout<<ans<<"\n";for(int i=0;i<=n+1;++i) ch[i][0]=ch[i][1]=fa[i]=su[i]=vl[i]=rv[i]=0;
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}
*E. [CF2122F] Colorful Polygon (7.5)
Problem Link
考虑 \(n=2\) 怎么做,可以发现构造一个 \(1\times k\) 矩形,然后再上下边界上分别放 \(a-1,b-1\) 个点,那么此时一个三角剖分相当于让下边界(包括边界)的每一个点匹配上边界的一个区间。
考虑每个点的区间长度,相当于把 \(a\) 个上边界上的段分配给 \(b+1\) 个下边界上的点,方案数 \(\binom{a+b}{a}\)。
然后考虑把两个矩形的方案乘起来,可以在 \((1,1),(1,200)\) 处构造两个矩形,然后用 \((0,100)\) 作为顶点的一个非常扁平的三角形连接,就能让两个矩形之间无法连边。
还要满足点数限制,构造组合数 \(\binom{x+y}{x}\) 的代价为 \(x+y+3\),可以使用分治,每次把 \(a\) 分成的等大小的 \(p,q\) 两部分,然后内部构造 \(p,q\),以及 \(\binom{S_p+S_q}{S_p}\)。
点数不超过 \(\log_2n\sum a_i+3n\)。
时间复杂度 \(\mathcal O(\sum a_i\log n)\)。
代码:
#include<bits/stdc++.h>
using namespace std;
int w[10],n,m,a[10],b[10];
void cdq(int l,int r) {if(l==r) return ;int mid=(l+r)>>1;++m,a[m]=w[mid]-w[l-1],b[m]=w[r]-w[mid];cdq(l,mid),cdq(mid+1,r);
}
vector <array<int,2>> L,R;
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;++i) cin>>w[i],w[i]+=w[i-1];cdq(1,n);int x=0,y=0;for(int i=1;i<=m;++i) {if(i&1) {for(int j=0;j<a[i];++j) L.push_back({x,y+j});for(int j=0;j<b[i];++j) R.push_back({x+1,y+j});y+=max(a[i],b[i]);L.push_back({x,y}),R.push_back({x+1,y});if(i<m) L.push_back({x+100,y+1}),x+=200;} else {for(int j=0;j<a[i];++j) L.push_back({x,y-j});for(int j=0;j<b[i];++j) R.push_back({x-1,y-j});y-=max(a[i],b[i]);L.push_back({x,y}),R.push_back({x-1,y});if(i<m) R.push_back({x+100,y-1}),x+=200;}}cout<<L.size()+R.size()<<"\n";for(auto z:L) cout<<z[0]<<" "<<z[1]<<"\n";reverse(R.begin(),R.end());for(auto z:R) cout<<z[0]<<" "<<z[1]<<"\n";return 0;
}
*F. [CF2147H] Maxflow GCD Coloring (8)
Problem Link
猜测所有图都能给出 \(c=2,d=2\) 的构造,下给出构造性证明。
首先刻画任意最小割为偶数的图:尝试将边权 \(\bmod 2\),但此时无法考虑最小割的限制,不妨加强成任意一组割都是 \(2\) 的倍数。
此时只要保留边权为奇数的边,可以发现如果该图有欧拉回路,那么对于一组割 \((S,T)\),欧拉回路上 \(S\to T,T\to S\) 的边数相等,那么此时任意割大小都是偶数。
如果图不连通,那么只要每个连通块都有欧拉回路,因此总的条件就是每个点度数为偶数。
保留边权为奇数的边,现在要把点集分成两部分使得每个导出子图度数都是偶数。
设 \(x_u\) 为一个点所属的集合,那么要求就是 \(\forall u,\oplus_{(u,v)\in E}(x_u\oplus x_v\oplus 1)=0\)。
我么要证明该方程组有解,相当于对于任意的 \(S\),\(S\) 中每个点对应向量异或和不为 \([0,0,\dots,0,1]\)。
考虑一条边:如果两端都在 \(S\) 中则两个端点的贡献抵消,所以只要考虑 \(S\to U\setminus S\) 中的边,此时常数项的异或和等于 \(U\setminus S\) 中所有项的异或和等于 \(0\),因此不存在这样的 \(S\)。
所以一定能给出 \(c=2,d=2\) 的构造。
那么用最小割树判断 \(c=1\) 是否可行,然后高斯消元求 \(c=2\) 构造即可。
代码:
#include<bits/stdc++.h>
using namespace std;
namespace F {
const int inf=1e9;
struct Edge { int v,f,lst; } G[6005];
int tot=1,S,T,hd[55],cur[55],d[55];
void clr() { for(int i=2;i<=tot;i+=2) G[i].f+=G[i^1].f,G[i^1].f=0; }
void adde(int u,int v,int f) { G[++tot]={v,f,hd[u]},hd[u]=tot; }
void link(int u,int v,int f) { adde(u,v,f),adde(v,u,0); }
bool BFS() {memcpy(cur,hd,sizeof(cur));memset(d,-1,sizeof(d));queue <int> Q;d[S]=0,Q.push(S);while(!Q.empty()) {int u=Q.front(); Q.pop();for(int i=hd[u],v;i;i=G[i].lst) if(G[i].f&&d[v=G[i].v]==-1) {d[v]=d[u]+1,Q.push(v);}}return ~d[T];
}
int dfs(int u,int f) {if(u==T) return f;int r=f;for(int i=cur[u],g,v;i&&r;i=G[i].lst) {cur[u]=i,v=G[i].v;if(G[i].f&&d[v]==d[u]+1) {g=dfs(v,min(r,G[i].f));if(!g) d[v]=-1;G[i].f-=g,G[i^1].f+=g,r-=g;}}return f-r;
}
int Dinic() {int ans=0;while(BFS()) ans+=dfs(S,inf);return ans;
}
int cut(vector<int>&v,vector<int>&x,vector<int>&y) {clr();S=v[0],T=v[1];int ans=Dinic();for(int i:v) {if(~d[i]) x.push_back(i);else y.push_back(i);}return ans;
}
int ans;
void build(vector<int>&v) {if(v.size()==1) return ;vector<int>x,y;ans=__gcd(ans,F::cut(v,x,y));build(x),build(y);
}
void init() { ans=0,tot=1,memset(hd,0,sizeof(hd)); }
int ask(int n) {vector<int>v(n);for(int i=0;i<n;++i) v[i]=i+1;build(v);return ans;
}
}
bitset <55> f[55];
void solve() {int n,m;cin>>n>>m,F::init();vector <array<int,3>> E;for(int i=1,u,v,w;i<=m;++i) cin>>u>>v>>w,F::link(u,v,w),F::link(v,u,w),E.push_back({u,v,w});if(F::ask(n)!=1) {cout<<1<<"\n"<<n<<"\n";for(int i=1;i<=n;++i) cout<<i<<" \n"[i==n];return ;}for(int i=1;i<=n;++i) f[i].reset();for(auto e:E) if(e[2]&1) {int u=e[0],v=e[1];f[u].flip(u),f[u].flip(v),f[u].flip(n+1);f[v].flip(u),f[v].flip(v),f[v].flip(n+1);}for(int i=1;i<=n;++i) {for(int j=i;j<=n;++j) if(f[j][i]) { swap(f[i],f[j]); break; }for(int j=1;j<=n;++j) if(i!=j&&f[j][i]) f[j]^=f[i];}vector <int> z[2];for(int i=1;i<=n;++i) z[f[i][n+1]].push_back(i);cout<<"2\n";for(int o:{0,1}) {cout<<z[o].size()<<"\n";for(int x:z[o]) cout<<x<<" ";cout<<"\n";}
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}
G. [CF2055F] Cosmic Divide (4.5)
Problem Link
首先输入的 \(l_i\) 单谷,\(r_i\) 单峰。
首先有一个多边形过 \((1,l_i)\),枚举另一个多边形的第一行 \(x\),如果 \(x=1\),那么要求每行长度相等,并且在中间处切分。
否则该多边形一定占据第 \(x\) 行的一个前缀或一个后缀。
不妨假设占据的是前缀,否则可以通过左右对称多边形等价。
已知 \(x\) 不难递推出每行两个多边形的分界点从而 \(\mathcal O(n)\) 检验。
考虑特判掉一些无用的 \(x\)。
首先如果 \(l\) 不是严格递减,那么应该有 \(2(x-1)\le \mathrm{argmin}(l)\),并且 \(\forall i\in[1,x-1)\) 应有 \(l_{i+1}-l_i=l_{i+x}-l_{i+x-1}\) 且 \(l_{x-1}-l_{x}=(r_1-l_1+1)+l_{2x-2}-l_{2x-1}\)。
用 Z 函数可以优化到 \(\mathcal O(1)\) 完成这部分判断,可以证明符合这样条件的 \(x\) 只有 \(\mathcal O(\log n)\) 个。
时间复杂度 \(\mathcal O(n\log n)\)。
代码:
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int n,l[MAXN],r[MAXN],t[MAXN],ok,a[MAXN],z[MAXN];
void solve() {cin>>n;for(int i=1;i<=n;++i) cin>>l[i]>>r[i];if(n%2==0) {ok=1;for(int i=1;i<=n/2;++i) ok&=(r[i]-l[i]==r[i+n/2]-l[i+n/2]&&l[i]-l[1]==l[i+n/2]-l[1+n/2]);if(ok) return cout<<"YES\n",void();}ok=(r[1]-l[1])&1;for(int i=2;i<=n;++i) ok&=(r[i]-l[i]==r[1]-l[1])&&(l[i]+r[i])/2>=l[i-1]&&(l[i]+r[i])/2+1<=r[i-1];if(ok) return cout<<"YES\n",void();for(int o:{0,1}) {auto chk=[&](int p) {for(int i=1;i<=p;++i) t[i]=l[i];for(int i=p+1;i<=n;++i) {t[i]=l[i]+r[i-p]-t[i-p]+1;if(t[i]>r[i]+1||t[i]<=l[i]) return 0;if(i+p>n&&t[i]<=r[i]) return 0;if(t[i]<=r[i]&&(t[i]>r[i-1]||r[i]<t[i-1])) return 0;if(i>p+1&&(t[i]<=l[i-1]||t[i-1]<=l[i])) return 0;if(i>p+1&&l[i]-l[i-1]!=t[i-p]-t[i-1-p]) return 0;}return 1;};for(int i=1;i<n;++i) z[i]=i>1?0:n-1,a[i]=l[i]-l[i+1];for(int i=2,L=1,R=1;i<n;++i) {if(i<=R) z[i]=min(R-i+1,z[i-L+1]);for(;i+z[i]<n&&a[i+z[i]]==a[1+z[i]];++z[i]);if(i+z[i]-1>R) L=i,R=i+z[i]-1;}int id=1;while(id<n&&l[id+1]<=l[id]) ++id;if(l[id]==l[1]) id=n;for(int p=1;p<=id/2;++p) {if(z[p+1]>=p-1&&(2*p==id||l[2*p]-l[2*p+1]+r[1]-l[1]+1==l[p]-l[p+1])&&chk(p)) return cout<<"YES\n",void();}int S=*min_element(l+1,l+n+1)+*max_element(r+1,r+n+1);for(int i=1;i<=n;++i) l[i]=S-l[i],r[i]=S-r[i],swap(l[i],r[i]);}cout<<"NO\n";
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}
H. [CF2115E] Gellyfish and Mayflower (4)
Problem Link
容量较大重量较小的多重背包是经典问题,当 \(V>\max c^2\) 时,答案一定是选取若干性价比最高的物品,然后买少量其他物品调整余数,可以同余最短路维护。
本题先对 \(V\le\max c^2\)的跑朴素背包,然后枚举性价比最高的物品 \(x\) 跑同余最短路,并且在每个点上可以预处理每种 \(V\bmod c_x\) 对应的答案。
注意我们要求这样的路径必须经过 \(x\),只要钦定不经过 \([1,x)\to (x,n]\) 的边即可。
时间复杂度 \(\mathcal O(mc^2+nmc+qn)\)。
代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=205,V=40000,MAXQ=2e5+5;
inline void chkmax(ll &x,const ll &y) { x=y>x?y:x; }
int n,m,q,c[MAXN],P[MAXQ],w[MAXN],R[MAXQ];
ll f[MAXN][MAXN],g[MAXN][V+5],h[MAXN][MAXN],ans[MAXQ];
vector <int> G[MAXN];
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;++i) cin>>c[i]>>w[i];for(int i=1,u,v;i<=m;++i) cin>>u>>v,G[u].push_back(v);cin>>q;for(int i=1;i<=q;++i) cin>>P[i]>>R[i];for(int x=1;x<=n;++x) {const int p=c[x],d=w[x];memset(f,-0x3f,sizeof(f)),f[1][0]=0;for(int u=1;u<=n;++u) if(1ll*w[u]*p<=1ll*d*c[u]) {const int t=c[u],z=w[u];for(int r=0,gc=__gcd(t,p);r<gc;++r) {for(int i=r,o=0;o<2;i=(i+t)%p,o+=i==r) {chkmax(f[u][(i+t)%p],f[u][i]+z-1ll*(i+t)/p*d);}}for(int v:G[u]) if(v<=x||x<=u) for(int i=0;i<p;++i) chkmax(f[v][i],f[u][i]);}memset(h,-0x3f,sizeof(h));for(int u=1;u<=n;++u) {ll z=(*max_element(f[u],f[u]+p))-d;for(int i=0;i<p;++i) h[u][i]=z=max(z,f[u][i]);}for(int i=1;i<=q;++i) if(R[i]>V&&P[i]>=x) chkmax(ans[i],h[P[i]][R[i]%p]+1ll*R[i]/p*d);}for(int u=1;u<=n;++u) {for(int i=c[u];i<=V;++i) chkmax(g[u][i],g[u][i-c[u]]+w[u]);for(int v:G[u]) for(int i=0;i<=V;++i) chkmax(g[v][i],g[u][i]);}for(int i=1;i<=q;++i) if(R[i]<=V) ans[i]=g[P[i]][R[i]];for(int i=1;i<=q;++i) cout<<ans[i]<<"\n";return 0;
}
I. [CF2041K] Trophic Balance Species (3.5)
Problem Link
缩点转成 DAG。
由于最小链覆盖不超过 \(k\),因此求出最小链覆盖后对每条链分别处理,每个点的前驱都是链的前缀,后继都是链的后缀,可以 DAG 上扫一遍求出答案。
问题转成求最小链覆盖,不能直接网络流,但我们只要求出一个大小较小的链覆盖就行。
考虑朴素贪心:每次选择经过未覆盖点数最多的链,可以证明此时链覆盖大小是 \(\mathcal O(k\log n)\) 级别的。
时间复杂度:\(\mathcal O(mk\log n)\)。
代码:
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
vector <int> E[MAXN],G[MAXN],ord;
int n,m,dfn[MAXN],low[MAXN],dcnt,st[MAXN],tp,bl[MAXN],vc,a[MAXN];
bool ins[MAXN],vis[MAXN];
void tarjan(int u) {dfn[u]=low[u]=++dcnt,st[++tp]=u,ins[u]=true;for(int v:E[u]) {if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);else if(ins[v]) low[u]=min(low[u],dfn[v]);}if(low[u]==dfn[u]) for(++vc;ins[u];ins[st[tp--]]=false) bl[st[tp]]=vc,++a[vc];
}
int deg[MAXN],q,f[MAXN],g[MAXN],z[MAXN];
vector <int> b[MAXN];
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1,u,v;i<=m;++i) cin>>u>>v,E[u].push_back(v);for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);for(int u=1;u<=n;++u) for(int v:E[u]) if(bl[u]^bl[v]) ++deg[bl[v]],G[bl[u]].push_back(bl[v]);queue <int> Q;for(int i=1;i<=vc;++i) if(!deg[i]) Q.push(i);ord.resize(vc);for(int i=0;i<vc;++i) {int u=ord[i]=Q.front(); Q.pop();for(int v:G[u]) if(!--deg[v]) Q.push(v);}for(int ct=vc;ct>0;++q) {memset(f,0,sizeof(f));for(int u:ord) {f[u]+=!vis[u];for(int v:G[u]) if(f[u]>f[v]) f[v]=f[u],g[v]=u;}int x=max_element(f+1,f+vc+1)-f;for(;x;x=g[x]) if(!vis[x]) b[q].push_back(x),--ct,vis[x]=1;reverse(b[q].begin(),b[q].end());}for(int t=0;t<q;++t) {memset(f,0,sizeof(f));for(int i=0,s=0;i<(int)b[t].size();++i) f[b[t][i]]=s+=a[b[t][i]];for(int u:ord) for(int v:G[u]) f[v]=max(f[v],f[u]);for(int i=1;i<=vc;++i) z[i]+=f[i];memset(f,0,sizeof(f));for(int i=b[t].size()-1,s=0;~i;--i) f[b[t][i]]=s+=a[b[t][i]];for(int i=ord.size()-1;~i;--i) for(int v:G[ord[i]]) f[ord[i]]=max(f[ord[i]],f[v]);for(int i=1;i<=vc;++i) z[i]-=f[i];}for(int i=1;i<=vc;++i) z[i]=abs(z[i]);int w=*min_element(z+1,z+vc+1);for(int i=1;i<=n;++i) if(z[bl[i]]==w) cout<<i<<" ";cout<<"\n";return 0;
}
J. [CF2097D] Homework (3.5)
Problem Link
设 \(n=m2^k\),其中 \(2\nmid m\),那么序列可以看成 \(m\) 个 \([0,2^k)\) 的数 \(x_1\sim x_m\)。
可以证明我们能让任意 \(x_i\gets x_i\oplus x_j\),那么只要判断 \(s,t\) 对应的矩阵是否相似,可以直接分别高斯消元。
时间复杂度 \(\mathcal O\left(\dfrac{n\sqrt n}{\omega}\right)\)。
代码:
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int MAXN=1e6+5;
typedef vector<ull> bs;
int n,m,d,k;
void guass(vector<bs>&a) {for(int i=0,p=0;i<d&&p<k;++i) {bool ok=0;for(int j=p;j<k;++j) if(a[j][i>>6]>>(i&63)&1){ swap(a[p],a[j]),ok=1; break; }if(!ok) continue;for(int j=0;j<k;++j) if(j!=p&&(a[j][i>>6]>>(i&63)&1)) for(int t=0;t<m;++t) a[j][t]^=a[p][t];++p;}
}
void solve() {string s,t;cin>>n>>s>>t,k=1<<__builtin_ctz(n),d=n/k,m=d/64+1;vector <bs> a(k,bs(m)),b(k,bs(m));for(int i=0;i<n;++i) {if(s[i]=='1') a[i/d][i%d>>6]|=1ull<<(i%d&63);if(t[i]=='1') b[i/d][i%d>>6]|=1ull<<(i%d&63);}guass(a),guass(b);for(int i=0;i<k;++i) if(a[i]!=b[i]) return cout<<"NO\n",void();cout<<"YES\n";
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}
K. [CF2034H] Rayan vs. Rayaneh (5)
Problem Link
注意到一个集合 \(S\) 合法当且仅当 \(\forall x\in S\) 都有 \(\gcd(S)\ne \gcd(S\setminus\{x\})\)。
考虑每个质因子的贡献,相当于对每个 \(x\) 存在一个 \(p\) 使得任意 \(y\ne x\) 都有 \(v_p(y)>v_p(x)\),并且这样的 \(p\) 两两不同。
枚举 \(d=\prod_{x\in S} p^{v_p(x)+1}\),记 \(m=\max a_i\),此时任意 \(\dfrac d{p^{v_p(x)}}\le m\),所以答案不超过 \(w(n)+1=7\)。
且答案 \(\ge 3\) 时最小的 \(p^{v_p(x)}\le\sqrt m\),可以证明这样的 \(p^{v_p(x)}\) 只有 \(\mathcal O\left(\dfrac{\sqrt m}{\log m}\right)\) 个。
答案 \(=2\) 的情况只要找到 \(a_i\nmid a_j\),这是平凡的。
所以可以暴力枚举 \(d\),判定的时候只要 \(\forall p\),存在一个 \(\dfrac dp\) 的倍数不是 \(p\) 的倍数即可,容易预处理倍数个数 \(\mathcal O(w(n))\) 判断。
爆搜 \(d\) 即可,需要进行一定的剪枝,例如通过当前答案优化可能的 \(p\) 的上界。
时间复杂度 \(\mathcal O\left(\dfrac{m\sqrt m}{\log m}w(n)+m\log m\right)\)。
代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+5,m=1e5,lim[]={1,1,3,15,105,1155,15015,255255};
int pr[MAXN],k;
basic_string <int> fc[MAXN],PR;
int n,a[MAXN],ct[MAXN],f[MAXN],ans,o,q[10];
void dfs(int x,ll z,int w) {for(int i=0;i<w;++i) if(z/q[i]>m||f[z/q[i]]==(z<=m?f[z]:0)) return ;if(w>ans) ans=w,o=z;if(w) for(ll i=0,t=z/q[0];i<=ans-w;t*=pr[x+i],++i) if(x+i>=k||t*pr[x+i]>=m) return ;for(int y=x;y<k&&pr[y]*lim[ans]<=m;++y) {ll t=z;for(q[w]=pr[y];t*pr[y]/q[0]<=m;) dfs(y+1,t*=pr[y],w+1);if(z*pr[y]/q[0]>m) break;}
}
void solve() {cin>>n,ans=1,o=k=0;vector <int> w;for(int i=1;i<=n;++i) {cin>>a[i];if(!ct[a[i]]++) w.push_back(a[i]);}for(int x:w) for(int y:fc[x]) f[y]+=ct[x];for(int p:PR) if(f[p]) pr[k++]=p;sort(w.begin(),w.end(),greater<>());int sz=0;for(int x:w) if((sz+=ct[x])>f[x]) { ans=2,o=x; break; }if(ans==1) return cout<<"1\n"<<a[1]<<"\n",void();dfs(0,1,0);if(ans==2) {cout<<"2\n"<<o<<" ";for(int y:w) if(y>o&&y%o) return cout<<y<<"\n",void();}cout<<ans<<"\n";for(int i=0;i<k;++i) if(o%pr[i]==0) {for(int x=1;x<=n;++x) if(a[x]%o&&a[x]%(o/pr[i])==0) {cout<<a[x]<<" "; break;}}cout<<"\n";
}
bool np[MAXN];
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);for(int i=2;i<=m;++i) if(!np[i]) {if(i*3<=m) PR.push_back(i);for(int j=i;j<=m;j+=i) np[j]=true;}for(int i=1;i<=m;++i) for(int j=i;j<=m;j+=i) fc[j]+=i;int _; cin>>_;while(_--) {solve(),memset(f,0,sizeof(f));for(int i=1;i<=n;++i) ct[a[i]]=0;}return 0;
}
L. [CF2129E] Induced Subgraph Queries (3)
Problem Link
静态区间查询可以莫队,用 Sqrt-Tree 快速维护第 \(k\) 小,修改一个点的复杂度是 \(\deg_u+1\),按这个值带权分块即可。
时间复杂度 \(\mathcal O((n+m)\sqrt q+q\sqrt[3]n)\)。
代码:
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1.5e5+5,B=640;
int n,m,q,bl[MAXN],ans[MAXN],a[MAXN],d[MAXN];
basic_string <int> G[MAXN];
struct Qy { int l,r,k,i; } b[MAXN];
int c1[MAXN],c2[MAXN],c3[MAXN*2];
void add(int x,int k) { c1[x>>12]+=k,c2[x>>6]+=k,c3[x]+=k; }
int ask(int k) {int h=0;for(;k>c1[h>>12];h+=1<<12) k-=c1[h>>12];for(;k>c2[h>>6];h+=1<<6) k-=c2[h>>6];for(;k>c3[h];++h) k-=c3[h];return h;
}
void solve() {cin>>n>>m;for(int i=1;i<=n;++i) G[i].clear(),a[i]=0,d[i]=1;for(int i=1,u,v;i<=m;++i) cin>>u>>v,G[u]+=v,G[v]+=u,++d[u],++d[v];cin>>q;for(int i=1;i<=q;++i) cin>>b[i].l>>b[i].r>>b[i].k,b[i].i=i;for(int i=1,p=0,k=0,s=0;i<=n;++i) if(i==n||d[i+1]>B||(s+=d[i])>B) {fill(bl+p+1,bl+i+1,++k),s=0,p=i;}sort(b+1,b+q+1,[&](auto x,auto y) {if(bl[x.l]^bl[y.l]) return x.l<y.l;return bl[x.l]&1?x.r<y.r:x.r>y.r;});int l=1,r=0;auto ins=[&](int x) {for(int y:G[x]) if(l<=y&&y<=r) add(a[y],-1),a[y]^=x,add(a[y],1),a[x]^=y;add(a[x],1);};auto ers=[&](int x) {add(a[x],-1);for(int y:G[x]) if(l<=y&&y<=r) add(a[y],-1),a[y]^=x,add(a[y],1),a[x]^=y;};for(int i=1;i<=q;++i) {while(r<b[i].r) ins(++r);while(l>b[i].l) ins(--l);while(l<b[i].l) ers(l++);while(r>b[i].r) ers(r--);ans[b[i].i]=ask(b[i].k);}for(int i=l;i<=r;++i) add(a[i],-1),a[i]=0;for(int i=1;i<=q;++i) cout<<ans[i]<<"\n";
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}
M. [CF2062F] Traveling Salescat (2.5)
Problem Link
考虑 \(\max(a_i+b_j,b_i+a_j)=b_i+b_j+\max(a_i-b_i,a_j-b_j)=b_i+b_j+\dfrac{a_i-b_i+a_j-b_j+|a_i-b_j-a_j+b_j|}{2}\)。
记 \(x_i=a_i+b_i,y_i=a_i-b_i\),那么只要最小化 \(\sum x_i+x_j+|y_i-y_j|\) 即可。
注意到只有起点终点的 \(x_i\) 系数为 \(1\),其他点系数为 \(2\),因此确定起点终点后剩下的点必定按 \(y\) 升序。
那么我们只要知道起点终点,以及 \(y\) 的最小最大之就能确定权值,按 \(y\) 排序后 dp,\(f_{i,j,0/1,0/1}\) 表示 \([1,i]\) 选了 \(j\) 个点,是否确定起点、终点。
转移简单分讨,注意 \(y\) 最值处要特殊处理。
时间复杂度 \(\mathcal O(n^2)\)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3005;
struct info { ll z,w; } a[MAXN];
int n;
ll f[MAXN][2][2],g[MAXN];
inline void upd(ll &x,const ll &y) { x=y<x?y:x; }
void solve() {cin>>n;for(int i=1,A,B;i<=n;++i) cin>>A>>B,a[i]={A+B,A-B};memset(f,0x3f,sizeof(f)),memset(g,0x3f,sizeof(g));sort(a+1,a+n+1,[&](auto x,auto y){ return x.w<y.w; });for(int i=1;i<=n;++i) {for(int j=i-1;j;--j) for(int x:{0,1}) for(int y:{0,1}) {if(x) upd(g[j+1],f[j][x][y]+a[i].z+a[i].w+y*(a[i].z+a[i].w));upd(f[j+1][x][y],f[j][x][y]+2*a[i].z);if(!x) upd(f[j+1][1][y],f[j][0][y]+a[i].z+a[i].w);if(!y) upd(f[j+1][x][1],f[j][x][0]+a[i].z-a[i].w);}for(int x:{0,1}) upd(f[1][x][0],a[i].z-a[i].w+(1-x)*(a[i].z-a[i].w));}for(int i=2;i<=n;++i) cout<<g[i]/2<<" \n"[i==n];
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}
*N. [CF2138E2] Determinant Construction (7)
Problem Link
考虑构造带状矩阵,即只有 \(|i-j|\le 1\) 的 \(M_{i,j}\) 有值。
设左上角 \(k\times k\) 矩阵的行列式为 \(f_k\),那么 \(M_{k,k}=M_{k,k-1}=1,M_{k-1,k}=-1\) 时 \(f_k=f_{k-1}+f_{k-2}\),如果 \(M_{k-1,k}=1\),则 \(f_k=f_{k-1}-f_{k-2}\)。
考虑 \(f_k,f_{k-1}\) 已知时必定有 \(f_{k-2}=|f_k-f_{k-1}|\),那么枚举 \(f_{k-1}\) 并判定即可。
注意到上述做法本质是辗转相减,自然想到下降速度最快的斐波那契数列,考虑在 \(\dfrac{\sqrt 5-1}{2}x\) 附近枚举 \(f_{k-1}\),可以通过。
时间复杂度 \(\mathcal O(n^2)\)。
代码:
#include<bits/stdc++.h>
using namespace std;
bool qry(int x,int y) {if(__gcd(x,y)>1) return false;int z=0;while(x>1||y>1) {++z,x=abs(x-y),swap(x,y);if(z>=50) return false;}return true;
}
const long double P=(sqrtl(5)-1)/2;
mt19937 rnd(135);
int a[105][105],n;
long double b[105][105];
void solve() {cin>>n;if(n<=1) return cout<<"1\n"<<n<<"\n",void();int l=n*(P-0.01),r=n*(P+0.01),z=-1;if(n<=100000) l=1,r=n;l=max(l,1),r=min(r,n);while(true) {int k=rnd()%(r-l+1)+l;if(qry(n,k)) { z=k; break; }}vector <int> h;for(int x=n,y=z;x>1||y>1;) {h.push_back(x>y?-1:1);x=abs(x-y),swap(x,y);}memset(a,0,sizeof(a));int m=1; a[1][1]=1;for(int x:h) {++m,a[m][m]=a[m][m-1]=1,a[m-1][m]=x;}cout<<m<<"\n";for(int i=1;i<=m;++i) for(int j=1;j<=m;++j) cout<<a[i][j]<<" \n"[j==m];
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}
*O. [CF2081F] Hot Matrix (7)
Problem Link
首先有解当且节点 \(n=1\lor2\mid n\),设 \(n>1,m=\dfrac n2\),考虑左上角 \(m\times m\) 矩阵。
容易发现该矩阵已知后可以确定整个矩阵。
注意到我们只关心两个值的和是否为 \(n-1\),因此可以把 \(0\sim n-1\) 对应 \(1\sim m\) 加上 \(-m\sim -1\),限制变为对应位置和为 \(0\)。
打表发现 \(m\) 为偶数时,存在方案使得左下右上对角线上元素相等,且所有元素中心对称,例如:
3 2 4 5 1 64 3 1 2 6 -52 5 3 6 -4 11 4 6 -3 5 -25 6 -2 1 -3 46 -1 5 -4 2 -3
注意到负元素是右下部分的第 $2,4,6,\dots $ 条对角线,这是因为左上部分给出正数的合法构造,然后中心对称保证每行依然是排列,为了让每个右下部分每条边恰好有一端被取反,不难想到黑白染色。
所以只要考虑左上角的三角形,填入 \([1,m)\) 使得任意无序数对 \((x,y)\) 都在横向纵向相邻点之间出现恰好依次。
逐条对角线写成等腰三角形的形式,观察 \(m=6,m=8\) 时的规律:
32 44 3 25 1 5 1
1 2 3 4 545 33 4 52 6 2 66 5 4 3 27 1 7 1 7 1
1 2 3 4 5 6 7
注意到此时最下面一行是 \(1\sim m-1\),然后第二行是 $1,m-1,1,m-1\dots $ 交错,上面部分是一个大小 \(m-2\) 的构造,左右翻转后值域全体加一。
可以归纳证明,任何 \(\min(x,y)=1\) 或 \(\max(x,y)=m-1\) 的数对都在最后两行出现过,而其余数对则在上面的子问题中出现。
那么我们就能构造三角形,按上面的过程可以逐步还原原矩阵。
而 \(m\) 是奇数的情况依然考虑构造左上三角形,可以直接取 \(m+1\) 时的构造,为了保证每行是排列,直接沿对角线对称,然后黑白染色取负号,例如 \(m=7\) 时的构造:
4 5 3 2 6 7 13 4 6 5 1 2 -75 2 4 7 3 -1 66 3 1 4 -7 5 -22 7 5 -1 4 -6 31 6 -7 3 -2 4 -57 -1 2 -6 5 -3 4
按上述过程构造即可。
时间复杂度 \(\mathcal O(n^2)\)。
代码:
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3005;
int n,a[MAXN][MAXN];
void solve() {cin>>n;if(n==1) return cout<<"YES\n0\n",void();if(n&1) return cout<<"NO\n",void();n/=2; int m=n%2?n:n-1;for(int l=1,r=m,o=0;l<r;++l,--r,o^=1) {for(int i=l;i<=r;++i) a[i-l+1][r+1-i]=o?l+r-i:i;for(int i=l;i<r;++i) a[i-l+1][r-i]=(i-l)%2==o?r:l;}a[1][1]=(m+1)/2;if(n%2==0) for(int i=1;i<=n;++i) a[i][n+1-i]=n;int w=2*n+1;for(int i=1;i<=n;++i) for(int j=1;j<=n-i;++j) {if(n&1) a[n+1-j][n+1-i]=(i+j+n)&1?a[i][j]:-a[i][j];else a[n+1-i][n+1-j]=(i+j+n)&1?a[i][j]:-a[i][j];}for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) a[i][w-j]=a[w-i][j]=w-a[i][j],a[w-i][w-j]=a[i][j];cout<<"YES\n";for(int i=1;i<=2*n;++i) for(int j=1;j<=2*n;++j) cout<<a[i][j]-1<<" \n"[j==2*n];
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}
P. [CF2041G] Grid Game (3.5)
Problem Link
考虑每列上很多点的状态相同:于第 \(i\) 列,把 \(i-1,i,i+1\) 列上所有极长白色连续段的开头和结尾取出来删掉,剩余的白色连续段状态相同。
因此可以把每列的等价类缩成一个点跑 tarjan:把 \(i-1,i,i+1\) 列上每个白连续段的开头和结尾建点,然后白连续段可以看成两个端点之间的边,权值为中间点数,然后每个点向左右两侧的同行的关键点连边。
答案应该就是割点个数加上割边权值之和。
注意如果第 \(i\) 列一个来自 \(i-1\) 列的端点想向 \(i+1\) 列连边,但同行点可能不存在,我们可以证明此时连向对应白连续段的下一个端点不影响正确性。
此时列数太多,注意到如果一个列左右两列都没有黑点,那么这些列中必定无割点,可以把这样连续的若干列缩成一个点。
时间复杂度 \(\mathcal O(q\log q)\)。
代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e6+5;
int n,m,k,q,w[MAXN],nx[MAXN];
vector <array<int,2>> g[MAXN],p[MAXN];
bool ty[MAXN];
struct Edge { int v,w; };
vector <Edge> G[MAXN];
bool qcol(int x,int y) {auto it=lower_bound(g[x].begin(),g[x].end(),array<int,2>{y+1,0});return it!=g[x].begin()&&(*--it)[1]>=y;
}
array<int,2> qid(int x,int y) {auto it=lower_bound(p[x].begin(),p[x].end(),array<int,2>{y,0});return *it;
}
void link(int u,int v,int z) {G[u].push_back({v,z}),G[v].push_back({u,z});
}
ll ans=0;
int low[MAXN],dfn[MAXN],dcnt;
void tarjan(int u,int fz) {int op=0,ct=0;dfn[u]=low[u]=++dcnt;for(auto e:G[u])if(e.v^fz) {if(!dfn[e.v]) {tarjan(e.v,u),low[u]=min(low[u],low[e.v]);if(dfn[u]<low[e.v]) ans+=e.w;if(u!=1&&dfn[u]<=low[e.v]) op=1;if(u==1&&ct++) op=1;} else low[u]=min(low[u],dfn[e.v]);}if(op&&!ty[u]) ++ans;
}
void solve() {cin>>n>>q,m=k=dcnt=ans=0;vector <array<int,3>> E(q);for(auto &e:E) {cin>>e[0]>>e[1]>>e[2];for(int x:{e[0]-1,e[0],e[0]+1}) if(1<=x&&x<=n) w[++k]=x;}sort(w+1,w+k+1),k=unique(w+1,w+k+1)-w-1;for(auto e:E) g[lower_bound(w+1,w+k+1,e[0])-w].push_back({e[1],e[2]});for(int i=1;i<=k;++i) if(g[i].size()) {sort(g[i].begin(),g[i].end());vector <array<int,2>> e;for(auto x:g[i]) {if(e.empty()||e.back()[1]<x[0]-1) e.push_back(x);else e.back()[1]=max(e.back()[1],x[1]);}g[i].clear();if(e[0][0]>1) g[i].push_back({1,e[0][0]-1});for(int j=1;j<(int)e.size();++j) g[i].push_back({e[j-1][1]+1,e[j][0]-1});if(e.back()[1]<n) g[i].push_back({e.back()[1]+1,n});} else g[i]={{1,n}};w[0]=0,w[k+1]=n+1;for(int i=1;i<=k;++i) {for(auto e:g[i]) for(int x:e) p[i].push_back({x,0});if(i>1&&w[i-1]==w[i]-1) for(auto e:g[i-1]) for(int x:e) if(qcol(i,x)) p[i].push_back({x,0});if(i<k&&w[i+1]==w[i]+1) for(auto e:g[i+1]) for(int x:e) if(qcol(i,x)) p[i].push_back({x,0});sort(p[i].begin(),p[i].end());p[i].erase(unique(p[i].begin(),p[i].end()),p[i].end());for(auto &e:p[i]) e[1]=++m;}for(int i=0;i<=k;++i) if(w[i+1]-w[i]>1) nx[i]=++m,ty[m]=true;for(int i=1;i<=k;++i) {for(auto x:p[i]) {if(i>1&&w[i-1]==w[i]-1) {if(qcol(i-1,x[0])) link(x[1],qid(i-1,x[0])[1],0);} else if(w[i]-w[i-1]>1) link(x[1],nx[i-1],0);if(i<k&&w[i+1]==w[i]+1) {if(qcol(i+1,x[0])) {auto o=qid(i+1,x[0]);if(o[0]>x[0]) link(x[1],o[1],0);}} else if(w[i+1]-w[i]>1) link(x[1],nx[i],0);}for(auto e:g[i]) {int l=lower_bound(p[i].begin(),p[i].end(),array<int,2>{e[0],0})-p[i].begin();int r=lower_bound(p[i].begin(),p[i].end(),array<int,2>{e[1],0})-p[i].begin();for(int j=l;j<r;++j) link(p[i][j][1],p[i][j+1][1],p[i][j+1][0]-p[i][j][0]-1);}}tarjan(1,0);cout<<ans<<"\n";for(int i=1;i<=m;++i) low[i]=dfn[i]=ty[i]=0,G[i].clear();for(int i=1;i<=k;++i) w[i]=nx[i]=0,g[i].clear(),p[i].clear();
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _=0; cin>>_;while(_--) solve();return 0;
}
Q. [CF2119F] Volcanic Eruptions (5.5)
Problem Link
观察当前节点与岩浆的距离,向下走不变,向上走减二,所以每次移动距离严格不增,我们只要最后的终点合法即可。
那么我们只要关心一条路径的长度和终点。
如果一条路径经过了两个相邻的 \(1\),那么长度可以任意延长(每次 \(+2\))。
确定终点后,由于节点和岩浆距离奇偶性不变,所以可以算出路径长度。
考虑解的形态,我们只要在到终点最短路的基础上额外前往一个相邻的 \(1\) 上即可。
注意到在到达相邻 \(1\) 之前的路径权值一定是 \(\pm 1\) 交错,因此可以 bfs 预处理从每个点走到相邻 \(1\) 的最短路,然后从根节点 dfs 枚举终点并维护答案。
时间复杂度 \(\mathcal O(n)\)。
代码:
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5,inf=1e9;
vector <int> G[MAXN];
int n,rt,ans,w[MAXN],d[MAXN],f[MAXN];
void dfs1(int u,int fz) { for(int v:G[u]) if(v^fz) d[v]=d[u]+1,dfs1(v,u); }
void dfs2(int u,int fz,int di,int su,int lm,int fw) {lm=max(lm,-su);if(!lm) fw=min(fw,f[u]);if(di+(lm?((lm+1)/2+fw)*2:0)<d[u]) ans=max(ans,d[u]-(d[rt]%2==0));for(int v:G[u]) if(v^fz) dfs2(v,u,di+1,su+w[v],lm,fw);
}
void solve() {cin>>n>>rt,ans=0;for(int i=1;i<=n;++i) cin>>w[i],d[i]=0,f[i]=inf,G[i].clear();for(int i=1,u,v;i<n;++i) cin>>u>>v,G[u].push_back(v),G[v].push_back(u);dfs1(1,0);queue <int> Q;for(int i=1;i<=n;++i) if(w[i]>0) for(int j:G[i]) if(w[j]>0) { f[i]=0,Q.push(i); break; }while(Q.size()) {int u=Q.front(); Q.pop();for(int v:G[u]) if(max(w[u],w[v])>0&&f[v]>f[u]+1) f[v]=f[u]+1,Q.push(v);}dfs2(rt,0,0,w[rt],0,inf);cout<<ans<<"\n";
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}
*R. [CF2127G2] Inter Active (9.5)
Problem Link
单个询问几乎没有信息,考虑两个近似排列答案的变化量。
如果没有 \(i\ne k\) 的限制,那么询问 \(q\) 的每个循环移位答案都不变,因为原本的 \(q_n\) 入边贡献必定减少,出边贡献必定增多。
那么加上 \(i\ne k\) 的限制,如果我们知道无限制时的答案,那么就能知道 \(q_k\) 的出边是否属于 \(q[k+1,n]\)。
不妨取 \(k=\lfloor \frac n2\rfloor+1\),那么每次询问 \(q\) 就能知道每个 \(i\) 在 \(q\) 中与 \(p_i\) 的距离是否 \(\le n-k\)。
那么我们如果构造 \(\log n\) 个 \(q\) 使得对于每个 \(i\),所有的 \(j\) 每次回答不完全相同。
记 \(b=q^{-1}\),则对于任意 \((x,y)\) 存在一个 \(b\) 使得 \([b_y-b_i\le n-k]\ne [b_x-b_i\le n-k]\)(减法是 \(\bmod n\) 意义下的)。
-
如果 \(n\) 是偶数,我们可以按如下方式构造:初始 \(b_{d,i}=i\),\(\forall i\in[1,\frac n2]\),如果 \(i-1\) 的第 \(d\) 个二进制位是 \(1\) 就交换 \(b_i,b_{i+n/2}\),其中 \(d\in[0,6]\)。
考虑任意的 \((i,x,y)\),我们要求存在一个 \(d\) 使得 \(x\bmod \frac n2,y\bmod \frac n2\) 的第 \(d\) 位相同或不同,由于 \(\frac n2<2^{6}\) 所以必定存在。
-
如果 \(n\) 是奇数,我们可以按如下方式构造:\(b_{d,i}=(i-1)\times 2^d\bmod n+1\),其中 \(d\le [0,6]\)。
对于 \((i,x,y)\),只要某个 \(d\) 满足 \(2^d(x-y)\bmod n>\frac n2\) 就一定能得到不同的结果,很显然。
想要知道 \(q\) 在无限制下的答案,需要先确定任意一个 \(p_x=y\)。
如果 \(n\) 是偶数,设 \(n=2m\),则询问 \([q_1,\dots,q_{m},q_{m+1},\dots q_{2m}]\) 和 \([q_{2m},q_{2m-1},\dots,q_m,q_{m+1},q_{m-1},q_{m-2}\dots q_1]\),此时对于任意 \(i\ne q_{m+1}\),\(i\to p_i\) 在两个排列中恰有一个产生贡献,除非 \(i=q_m,p_i=q_{m+1}\)。
那么我们固定 \(q_{m+1}\),枚举 \(q_m\) 就能找到 \(p_x=q_{m+1}\) 的 \(x\),具体来说找到两次询问之和 \(=n\) 的一个作为 \(x\) 即可。
如果 \(n\) 是奇数,那么固定 \(q_n=n\),然后 \(q_m=1\sim n-1\) 都不满足的时候则 \(x=n\),注意此时 \(q_m=x\) 时答案之和不一定是 \(n\),要找和最大的一个作为 \(x\)。
因此可以在 \(2n\) 次操作内确定 \((x,y)\),然后 \(7n\) 次询问还原排列,总次数 \(2n+n\log_2n\)。
时间复杂度 \(\mathcal O(n^2\log n)\)。
代码:
#include<bits/stdc++.h>
using namespace std;
int n,a[105][105],b[105],p[105],q[105],w[105];
int ask() {cout<<"?";for(int i=1;i<=n;++i) cout<<" "<<q[i];cout<<endl;int o; cin>>o; return o;
}
void solve() {cin>>n;int k=n/2+1,x=n,y=k; //find p[x]=ycout<<k<<endl;for(int i=1,m=n-(n&1),c=0;i<=m;++i) if(i!=k) {iota(q+1,q+n+1,1),swap(q[i],q[k-1]);int z=ask();reverse(q+1,q+m+1),swap(q[k],q[k-1]),z+=ask();if(i>1&&z>c) { x=i; break; }else if(c>z) { x=1; break; }else c=z;}memset(a,0,sizeof(a)),memset(b,0,sizeof(b));iota(p+1,p+n+1,1);for(int d=0;d<7;++d) {if(~n&1) {iota(p+1,p+n+1,1);for(int i=1;i<=n/2;++i) if((i-1)>>d&1) swap(p[i],p[i+n/2]);}for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) a[i][j]|=((p[j]+n-p[i])%n<=n-k)<<d;for(int i=1;i<=n;++i) q[p[i]]=i;for(int i=1;i<=n;++i) w[q[k]]=ask(),rotate(q+1,q+2,q+n+1);int o=w[x]+((p[y]+n-p[x])%n<=n-k);for(int i=1;i<=n;++i) b[i]|=(o-w[i])<<d;if(n&1) for(int i=1;i<=n;++i) p[i]=(p[i]-1)*2%n+1;}for(int i=1;i<=n;++i) q[i]=find(a[i]+1,a[i]+n+1,b[i])-a[i];cout<<"!";for(int i=1;i<=n;++i) cout<<" "<<q[i];cout<<endl;
}
signed main() {int _; cin>>_;while(_--) solve();return 0;
}
S. Gellyfish and Forget-Me-Not (3.5)
Problem Link
可以看成从 \(\oplus a_i\) 开始每次选择是否异或上 \(v_i=a_i\oplus b_i\)。
从高到低确定每一位的取值,首先最高位 \(k\) 的取值只和最后一个包含 \(2^k\) 的 \(v_i\) 对应的 \(c_i\) 有关。
然后考虑 \(k-1\),如果最后一个包含 \(2^{k-1}\) 的 \(v_j\) 满足 \(j\ne i\),那么只要考虑 \(c_j\),否则玩家 \(c_i\) 应该尽可能让异或和的 \(k,k-1\) 位相同。
所以从 \(j\) 继续往前找一个 \(k,k-1\) 位不同的即可,继续类推 \(k-2,k-3,\dots\) 的情况,可以发现最终每个位置的决策都形如 \(f_i,g_i\),即当前的异或和 \(S\) 若 \(\mathrm{popcount}(f_i\operatorname{AND}S)\bmod 2\ne g_i\) 就异或上 \(a_i\)。
维护 \(f_i,g_i\) 只要从后往前维护玩家 \(0\) 的目标 \((w,h)\) 表示尽可能让 \(\mathrm{popcount}(w\operatorname{AND}S)\bmod 2= h\)。
时间复杂度 \(\mathcal O(n\log V)\)。
代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+5;
ll a[MAXN],b[MAXN],f[MAXN];
bool c[MAXN],g[MAXN];
bool mul(ll x,ll y) { return __builtin_popcountll(x&y)&1; }
void solve() {int n; ll z=0,S=0;cin>>n;for(int i=1;i<=n;++i) cin>>a[i],S^=a[i],f[i]=g[i]=0;for(int i=1;i<=n;++i) cin>>b[i],a[i]^=b[i];for(int i=1;i<=n;++i) { char o; cin>>o,c[i]=o-'0'; }for(int k=59;~k;--k) {int x=n; ll w=1ll<<k; bool h=0;for(;;--x) {for(;x&&!mul(a[x],w);--x);if(!x) { z|=(mul(S,w)^h)*(1ll<<k); break; }h^=c[x]^g[x],w^=f[x];if(!f[x]) { f[x]=w,g[x]=h^c[x],z|=c[x]*(1ll<<k); break; }}}cout<<z<<"\n";
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}
*T. [CF2068B] Urban Planning (7.5)
Problem Link
首先考虑一个朴素贪心,从上到下从左到右,能填 #
就填,如果一整行对答案都没有贡献就全部删掉换成 .
。
这个构造能解决 \(k\le 4\times 10^{14}\) 的情况,对于更大的 \(n\) 需要进一步处理。
注意到 \(k\) 的限制相当接近 \(2024\times 2024\) 矩阵的总方案数,因此考虑从一个相当大的矩阵开始调整。
我们枚举 \(m\le 2023\) 并构造 \(m\times (m+1)\) 矩阵,从左上角逐条对角线删点直到剩余环数 \(w\le k-m(m-1)\)。
此时我们把 \(k-w\) 写成 \(xm+y(m+1)\) 的形式,由于 \(k-w\ge m^2-m\) 所以这样的正整数 \((x,y)\) 总是存在。
然后把 \(x,y\) 贪心地拆成若干个 \(\binom p2\) 的和,在 \(m+1\) 行和 \(m+2\) 列上用长度为 \(p\) 的连续段调整即可。
但我们要保证这些连续段对应的行和列上没有被删掉的点,注意到 \(m\) 增加时 \(w\) 的变化量是 \(\mathcal O(m^3)\) 的,因此 \(w-k\) 应该是 \(\mathcal O(m^3)\) 级别,每次删点会让 \(w\) 减小 \(\Omega(m^2)\) 级别,所以删掉的的点是 \(\mathcal O(m)\) 级别,由于这些点在对角线上,所以影响的行列是 \(\mathcal O(\sqrt m)\) 级别的。
可以证明 \(m\) 较大时任意的 \(k\) 都不会覆盖到被影响的行列,\(m\) 较小使用第一种构造即可。
时间复杂度 \(\mathcal O(\sqrt k)\)。
代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int m=2025,MAXN=2105;
ll s,t;
char a[MAXN][MAXN];
signed main() {cin>>s,t=s;memset(a,'.',sizeof(a));for(int i=1;i<=m;++i) a[1][i]='#';for(int i=2,p=1;i<=m;) {bool op=0;for(int j=1,c=0;j<=m;++j) {if(a[i-1][j]=='.') c=0;else {ll w=c*(i-p);if(t>=w) t-=w,a[i][j]='#',++c,op|=w>0;else c=0;}}if(!op) {for(int j=1;j<=m;++j) a[i][j]='.',a[i+1][j]='#';i+=2,p=i-1;} else ++i;}if(!t) {cout<<m<<" "<<m<<"\n";for(int i=1;i<=m;++i,cout<<"\n") for(int j=1;j<=m;++j) cout<<a[i][j];return 0;}memset(a,'.',sizeof(a));int n=1;while(n<m-2&&1ll*(n-1)*n*n*(n+1)/4+n*(n-1)<s) ++n;for(int i=1;i<=n;++i) for(int j=1;j<=n+1;++j) a[i][j]='#';t=s-1ll*(n-1)*n*n*(n+1)/4;for(int i=2;t<n*(n-1);++i) {for(int x=1;x<i&&t<n*(n-1);++x) a[x][i-x]='.',t+=(n-x)*(n+1-i+x);}int x=0,y=0;while((t-x*n)%(n+1)) ++x;y=(t-x*n)/(n+1);while(y-n>=x+n+1) y-=n,x+=n+1;for(int i=n+1,k;x>0;i-=k+1,x-=k*(k-1)/2) {for(k=1;k*(k+1)/2<=x;++k);for(int j=i;j>i-k;--j) a[n+1][j]='#';}for(int i=n,k;y>0;i-=k+1,y-=k*(k-1)/2) {for(k=1;k*(k+1)/2<=y;++k);for(int j=i;j>i-k;--j) a[j][n+2]='#';}cout<<m<<" "<<m<<"\n";for(int i=1;i<=m;++i,cout<<"\n") for(int j=1;j<=m;++j) cout<<a[i][j];return 0;
}
*U. [CF2041N] Railway Construction (7)
Problem Link
考虑 Boruvka,但是直接 Boruvka 没有很好地利用图中的性质。
只观察性质较好的第一轮操作,取出 \(a\) 最小的 \(\sqrt m\) 个点,很显然只有 \(\mathcal O(\sqrt m)\) 个点的最小出边不连向这些点。
因此一轮增广后只会剩下 \(\mathcal O(\sqrt m)\) 个连通块,可以预处理出两两最短边之后 Prim。
考虑如何如何处理两个连通块 \(s,t\) 之间的最短边,设 \((s,t)\) 之间被删掉了 \(e\) 条边,那么只要枚举 \(s\) 的前 \(e+1\) 小点(实际上只需要 \(\sqrt e+1\) 个点),并分别求出到 \(t\) 的最小边,容易做到 \(\mathcal O(e)\),均摊就是 \(\mathcal O(m)\) 的。
现在我们就可以线性求图中 MST。
继续观察性质,注意到第一轮 Boruvka 后只有 \(\mathcal O(\sqrt m)\) 个度数 \(>1\) 的点,那么再连 \(\mathcal O(\sqrt m)\) 条边,非叶子节点个数依旧是 \(\mathcal O(\sqrt m)\) 级别,我们只要对这些点暴力重跑 Borvuka 即可。
时间复杂度 \(\mathcal O((n+m)\sqrt m)\)。
代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+5,MAXM=505;
int n,a[MAXN],b[MAXN],id[MAXN],rk[MAXN];
basic_string <int> G[MAXN],S[MAXM],Q[MAXN];
int dsu[MAXN],dg[MAXN],cnt=0,wn[MAXN],ban[MAXN];
int find(int x) { while(dsu[x]^x) x=dsu[x]=dsu[dsu[x]]; return x; }
bool inq[MAXN];
struct info {int x,y;inline friend bool operator <(const info &u,const info &v) { return a[u.x]+a[u.y]<a[v.x]+a[v.y]; }
} e[MAXM][MAXM],ds[MAXM];
inline void chkmin(info &x,const info&y) { x=y<x?y:x; }
int ec[MAXM][MAXM];
ll solve(bool ty) {ll ans=0; cnt=0,memset(ec,0,sizeof(ec));for(int i=1;i<=n;++i) dsu[i]=i,Q[i].clear();for(int i=1;i<=n;++i) if(!ban[i]) {++ban[i]; for(int x:G[i]) ++ban[x];for(int j=1;j<=n;++j) if(!ban[j]) {if(find(j)!=find(i)) {if(ty) ++dg[i],++dg[j],wn[i]=wn[j]=a[i]+a[j];ans+=a[i]+a[j],++cnt,dsu[find(i)]=find(j);}break;}--ban[i]; for(int x:G[i]) --ban[x];}int m=0;for(int i=1;i<=n;++i) if(!ban[i]&&dsu[i]==i) b[i]=++m,S[m].clear();for(int i=1;i<=n;++i) if(!ban[i]) b[i]=b[find(i)],S[b[i]]+=i;for(int i=1;i<=n;++i) if(!ban[i]) for(int x:G[i]) ++ec[b[i]][b[x]];for(int i=1;i<=m;++i) for(int j=i+1;j<=m;++j) {e[i][j]=e[j][i]={0,0};int lim=sqrt(ec[i][j]);for(int k=0;k<=lim&&k<(int)S[i].size();++k) Q[S[i][k]]+=j;for(int k=0;k<=lim&&k<(int)S[j].size();++k) Q[S[j][k]]+=i;}for(int i=1;i<=n;++i) if(!ban[i]) {for(int x:G[i]) ++ban[x];for(int q:Q[i]) for(int x:S[q]) if(!ban[x]) { chkmin(e[b[i]][q],{i,x}); break; }for(int x:G[i]) --ban[x];}for(int i=1;i<=m;++i) for(int j=1;j<=m;++j) if(e[i][j]<e[j][i]) e[j][i]={e[i][j].y,e[i][j].x};for(int i=1;i<=m;++i) inq[i]=(i==1),ds[i]=e[1][i];for(int t=1;t<m;++t) {info z={0,0};for(int i=1;i<=m;++i) if(!inq[i]) chkmin(z,ds[i]);if(!z.x) break;int u=b[z.y]; ++cnt,inq[u]=true,ans+=a[z.x]+a[z.y];if(ty) wn[z.x]=wn[z.y]=a[z.x]+a[z.y],++dg[z.x],++dg[z.y];for(int i=1;i<=m;++i) if(!inq[i]) chkmin(ds[i],e[u][i]);}return ans;
}
ll ans[MAXN];
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int m; cin>>n>>m,a[0]=1e9+7;for(int i=1;i<=n;++i) cin>>a[i],id[i]=i;sort(id+1,id+n+1,[&](int x,int y){ return a[x]<a[y]; });for(int i=1;i<=n;++i) rk[id[i]]=i;sort(a+1,a+n+1);for(int i=1,u,v;i<=m;++i) cin>>u>>v,G[rk[u]]+=rk[v],G[rk[v]]+=rk[u];ll z=solve(1);if(cnt<n-2) {for(int i=1;i<=n;++i) cout<<"-1"<<" \n"[i==n];return 0;}if(cnt==n-2) {for(int i=1;i<=n;++i) cout<<(dg[rk[i]]?-1:z)<<" \n"[i==n];return 0;}for(int i=1;i<=n;++i) {int x=rk[i];if(dg[x]==1) { cout<<z-wn[x]<<" \n"[i==n]; continue; }++ban[x]; ll w=solve(0);cout<<(cnt==n-2?w:-1)<<" \n"[i==n],--ban[x];}return 0;
}
V. [CF2084H] Turtle and Nediam 2 (5.5)
Problem Link
观察题目的操作,注意到删除元素一定是 \(s_i\) 或 \(s_{i+1}\),因此 \(s_{i+2}\) 总是不变,并且除非 \(s_i=s_{i+1}=s_{i+2}\) 时生成两个 \(s_{i+2}\),否则必定生成 \(\overline{s_{i+2}}s_{i+2}\)。
那么从后往前考虑判定一个字符串 \(t\)。
首先 \(s,t\) 末尾必定相等,不妨设为 \(0\),如果 \(t\) 的末尾是 \(00\),那么要求 \(s\) 的末尾也是 \(00\),否则我们可以任意选 \(s\) 的一个后缀 \(s[k,|s|]\),要求范围内有 \(1\),然后删掉 \(s[k,|s|-1]\) 替换成 \(1\)。
那么我们考虑 \(t\) 中的每个连续段:首先 \(s\) 末尾段长要大于等于 \(t\) 的末尾段长,然后我们能向前转移到某个 \(s\) 的\(1\) 连续段,要求其长度超过 \(t\) 的倒数第二段段长。
容易发现我们贪心匹配最近的是最优的,因为每次切换连续段时都能转移到前面任意的连续段。
那么尝试计算转移到 \(s\) 从后往前的第 \(k\) 个连续段 \([l,r]\) 时,最多能生成几个 \(1\):首先至少有 \(r-l+1\) 个原有的 \(1\),然后对于中间的 \(k-1\) 个 \(0,1\) 连续段,都可以通过操作删到长度为 \(1\),然后从前往后每次把 \(010\) 变成 \(10\) 即可,因此这个段能匹配长度 \(\le r-l+k\) 的情况。
注意 \(t\) 的开头一段必须匹配 \(s\) 的开头一段,或者 \(t_1\ne s_1\),此时 \(t_2\ne t_1\),即 \(t_2\) 所属段匹配完成后直接把剩余前缀全部删除变成 \(t_1\)。
预处理每段长度并翻转序列,设段长为 \(a_1\sim a_m\),\(f_i\) 为当前匹配到 \(i\) 的方案数,首先会转移到 \(f_{i+1}\),其次会找 \(a_{x}+\lfloor \frac x2\rfloor\) 的的后缀最大值转移,可以写出如下的暴力代码:Submission Link。
用单调栈维护后缀最值的结构,我们从后往前扫一遍,离线下来对单调栈结构的修改,然后每次转移 \(f_i\) 就是给单调栈的一个前缀进行更新,可以把懒标记打到当前栈顶上,弹出时 pushdown 到新的栈顶上即可。
时间复杂度 \(\mathcal O(n)\)。
代码:
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e6+5,MOD=1e9+7;
int n,m,a[MAXN],f[MAXN];
vector <int> op[MAXN];
struct ds {int b[MAXN],w[MAXN],k;void init() { for(;k;--k) b[k]=w[k]=0; }void add(int x) {for(;k&&a[b[k]]+b[k]/2<=a[x]+x/2;--k) op[x-1].push_back(b[k]);b[++k]=x;}void pop() {if(k>1) w[k-1]=(w[k-1]+w[k])%MOD,f[b[k-1]]=(f[b[k-1]]+1ll*w[k]*(a[b[k-1]]-a[b[k]]+(b[k-1]-b[k])/2))%MOD;b[k]=w[k]=0,--k;}void upd(int z) { w[k]=(w[k]+z)%MOD; }
} g[2];
void solve() {cin>>n,m=0;for(int i=1,z=0;i<=n;++i) {char h; cin>>h;if(!m||h!=z) a[++m]=1,z=h;else ++a[m];}if(m==1) return cout<<n-1<<"\n",void();for(int i=1;i<=m;++i) f[i]=0,op[i].clear();reverse(a+1,a+m+1),g[0].init(),g[1].init();for(int i=m-2;i;--i) g[i&1].add(i+1);f[1]=a[1];for(int i=1;i<=m-2;++i) {auto &o=g[i&1];o.w[o.k]=(o.w[o.k]+f[i])%MOD;f[i+1]=(f[i+1]+1ll*f[i]*a[i+1])%MOD;o.pop(),reverse(op[i].begin(),op[i].end());for(int x:op[i]) o.b[++o.k]=x;}int ans=0;for(int i=m-1;i>0;i-=2) ans=(ans+1ll*(a[m]+(m-1-i)/2)*f[i])%MOD;for(int i=m-2;i>0;i-=2) ans=(ans+1ll*(m-i)/2*f[i])%MOD;cout<<ans<<"\n";
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _; cin>>_;while(_--) solve();return 0;
}
*W. [CF2135F] To the Infinity (7)
Problem Link
尝试化简 \(f_u\),按左儿子展开时 $f_u=(f_{L(u)}){f_{R(u)}}=(f_{L(L(u))})f_{R(L(u))}}=\cdots $。
因此 \(f_u=x^{\prod_k f_{R(L^k(u))}}\),比较 \(f_u,f_v\) 只要比较 \(\prod_{k=0}^{\infty}f_{R(L^k(u))},\prod_{k=0}^{\infty}f_{R(L^k(v))}\)。
尝试比较两个集合 \(S,T\) 的 \(\prod f_u\),一个想法是如果 \(f_u>f_v\),那么必定有 \(f_u\ge (f_v)^x\),可以用归纳法证明。
所以只要 \(S\) 中的最大值大于 \(T\) 中最大值,则剩余的 \(\prod f\) 贡献不会超过 \((f_v)^n\),必定是 \(S\) 更大。
因此我们只要把 \(S,T\) 按 \(f\) 降序排列并比较字典序即可。
然后用数据结构维护之:注意到 \(f_u\) 总是小于 \(f_{fa(u)}\),因此只要确定所有儿子排名之后再计算父亲的 \(f\),即用堆维护所有叶子,每次删除最小值,如果其父亲变成叶子就计算 \(f\) 并插入堆中。
维护和比较 \(f\) 直接用线段树维护哈希,注意可能有 \(f_u\) 相等,线段树上要维护每种 \(f\) 的个数。
时间复杂度 \(\mathcal O(n\log^2n)\)。
代码:
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int MAXN=4e5+5;
mt19937_64 rnd(time(0));
ull hw[MAXN];
struct Segt {int ls[MAXN*20],rs[MAXN*20],tot;ull hs[MAXN*20];void ins(int x,int l,int r,int q,int &p) {hs[p=++tot]=hs[q]+hw[x];if(l==r) return ;int mid=(l+r)>>1;if(x<=mid) ins(x,l,mid,ls[q],ls[p]),rs[p]=rs[q];else ins(x,mid+1,r,rs[q],rs[p]),ls[p]=ls[q];}bool cmp(int l,int r,int q,int p) {if(l==r) return hs[q]<hs[p];int mid=(l+r)>>1;return hs[rs[q]]!=hs[rs[p]]?cmp(mid+1,r,rs[q],rs[p]):cmp(l,mid,ls[q],ls[p]);}void init() {for(int i=1;i<=tot;++i) ls[i]=rs[i]=hs[i]=0;tot=0;}
} T;
int n,m,ls[MAXN],rs[MAXN],fa[MAXN],rt[MAXN],rk[MAXN];
struct cmp {inline bool operator()(int y,int x) const {return (T.hs[rt[x]]==T.hs[rt[y]])?x<y:T.cmp(1,n,rt[x],rt[y]);}
};
void solve() {cin>>n,m=0;for(int i=1;i<=n;++i) cin>>ls[i]>>rs[i],rk[i]=fa[i]=rt[i]=0;priority_queue <int,vector<int>,cmp> Q;for(int i=1;i<=n;++i) {if(!ls[i]) Q.push(i);else fa[ls[i]]=fa[rs[i]]=i;}for(int p=0,u;Q.size();p=u) {u=Q.top(),Q.pop(),cout<<u<<" ";rk[u]=m+=(!p||T.hs[rt[u]]!=T.hs[rt[p]]);if(u==1||!rk[ls[fa[u]]]||!rk[rs[fa[u]]]) continue;T.ins(rk[rs[fa[u]]],1,n,rt[ls[fa[u]]],rt[fa[u]]),Q.push(fa[u]);}cout<<"\n",T.init();
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);for(int i=1;i<MAXN;++i) hw[i]=rnd()>>20;int _; cin>>_;while(_--) solve();return 0;
}
X. [CF2127F] Hamed and AghaBalaSar (2)
Problem Link
\(f\) 的本质就是把每个最大值减去下一个数的值再求和。
对每个最大值 \(v\) 算贡献,可以假设最大值不是 \(a_n\),那么枚举下一个数 \(t\),然后容斥钦定 \(k\) 个位置 \(>v\),此时 \(k\le\dfrac nv\),先枚举 \((v,k)\),对所有 \(t\) 算答案可以通过组合恒等式写成上指标求区间和的形式 \(\mathcal O(1)\) 计算。
时间复杂度 \(\mathcal O(n\log n)\)。
代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=4e5+5,MOD=1e9+7;
ll ksm(ll a,ll b=MOD-2) { ll s=1; for(;b;a=a*a%MOD,b>>=1) if(b&1) s=s*a%MOD; return s; }
ll fac[MAXN],ifac[MAXN],s;
ll C(int x,int y) { return y<0||y>x?0:fac[x]*ifac[y]%MOD*ifac[x-y]%MOD; }
ll S(int l,int r,int y) { l=max(l,y); return l>r?0:(C(r+1,y+1)+MOD-C(l,y+1))%MOD; }
void solve() {int n,m;cin>>n>>m,s=0;if(n==2) {for(int i=0;i<=m/2;++i) s=(s+m-2*i)%MOD;return cout<<s<<"\n",void();}for(int v=0;v<=m;++v) {for(int i=0;i<=n-2&&i<=(m-v)/(v+1);++i) {int mx=m-v-(v+1)*i+n-3;s=(s+(S(mx-v,mx,n-3)*(MOD+v-mx-1)+S(mx+1-v,mx+1,n-2)*(n-2))%MOD*(i&1?MOD-C(n-2,i):C(n-2,i)))%MOD;}if(n==3) { s=(s+(m>=2*v?max(0,3*v-m):0))%MOD; continue; }for(int i=0;i<=n-3&&i<=(m-2*v)/(v+1);++i) {int mx=m-2*v-(v+1)*i+n-4;s=(s+(S(mx-v,mx,n-4)*(MOD+v-mx-1)+S(mx+1-v,mx+1,n-3)*(n-3))%MOD*(i&1?MOD-C(n-3,i):C(n-3,i))%MOD*(n-2)%MOD)%MOD;} }cout<<s<<"\n";
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);for(int i=fac[0]=1;i<MAXN;++i) fac[i]=fac[i-1]*i%MOD;ifac[MAXN-1]=ksm(fac[MAXN-1]);for(int i=MAXN-1;i;--i) ifac[i-1]=ifac[i]*i%MOD;int _; cin>>_;while(_--) solve();return 0;
}
Y. [CF2122G] Tree Parking (3.5)
Problem Link
首先考虑树结构确定的做法,设 \(f_u\) 表示 \(u\) 子树的答案,那么限制就是每个子树的子序列合法,且 \((l_u,r_u)\) 要相邻。
那么 \(f_u=(2siz_u-2)!\times (2siz_u-1)\times \prod_v\dfrac{f_v}{(2siz_v)!}\),则 \(f_1=\dfrac{\prod_u (2siz_u-1)!}{\prod_{u>1} (2siz_u)!}=\dfrac{\prod{(2n)!}}{2^n\prod siz_u!}\)。
只要求 \(\sum_T\prod_u\dfrac 1{siz_u!}\),可以转成求所有合法树 \(T\) 的重标号 \(p\) 计数,满足任意 \(p_u<p_{fa(u)}\)。
我们可以先枚举一棵树 \(T\) 以及其重标号 \(p\),然后求原标号时任意 \(q_1=1\) 的排列 \(q\) 都能作为 \(p^{-1}\),因此直接乘上 \((n-1)!\)。
现在要计数有多少 \((T,p)\),直接按标号加入,\(f_{i,j}\) 表示 \(i\) 个点有 \(j\) 个叶子的方案数,转移就是 \(f_{i,j}=f_{i-1,j-1}\times (i-j)+f_{i-1,j}\times j\)。
打表发现 \(f_{i,j}\) 是欧拉数,可以直接用公式 \(T(n,m)=\sum_{i=0}^m(-1)^i\binom{n+1}i(m+1-i)^n\) 计算。
时间复杂度 \(\mathcal O(n\log n)\)。
代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=4e5+5,MOD=998244353;
ll ksm(ll a,ll b=MOD-2) { ll s=1; for(;b;a=a*a%MOD,b>>=1) if(b&1) s=s*a%MOD; return s; }
ll fac[MAXN],ifac[MAXN],f[MAXN],g[MAXN];
ll C(int x,int y) { return y<0||y>x?0:fac[x]*ifac[y]%MOD*ifac[x-y]%MOD; }
ll S(int n,int m) {ll s=0;for(int i=0;i<=m;++i) s=(s+(i&1?MOD-C(n+1,i):C(n+1,i))*ksm(m+1-i,n))%MOD;return s;
}
void solve() {int n,m;cin>>n>>m;ll ans=S(n-1,m-1)*ifac[n]%MOD*fac[n-1]%MOD*fac[2*n]%MOD*ksm(2,MOD-1-n)%MOD;cout<<ans<<"\n";
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);for(int i=fac[0]=1;i<MAXN;++i) fac[i]=fac[i-1]*i%MOD;ifac[MAXN-1]=ksm(fac[MAXN-1]);for(int i=MAXN-1;i;--i) ifac[i-1]=ifac[i]*i%MOD;int _; cin>>_;while(_--) solve();return 0;
}
Z. [CF2066E] Tropical Season (3)
Problem Link
模拟判定的过程,首先对 \(a\) 排序,然后如果有 \(a_i=a_{i+1}\),那么称这两个桶,如果有毒药就直接解决,否则就得到了两桶水。
然后我们可以找到 \(a_{j+1}-a_j\le 2a_i\),然后把 \(a_i,a_{i+1}\) 倒进 \(a_j\) 中直到 \(a_j=a_{j+1}\),然后就能确定这两个桶是否是水桶。
因此答案的过程一定是不断维护若干水桶,然后用刚才的方法不断得到新的水桶,设当前水量和为 \(S\),可以证明能得到水桶 \(a_i\) 当且仅当 \(S\ge\min(a_i,a_{i+1}-a_i)\)。
我们要求最后得到至少 \(n-1\) 个水桶,很显然我们会按 \(b_i=\min(a_i,a_{i+1}-a_i)\) 从小到大贪心。
这个问题类似求 \(\mathrm{mex}\),考虑值域倍增分块,按 \(\log_2 b_i\) 分块,只要我们在块 \([2^k,2^{k+1})\) 中得到任意一个水桶,则新的 \(S\) 必定 \(\ge 2^{k+1}\),从而得到这个块中所有的水桶。
用 std::multiset
维护序列,每个块用可删堆维护最小值。
时间复杂度 \(\mathcal O(n\log n\log V)\)。
代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct Heap {priority_queue <int,vector<int>,greater<>> qi,qo;ll su;void add(int x,int y,int k) { su+=k*y,(k>0?qi:qo).push(x); }int sz() { return qi.size()-qo.size(); }int top() {while(qo.size()&&qi.top()==qo.top()) qi.pop(),qo.pop();return qi.top();}
} f[32];
multiset <int> S;
ll s0=0; int c0=0;
int w(auto it) {if(S.size()==1) return 0;if(it==S.begin()) return *next(it)-*it;if(it==--S.end()) return *it;return min(*next(it)-*it,*it);
}
void add(auto it,int k) {int x=w(it),y=*it;if(!x) s0+=k*y,c0+=k;else f[__lg(x)].add(x,y,k);
}
void ins(int z) {auto it=S.lower_bound(z);if(it!=S.end()) add(it,-1);if(it!=S.begin()) add(prev(it),-1);it=S.insert(it,z),add(it,1);if(it!=S.begin()) add(prev(it),1);if(it!=--S.end()) add(next(it),1);
}
void ers(int z) {auto it=S.lower_bound(z);add(it,-1);if(it!=S.begin()) add(prev(it),-1);if(it!=--S.end()) add(next(it),-1);it=S.erase(it);if(it!=S.end()) add(it,1);if(it!=S.begin()) add(prev(it),1);
}
bool qry() {int ct=c0,n=S.size(); ll su=s0;for(int k=0;k<32&&ct<n-1;++k) if(f[k].sz()) {if(su<f[k].top()) return ct>=n-1;ct+=f[k].sz(),su+=f[k].su;}return ct>=n-1;
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int n,q; cin>>n>>q;for(int i=1,x;i<=n;++i) cin>>x,S.insert(x);for(auto it=S.begin();it!=S.end();++it) add(it,1);cout<<(qry()?"Yes\n":"No\n");for(char op;q--;) {int x; cin>>op>>x;op=='+'?ins(x):ers(x);cout<<(qry()?"Yes\n":"No\n");}return 0;
}