牛客2025多校 R3

牛客2025多校 R3

F：

题目大意：

void solve(){int n,a,b;cin>>n>>a>>b;if (n<=a) cout<<"Sayonara"<<endl;else if (n%(a+b)<=a) cout<<n%(a+b)<<endl;else cout<<0<<endl;
}

D：
题目大意：

void solve(){int n,a;cin>>n>>a;string s;cin>>s;s=' '+s;int cnt1=0,cnt0=0,sx1=0,sx0=0,mx0=0,mx1=0;for (int i=1;i<=n;i++){if (s[i]=='1'){cnt1++;mx0=max(mx0,sx0);sx0=0;sx1++;}else{cnt0++;mx1=max(mx1,sx1);sx1=0;sx0++;}}mx0=max(mx0,sx0);mx1=max(mx1,sx1);if (mx1<a&&mx0<a+1) cout<<cnt1<<endl;else cout<<n<<endl;
}

当一开始存在至少 \(a+1\) 个连续的关机机器人或 \(a\) 个连续的开机机器人，那么就能够通过有限次的操作使得所有的机器人都被开机

否则答案为最初开机机器人的个数

J：

题目大意：

void solve(){LL x,y;cin>>x>>y;if ((x+y)%2){cout<<-1<<endl;return;}LL m=x+y>>1;LL g=__gcd(x,y);if (m%g)cout<<-1<<endl;else{LL q=m/g;if (q<=0||(q&(q-1))!=0) {cout<<-1<<endl;return;}cout<<(LL)log2(q)+1<<endl;}
}

不难发现轮数和 \(x,y\) 的关系是 \(\log\) 级别的，即暴力模拟至多 \(\log (x+y)\) 次就能通过

游戏能够结束当且仅当 \((x+y)/\mathrm{gcd}(x,y)\) 是 \(2\) 的正整数次幂，证明如下：

设 \(\mathrm{gcd}(x,y)=g\)，那么 \(x,y\) 可以被表示为 \(ag,bg\) ，对 \((x,y)\) 同除 \(g\) 后有：\((x,y)\equiv (a,b) (\mathrm{mod}\ a+b)\)

假设当前是 \(a<b\) 那么进行一轮操作后变为 \((2a,b-a)\) ，其中较小者要么为 \(2a\) 要么为 \(b-a\)

又因为 \(b-a\) 可以被表示为 \((a+b)-2a\) ，所以较小值一定可以被表示为 \(\mathrm{min}(2a,(a+b)-2a)\)

\(\mathrm{min}(2a,(a+b)-2a)\) 的含义是每次操作后都是将较小的数乘以 \(2\)

那么如果游戏能够结束，充分必要条件显然为 \(2^k\cdot a\equiv 0(\mathrm{mod}\ a+b)\) ，即存在一个正整数 \(k\) 使得 \(2^k=a+b\)

\[2^k=a+b\implies 2^k\cdot g=x+y\implies 2^k=\frac{x+y}{\mathrm{gcd}(x,y)} \]

A：

题目大意：

void solve(){int n;cin>>n;vector<int> f(n);for (int i=0;i<n;i++) cin>>f[i];vector<vector<int>> g(n+1,vector<int>(n+1,0));for (int i=0;i<n;i++) g[i][i]=1;for (int i=0;i<n;i++) g[i][i+1]=0;g[0][0]=0;for (int i=0;i<n;i++)for (int j=i+2;j<n;j++)g[i][j]=i+2;for (int i=0;i<n;i++)for (int j=0;j<n;j++)if (g[i][j]==f[i]||g[i][j]==f[j]) g[i][j]=n;for (int i=0;i<n;i++){for (int j=0;j<n;j++){if (i<=j) cout<<g[i][j]<<' ';else cout<<g[j][i]<<' ';}cout<<endl;}
}

人类智慧题目，构造方案是先构造满足 \(f_i=i\) 序列的矩阵，然后每次对于给定的 \(f_i\) 都判断需要修改哪一个在排列中的数

