Codeforces Round 997 (Div. 2)

### 关于 Codeforces Round 997 Div. 2 的题目及解析 #### A. XOR Mixup 在这个问题中，给定了两个整数 \(a\) 和 \(b\) ，以及一个正整数 \(k\) 。目标是在不超过 \(k\) 步内通过交换 \(a\) 和 \(b\) 中任意一位来使得两者相等。如果可以在指定步数内完成，则返回 "YES"；否则返回 "NO"[^1]。 对于这个问题的一个有效解决方案是计算不同位的数量并判断其是否小于等于两倍的 k 值加上 a 和 b 的二进制表示中最右边不同的位置索引之差。这是因为每一步最多能改变一对不匹配的位置状态。 ```cpp #include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while(t--) { long long a, b, k; cin >> a >> b >> k; bitset<32> ba(a), bb(b); int diff = 0; for(int i=0; i<32; ++i){ if(ba[i]!=bb[i])++diff; } cout << ((abs(__builtin_ctzll(a ^ b)) + 2 * k >= diff) ? "YES\n":"NO\n"); } } ``` #### B. Array Shrinking 此题描述了一个数组缩小的过程：允许选取连续子数组并将它们替换为其最大公约数值(GCD)，直到整个数组变成单个元素为止。询问最终剩余的那个唯一数字是什么样的最小可能值[^2]？ 解决方法涉及到动态规划的思想——维护一个二维表 dp[][],其中dp\[l\]\[r\] 表达的是区间 \([l,r]\) 能够被压缩成的最大 GCD 数字。转移方程基于枚举中间点 m 来分割原区间为更小子区间的组合方式实现更新。 ```cpp const int N = 2e5+7; long long gcd(long long a,long long b){return !b?a:gcd(b,a%b);} vector<int> v(N); unordered_map<long long,int> mp[N]; void solve(){ int n; scanf("%d",&n); for(int i=1;i<=n;++i)v[i]=rand()%N+1; memset(mp,0,sizeof(mp)); for(int len=1;len<=n;++len) for(int l=1;l+len-1<=n;++l){ int r=l+len-1; if(len==1)mp[l][v[l]]=1; else{ unordered_set<long long> st; for(auto &p : mp[l]) if(p.second>=len-1&&gcd(v[r],p.first)==v[r]){ printf("0");exit(0); }else{st.insert(gcd(v[r],p.first));} for(auto x:st)mp[l][x]++; } } puts(to_string(mp[1].begin()->first).c_str()); } signed main(){solve();} ```