atcoder 杂题 #02
arc065_b
对两种边分别建图求并查集，其实就是求有多少个点满足两个图都在同一个并查集。
可以把一个点的并查集标号扔进 map<pair<int,int>,int> 里，就能统计个数了。
时间复杂度 \(O(n\log n)\)。
这道题容易往错误的方向想或者想复杂。
AC 代码：
const int N=2e5+5;
int n,m,p;
int fa[N];
int getfa(int x){
if(fa[x]==x)return x;
return fa[x]=getfa(fa[x]);
}
int fa2[N];
int getfa2(int x){
if(fa2[x]==x)return x;
return fa2[x]=getfa2(fa2[x]);
}
map<pair<int,int>,int> mp;
signed main(){
read(n,m,p);
fo(i,1,n)fa[i]=i,fa2[i]=i;
fo(i,1,m){
int u,v;
read(u,v);
u=getfa(u),v=getfa(v);
if(u!=v)fa[u]=v;
}
fo(i,1,p){
int u,v;
read(u,v);
u=getfa2(u),v=getfa2(v);
if(u!=v)fa2[u]=v;
}
fo(i,1,n)mp[{getfa(i),getfa2(i)}]++;
fo(i,1,n){
write(mp[{getfa(i),getfa2(i)}],' ');
}
return 0;
}
arc137_b
我没有想到这样神奇的水题。
考虑一个要翻转的区间 \([l,r]\)，把一个端点移动一个位置，那么贡献的变化量为 1。
那么求出贡献的最大值和最小值，最大值的区间一定能通过不断移动一单位的端点变成最小值的区间，那么最大值到最小值都能取遍。
于是用前缀和求贡献变化量的最大值 \(Max\) 和最小值 \(Min\)。答案就是 \(Max-Min+1\)。
而翻转一段区间的变化量就是 \(len-2*cnt\)，即 \((r-2*cnt_r)-(l-1-2*cnt_{l-1})\)。
时间复杂度 \(O(n)\)。
AC 代码：
const int N=3e5+5;
int n;
int a[N];
int s[N];
int mx=0,mn=0;
int Max=0,Min=0;
signed main(){
read(n);
fo(i,1,n){
read(a[i]);
s[i]=s[i-1]-2*a[i];
}
fo(i,1,n){
s[i]+=i;
mx=max(mx,s[i]-Min);
mn=min(mn,s[i]-Max);
Max=max(Max,s[i]);
Min=min(Min,s[i]);
}
write(mx-mn+1);
return 0;
}
abc287_f
一眼树上背包，并且看到 \(n\le 5000\) 是可以通过的。
我们要注意在限制枚举范围的情况下，树上背包的复杂度是 \(O(n^2)\) 的。
设 \(f_{i,j}\) 表示选择点 \(i\) 且子树内有 \(j\) 个连通块的方案数，\(g_{i,j}\) 表示不选择点 \(i\) 的方案数。
\(f\to g,g\to g,g\to f\) 都是直接把连通块个数相加，\(f\to f\) 则把连通块个数相加后减 1。
注意要先转移再把 \(sz\) 加上复杂度才是正确的。
AC 代码：
const int N=5005;
const int mod=998244353;
int n;
vector<int> G[N];
int f[N][N],g[N][N];
int sz[N];
void dfs(int x,int y){
g[x][0]=1;
f[x][1]=1;
sz[x]=1;
for(int v:G[x]){
if(v==y)continue;
dfs(v,x);
fd(i,sz[x],0){
fd(j,sz[v],1){
g[x][i+j]=(g[x][i+j]+(ll)g[x][i]*g[v][j])%mod;
g[x][i+j]=(g[x][i+j]+(ll)g[x][i]*f[v][j])%mod;
f[x][i+j]=(f[x][i+j]+(ll)f[x][i]*g[v][j])%mod;
f[x][i+j-1]=(f[x][i+j-1]+(ll)f[x][i]*f[v][j])%mod;
}
}
sz[x]+=sz[v];
}
}
signed main(){
read(n);
fo(i,1,n-1){
int u,v;
read(u,v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,0);
fo(i,1,n){
write((f[1][i]+g[1][i])%mod,'\n');
}
return 0;
}
abc308_g
考虑对每个数建出 01-Trie。对于一个数 \(x\)，我们找一个数 \(y\) 要使异或和最小，那么 \(\text{LCA}(x,y)\) 的深度要尽可能大，即高位连续相等的位要尽可能多。而如果 \(x,y\) 在 01-Trie 上低位还有分支，那么 \(x\oplus y\) 肯定不是最优的。
于是发现，答案就是 01-Trie 上相邻两个叶子的异或和的最小值，又发现 01-Trie 上相邻两个叶子在值域上也相邻。
于是用 set 维护当前黑板上的数，同时也能方便得到相邻的数。再用一个 set 维护出相邻两个数的异或和。
可以使用 prev 和 next 方便地得到前驱和后继的迭代器。
时间复杂度 \(O(Q\log Q)\)。
int Q;
const int N=3e5+5;
int tot;
int a[N];
set<pair<int,int> > s;
set<pair<int,pair<int,int>> > t;
void del(int x,int y){
if(x>y)swap(x,y);
t.erase({a[x]^a[y],{x,y}});
}
void add(int x,int y){
if(x>y)swap(x,y);
t.insert({a[x]^a[y],{x,y}});
}
signed main(){
cin>>Q;
while(Q--){
int opt;
cin>>opt;
if(opt==1){
++tot;
cin>>a[tot];
auto i=s.insert({a[tot],tot}).first;
if(i!=s.begin())add(prev(i)->second,tot);
if(next(i)!=s.end())add(next(i)->second,tot);
if(i!=s.begin()&&next(i)!=s.end())del(prev(i)->second,next(i)->second);
}
else if(opt==2){
int x;
cin>>x;
auto i=s.lower_bound({x,0});
if(i!=s.begin())del(prev(i)->second,i->second);
if(next(i)!=s.end())del(next(i)->second,i->second);
if(i!=s.begin()&&next(i)!=s.end())add(prev(i)->second,next(i)->second);
s.erase(i);
}
else{
cout<<(t.begin()->first)<<'\n';
}
}
return 0;
}