for (int i=0;i<n;i++)for (int j=0;j<n;j++)if (g[i][j]==f[i]||g[i][j]==f[j]) g[i][j]=n;//改为n不会对mex造成影响

E：
题目大意：

const int N=5e6+10;int spf[N];void init(){for (int i=1;i<=N;i++) spf[i]=i;for (int i=2;i<=N;i++){if (spf[i]==i){for (int j=2;i*j<=N;j++)if (spf[i*j]==i*j) spf[i*j]=i;}}
}void solve(){int n;cin>>n;vector<int> a(n+1);for (int i=1;i<=n;i++) cin>>a[i];if (n&1){cout<<"YES"<<endl;return;}if (n==2){if (a[1]==a[2]) cout<<"YES"<<endl;else cout<<"NO"<<endl;return;}unordered_map<int,int> mp;for (int i=1;i<=n;i++){while (a[i]>1){mp[spf[a[i]]]^=1;a[i]/=spf[a[i]];}}bool sum=0;for (auto [k,v]:mp) sum|=(v&1);if (sum&1)cout<<"NO"<<endl;elsecout<<"YES"<<endl;
}

操作一的意义是将两个数同时约去一个他们的公因子，操作二的意义时将两个数同时乘上一个因子

因为目标时让所有数都相同，根据唯一分解定理，给定的 \(a_i\) 都可以被表示为 \(a_i=\prod_{a_i} p_j^{\alpha_j}\) 即质因子的连乘积

那么对于每一个质因子 \(p_j\) 而言，最后每个 \(a_i\) 拥有的 \(p_j\) 数量一定相同，设最终相同的元素为 \(K\) ，那么有

\[K=\prod_K p_j^{\alpha_j}=a_i=\prod_{a_i} p_j^{\alpha_j}(\forall i\in[1,n]) \]

又因为对于一个质因子而言，操作一和二都是令他的数量增加或减少 \(2\) ，在模 \(2\) 意义下的结果都是相同的（不改变奇偶性）

对于任意的一个质因子 \(p_j\) 的数量而言，需要满足以下约束关系

\[\sum_{a_i}\sum_{p_j} \alpha_j \equiv n\cdot \sum_K\alpha_j (\mathrm{mod}\ 2) \]

当 \(n\) 是奇数时，同余式右侧的结果可能为奇数也可能为偶数，则左侧一定存在某种方案能够使得同余式成立，奇数个向量总能被“两两同加”操作调和成完全相同

当 \(n\) 是偶数时，同余式右侧一定为偶数，为了满足同余式成立，左侧必须为偶数

可以推导出题目成立的充分必要条件：

• 如果 \(n\) 为奇数，一定存在合适的操作方案
• 如果 \(n\) 为偶数，当且仅当所有元素的质因子的数量都为偶数时才满足题意

朴素的质因子分解是 \(O(\sqrt a_i)\) 的时间复杂度，在给定的时间范围内无法通过

需要预处理出在 \(N\) 范围内的所有数的最小质因子 \(\mathrm{spf}_i\) ，最后每次迭代都约去当前的最小质因子，时间复杂度为 \(O(\log a_i)\)

总时间复杂度可以被优化到 \(O(n\log a_i+N)\)

H：

题目大意：

const int N=1e6+10;int fa[N][22];
vector<int> e[N];
int dep[N];void dfs(int x){dep[x]=dep[fa[x][0]]+1;for (int i=1;i<=20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];for (auto v:e[x]) dfs(v);	
}void solve(){int n,k;cin>>n>>k;for (int i=2;i<=n;i++){cin>>fa[i][0];e[fa[i][0]].push_back(i);}dfs(1);vector<int> vis(n+1,-1);vis[0]=vis[1]=1;for (int i=1;i<=k;i++){int u,l,r;cin>>u>>l>>r;if (vis[u]!=-1){cout<<l;return;}int tu=u;for (int i=20;i>=0;i--)if (vis[fa[tu][i]]==-1) tu=fa[tu][i];tu=fa[tu][0];int uu=u;for (int i=20;i>=0;i--)if (dep[fa[uu][i]]-dep[tu]>=r-l+1) uu=fa[uu][i];for (;uu!=tu;uu=fa[uu][0])vis[uu]=l+dep[uu]-dep[tu]-1;if (vis[u]!=-1){cout<<vis[u];return;}}cout<<-1;
}

