https://oj.gxyzh.com/d/hzoj/contest/698da89b5bbfea398a9e6b7f
（其实是 \(NOIP\) 模拟赛，四道题全打的部分分）
星际联邦
题解
考虑 \(Boruvka\) 算法：每次选取每个联通块向外最小的边，加入 \(MST\)。
选取最小边时，可以拆分成 \(a_j\) 与 \(max_{i=1}^{j-1}(a_i)\)，维护不在 \(a_j\) 联通块的 前缀最大值。
向后选取最小边同理。
时间复杂度：\(O(nlogn)\)。
对于 \(Kruskal\) 算法：
显然，对于每个点选取一条向前的边，最终一定能构成一棵树。
考虑如下剪枝：
对于点 \(j\)，选取向前最短的边 \(e(i,j)\)，向后最短的边 \(e(j,k)\)。
但这样依旧有可能不是最优，为何？因为 \(e(i,k)\ge e(i,j)\)，再选取 \(e(i,k)\),这样就能保证最优。
代码
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
constexpr int N=1e6+5;
int n,a[N],cnt,top,ans;
struct DisJoint_Set{int f[N],id[N];void clear(){ for(int i=1;i<=n;i++)f[i]=i; }int find(int x){ return (f[x]==x)?x:f[x]=find(f[x]); }void merge(int x,int y){ f[find(y)]=find(x); }bool check(int x,int y){ return find(x)!=find(y); }
}s;
struct E{int u,v,len;bool operator <(const E &x)const{return len<x.len;}
}e[N];
int maxn[N],minn[N];
signed main(){ios::sync_with_stdio(0),cin.tie(0);cin>>n,s.clear();for(int i=1;i<=n;i++)cin>>a[i];for(int i=1,m=-1e9,k=0;i<=n;i++){maxn[i]=k;if(a[i]>m)m=a[i],k=i;}for(int i=n,m=1e9,k=0;i>=0;i--){minn[i]=k;if(a[i]<m)m=a[i],k=i;}for(int i=1;i<=n;i++)e[++top]=E{maxn[i],i,a[i]-a[maxn[i]]},e[++top]=E{i,minn[i],a[minn[i]]-a[i]},e[++top]=E{maxn[i],minn[i],a[minn[i]]-a[maxn[i]]};sort(e+1,e+top+1);for(int i=1;i<=top;i++)if(s.check(e[i].u,e[i].v)){if(!e[i].u||!e[i].v)continue;s.merge(e[i].u,e[i].v);ans+=e[i].len,cnt++;if(cnt==n-1)break;}cout<<ans<<'\n';return 0;
}
和平精英
题解
对于这道题，我们必须发现一些性质。
假设 \(val\) 为使得 与党 与 或党 相同的数。
那么，由于 \(a\wedge b\le a\) 且 \(a\vee b\ge a\)
所以 \(<val\) 的数应当在 或党，\(>val\) 的数应当在 与党。
每次询问时暴力对区间排序枚举，时间复杂度 \((Qnlogn)\)。
考虑 \(val\) 的 \(popcount\)，
比其小的应当在 或党，比其大的应当在 与党。
与其相同的应该都等于 \(val\)。
每次询问时枚举 \(popcount\)，时间复杂度 \(O(QnlogV)\)。
考虑上面的算法，不难发现有许多重复的地方：将区间的 \(<popcount\) 的 \(>popcount\) 的数分开。
故考虑离线算法，将 \(popcount\) 相同的 \(check\) 一起处理。
设当前 \(check\) 的 \(popcount\) 为 \(p\)，对于 \(popcount<p\) 的数放入 或党，\(popcount>p\) 的数放入 与党，\(popcount=p\) 的数单独处理，\(check\) 时区间查询，不难发现三棵线段树可以维护。
（将线段树改为主席树即为在线做法）。
时间复杂度 \(O(QlognlognV)\)
当然还有更简单的方法：考虑上上面的算法，由于主要的时间花费用在了每次都要遍历一遍区间，将这一维去掉可以获得优秀的复杂度，解决方法是：开 \(logV\) 个 \(ST\) 表，时间复杂度 \(O(nlogV)\)。
还有猫树分治做法，我还不会。
代码
#include<iostream>
#include<vector>
#define lch (x<<1)
#define rch (x<<1|1)
using namespace std;
constexpr int N=1e5+5;
int n,m,a[N],cnt[N]; bool ans[N];
vector<int> v[35];
int popcount(int x){int cc=0;for(int i=30;i>=0;i--)cc+=((x>>i)&1);return cc;
}
struct Q{ int L,R; }q[N];
struct State1{int sum,num;State1 operator +(const State1 &b)const{return State1{sum+b.sum,num|b.num};}
};
struct Segment_Tree1{//区间或 State1 c[N<<2];void add(int x,int id,int val,int L,int R){if(L==R){ if(val<0)c[x]=State1{0,0};else c[x]=State1{1,val}; return; }int mid=(L+R)>>1;if(id<=mid)add(lch,id,val,L,mid);else add(rch,id,val,mid+1,R);c[x]=c[lch]+c[rch];}State1 query(int x,int l,int r,int L,int R){if(L==l&&R==r)return c[x]; int mid=(L+R)>>1;if(r<=mid)return query(lch,l,r,L,mid);else if(mid+1<=l)return query(rch,l,r,mid+1,R);else return query(lch,l,mid,L,mid)+query(rch,mid+1,r,mid+1,R);}
}tr1;
struct State2{int sum,num;State2 operator +(const State2 &b)const{return State2{sum+b.sum,num&b.num};}
};
struct Segment_Tree2{//区间与 State2 c[N<<2];void add(int x,int id,int val,int L,int R){if(L==R){ if(val<0)c[x]=State2{0,(1<<30)-1};else c[x]=State2{1,val}; return; }int mid=(L+R)>>1;if(id<=mid)add(lch,id,val,L,mid);else add(rch,id,val,mid+1,R);c[x]=c[lch]+c[rch];}State2 query(int x,int l,int r,int L,int R){if(L==l&&R==r)return c[x]; int mid=(L+R)>>1;if(r<=mid)return query(lch,l,r,L,mid);else if(mid+1<=l)return query(rch,l,r,mid+1,R);else return query(lch,l,mid,L,mid)+query(rch,mid+1,r,mid+1,R);}
}tr2;
struct State3{ int sum,num; State3 operator +(const State3 &b)const{State3 a=*this;if(a.num==-1)return b;if(b.num==-1)return a;if(a.num!=b.num)return State3{-1,0};else return State3{a.sum+b.sum,a.num};}
};
struct Segment_Tree3{//区间加 State3 c[N<<2]; void add(int x,int id,int val,int L,int R){if(L==R){ if(val<0)c[x]=State3{0,-1};else c[x]=State3{1,a[L]};return;}int mid=(L+R)>>1;if(id<=mid)add(lch,id,val,L,mid);else add(rch,id,val,mid+1,R);c[x]=c[lch]+c[rch];}State3 query(int x,int l,int r,int L,int R){if(L==l&&R==r)return c[x]; int mid=(L+R)>>1;if(r<=mid)return query(lch,l,r,L,mid);else if(mid+1<=l)return query(rch,l,r,mid+1,R);else return query(lch,l,mid,L,mid)+query(rch,mid+1,r,mid+1,R);}
}tr3;
signed main(){ios::sync_with_stdio(0),cin.tie(0);cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i],cnt[i]=popcount(a[i]);for(int i=1;i<=m;i++)cin>>q[i].L>>q[i].R;for(int i=1;i<=n;i++)tr2.add(1,i,a[i],1,n),tr3.add(1,i,-1,1,n);for(int i=1;i<=n;i++)v[cnt[i]].push_back(i);for(int i=0;i<=30;i++){//枚举 popcount for(int u:v[i])tr3.add(1,u,1,1,n),tr2.add(1,u,-1,1,n);for(int j=1;j<=m;j++){if(q[j].L==q[j].R)continue;State1 x1=tr1.query(1,q[j].L,q[j].R,1,n);State2 x2=tr2.query(1,q[j].L,q[j].R,1,n);State3 s=tr3.query(1,q[j].L,q[j].R,1,n);if(s.sum<0)continue;else if(!s.sum){if(x1.sum&&x2.sum&&x1.num==x2.num)ans[j]=1;}else if(s.sum==1){if(x2.sum&&(x1.num|s.num)==x2.num)ans[j]=1;if(x1.sum&&x1.num==(x2.num&s.num))ans[j]=1;}else if(s.sum>1){if(x2.sum&&(x1.num|s.num)==x2.num)ans[j]=1;if(x1.sum&&x1.num==(x2.num&s.num))ans[j]=1;if((x1.num|s.num)==(x2.num&s.num))ans[j]=1;}}for(int u:v[i])tr1.add(1,u,a[u],1,n),tr3.add(1,u,-1,1,n);}for(int i=1;i<=m;i++)cout<<(ans[i]?"YES\n":"NO\n");return 0;
}
摆烂合唱
题解
这应该是赛时最好想的一道题，但是还是没有想出来。
看到这样的表达式，先建一棵树，使用栈可以做到 \(O(n)\) 建树，叶子结点即为变量。
这样考虑：假设对于一种情况，叶子结点 \(i\) 取 \(0/1\) 时会导致 \(rot\) 取 \(0/1\) 不同，那么一定会有 \(i\to rot\) 的这条链上所有节点取 \(0/1\) 均不同。
设 \(dp_{u,0/1}\) 表示 左/右 儿子取 \(0/1\) 时导致 \(u\) 不同的概率（\(dp\) 中 \(0/1\) 表示 左/右 儿子）。
那么答案就是 \(rot\to i\) 这条链上的 \(dp\) 值累乘。
现在考虑如何求 \(dp_{u,0/1}\)。由于每次只有一个节点是固定的 \(0/1\)，其他节点都是随机情况，故考虑随机情况下点 \(u\) 为 \(1\) 的概率 \(f_u\) ，简单分讨轻松求出。
通过 \(f_u\) 可以求出 \(dp_{u,0/1}\)。
通过一次建树，两次 \(dfs\) 实现，时间复杂度 \(O(n)\)。
代码
#include<iostream>
#include<string.h>
#define int long long
using namespace std;
constexpr int N=2e5+5,p=998244353,inv=499122177;
int n,m; char s[N<<2];
int lch[N],rch[N],opt[N];
int cnt,sta[N],top;
int f[N],dp[N][2],ans[N];
void build_tree(){for(int i=1;i<=m;i++){//利用栈 O(n) 建树(模拟递归) if(s[i]=='('){sta[++top]=++cnt;int f=sta[top-1];if(!lch[f])lch[f]=cnt;//左儿子 else { //右儿子 rch[f]=cnt;if(s[i-1]=='&')opt[f]=-1;//运算 if(s[i-1]=='|')opt[f]=-2;if(s[i-1]=='^')opt[f]=-3;}}if(s[i]==')')top--;//退出 if(s[i]=='x'){int f=sta[top]; cnt++;if(!lch[f])lch[f]=cnt;//左儿子 else { //右儿子 rch[f]=cnt;if(s[i-1]=='&')opt[f]=-1;//运算 if(s[i-1]=='|')opt[f]=-2;if(s[i-1]=='^')opt[f]=-3;}opt[cnt]=++n;//节点编号 }}
}void dfs1(int x){if(!lch[x]){ f[x]=inv; return; }dfs1(lch[x]),dfs1(rch[x]);if(opt[x]==-1)f[x]=f[lch[x]]*f[rch[x]]%p;if(opt[x]==-2)f[x]=(1-(1-f[lch[x]])*(1-f[rch[x]]))%p;if(opt[x]==-3)f[x]=(f[lch[x]]*(1-f[rch[x]])+f[rch[x]]*(1-f[lch[x]]))%p;if(opt[x]==-1)dp[x][0]=f[rch[x]],dp[x][1]=f[lch[x]];if(opt[x]==-2)dp[x][0]=(1-f[rch[x]])%p,dp[x][1]=(1-f[lch[x]])%p;if(opt[x]==-3)dp[x][0]=1,dp[x][1]=1;
}void dfs2(int x,int mul){if(!lch[x]){ ans[opt[x]]=mul; return; }dfs2(lch[x],mul*dp[x][0]%p);dfs2(rch[x],mul*dp[x][1]%p);
}signed main(){ios::sync_with_stdio(0),cin.tie(0);cin>>n>>(s+1),m=strlen(s+1),n=0;build_tree(),dfs1(1),dfs2(1,1); for(int i=1;i<=n;i++)cout<<(ans[i]+p)%p<<'\n';return 0;
}
对称旅行者
题解
对于这道题，由于直接求解总和不好做，又知道总情况数为 \(2^{nK}\)，故考虑转化为期望求解。
对于 \(i\) 要旅行，那么 \(f_i\gets \frac{1}{2}(2f_{i-1}-f_i+2f_{i+1}-f_i)=f_{i-1}+f_{i+1}-f_i\)，
考虑几何意义，将 \(f_i\) 关于 \(f_{i-1}\) 与 \(f_{i+1}\) 的中点对称。
联想区间长度，设 \(g_i=f_{i+1}-f_i\)，那么 \(i\) 旅行一次就是交换 \(g_{i-1}\) 与 \(g_i\)。
这样就构成了一个置换，通过倍增或者快速幂可以做到 \(O(nlogK)\)。
当然求出每个数的循环节也是可行的，考虑图论建模，每个点入度和出度都为 \(1\)，那么就会构成一个个环，使用简化 \(Tarjan\) 即可，时间复杂度 \(O(n)\)。
注意：\(m\times K\) 会溢出 long long，解决方法是开 __int128，或者是用扩展欧拉定理化简。
#include<iostream>
#define int long long
using namespace std;
constexpr int N=1e5+5,p=1e9+7;
int qpow(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a%p;a=a*a%p,b>>=1;}return ans;
}
int n,m,mul,ans,K,f[N],g[N],ST[65][N],g2[N];
signed main(){ios::sync_with_stdio(0),cin.tie(0);cin>>n;for(int i=1;i<=n;i++)cin>>f[i];cin>>m>>K,mul=qpow(2,K%(p-1)*m);for(int i=1;i<n;i++)g[i]=f[i+1]-f[i];for(int i=1;i<n;i++)ST[0][i]=i;for(int i=1,x;i<=m;i++)cin>>x,swap(ST[0][x-1],ST[0][x]);for(int i=1;i<=60;i++)for(int j=1;j<n;j++)ST[i][j]=ST[i-1][ST[i-1][j]];for(int i=1;i<n;i++){int K2=K; int x=i;for(int j=60;j>=0;j--)if((1ll<<j)<=K2)x=ST[j][x],K2-=(1ll<<j);g2[i]=g[x];}for(int i=2;i<=n;i++)f[i]=(g2[i-1]+f[i-1])%p;for(int i=1;i<=n;i++)cout<<(f[i]*mul%p+p)%p<<' '; cout<<'\n';return 0;
}