A. Flip Flop Sum
能换 \(-1,-1\) 就换，不能能换 \(1,-1\) 或 \(-1,1\) 也可以，否则只能换 \(1,1\)。
B. The Forbidden Permutation
如果原序列一开始就是好的那就结束，否则尝试打破一边的不等号即可。
C. Flexible String
暴力搜索每一个字符是否在 \(S\) 当中。时间复杂度 \(O(n2^{|\Sigma|})\)
D. Flexible String Revisit
随机给 \(01\) 串取反，问变到全 \(0\) 的期望步数。
考虑 \(f_i\) 表示当前有 \(i\) 个 \(1\) 的期望步数。不难有：
\[f_0=0,f_i=\dfrac inf_{i-1}+\dfrac{n-i}n f_{i+1}+1 \]我们假设 \(f_n=x\)，我们可以把每一个 \(f\) 写成关于 \(x\) 的一次函数，推回到 \(f_0\) 时解出 \(x\) 即可。
给一段参考代码。
void init(){
// 求 p[n]
a[n]=1,b[n]=0;
for(int i=n;i>=1;i--){
// ip[i-1]=np[i]-(n-i)p[i+1]-n
a[i-1]=(n*a[i]%MOD-(n-i)*a[i+1]%MOD+MOD)%MOD*inv(i)%MOD;
b[i-1]=((n*b[i]%MOD-(n-i)*b[i+1]%MOD+MOD)%MOD-n+MOD)*inv(i)%MOD;
}
ll x=(MOD-b[0])*inv(a[0])%MOD;
for(int i=0;i<=n;i++)
p[i]=(a[i]*x+b[i])%MOD;
}
E. The Tree Has Fallen!
- 给一棵点权树，每次询问查询以 \(r\) 为根时 \(u\) 的子树当中可选若干点权异或最大。
- \(n,q\leq2\times 10^5\)。
首先这个问题显然时线性基，我们考虑对每个结点维护一个线性基存入他的子树点权。由于根可能被改变，所以需要换根。
更具体的，当我们把根从 \(u\) 换到 \(v\) 的时候，那么 \(v\) 的线性基就会变成全部元素的线性基，但是 \(u\) 的线性基会变成所有节点去除 \(v\) 节点的线性基的合并。但是线性基没有可减性，所以我们需要维护一个节点的相邻节点的前缀线性基，后缀线性基才可以完成转移。
代码写起来很丑，而且常熟巨大，当乐子看就好了。听说有 dfs 序的简单一点的代码，但是懒得打。
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define ll long long
#define MP make_pair
const int MAXN=2e5+5;
int _;
struct Xxj{
int a[32];
}xxj[MAXN];
int ask(Xxj x){
ll res=0;
for(int i=31;i>=0;i--)
if((res&(1<<i))==0)
res^=x.a[i];
return res;
}
void insert(Xxj &x,int k){
for(int i=31;i>=0;i--)
if(!x.a[i]&&(k&(1<<i))){
x.a[i]=k;
return;
}else if(k&(1<<i))k^=x.a[i];
}
Xxj merge(Xxj x,Xxj y){
Xxj res=x;
for(int i=31;i>=0;i--)
if(y.a[i])
insert(res,y.a[i]);
return res;
}
void Clear(Xxj &x){
for(int i=31;i>=0;i--) x.a[i]=0;
}
vector<int> ve[MAXN];
vector<pair<int,int> > qe[MAXN];
int ans[MAXN];
int n,q,a[MAXN];
void dfs(int u,int fa){
insert(xxj[u],a[u]);
for(int v:ve[u]) if(v!=fa){
dfs(v,u);
xxj[u]=merge(xxj[u],xxj[v]);
}
}
void dfs_root(int u,int fa){
for(auto i:qe[u])
ans[i.second]=ask(xxj[i.first]);
int sz=ve[u].size();
vector<Xxj> pl(sz+1),pr(sz+1);
pl[0]=xxj[ve[u][0]];
pr[sz-1]=xxj[ve[u][sz-1]];Clear(pr[sz]);
for(int i=1;i<sz;i++)
pl[i]=merge(pl[i-1],xxj[ve[u][i]]);
for(int i=sz-2;i>=0;i--)
pr[i]=merge(pr[i+1],xxj[ve[u][i]]);
Xxj rt=xxj[u],copy;
for(int i=0;i<sz;i++)if(ve[u][i]!=fa){
if(!i) xxj[u]=pr[i+1];
else xxj[u]=merge(pl[i-1],pr[i+1]);
insert(xxj[u],a[u]);
copy=xxj[ve[u][i]],xxj[ve[u][i]]=rt;
dfs_root(ve[u][i],u);
xxj[ve[u][i]]=copy;
}
xxj[u]=rt;
return;
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++) ve[i].clear(),qe[i].clear(),Clear(xxj[i]);
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
ve[u].push_back(v);
ve[v].push_back(u);
}
cin>>q;
for(int i=1;i<=q;i++){
int r,u;cin>>r>>u;
qe[r].push_back(MP(u,i));
}
dfs(1,0);
dfs_root(1,0);
for(int i=1;i<=q;i++)
cout<<ans[i]<<endl;
return;
}
int main(){
cin>>_;
while(_--)
solve();
}
F. Maximizing Root
- 给一颗点权树（\(1\) 为根），每次可以选择一个未选择过的节点 \(u\) 然后把他的所有儿子点权乘上这颗子树所有节点点权的 \(\gcd\)。
- 最多 \(k\) 次操作，最大化 \(1\) 的点权。
- \(n\leq10^5,a_i\leq10^3\)。
显然操作肯定时自下而上的，也就是不会选择了一个祖先又选择了一个儿子。对于一次操作来说，变化的是一个子树的 \(\gcd\) 变成了它本身的平方。
考虑树形 dp。\(f_{i,j}\) 表示对 \(i\) 的子树，不操作根节点要所有权值都是 \(j\) 的倍数的最小操作数，容易得到转移：
\[f_{i,j}=\sum_{v\in son_i} \min(f_{v,j},(\min_{j|k^2} f_{v,k})+1) \]这个转移是 \(d(V)^2\) 的。总的时间复杂度时 \(O(n d^2(V))\)，得以通过。
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
const int MAXN=1e5+5;
const int MR=1005;
int f[MAXN][1005];// f[i][j] 表示 i 子树公约数 j 倍数最小操作数
vector<int> ve[MAXN],d[MR];
int tmp[1005],a[MAXN];
int n,k;
int gcd(int x,int y){
return (x%y==0)?y:gcd(y,x%y);
}
void dfs(int u,int fa){
for(int i:d[a[u]]) f[u][i]=0;
for(int v:ve[u])if(v!=fa){
dfs(v,u);
for(int p:d[a[v]]) if(f[v][p]!=1e9){
int g=gcd(a[u],p);
tmp[g]=min(tmp[g],f[v][p]);
g=gcd(a[u],p*p);
tmp[g]=min(tmp[g],f[v][p]+1);
}
for(int i:d[a[u]])
for(int j:d[i]) tmp[j]=min(tmp[j],tmp[i]);
for(int i:d[a[u]])
f[u][i]=min(f[u][i]+tmp[i],(int)1e9),tmp[i]=1e9;
}
return;
}
void solve(){
cin>>n>>k;
for(int i=1;i<=n;i++) ve[i].clear();
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
ve[u].push_back(v);
ve[v].push_back(u);
}
if(k==0){
cout<<a[1]<<endl;
return;
}
dfs(1,0);
int ans=0;
for(int i:d[a[1]])
if(f[1][i]<k) ans=max(ans,a[1]*i);
cout<<ans<<endl;
return;
}
int main(){
for(int i=1;i<MR;i++){
tmp[i]=1e9;
for(int j=i;j<MR;j+=i)
d[j].push_back(i);
}
int _;cin>>_;
while(_--) solve();
}