能够重合的点一定在包含根节点的一个连通块上，断边操作可以随时操作表明可以令棋子停留在任意一个到 \(u_i\) 的简单路径的节点上

对于每个时刻给出的节点 \(u_i\) ，向上寻找这个节点最接近的可访问的节点 tu

int tu=u;for (int i=20;i>=0;i--)if (vis[fa[tu][i]]==-1) tu=fa[tu][i];
tu=fa[tu][0];

然后利用当前时间维护这段时间内，从 tu 出发到 \(u_i\) 的简单路径上可访问的节点，最后判断 \(u_i\) 是否能被访问

int uu=u;for (int i=20;i>=0;i--)if (dep[fa[uu][i]]-dep[tu]>=r-l+1) uu=fa[uu][i];for (;uu!=tu;uu=fa[uu][0])vis[uu]=l+dep[uu]-dep[tu]-1;

倍增处理向上找节点的过程，总时间复杂度为 \(O(q\sqrt n)\)

B：

题目大意：

int bt(int x){if (x==0) return 0;return 32-__builtin_clz(x);
}void solve(){int a,b,c;cin>>a>>b>>c;int ta=a,tb=b,tc=c;if (a==0&&b==0){if (c==0) cout<<"0"<<endl;else cout<<"-1"<<endl;return;	}vector<int> op;if (bt(a)<bt(b)) op.push_back(3),a^=b;if (bt(b)<bt(a)) op.push_back(4),b^=a;if (bt(a)>bt(c)){while (bt(b)>bt(c)){if (bt(b)==bt(a)) op.push_back(3),a^=b;op.push_back(2),b>>=1;}}if (bt(a)<bt(b)) op.push_back(3),a^=b;while(bt(a)<bt(c)){if ((a>>(bt(b)-1))!=(c>>(bt(c)-bt(a)+bt(b)-1)))op.push_back(3),a^=b;op.push_back(1);a<<=1;}while (b){if ((a>>(bt(b)-1))!=(c>>(bt(b)-1)))op.push_back(3),a^=b;op.push_back(2),b>>=1;}op.push_back(4);b^=a;cout<<op.size()<<endl;for (auto it:op) cout<<it<<' ';cout<<endl;
}

操作次数比较严格，给定的数在 \([1,2^{31}-1]\) 的范围内，那么对于每个二进制位我们最多通过 \(2\) 次操作使得能够满足要求

构造方案具体是先将 \(a,b\) 的最高位对齐，如果 \(a<c\) ，那么每次执行 \(a\times 2\) 的操作，将 \(a\) 左移一位，在这过程中，如果发现 \(b\) 的最高位对应的 \(a,c\) 的二进制位上 \(bt(a)\ne bt(c)\) ，那么通过一次 \(a\oplus b\) 操作即可使得这一位对齐

最后 \(a=c\) ，将 \(b\) 除为 \(0\) 后和 \(a\) 进行一次异或操作，三个数都相同

如果一开始 \(a>c\) ，那么利用异或操作 $a=a\oplus b $ 消去 \(a\) 的最高位，然后将 \(b\) 除 \(2\) ，做右移一位操作

while(bt(a)<bt(c)){if ((a>>(bt(b)-1))!=(c>>(bt(c)-bt(a)+bt(b)-1)))op.push_back(3),a^=b;op.push_back(1);a<<=1;
}

通过不断的异或调整，最终使得 \(a\) 的最高位小于 \(c\) 的最高位，但此时 \(b\) 的最高位和 \(c\) 相同，所以再做一次异或操作即可对齐 \(a,c\)