个人训练赛题解（七）
\(\text{By DaiRuiChen007}\)
Round #25 - 2024.10.23
A. [AGC010D] Divisor
题目大意
给定 \(a_1\sim a_n\)，保证 \(\gcd(a_1,\dots,a_n)=1\)。
两人轮流操作，每次给一个大于一的 \(a_i\) 减一，然后所有 \(a_i\) 约去 \(\gcd(a_1,\dots,a_n)\)，无法操作者输，求谁必胜。
数据范围：\(n\le 10^5\)。
思路分析
如果 \(a_i\) 中有 \(1\)，那么说明此后 \(\gcd(a)=1\)，答案只和 \(\sum (a_i-1)\) 的奇偶性有关。
此时先手必胜当且仅当 \(a\) 中有奇数个偶数。
然后考虑一般的情况，如果偶数个数仍然为奇数，那么修改一个偶数，此时奇数个数 \(\ge 2\)（初始至少存在一个偶数），后手无论如何操作一定有 \(2\nmid \gcd(a)\)，无法改变元素奇偶性。
因此只要 \(a\) 中有奇数个偶数，先手必胜。
否则考虑刚才的结果，如果此时奇数个数 \(\ge 2\)，先手无法改变元素奇偶性，必败，否则必定操作这个元素，然后交换先后手变成一个值域折半的子问题，递归计算即可。
时间复杂度 \(\mathcal O(n\log^2V)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n,a[MAXN];
void solve(string A,string B) {
int s=0;
for(int i=1;i<=n;++i) s^=(a[i]-1)&1;
if(s) return cout<<A,void();
int o=0;
for(int i=1;i<=n;++i) {
if(a[i]==1) return cout<<B,void();
if(a[i]&1) {
if(o) return cout<<B,void();
o=i;
}
}
--a[o];
int g=a[1];
for(int i=2;i<=n;++i) g=__gcd(a[i],g);
for(int i=1;i<=n;++i) a[i]/=g;
solve(B,A);
}
signed main() {
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i];
solve("First\n","Second\n");
return 0;
}
B. [AGC011D] Reflect
题目大意
给定 \(n\) 个门，初始有开有关，\(k\) 次操作从第一个门左侧扔一个球进去，如果一个门是开的，球会穿过，否则会被反弹，在此之后门会改变开关状态，求最终每个门的状态。
数据范围：\(n\le 2\times 10^5,k\le 10^9\)。
思路分析
如果第一个门是关的，会打开第一个门并结束，否则考虑整个过程：对于第 \(i\) 个门，球第一次经过时一定是从左到右，且此时第 \(i-1\) 个门是关着的。
如果第 \(i\) 个门是开着的，那么会直接穿过并继续，否则会发开第 \(i-1\) 个门并反弹。
那么第 \(i-1\) 个门最终的状态就是第 \(i\) 个门原始的状态取反。
因此第一个门是开着的时，会将所有门翻转并循环左移一位。
那么维护当前的偏移量，可以 \(\mathcal O(1)\) 维护每次扔球的过程。
打表发现，经过 \(\mathcal O(n)\) 次操作后序列的状态构成长度为 \(2\) 的循环节，因此只要模拟 \(\mathcal O(n)\) 次。
时间复杂度 \(\mathcal O(n)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
char s[MAXN];
signed main() {
int n,k;
scanf("%d%d%s",&n,&k,s);
k=min(k,4*n+(k&1));
int i=0;
while(k--) {
if(s[i%n]==(i&1?'B':'A')) s[i%n]^=3;
else ++i;
}
for(int j=i;j<i+n;++j) printf("%c",s[j%n]^(i&1?3:0));
return 0;
}
C. [AGC014E] Cut
题目大意
给定一棵 \(n\) 个点的树，每次选择一条边割掉，然后在两端连通块中选一个点，在第二棵树上连起来，求能否在第二棵树上构造出目标树。
数据范围：\(n\le 10^5\)。
思路分析
考虑第一条删除的边 \(e\)，此后两个连通块中不会再连边，因此第一次连的边必须是唯一跨越 \(e\) 的边。
因此一个朴素的做法就是把目标树上的边看成路径，覆盖在第一棵树上，每次取出被覆盖次数恰好 \(=1\) 的一条边割断，连接覆盖这条边的路径。
遇到多个覆盖次数 \(=1\) 的边时，可以任选一条，用树剖维护该过程即可。
时间复杂度 \(\mathcal O(n\log^2n)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5,inf=1e9;
int n,rk[MAXN],cov[MAXN];
struct ZkyGt1 {
static const int N=1<<17;
int tr[N<<1];
void psu(int p) {
int k=min(tr[p<<1],tr[p<<1|1]);
tr[p]+=k,tr[p<<1]-=k,tr[p<<1|1]-=k;
}
void init() {
for(int i=0;i<N;++i) tr[i+N]=(1<i&&i<=n?cov[rk[i]]:inf);
for(int i=N-1;i;--i) psu(i);
}
void add(int l,int r,int x) {
for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1) {
if(~l&1) tr[l^1]+=x;
if(r&1) tr[r^1]+=x;
psu(l>>1),psu(r>>1);
}
for(;l>1;l>>=1) psu(l>>1);
}
int qry() {
int p=1;
while(p<N) {
p<<=1;
if(tr[p]>tr[p^1]) p^=1;
}
tr[p]=inf;
for(int x=p;x>1;x>>=1) psu(x>>1);
return rk[p-N];
}
} T;
struct FenwickTree {
int tr[MAXN],s;
void add(int x,int v) { for(;x<=n;x+=x&-x) tr[x]^=v; }
int qry(int x) { for(s=0;x;x&=x-1) s^=tr[x]; return s; }
} Q;
int st[MAXN],ed[MAXN],siz[MAXN],dep[MAXN],fa[MAXN],hson[MAXN],top[MAXN],dfn[MAXN],dcnt;
vector <int> G[MAXN];
void dfs0(int u,int fz) {
siz[u]=1,dep[u]=dep[fz]+1,fa[u]=fz;
for(int v:G[u]) if(v^fz) {
dfs0(v,u),siz[u]+=siz[v];
if(siz[v]>siz[hson[u]]) hson[u]=v;
}
}
void dfs1(int u,int rt) {
top[u]=rt,dfn[u]=++dcnt,rk[dcnt]=u;
if(hson[u]) dfs1(hson[u],rt);
for(int v:G[u]) if(v!=fa[u]&&v!=hson[u]) dfs1(v,v);
}
int LCA(int u,int v) {
while(top[u]^top[v]) {
if(dep[top[u]]<dep[top[v]]) swap(u,v);
u=fa[top[u]];
}
return dep[u]<dep[v]?u:v;
}
void add(int u,int v,int k) {
while(top[u]^top[v]) {
if(dep[top[u]]<dep[top[v]]) swap(u,v);
T.add(dfn[top[u]],dfn[u],k),u=fa[top[u]];
}
if(dep[u]<dep[v]) swap(u,v);
if(u^v) T.add(dfn[v]+1,dfn[u],k);
}
void dfs3(int u) {
for(int v:G[u]) if(v^fa[u]) dfs3(v),cov[u]+=cov[v];
}
signed main() {
ios::sync_with_stdio(false);
cin>>n;
for(int i=1,u,v;i<n;++i) cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
dfs0(1,0),dfs1(1,1);
for(int i=1;i<n;++i) {
cin>>st[i]>>ed[i];
Q.add(dfn[st[i]],i),Q.add(dfn[ed[i]],i);
++cov[st[i]],++cov[ed[i]];
cov[LCA(st[i],ed[i])]-=2;
}
dfs3(1),T.init();
for(int o=1;o<n;++o) {
if(T.tr[1]!=1) return puts("NO"),0;
int x=T.qry(),i=Q.qry(dfn[x]+siz[x]-1)^Q.qry(dfn[x]-1);
add(st[i],ed[i],-1);
Q.add(dfn[st[i]],i),Q.add(dfn[ed[i]],i);
}
puts("YES");
return 0;
}
D. [AGC012E] Camel
题目大意
数轴上有 \(n\) 个点 \(a_1\sim a_n\)，当前移动距离上限为 \(x\)，每次操作可以移动到距离当前点 \(\le x\) 的 \(a_i\) 上，或者令 \(x\gets \lfloor x/2\rfloor\) 后移动到任意一点上，对每个 \(a_i\) 求从当前点出发能否遍历所有点。
数据范围：\(n,x\le 2\times 10^5\)。
思路分析
容易发现瞬移操作最多进行 \(\mathcal O(\log V)\) 次。
并且每次瞬移后会把当前点左侧和右侧距离 \(\le x\) 的点全部遍历，相当于覆盖一个区间的点。
那么我们需要在 \(\log V\) 个线段集合中各选择一个，覆盖 \([1,n]\) 中的所有点。
可以用 dp 解决，\(f_S\) 表示在 \(S\) 对应的集合中选过线段，覆盖的前缀长度最大值，有解要求 \(f_U=n\)。
要对每个起点求答案，相当于钦定了第一个集合中选择的线段，那么我们分别计算 \(f_S,g_S\) 表示用 \(S\) 中线段覆盖的前缀、后缀长度最大值。
求答案时枚举 \(S\) 即可，但此时要枚举 \(\mathcal O(n)\) 次，不可接受，但我们发现同一条线段内的只需要枚举一次，并且初始线段个数 \(>\log V\) 时一定无解，因此只要枚举 \(\mathcal O(\log V)\) 次。
时间复杂度 \(\mathcal O((n+V)\log V)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int n,m,K,V[20],a[MAXN],lp[20][MAXN],rp[20][MAXN],f[1<<20],g[1<<20],t[MAXN];
signed main() {
scanf("%d%d",&n,&K);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=K;i;i>>=1) V[m++]=i;
V[m++]=0;
for(int k=0;k<m;++k) {
lp[k][1]=1,rp[k][n]=n;
for(int i=2;i<=n;++i) lp[k][i]=(a[i]-a[i-1]>V[k])?i:lp[k][i-1];
for(int i=n-1;i;--i) rp[k][i]=(a[i+1]-a[i]>V[k])?i:rp[k][i+1];
}
for(int s=0;s<(1<<m);++s) {
f[s]=0,g[s]=n+1;
for(int i=0;i<m;++i) if(s>>i&1) {
f[s]=max(f[s],rp[i][f[s^(1<<i)]+1]);
g[s]=min(g[s],lp[i][g[s^(1<<i)]-1]);
}
}
int q=0;
for(int i=1;i<=n;++i) if(i==n||a[i+1]-a[i]>K) t[++q]=i;
if(q>m) {
for(int i=1;i<=n;++i) puts("Impossible");
return 0;
}
for(int i=1;i<=q;++i) {
int U=(1<<m)-2; bool ok=0;
for(int s=0;s<(1<<m);++s) if(!(s&1)&&t[i-1]<=f[s]&&g[U^s]<=t[i]+1) {
ok=1; break;
}
for(int j=t[i];j>t[i-1];--j) puts(ok?"Possible":"Impossible");
}
return 0;
}
*E. [AGC011F] Timetable
题目大意
给定 \(n\) 段铁路连接站点 \(0\sim n+1\)，每隔 \(k\) 时刻分别有一辆 \(0\to n+1\) 和 \(n+1\to 0\) 的列车发车，穿过第 \(i\) 段铁路的时刻是 \(t_i\)。
安排两种列车在每个站点停靠的时间，使得对于若干条特殊铁路，两种列车穿过其的时间不交，最小化两种列车运行时间之和。
数据范围：\(n\le 10^5\)。
思路分析
在 \(\bmod k\) 意义下考虑所有时间，那么从 \(n+1\to 0\) 的列车等价于往时间轴负方向移动。
设 \(x_i,y_i\) 表示两种方向的列车在第 \(i\) 个站的停靠时间，对应的大写字母表示其数组前缀和。
那么我们要求就是 \([X_{i-1}+T_{i-1},X_{i-1}+T_i]\) 与 \([-Y_{i-1}-T_{i},-Y_{i-1}-T_{i-1}]\) 交集为空。
展开后可以得到这相当于 \(X_{i-1}+Y_{i-1}\in[-2T_{i-1},-2T_i]\)。
目标是最小化 \(X_n+Y_n+2T_n\)，直接 dp 设 \(f_{i,j}\) 表示 \(X_i+Y_i=j\) 的最小代价。
转移时 \(f_{i,j}+x\to f_{i+1,(j+x)\bmod k}\)，要求 \((j+x)\bmod k\in [l_i,r_i]\)，发现每个 \(j\) 都是某个 \(l_i/r_i\)，可以离散化。
直接把 \([l_i,r_i]\) 以外的 dp 值全部删除并插入到 \(l_i\) 上即可，用 map 维护 dp 过程即可。
时间复杂度 \(\mathcal O(n\log n)\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+5;
const ll inf=1e18;
int n,m=0,p=0,K;
ll a[MAXN],L[MAXN],R[MAXN],w[MAXN*2];
map <int,ll> dp;
signed main() {
scanf("%d%d",&n,&K);
for(int i=1,op;i<=n;++i) {
scanf("%lld%d",&a[i],&op);
if(op==1&&2*a[i]>K) return puts("-1"),0;
a[i]+=a[i-1];
if(op==1) ++m,L[m]=(K-2*a[i-1]%K)%K,R[m]=(K-2*a[i]%K)%K,w[++p]=L[m],w[++p]=R[m];
}
sort(w,w+p+1),p=unique(w,w+p+1)-w;
for(int i=0;i<=p;++i) dp[i]=0;
for(int i=1;i<=m;++i) {
int l=lower_bound(w,w+p,L[i])-w;
int r=lower_bound(w,w+p,R[i])-w;
ll z=inf;
if(l<=r) {
auto il=dp.begin(),ir=dp.lower_bound(l);
for(auto it=il;it!=ir;++it) z=min(z,it->second+w[l]-w[it->first]);
dp.erase(il,ir);
il=dp.upper_bound(r),ir=dp.end();
for(auto it=il;it!=ir;++it) z=min(z,it->second+w[l]-w[it->first]+K);
dp.erase(il,ir);
} else {
auto il=dp.upper_bound(r),ir=dp.lower_bound(l);
for(auto it=il;it!=ir;++it) z=min(z,it->second+w[l]-w[it->first]);
dp.erase(il,ir);
}
if(dp.count(l)) dp[l]=min(dp[l],z);
else dp[l]=z;
}
ll ans=inf;
for(auto it:dp) ans=min(ans,it.second);
printf("%lld\n",ans+2*a[n]);
return 0;
}
*F. [AGC013F] Flip
题目大意
给定 \(n-1\) 个二元组 \((a_i,b_i)\)，以及 \(n\) 个数 \(c_1\sim c_{n}\)。
、\(q\) 次独立询问，加入一个新的二元组 \((d_i,e_i)\)，给每个二元组选择 \(x_i\in \{a_i,b_i\}\)，并把他们和 \(c\) 两两匹配，要求 \(x_i\le c_{p_i}\)。最大化 \(x_i=a_i\) 的个数。
数据范围：\(n,q\le 10^5\)。
思路分析
先离散化使得 \(c_1\sim c_{n}=1\sim n\)。
考虑如何判定一组 \(\{x_i\}\) 是否合法，显然将两个序列都升序排列最优，但这样的条件不方便求答案。
可以转化成给 \(f[x_i,n]\) 后缀加一，\(f[c_i,n]\) 后缀减一，要求所有 \(f_i\ge 0\)。
不妨假设所有 \(b_i<a_i\)，先选择所有 \(x_i=a_i\)，然后我们可以以 \(-1\) 的代价将 \(f[b_i,a_i)\) 区间加一，要求调整成所有 \(f_i\ge 0\)。
可以采用朴素贪心，从前往后扫描所有 \(f_i\)，遇到一个 \(f_i<0\) 就找到覆盖 \(f_i\) 且右端点最大的区间进行 \(+1\)，用优先队列维护。
考虑优化，我们呢可以枚举每个询问选了 \(d_i\) 还是 \(e_i\)，那么就要对每个 \(x\) 求出给 \(f[x,n]\) 加一后，用初始的 \([b_i,a_i)\) 使得所有 \(f_i\ge 0\) 的最小代价。
我们发现如果 \(f_i<-1\)，那么 \(f[x,n]\) 加一后也是负数，因此至少有一个原始区间 \([b_j,a_j)\) 包含 \(i\)，根据贪心，从后向前找每个 \(f_i<-1\)，取出左端点最小的一个区间进行 \(+1\) 一定是最优的。
那么我们可以先用一些操作使得所有 \(f_i\ge -1\)，然后 \(f[x,n]\) 加一后说明 \(f[x,n]\ge 0\)，只要求出 \(f[1,x-1]\) 的答案，然后用前述贪心从左到右求出每个前缀的答案即可。
时间复杂度 \(\mathcal O(n\log n+q)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5,inf=1e9;
int n,m,a[MAXN],b[MAXN],c[MAXN],qx[MAXN],qy[MAXN];
int rv,f[MAXN],tg[MAXN],dp[MAXN],nxt[MAXN];
vector <int> op[MAXN];
bool st[MAXN];
void solve1() {
priority_queue <array<int,2>,vector<array<int,2>>,greater<array<int,2>>> q;
for(int i=n,s=0;i>=1;--i) {
s+=tg[i];
for(int o:op[i]) q.push({b[o],o});
while(s+f[i]<-1) {
while(q.size()&&q.top()[0]>i) q.pop();
if(q.empty()) {
for(int j=1;j<=m;++j) puts("-1");
exit(0);
}
int z=q.top()[1]; q.pop();
st[z]=true,++rv,++s,++tg[a[z]-1],--tg[b[z]-1];
}
}
}
void solve2() {
priority_queue <array<int,2>> q;
for(int i=1,s=0;i<=n;++i) {
s+=tg[i],dp[i+1]=dp[i];
for(int o:op[i]) q.push({a[o]-1,o});
if(s+f[i]<0) {
while(q.size()&&q.top()[0]<i) q.pop();
if(q.empty()) {
for(int j=i+1;j<=n+1;++j) dp[j]=inf;
return ;
}
int z=q.top()[1]; q.pop();
++dp[i+1],++s,++tg[b[z]],--tg[a[z]];
}
}
}
signed main() {
scanf("%d",&n),++n;
for(int i=1;i<n;++i) scanf("%d%d",&a[i],&b[i]);
for(int i=1;i<=n;++i) scanf("%d",&c[i]),f[i]=-1;
sort(c+1,c+n+1);
scanf("%d",&m);
for(int i=1,x,y;i<=m;++i) {
scanf("%d%d",&x,&y);
qx[i]=lower_bound(c+1,c+n+1,x)-c;
qy[i]=lower_bound(c+1,c+n+1,y)-c;
}
for(int i=1;i<n;++i) {
a[i]=lower_bound(c+1,c+n+1,a[i])-c;
b[i]=lower_bound(c+1,c+n+1,b[i])-c;
b[i]=min(a[i],b[i]),++f[a[i]];
if(a[i]>b[i]) op[a[i]-1].push_back(i);
}
for(int i=1;i<=n;++i) f[i]+=f[i-1];
solve1();
for(int i=n;i>=1;--i) tg[i]+=tg[i+1],f[i]+=tg[i];
for(int i=1;i<=n;++i) op[i].clear();
for(int i=1;i<n;++i) if(!st[i]&&a[i]>b[i]) op[b[i]].push_back(i);
memset(tg,0,sizeof(tg));
solve2();
for(int i=1;i<=m;++i) printf("%d\n",max({-1,n-rv-dp[qx[i]],n-rv-dp[qy[i]]-1}));
return 0;
}
*G. [AGC014F] Localmax
题目大意
给定 \(1\sim n\) 排列 \(a\)，每次操作会把所有 LocalMax 按顺序放到序列末尾，求多少次操作后序列被排好序。
数据范围：\(n\le 2\times 10^5\)。
思路分析
我们发现整个排列中性质最好的元素就是 \(1\)，因为 \(1\) 的位置并不影响其他元素是否是 LocalMax。
因此我们先假设已知值域为 \([2,n]\) 的元素的排序过程，然后加入元素 \(1\) 的贡献。
假设将值域 \([2,n]\) 的元素排序需要 \(f\) 步：
如果 \(f=0\)：说明序列未经操作，当且仅当 \(a_1=1\) 时不用操作，否则需要进行一次操作。
否则我们需要判断操作 \(f\) 步后是否有 \(a_1=1\)。
考虑进行 \(f-1\) 次操作后的序列：此时序列开头不可能是 \(2\)，否则操作后一定会把 \(2\) 放到序列末尾。
那么我们可以取出此时的序列开头 \(x\)，分析 \((1,2,x)\) 的位置关系，一定是 \((x,1,2)\) 或 \((x,2,1)\)，容易发现操作之后 \(a_1=1\) 当且仅当此时他们的相对顺序是 \((x,1,2)\)。
我们发现在操作过程中，如果 \(x\) 时 LocalMax，那么 \(x\) 一定是序列开头：
由于操作次数有限，因此取出最后的一个时刻满足 \(x\) 是非开头 LocalMax，那么操作后 \(x\) 的前一个元素 \(y\) 也应该是原序列的 LocalMax。
那么由于 \(x\) 最终要变成序列开头，因此在此之后必然存在一次操作不同时移动 \(x,y\)，此时 \(x\) 又变成非开头 LocalMax，矛盾。
然后通过分类讨论 \((1,2,x)\) 的位置关系，我们发现进行任意次操作，他们的位置关系始终循环同构，因此只需要维护他们的初始位置关系即可判断复原 \(1\) 是否会额外产生一次操作。
倒序枚举，不断从值域 \([i,n]\) 转移到 \([i-1,n]\) 即可解决。
时间复杂度 \(\mathcal O(n)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int n,a[MAXN],p[MAXN];
signed main() {
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]),p[a[i]]=i;
int f=0,x=0;
for(int i=n-1;i;--i) {
if(!f) {
if(p[i]<p[i+1]);
else ++f,x=i+1;
} else {
if((p[x]<p[i]&&p[i]<p[i+1])||(p[i]<p[i+1]&&p[i+1]<p[x])||(p[i+1]<p[x]&&p[x]<p[i]));
else ++f,x=i+1;
}
}
printf("%d\n",f);
return 0;
}
Round #26 - 2024.10.29
A. [AGC015D] Or
题目大意
在 \([l,r]\) 的元素中选出一个子集 \(S\)，求 \(S\) 中元素按位或有多少种不同取值。
数据范围：\(l,r<2^{60}\)。
思路分析
首先 \([l,r]\) 内的元素肯定能得到，只需要考虑 \(>r\) 的元素有哪些能得到。
对于 \(l,r\) 二进制下的一段公共前缀，很显然不会影响答案，可以去掉。
此时设 \(r\) 的最高位为 \(x\)，次高位为 \(y\)，很显然 \(l<2^x\)。
那么我们把元素分成 \([l,2^x)\) 和 \([2^x,r)\) 两部分。
如果不选第一部分的元素，那么能得到的元素就是 \([2^x,2^x+2^{y+1}-1]\)，否则得到的元素就是 \([2^x+l,2^{x+1}-1]\)。
取出这两部分元素的并，并且和 \((r,2^{x+1}-1]\) 取并得到答案。
时间复杂度：\(\mathcal O(1)\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int d(ll x) { return x?63-__builtin_clzll(x):-1; }
signed main() {
ll A,B;
scanf("%lld%lld",&A,&B);
if(A==B) return puts("1"),0;
ll ans=B-A+1,i=d(A^B),S=(1ll<<i)-1;
A&=S,B&=S;
if(d(A)<=d(B)) ans+=S-B;
else ans+=S-A+(1ll<<(d(B)+1))-B;
printf("%lld\n",ans);
return 0;
}
B. [AGC015E] Car
题目大意
给定 \(n\) 个动点，第 \(i\) 个动点从 \(x_i\) 出发以 \(v_i\) 的速度移动，初始给若干个动点染色，两个动点相遇后，如果有一个染色点，会给另一个点也染色。
求有多少种初始染色方案，使得最终每个点都被染色。
数据范围：\(n\le 2\times 10^5\)。
思路分析
设 \(f(S)\) 表示给 \(S\) 染色后最终会有哪些点被染色，容易发现 \(f(S\cup T)=f(S)\cup f(T)\)，否则考虑一个 \(x\in f(S\cup T)\setminus f(S)\cup f(T)\)，不断考虑 \(x\) 从哪里被染色会导出矛盾。
观察 \(f(\{i\})\) 的性质，把每个点画在 \((v_i,x_i)\) 的坐标上，两个点相遇当且仅当连线斜率 \(<0\)，且连线越平缓相遇时间越早。
因此一条染色路径是斜率 \(<0\) 且递减的折线。
观察发现每个点可以染色的点是横坐标连续的一段区间，即 \(v_j<v_i\) 且 \(x_j>x_i\) 的最小的 \(j\)，以及 \(v_i<v_j\) 且 \(x_j<x_i\) 的最大的 \(j\)。
那么给一个点染色相当于选择一个区间，要求所有区间的并为 \([1,n]\)。
用 \(f_i\) 表示考虑当前恰好覆盖 \([1,i]\) 的方案数，转移时枚举 \(r=i\) 的区间，从 \(f_{l-1}\sim f_r\) 更新 \(f_r\)，注意右端点相同的区间要先从 \(l\) 最小的开始更新。
时间复杂度 \(\mathcal O(n\log n)\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5,MOD=1e9+7;
struct Node { int x,v; } a[MAXN];
ll f[MAXN],s[MAXN];
int n,l[MAXN],r[MAXN];
vector <int> op[MAXN];
signed main() {
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d%d",&a[i].x,&a[i].v);
sort(a+1,a+n+1,[&](auto i,auto j){ return i.v<j.v; });
map <int,int> q;
for(int i=1,t=0;i<=n;++i) {
if(a[i].x>t) q[t=a[i].x]=i;
l[i]=q.lower_bound(a[i].x)->second;
}
q.clear();
for(int i=n,t=MOD;i>=1;--i) {
if(a[i].x<t) q[t=a[i].x]=i;
r[i]=(--q.upper_bound(a[i].x))->second;
op[r[i]].push_back(l[i]);
}
f[0]=s[0]=1;
for(int i=1;i<=n;++i) {
s[i]=s[i-1];
sort(op[i].begin(),op[i].end());
for(int k:op[i]) {
f[i]=(f[i]+s[i]+MOD-(k>1?s[k-2]:0))%MOD;
s[i]=(s[i-1]+f[i])%MOD;
}
}
printf("%lld\n",f[n]);
return 0;
}
C. [AGC017F] Path
题目大意
给定 \(n\times n\) 杨辉三角，选出 \(m\) 条折线，每条折线在每一层都要从左到右升序排列。
还有 \(q\) 个限制形如第 \(i\) 个折线第 \(j\) 层必须向下 / 向右下，求方案数。
数据范围：\(n,m\le 20\)。
思路分析
考虑类似轮廓线 dp 的想法，\(f_{i,j,s}\) 表示处理到第 \(i\) 条折线的 \([1,j]\) 行，\(s\) 中状压记录第 \(i\) 条折线的 \([1,j]\) 行，以及第 \(i-1\) 条折线的 \([j+1,n]\) 行。
但此时我们还需要额外记录第 \(i-1\) 条折线在第 \(j\) 行的取值，无法接受。
考虑优化，我们发现两条折线取值不同当且仅当某一行第 \(i-1\) 条折线向下，第 \(i+1\) 条折线向右下。
因此这种情况发生后，在第 \(i-1\) 条折线下一次向右下方移动之前，两条折线不可能重叠。
因此我们可以把这条折线的下一次向右下方移动提前到当前位置上来，这样第 \(i-1\) 条折线在第 \(j\) 行的取值就和第 \(i\) 条折线一致，且不会影响折线之间的重叠情况。
然后进行 dp 即可，用位运算优化状态转移即可。
时间复杂度 \(\mathcal O(nm2^n)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
inline void add(int &x,const int &y) { x=(x+y>=MOD)?x+y-MOD:x+y; }
int lim[25][25],f[1<<20],g[1<<20];
signed main() {
int n,m,q;
scanf("%d%d%d",&n,&m,&q),--n;
for(int i=0;i<m;++i) for(int j=0;j<n;++j) lim[i][j]=-1;
for(int x,y,z;q--;) scanf("%d%d%d",&x,&y,&z),lim[x-1][y-1]=z;
f[0]=1;
for(int i=0;i<m;++i) for(int j=0;j<n;++j) {
memset(g,0,sizeof(g));
for(int s=0;s<(1<<n);++s) {
if(lim[i][j]!=1) if(!(s>>j&1)) add(g[s],f[s]);
if(lim[i][j]!=0) {
if(s>>j&1) add(g[s],f[s]);
else {
int o=s>>j; if(o) o&=o-1;
add(g[((o|1)<<j)|(s&((1<<j)-1))],f[s]);
}
}
}
memcpy(f,g,sizeof(f));
}
int ans=0;
for(int s=0;s<(1<<n);++s) add(ans,f[s]);
printf("%d\n",ans);
return 0;
}
*D. [AGC019E] Shuffle
题目大意
给定两个长度为 \(n\) 的 01 串 \(A,B\)，\(1\) 的个数相同，记为 \(a_1\sim a_k,b_1\sim b_k\)。
随机排列 \(a,b\)，然后依次交换 \(A_{a_i},A_{b_i}\)，求最终 \(A=B\) 的概率。
数据范围：\(n\le 10^4\)。
思路分析
我们先考虑将 \(a_i,b_i\) 一一匹配，然后确定一组交换 \(a_i,b_i\) 的顺序。
假设我们已经知道所有 \((a_i,b_i)\) 为匹配，那么考虑哪些交换顺序是合法的。
用有向边连接所有 \(a_i\to b_i\)，很显然每个点出度入度 \(\le 1\)，图会形成若干环和链。
环上的每个点 \(A_i=B_i=1\)，任何顺序交换不影响答案，每条链的链头 \(A_i=1\)，要移动到链尾 \(B_i=1\) 的位置上，只能从前往后按顺序交换每条边。
我们发现每个点是什么状态实际是由 \(A,B\) 确定的，我们可以确定有多少点只有出度 / 入度，多少点两者都有。
那么假设只有出度 / 入度的点有 \(p\) 个，两者都有的点有 \(q\) 个。
那么图上会包含 \(p\) 条链和若干个环，其中“中转点”（入度出度均为 \(1\) 的点）有 \(q\) 个。
设 \(f_{i,j}\) 表示当前图上有 \(i\) 条链，链上有 \(j\) 个“中转点”的方案数。
- 如果加入一条链，那么选择两个端点，转移 \(f_{i-1,j}\times (p-i+1)^2\to f_{i,j}\)。
- 如果在链中间加入一个中转点，插入在某条链的末尾，转移 \(f_{i,j-1}\times (q-j+1)\times i\to f_{i,j}\)。
计算答案的时候枚举链上“中转点”个数，剩余的环随便连：
\[\mathrm{Ans}=\sum_{i=0}^q\binom{p+q}{i}i!^2f_{p,q-i} \]时间复杂度 \(\mathcal O(n^2)\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=10005,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; }
char a[MAXN],b[MAXN];
int n,m,len;
ll ans,f[MAXN],fac[MAXN],ifac[MAXN];
signed main() {
for(int i=fac[0]=ifac[0]=1;i<MAXN;++i) ifac[i]=ksm(fac[i]=fac[i-1]*i%MOD);
scanf("%s%s",a+1,b+1),len=strlen(a+1);
for(int i=1;i<=len;++i) if(a[i]=='1') b[i]=='1'?++m:++n;
f[0]=1;
for(int i=1;i<=n;++i) {
for(int j=0;j<=m;++j) f[j]=f[j]*(n-i+1)*(n-i+1)%MOD;
for(int j=1;j<=m;++j) f[j]=(f[j]+f[j-1]*i*(m-j+1))%MOD;
}
for(int j=0;j<=m;++j) {
ans=(ans+f[m-j]*fac[n+m]%MOD*ifac[n+m-j]%MOD*fac[j])%MOD;
}
printf("%lld\n",ans);
return 0;
}
*E. [AGC018F] Subtree
题目大意
给定 \(n\) 个点的有根树 \(A,B\)，给每个点赋权值，使得两棵树上每个点的子树权值和都是 \(\pm 1\)。
数据范围：\(n\le 10^5\)。
思路分析
很显然每个点的权值的奇偶性和其儿子个数有关，如果两棵树上儿子个数奇偶性不同，一定无解。
可以猜测当每个点的权值取 \(\{-1,0,1\}\) 时一定有合法构造。
此时我们相当于每个点的子树中，和为 \(+1\) 和 \(-1\) 的子树数量差 \(\le 1\)。
这种题可以考虑用欧拉回路构造。
用一个虚根连接两棵树的根，方便处理每个节点。
此时度数为偶数的节点有奇数个儿子，权值一定取 \(0\)，否则要决定权值取 \(\pm1\)。
我们把这种度数为奇数的节点在两棵树上对应的点连起来，此时每个点度数为偶数，求出一条欧拉回路。
我们定义一个点的权值为 \(+1\) 当且仅当其连的额外边在欧拉回路中的方向是 \(A\to B\)。
此时 \(A\) 中的一棵子树，权值和为 \(+1\) 当且仅当子树根 \(u\) 到父亲的边在欧拉回路中方向是 \(fa\to u\)，容易验证该构造的正确性。
时间复杂度 \(\mathcal O(n)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
struct Edge { int v,id; };
vector <Edge> G[MAXN];
int n,ec=0,fx[MAXN],fy[MAXN],cur[MAXN],ans[MAXN];
bool vis[MAXN*2];
void link(int x,int y) {
++ec,G[x].push_back({y,ec}),G[y].push_back({x,ec});
}
void dfs(int u) {
for(int &i=cur[u];i<(int)G[u].size();++i) if(!vis[G[u][i].id]) {
Edge e=G[u][i];
vis[e.id]=true,dfs(e.v);
if(e.v==u+n) ans[u]=1;
else if(u==e.v+n) ans[e.v]=-1;
}
}
signed main() {
scanf("%d",&n);
for(int i=1;i<=n;++i) {
scanf("%d",&fx[i]);
link(~fx[i]?fx[i]:0,i);
}
for(int i=1;i<=n;++i) {
scanf("%d",&fy[i]);
link(~fy[i]?fy[i]+n:0,i+n);
}
for(int i=1;i<=n;++i) if(G[i].size()%2!=G[i+n].size()%2) return puts("IMPOSSIBLE"),0;
puts("POSSIBLE");
for(int i=1;i<=n;++i) if(G[i].size()%2) link(i,i+n);
dfs(0);
for(int i=1;i<=n;++i) printf("%d ",ans[i]);
puts("");
return 0;
}
*F. [AGC015F] Euclid
题目大意
定义 \(f(x,0)=0,f(x,y)=f(y,x\bmod y)+1\)，对于所有 \(x\in[1,X],y\in [1,Y]\) 的数对求 \(f(x,y)\) 的最大值，以及有多少 \(f(x,y)\) 取到最大值。
数据范围：\(X,Y\le 10^{18}\)。
思路分析
设 \(g(x,y)=\max_{i\le x,j\le y}f(i,j)\)，第一问要求 \(g(X,Y)\)，假设 \(X\le Y\)。
这是简单的，取到最大值的 \((x,y)\) 一定是一对斐波那契数，求最大的 \(\mathrm{Fib}_k\le x,\mathrm{Fib}_{k+1}\le Y\)，\(k\) 就是答案。
那么我们就是要找所有 \(f(i,j)=g(i,j)=k\) 的元素对。
我们发现如果 \(i>2j\)，那么 \(g(i,j)=g(i-j,j)\)，因此我们只要求出 \(j<i\le 2j\) 的 \(f(i,j)=g(i,j)=k\) 的“极大”元素对，然后就可以算出答案总数。
发现 \(k=x\) 时的极大元素对做一步转化一定能得到 \(k=x-1\) 的极大元素对。
然后考虑逆推生成，发现在 \(k=x-1\) 时的一个元素对 \((x,y)\) 对应 \(k=x\) 时的元素对 \((y+x,x)\)。
并且还有额外的一个元素对 \((\mathrm{Fib}_{k-1}+\mathrm{Fib}_{k+1},\mathrm{Fib}_{k+1})\)，可以证明其他的极大元素对不可能互相生成。
那么元素对个数是 \(\mathcal O(k)\) 级别的。
时间复杂度 \(\mathcal O(\log V)\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=105,MOD=1e9+7;
ll fib[MAXN];
vector <array<ll,2>> f[MAXN];
signed main() {
const int n=88;
fib[0]=fib[1]=1;
for(int i=2;i<=n;++i) fib[i]=fib[i-1]+fib[i-2];
f[1]={{1,2}};
for(int i=2;i<=n;++i) {
for(auto x:f[i-1]) f[i].push_back({x[1],x[0]+x[1]});
f[i].push_back({fib[i+1],fib[i-1]+fib[i+1]});
}
int T; scanf("%d",&T);
for(ll x,y;T--;) {
scanf("%lld%lld",&x,&y);
if(x>y) swap(x,y);
int i=1; ll c=0;
while(fib[i+1]<=x&&fib[i+2]<=y) ++i;
for(auto o:f[i]) {
if(o[0]<=x&&o[1]<=y) c=(c+(y-o[1])/o[0]+1)%MOD;
if(o[1]<=x&&o[0]<=y) c=(c+(x-o[1])/o[0]+1)%MOD;
}
if(i==1) c=(c+x)%MOD;
printf("%d %lld\n",i,c);
}
return 0;
}
*G. [AGC020F] Arc
题目大意
给定一个周长为 \(C\) 的环，有 \(n\) 条长度为 \(a_1\sim a_n\) 的弧，每条弧均匀随机一个实数位置放置，求所有弧覆盖整个环至少一次的概率。
数据范围：\(C\le 50,n\le 6\)。
思路分析
先从弧的位置是整点的情况入手：我们需要从一个合适的位置进行破环为链。
破环为链的一个缺陷是如果某个弧的起点 \(x_i\) 满足 \(x_i+a_i>C\)，那么会对这条链的一段前缀 \([1,x+a_i-C]\) 产生覆盖。
但我们可以从最长链 \(a_p\) 的起点开始破环为链，那么 \([1,a_p]\) 已经被覆盖，其他链覆盖的范围 \(x+a_i-C\) 一定不超过 \(a_p\)。
因此对于这种弧我们就不需要考虑越过 \(C\) 的贡献，只考虑对后缀的覆盖。
\(f_{i,j,s}\) 表示将 \(s\) 中的线段左端点放到 \([1,i]\) 中，覆盖范围 \([1,j]\) 的方案数，然后 dp 即可。
然后考虑取的是实数的情况。
事实上我们只关心 \(x_i,a_i+x_i\) 的相对大小关系，我们发现比较他们的大小关系只需要比较整数部分，以及小数部分的相对顺序。
因此我们可以直接枚举 \(\{x_i\}\)（小数部分）的相对顺序，由于 \(x_i\) 在实数范围内均匀随机，因此两个 \(x_i\) 小数部分相等的概率为 \(0\)，\(n!\) 枚举 \(\{x_i\}\) 的顺序，然后做上面的 dp 即可。
时间复杂度 \(\mathcal O(n!\times 2^nn^2C^2)\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dp[305][64],ans=0;
int n,m,a[10],p[10];
signed main() {
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i) scanf("%d",&a[i]),p[i]=i;
sort(a,a+n);
do {
memset(dp,0,sizeof(dp));
dp[a[n-1]*n][0]=1;
for(int i=1;i<=n*m;++i) if(i%n) {
int x=p[i%n-1];
for(int j=i;j<=n*m;++j) for(int s=0;s<(1<<(n-1));++s) if(!(s>>x&1)) {
dp[min(n*m,max(j,i+a[x]*n))][s|1<<x]+=dp[j][s];
}
}
ans+=dp[n*m][(1<<(n-1))-1];
} while(next_permutation(p,p+n-1));
long double z=ans;
for(int i=1;i<n;++i) z/=i;
for(int i=1;i<n;++i) z/=m;
printf("%.20Lf\n",z);
return 0;
}
Round #27 - 2024.10.31
A. [AGC024E] Insert
题目大意
从空序列开始，依次向序列中插入一个 \([1,k]\) 的元素，插入 \(n\) 次，要求字典序单调递增，求方案数。
数据范围：\(n,k\le 300\)。
思路分析
考虑对最终的序列 dp 删除元素的顺序，删除 \(a_i\) 要求 \(a_i\) 后面第一个 \(\ne a_i\) 的元素小于 \(a_{i}\)。
涉及元素大小关系的问题可以插入 dp，每次考虑插入最小值，值域从 \([2,k]\to [1,k]\)。
考虑第一个 \(1\) 什么时候删除，容易发现这个元素必须在 \(1\) 后面的元素全部删除后才能删除。
那么 \(1\) 前面的元素依然可以正常删除，因为前面的元素值域 \([2,k]\)，末尾元素是 \(1\) 还是空不影响是否可删的判定。
那么 \(f_{i,j}\) 表示值域 \([k-i+1,k]\)，序列长度为 \(j\) 的方案数，转移 \(f_{i,j}\gets f_{i-1,p}\times f_{i,j-p-1}\times\binom{j}{j-p}\)。
时间复杂度 \(\mathcal O(n^2k)\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=305;
ll f[MAXN][MAXN],C[MAXN][MAXN];
signed main() {
int n,m,MOD;
scanf("%d%d%d",&n,&m,&MOD);
for(int i=0;i<MAXN;++i) for(int j=C[i][0]=1;j<=i;++j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
f[0][0]=1;
for(int i=1;i<=m;++i) {
memcpy(f[i],f[i-1],sizeof(f[i]));
for(int j=1;j<=n;++j) for(int k=0;k<j;++k) {
f[i][j]=(f[i][j]+f[i-1][k]*f[i][j-k-1]%MOD*C[j][j-k])%MOD;
}
}
printf("%lld\n",f[m][n]);
return 0;
}
*B. [AGC023D] Vote
题目大意
给定数轴上 \(x_1\sim x_n\) 个点，第 \(i\) 个点有 \(a_i\) 个人在公交上，每个人要到对应的点上下车。
当前公交在 \(s\)，每个时刻所有人投票决定公交向左还是向右，选票多的方向（平票向左）。
每个人都向最小化到目标的时间，求最终运行时间。
数据范围：\(n\le 10^5\)。
思路分析
考虑哪个点最后访问，很显然是第 \(1\) 个或第 \(n\) 个判断哪个点最后访问，不难猜测最后访问 \(n\) 当且仅当 \(a_1\ge a_n\)。
对 \(n\) 归纳，如果 \(n=2\) 显然成立。
考虑 \(s\) 与 \(x_{n-1}\) 的关系，如果 \(x_{n-1}<s<x_{n}\) 那么 \(x_1\sim x_{n-1}\) 都想前往负方向，否则会变成 \(n\gets n-1\) 的子问题。
因此路径最后一步一定是 \(x_1\to x_n/x_n\to x_1\)，不妨假设 \(a_1\ge a_n\)，那么 \(x_n\) 中的人到达的时间等于 \(x_1\) 中人到达时间加定值 \(x_n-x_1\)。
所以 \(x_n\) 中人的目标转化成了最小化到达 \(x_1\) 时间，令 \(a_1\gets a_1+a_n\) 递归即可。
注意如果 \(a_1\ge a_n,a_1+a_n\ge a_{n-1}\)，那么 \(x_1\to x_{n}\) 的路径会顺带经过 \(x_{n-1}\)，因此统计答案的时候要记录当前最后一步的方向。
时间复杂度 \(\mathcal O(n)\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+5;
int n,s;
ll a[MAXN],x[MAXN];
ll f(int l,int r,int op) {
if(s<x[l]) return x[r]-s;
if(x[r]<s) return s-x[l];
if(a[l]<a[r]) return a[r]+=a[l],f(l+1,r,1)+(op!=1?x[r]-x[l]:0);
else return a[l]+=a[r],f(l,r-1,0)+(op!=0?x[r]-x[l]:0);
}
signed main() {
scanf("%d%d",&n,&s);
for(int i=1;i<=n;++i) scanf("%lld%lld",&x[i],&a[i]);
printf("%lld\n",f(1,n,-1));
return 0;
}
*C. [AGC024F] Sequence
题目大意
给定若干长度 \(\le n\) 的 01 串，求一个 01 串至少是其中 \(k\) 个串的子序列，且长度最长，同长度字典序最小。
数据范围：\(n\le 20\)。
思路分析
可以考虑计算出每个 01 串 \(s\) 是多少个串的子序列。
一个比较复杂的问题是如何让每个串恰好计算一次，可以考虑用子序列自动机进行判定。
对每个串建子序列自动机，\(f_{s,t}\) 表示当前取出的模式串是 \(s\)，在子序列自动机上匹配后，文本串的剩余部分是 \(t\)，这样的文本串有多少个。
转移就是 \(s\to s+c\)（\(c\in\{0,1\}\)），然后 \(t\) 删除从前往后第一个 \(c\) 以及其前面的部分，可以用位运算优化转移。
我们可以发现 \(|s|+|t|\le n\)，因此总状态数只有 \(\mathcal O(n2^n)\) 级别，转移可以做到线性。
时间复杂度 \(\mathcal O(n2^n)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
int n,K,f[21][1<<21],g[1<<21];
int hb(int x) { return 31-__builtin_clz(x); }
void add(int x,int i,int y,int w) { f[i][x<<i|y]+=w; }
signed main() {
cin>>n>>K;
for(int i=0;i<=n;++i) for(int s=0;s<(1<<i);++s) {
char op; cin>>op;
if(op=='1') ++f[i][1<<i|s];
}
for(int i=n;~i;--i) for(int s=0;s<(1<<(n+1));++s) if(f[i][s]) {
int x=s>>i,y=s&((1<<i)-1);
g[x]+=f[i][s];
if(y) {
int j=hb(y);
add(x<<1|1,j,y&((1<<j)-1),f[i][s]);
}
if(y!=(1<<i)-1) {
int j=hb(y^((1<<i)-1));
add(x<<1,j,y&((1<<j)-1),f[i][s]);
}
}
for(int i=n;i>=1;--i) for(int s=0;s<(1<<i);++s) if(g[1<<i|s]>=K) {
for(int o=i-1;~o;--o) cout<<(s>>o&1);
cout<<"\n";
return 0;
}
cout<<"\n";
return 0;
}
*D. [AGC021E] Box
题目大意
给定 \(n\) 个蓝色盒子，顺次加入 \(k\) 个红或蓝色的球，每个球选择一个盒子放入，如果该盒子中当前颜色的球严格多于另一种颜色的球，那么盒子会变成这种颜色。
求有多少种球的颜色序列使得存在至少一种放盒子的方案使得每个盒子最终为红色。
数据范围：\(n,k\le 5\times 10^5\)。
思路分析
枚举红球和蓝球个数 \(x,y\)。
一个盒子最终为红色，要么红球个数比蓝球多，要么两者相等且最后一次插入的是蓝球。
因此 \(x<y\) 和 \(x\ge y+n\) 是一定无解 / 有解的，可以忽略。
如果 \(x=y\)，那么最后一个球一定是蓝球，删去不影响结果，转成 \((x,y-1)\) 的子问题。
此时 \(y<x<y+n\)，如果一个盒子中红球比蓝球多 \(2\) 个以上，拿出一个给其他盒子一定不劣。
因此此时只会有 \(x-y\) 个红球比篮球多一个的盒子，以及 \(n-(x-y)\) 个红蓝球个数相等的盒子。
其次，我们发现一个红蓝球个数相等的盒子，如果红蓝球个数 \(>1\)，那么可以把一个红球和一个蓝球一起放到一个红球比蓝球多一个的盒子。
因此所有红蓝球个数相等的盒子中，只有一个红球一个蓝球。
那么我们把红球看成左括号，蓝球看成右括号，要满足的限制就是序列的最大括号匹配 \(\ge n-(x-y)\)。
把括号序列看成 \((0,0)\to (x+y,x-y)\) 的 \(\pm 1\) 折线，我们知道序列的最大括号匹配之和路径上最低点 \(h\) 有关，此时括号匹配等于 \(\dfrac{(x+y)-(0-h)-(x-y-h)}{2}\)。
展开得到 \(h\ge n-x\)，即路径不能低于 \(y=n-x\)，反射容斥得到方案数 \(\binom{x+y}{x}-\binom{x+y}{n-x+y-1}\)。
时间复杂度 \(\mathcal O(k)\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5e5+5,MOD=998244353;
ll fac[MAXN],ifac[MAXN],ans;
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 C(int x,int y) {
if(x<0||y<0||y>x) return 0;
return fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;
}
signed main() {
for(int i=fac[0]=ifac[0]=1;i<MAXN;++i) ifac[i]=ksm(fac[i]=fac[i-1]*i%MOD);
int n,K;
scanf("%d%d",&n,&K);
if(K<n) return puts("0"),0;
for(int R=(K+1)/2;R<=K;++R) {
int B=K-R; if(R==B) --B;
ans=(ans+C(R+B,R)+MOD-C(R+B,n-R+B-1))%MOD;
}
printf("%lld\n",ans);
return 0;
}
*E. [AGC022D] Shuttle
题目大意
给定 \(n\) 个商场位于 \(x_1\sim x_n\)，在商场 \(x_i\) 需要停留至少 \(t_i\) 时刻，一辆车在 \(0,L\) 之间以 \(1\) 的速度来回往返，经过商场的时候可以上下车，求遍历所有商场后回到起点的最小用时。
数据范围：\(n\le 3\times 10^5\)。
思路分析
首先整个过程以 \(2L\) 为周期，答案也是 \(2L\) 的倍数，那么可以把 \(t_i\) 先对 \(2L\) 取模，然后要计算最小周期数。
我们发现朴素的做法就是在每个 \(x_i\) 下车，由于 \(t_i<2L\)，因此等车下一次过 \(x_i\) 时停留结束上车即可。
考虑如何优化：这个过程中车在 \(0,L\) 分别折返一次才返回，实际经过了 \(x_i\) 两次。
我们发现有的时候只要车在 \(0\) 或 \(L\) 中的一处折返后停留时间就已经超过 \(t_i\) 了，可以经过一次时就提前上车。
因此记 \(l_i,r_i\) 表示当车在 \(0/L\) 折返后停留时间是否超过 \(t_i\)，即 \(2x_i\ge t_i\) 和 \(2(L-x_i)\ge t_i\)。
考虑如何减少折返轮次，首先一次折返经过每个点两次，因此一轮折返最多经过两个点。
那么我们肯定是在 \(L\) 折返时经过一个点，在 \(0\) 折返时经过一个点，即 \(x_i<x_j\) 且 \(l_i=r_j=1\) 的点之间可以匹配。
然后求出最大匹配即可。
进一步观察发现，一个 \((l,r)=(1,0)\) 的点一定位于 \(L/2\) 右边，一个 \((l,r)=(0,1)\) 的点一定位于 \(L/2\) 左边。
因此不存在形如 \((1,0)\) 和 \((0,1)\) 的点互相匹配，只有 \((1,0)\) 的点和 \(L/2\) 右边的 \((1,1)\) 匹配，\((0,1)\) 的点和 \(L/2\) 左边的 \((1,1)\) 匹配，剩余的 \((1,1)\) 内部匹配。
按顺序维护贪心即可。
注意特殊情况如：\(t_i=0\)，以及最后一个点不能匹配，只能在 \(r_n=1\) 时减少一次折返。
时间复杂度 \(\mathcal O(n)\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3e5+5;
int n,st[MAXN],tp;
ll a[MAXN],t[MAXN],L,ans;
bool l[MAXN],r[MAXN],vis[MAXN];
signed main() {
scanf("%d%lld",&n,&L),ans=n+1;
for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
for(int i=1;i<=n;++i) {
scanf("%lld",&t[i]),ans+=t[i]/(2*L),t[i]%=2*L;
l[i]=(2*a[i]>=t[i]),r[i]=(2*(L-a[i])>=t[i]);
}
if(r[n]) --ans;
for(int i=1;i<n;++i) if(!t[i]) --ans,vis[i]=true;
for(int i=1,hd=1,tl=0;i<n;++i) {
if(l[i]&&r[i]&&!vis[i]) st[++tl]=i;
if(!l[i]&&r[i]&&hd<=tl) --ans,vis[st[hd++]]=true;
}
tp=0;
for(int i=n-1,hd=1,tl=0;i;--i) {
if(l[i]&&r[i]&&!vis[i]) st[++tl]=i;
if(l[i]&&!r[i]&&hd<=tl) --ans,vis[st[hd++]]=true;
}
int c=0;
for(int i=1;i<n;++i) c+=l[i]&&r[i]&&!vis[i];
ans-=c>>1;
printf("%lld\n",2*L*ans);
return 0;
}
Round #28 - 2024.11.04
A. [AGC025D] Grid
题目大意
给定 \(n,x,y\)，在 \(2n\times 2n\) 的网格中选 \(n^2\) 个点使得任意两个点之间的距离不为 \(\sqrt x\) 或 \(\sqrt y\)。
数据范围：\(n\le 300\)。
思路分析
设 \(x=dx^2+dy^2\)，分讨 \(x\bmod 4\) 的奇偶性：
- \(x\bmod 4=2\)：说明 \(dx,dy\) 为奇数，因此距离为 \(\sqrt x\) 的点横坐标奇偶性不同。
- \(x\bmod 4=2\)：说明 \(dx,dy\) 恰有一个奇数，因此距离为 \(\sqrt x\) 的点黑白间隔染色后颜色不同。
- \(x\bmod 4=0\)：说明 \(dx,dy\) 均为偶数，将整个网格按横纵坐标 \(\bmod 2\) 分成四个完全相等的部分。
因此我们发现距离为 \(\sqrt x\) 的点对一定可以被黑白染色，即形成的图是二分图。
那么距离为 \(\sqrt x\) 或 \(\sqrt y\) 的点是两张二分图，我们要在其中找到一个大小 \(\ge \dfrac 14|V|\) 的独立集。
这是简单的，在两张二分图上黑白染色，如果两个点在两张二分图上颜色都相同就划入同一个等价类，可以把 \(V\) 恰分成 \(4\) 个等价类，根据抽屉原理，直接取最大的一个即可。
时间复杂度 \(\mathcal O(n^2)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=605;
int n,k1,k2;
void col(auto a,int k) {
int x=0;
while(k%4==0) k>>=2,++x;
if(k%4==1) {
for(int i=0;i<n;++i) for(int j=0;j<n;++j) a[i][j]=((i>>x)+(j>>x))&1;
} else if(k%4==2) {
for(int i=0;i<n;++i) for(int j=0;j<n;++j) a[i][j]=i>>x&1;
}
}
bool f[MAXN][MAXN],g[MAXN][MAXN];
signed main() {
scanf("%d%d%d",&n,&k1,&k2),n*=2;
col(f,k1),col(g,k2);
for(int p:{0,1}) for(int q:{0,1}) {
vector <array<int,2>> wys;
for(int i=0;i<n;++i) for(int j=0;j<n;++j) {
if(f[i][j]==p&&g[i][j]==q) wys.push_back({i,j});
}
if(wys.size()>=n*n/4) {
wys.resize(n*n/4);
for(auto z:wys) printf("%d %d\n",z[0],z[1]);
return 0;
}
}
return 0;
}
B. [AGC027D] Mod
题目大意
给定 \(n\)，构造 \(n\times n\) 矩阵，使得所有元素 \(\le 10^{15}\) 且两两不同。
且对于任意相邻元素 \(x,y\)，\(\max(x,y)\bmod \min(x,y)\) 都相等且 \(>0\)。
数据范围：\(n\le 500\)。
思路分析
一个朴素想法是对整个矩阵黑白间隔染色，然后在黑格上全填质数，白格填周围四个数的乘积 \(+1\)。
但这样要太多质数，一个更好的办法是给每行每列赋一个质数，黑格取所在行列质数乘积，白格填周围四个数的 \(\mathrm{lcm}+1\) ，但这样白格会变成周围六个质数乘积。
不难想到对于每条对角线赋一个质数，黑格取所在两条对角线质数乘积，白格周围就只剩下了四个质数。
时间复杂度 \(\mathcal O(n^2)\)。
代码呈现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=505,MAXV=10005;
bool isc[MAXV];
vector <int> pr;
ll a[MAXN][MAXN];
ll lcm(ll x,ll y) { return (__int128)x/__gcd(x,y)*y; }
signed main() {
for(int i=2;i<MAXV;++i) {
if(!isc[i]) pr.push_back(i);
for(int p:pr) {
if(i*p>=MAXV) break;
isc[i*p]=true;
if(i%p==0) break;
}
}
int n,op=0;
scanf("%d",&n);
if(n==2) return puts("4 7\n23 10"),0;
int L=0,R=2*n-1+(n&1);
auto val=[&](){ return (op^=1)?pr[L++]:pr[--R]; };
for(int i=0;i<=n+1;++i) for(int j=0;j<=n+1;++j) a[i][j]=1;
for(int i=1;i<=n;i+=2) for(int x=1,y=i,p=val();y>=1;++x,--y) a[x][y]*=p;
for(int i=2+(n&1);i<=n;i+=2) for(int x=i,y=n,p=val();x<=n;++x,--y) a[x][y]*=p;
for(int i=n-1+(n&1);i>=1;i-=2) for(int x=1,y=i,p=val();y<=n;++x,++y) a[x][y]*=p;
for(int i=3;i<=n;i+=2) for(int x=i,y=1,p=val();x<=n;++x,++y) a[x][y]*=p;
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if((i+j)&1) {
a[i][j]=lcm(lcm(a[i-1][j],a[i+1][j]),lcm(a[i][j-1],a[i][j+1]))+1;
}
for(int i=1;i<=n;++i,puts("")) for(int j=1;j<=n;++j) printf("%lld ",a[i][j]);
return 0;
}
C. [AGC026E] Pair
题目大意
给定 \(n\) 个
a,b构成的字符串，每次可以把从左往右的第 \(i\) 个a和b同时删除，求能得到的字典序最大的串。数据范围：\(n\le 3000\)。
思路分析
考虑从后往前 dp，设 \(f_i\) 表仅考虑第 \(i\sim n\) 个 a 和 b 得到的最大字典序串。
设 \(a_i,b_i\) 表示第 \(i\) 个 a 或 b 的位置。
很显然可以直接删除 \(a_i,b_i\) 得到 \(f_{i+1}\)。
否则如果保留了 \(a_i,b_i\)，如果 \(a_i<b_i\)，那么 \((a_i,b_i)\) 范围内的字符都是 \(<i\) 的 b 和 \(>i\) 的 a。
那么我们肯定不会保留这部分的 a，直接找到第一个 \(\min(a_j,b_j)>b_i\) 的位置并得到 \(\texttt{ba}+f_j\)。
否则 \((b_i,a_i)\) 范围内的是 \(>i\) 的 b 和 \(<i\) 的 a，很显然这些 b 一定是选择了更优，然后我们又会选若干 \(b_j<a_j\) 的字符对，把这部分的 b 继续选上，不断递归直到 \((b_j,a_j)\) 中没有 a，从 \(f_{j+1}\) 转移。
时间复杂度 \(\mathcal O(n^2)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=6005;
int n,id[MAXN],a[MAXN],b[MAXN];
char s[MAXN];
string f[MAXN];
signed main() {
scanf("%d%s",&n,s+1);
for(int i=1,x=0,y=0;i<=n*2;++i) {
if(s[i]=='a') a[id[i]=++x]=i;
else b[id[i]=++y]=i;
}
for(int i=n;i>=1;--i) {
if(a[i]<b[i]) {
int j=i+1;
for(;j<=n&&min(a[j],b[j])<=b[i];++j);
f[i]=max("ab"+f[j],f[i+1]);
} else {
int j=b[i];
for(;j<=n*2&&b[id[j]]<a[id[j]]&&(id[j]<=i||b[id[j]]<a[id[j]-1]);++j) {
if(id[j]>=i) f[i]+=s[j];
}
f[i]=max(f[i]+f[id[j]],f[i+1]);
}
}
printf("%s\n",f[1].c_str());
return 0;
}
D. [AGC027F] Link
题目大意
给定两棵 \(n\) 个点的树 \(A,B\)，对于每个点 \(u\) 可以在 \(A\) 上改变一个叶子的父亲（每个 \(u\) 操作至多一次）。
求让 \(A=B\) 的最小操作次数。
数据范围：\(n\le 50\)。
思路分析
假设操作次数 \(\ge 1\)，那么可以枚举第一步操作了哪个点 \(u\) 以及其新的父亲。
此后 \(u\) 不能被操作，因此可以在两棵树上都把 \(u\) 定为根，那么操作就是选一个叶子，把他的父亲改成在 \(B\) 中的父亲。
设两棵树上 \(u\) 的父亲是 \(fa_u,fb_u\)，那么操作数就是 \(fa_u\ne fb_u\) 的 \(u\) 个数。
并且对于一个要操作的 \(u\)，其 \(A\) 中的儿子和 \(B\) 中的父亲一定要在 \(u\) 操作前操作。
那么所有 \(u\) 的操作顺序就变成了一张拓扑图，在上面拓扑排序判断是否有解即可。
时间复杂度 \(\mathcal O(n^3)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=55;
int n,deg[MAXN],ind[MAXN],fa[MAXN],fb[MAXN];
bool w[MAXN];
vector <int> G[MAXN];
vector <array<int,2>> A,B;
void dfs(int u,int *f) { for(int v:G[u]) if(v^f[u]) f[v]=u,dfs(v,f); }
int sol(int rt) {
for(int i=1;i<=n;++i) G[i].clear();
for(auto e:A) G[e[0]].push_back(e[1]),G[e[1]].push_back(e[0]);
fa[rt]=0,dfs(rt,fa);
for(int i=1;i<=n;++i) G[i].clear();
for(auto e:B) G[e[0]].push_back(e[1]),G[e[1]].push_back(e[0]);
fb[rt]=0,dfs(rt,fb);
for(int i=1;i<=n;++i) G[i].clear(),ind[i]=0;
int s=0; w[rt]=0;
for(int i=1;i<=n;++i) if(i^rt) w[i]=fa[i]^fb[i],s+=w[i];
for(int i=1;i<=n;++i) {
if(!w[i]&&w[fa[i]]) return n+1;
if(w[i]&&w[fa[i]]) G[i].push_back(fa[i]),++ind[fa[i]];
if(w[i]&&w[fb[i]]) G[fb[i]].push_back(i),++ind[i];
}
queue <int> q;
for(int i=1;i<=n;++i) if(!ind[i]) q.push(i);
while(q.size()) {
int u=q.front(); q.pop();
for(int v:G[u]) if(!--ind[v]) q.push(v);
}
for(int i=1;i<=n;++i) if(ind[i]) return n+1;
return s;
}
void solve() {
scanf("%d",&n),A.resize(n-1),B.resize(n-1);
for(int i=1;i<=n;++i) deg[i]=0;
for(auto &e:A) {
scanf("%d%d",&e[0],&e[1]),++deg[e[0]],++deg[e[1]];
if(e[0]>e[1]) swap(e[0],e[1]);
}
for(auto &e:B) {
scanf("%d%d",&e[0],&e[1]);
if(e[0]>e[1]) swap(e[0],e[1]);
}
sort(A.begin(),A.end());
sort(B.begin(),B.end());
if(A==B) return puts("0"),void();
int ans=n+1;
for(auto &e:A) {
int u=e[0],v=e[1];
if(deg[u]==1) {
for(int i=1;i<=n;++i) if(i!=u&&i!=v) e={u,i},ans=min(ans,sol(u)+1);
}
if(deg[v]==1) {
for(int i=1;i<=n;++i) if(i!=u&&i!=v) e={i,v},ans=min(ans,sol(v)+1);
}
e={u,v};
}
printf("%d\n",ans>n?-1:ans);
}
signed main() {
int T; scanf("%d",&T);
while(T--) solve();
return 0;
}
*E. [AGC025E] Direct
题目大意
给定 \(n\) 个点的树和 \(m\) 条路径，给每条路径定向，一条边 \((u,v)\) 如果被沿 \(u\to v\) 或 \(v\to u\) 方向经过，分别产生 \(1\) 的收益，最大化收益。
数据范围：\(n,m\le 2000\)。
思路分析
假设每条边被覆盖次数为 \(d_e\)，那么其对答案的贡献至多为 \(\min(2,d_e)\)。
考虑构造，我们实际上可以将这个条件强化为沿 \(u\to v\) 经过和 \(v\to u\) 经过的路径数相差 \(\le 1\)。
可以发现在树上随意移动，如果最终回到原点，那么每条边沿两种方向经过的次数一定相同。
那么一个朴素的想法是对每条路径连接起点和终点，求出欧拉回路后按欧拉回路定向，此时每条边两种方向经过次数相同。
问题是这张图不一定有欧拉回路，可以调整，对于每个度数为奇数的点 \(u\)，把 \(u\) 和其父亲连一条边。
由于初始所有点度数总和为偶数，因此这样总能调整出解，并且每条树边至多被添加一次，删去这些树边后，两种方向的经过次数差就 \(\le 1\)。
时间复杂度 \(\mathcal O(n\log n+m)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2005;
int n,m;
vector <int> G[MAXN];
int dfn[MAXN],st[MAXN][20],dcnt;
int cmp(int x,int y) { return dfn[x]<dfn[y]?x:y; }
int bit(int x) { return 1<<x; }
int LCA(int x,int y) {
if(x==y) return x;
int l=min(dfn[x],dfn[y])+1,r=max(dfn[x],dfn[y]),k=__lg(r-l+1);
return cmp(st[l][k],st[r-bit(k)+1][k]);
}
void dfs0(int u,int fz) {
dfn[u]=++dcnt,st[dcnt][0]=fz;
for(int v:G[u]) if(v^fz) dfs0(v,u);
}
int d[MAXN],s[MAXN],t[MAXN],ans=0;
struct Edge { int v,id; };
vector <Edge> E[MAXN];
void dfs1(int u,int fz) {
for(int v:G[u]) if(v^fz) dfs1(v,u),d[u]+=d[v];
ans+=min(d[u],2);
if(E[u].size()&1) {
E[u].push_back({fz,u+m});
E[fz].push_back({u,u+m});
}
}
bool vis[MAXN*2];
int cur[MAXN];
void eul(int u) {
for(int &i=cur[u];i<(int)E[u].size();++i) if(!vis[E[u][i].id]) {
auto e=E[u][i];
vis[e.id]=true,eul(e.v);
if(e.id<=m&&u!=s[e.id]) swap(s[e.id],t[e.id]);
}
}
signed main() {
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<n;++i) {
scanf("%d%d",&u,&v);
G[u].push_back(v),G[v].push_back(u);
}
dfs0(1,0);
for(int k=1;k<=20;++k) for(int i=1;i+bit(k)-1<=n;++i) {
st[i][k]=cmp(st[i][k-1],st[i+bit(k-1)][k-1]);
}
for(int i=1;i<=m;++i) {
scanf("%d%d",&s[i],&t[i]);
++d[s[i]],++d[t[i]],d[LCA(s[i],t[i])]-=2;
E[s[i]].push_back({t[i],i});
E[t[i]].push_back({s[i],i});
}
dfs1(1,0);
for(int i=1;i<=n;++i) eul(i);
printf("%d\n",ans);
for(int i=1;i<=m;++i) printf("%d %d\n",s[i],t[i]);
return 0;
}
*F. [AGC025F] And
题目大意
给定两个 \(n,m\) 位二进制数 \(x,y\)，每次操作同时给 \(x,y\) 加上 \(x\operatorname{AND}y\)，求 \(k\) 次操作后的结果。
数据范围：\(n,m,k\le 10^6\)。
思路分析
朴素的做法就是模拟 \(k\) 轮，每轮从低往高处理 \(x_i=y_i=1\) 的进位。
但这样做不好优化，观察到单次操作中，后面的 \(x_i=y_i=1\) 不会撞到前面的 \(x_i=y_i=1\)。
因此对于 \((x_i,y_i)=(1,1)\) 的 \(1\)，我们可以直接在最大的 \(i\) 处连续处理 \(k\) 次进位。
即找到 \(x_i=y_i=1\) 的最大位，不断考虑 \(j=i,i+1,\dots\)，如果 \(x_j=y_j=1\) 那么给 \(x_j,y_j\) 加一并处理进位，然后令 \(k\gets k-1\)。
对于每个 \(i\) 重设 \(k\) 跑一遍，复杂度 \(\mathcal O(n^2)\)，容易发现大部分时候会有进位，即 \(\sum x_i+\sum y_i\) 减小。
没有进位当且仅当 \(x_i=y_i=1,x_{i+1}=y_{i+1}=0\)，那么用栈维护所有 \(x_i\ne 0\) 或 \(y_i\ne 0\) 的位置即可。
时间复杂度 \(\mathcal O(n+m+k)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e6+5;
int a[MAXN],b[MAXN],stk[MAXN],tp;
signed main() {
int n,m,K;
scanf("%d%d%d",&n,&m,&K);
for(int i=n;i;--i) scanf("%1d",&a[i]);
for(int i=m;i;--i) scanf("%1d",&b[i]);
stk[0]=MAXN-1;
for(int i=max(n,m);i;--i) {
vector <int> nw;
for(int j=i,c=K;;) {
nw.push_back(j);
while(stk[tp]<=j) --tp;
if(a[j]>1||b[j]>1) {
a[j+1]+=a[j]>>1,a[j]&=1;
b[j+1]+=b[j]>>1,b[j]&=1;
++j;
} else if(a[j]&&b[j]&&c) {
int p=min(stk[tp],c+j);
a[j]=b[j]=0,++a[p],++b[p],c-=p-j,j=p;
} else break;
}
reverse(nw.begin(),nw.end());
for(int o:nw) if(a[o]||b[o]) stk[++tp]=o;
}
for(n=MAXN-1;!a[n];--n);
for(int i=n;i;--i) printf("%d",a[i]); puts("");
for(m=MAXN-1;!b[m];--m);
for(int i=m;i;--i) printf("%d",b[i]); puts("");
return 0;
}