牛客 周赛106 20250904
https://ac.nowcoder.com/acm/contest/116002
A：
题目大意：
void solve(){int n;cin >> n;if (n & 1) cout << "NO" << '\n';else cout << "YES" << '\n';
}
签到
B：
题目大意：
void solve(){int n, k;cin >> n >> k;auto check = [](int x){int t = x, s = 0;while (t){s *= 10;s += (t % 10);t /= 10;}return s == x;};int cnt = 0;while (!check(n)){cnt ++;if (cnt > k) break;int t = n, s = 0;while (t){s *= 10;s += (t % 10);t /= 10;}n += s; }if (cnt > k) cout << n << ' ' << -1 << '\n';else cout << n << ' ' << cnt << '\n';
}
模拟即可，时间复杂度为 \(O(nk\log x)\)
C：
题目大意：
void solve(){int n, l1, r1, l2, r2;cin >> n >> l1 >> r1 >> l2 >> r2;vector<int> a(n + 1);for (int i = 3; i <= n; i ++) cin >> a[i];for (int i = l1; i <= min(r1, l1 + 9); i ++){for (int j = l2; j <= min(r2, l2 + 9); j ++){a[1] = i % 10, a[2] = j % 10;bool f = 1;for (int k = 3; k <= n; k ++){if (a[k] != (a[k - 1] * a[k - 2]) % 10){f = 0;break;}}if (f){cout << i << ' ' << j <<'\n';return;} }}cout << -1 << ' ' << -1 << '\n';
}
枚举所有个位的情况，按照字典序从小到大循环，时间复杂度为 \(O(100n)\)
D：
题目大意：
void solve(){int n;cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i ++) cin >> a[i];vector<int> xr[n + 1];for (int i = 1; i <= n; i ++){int x = a[i];do{xr[i].push_back(x);x ^= (x >> 1);}while(x != a[i]);}int ans = 0;for (int i = 1; i <= n/2; i ++){int j = n - i + 1;int s = 1e9;for (int l = 0; l < xr[i].size(); l ++)if (xr[i][l] == a[j]) s = min(l, (int)xr[i].size() - l);if (s == 1e9){cout << -1 << '\n';return;}ans += s;}cout << ans << '\n';
}
对 \(x\) 进行替换操作相当于把 \(x\) 和他自身右移一位的结果异或起来，这样的操作最多执行 \(\log x\) 次后 \(x\) 复原
所以计算每个元素通过给定的操作可以变成的数字，然后枚举回文的另一个位置上的元素是否也在循环中
for (int l = 0; l < xr[i].size(); l ++)if (xr[i][l] == a[j]) s = min(l, (int)xr[i].size() - l);
选取操作次数最少的方向累加答案，时间复杂度为 \(O(n\log x)\)
证明：
假设 \(x\) 的二进制表示为 \(a_0a_1a_2\cdots a_n\)，那么进行一次操作后二进制序列会变为
进行第二次操作会变为
定义 \(f_{i,j}\) 表示第 \(i\) 次操作后二进制序列的第 $j $ 个元素的值，得到递推式
又因为 \(j - 2^k\) 足够小时变为负数，越界后的 \(a_{j-2^k}\) 为前导零，那么 \(f_{i,j}=f_{i-2^k,j}\) 成立
E：
题目大意：
int D[10] = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};
LL val[25];void init(){val[0] = 1;val[1] = 4;val[2] = 8;for (int i = 3;i <= 22; i ++){if (i & 1) val[i] = val[i - 1] + 4 * pow(10, i >> 1);else val[i] = val[i - 1] + 4 * pow(10, (i >> 1) - 1);}
}void solve(){LL n, sum;cin >> n >> sum;if (sum < n){cout << -1 << '\n'; return;}LL avg = sum / n;LL base;for (int i = 0; i <= 20; i ++){if (val[i + 1] > avg){base = i;break;}}vector<LL> ans;while (sum < val[base + 1] *(n - ans.size())){ans.push_back(val[base]);sum -= val[base];}while (ans.size() < n)ans.push_back(val[base + 1]);for (auto x : ans) cout << x << ' ';cout << '\n';
}
在洞数为 \(i\) 的情况下，我们可以确定出一个值最小的 \(x\) 来满足洞数等于 \(i\)
\(8\) 可以提供两个洞，那么在能填 \(8\) 的情况下先填 \(8\) 一定最优，如果洞数为 \(1\)，那么 \(x\) 一定为 \(4\) ，因为 \(0\) 不能在前导位上
所以我们构造的策略是：洞数为偶数，全部都填 \(8\) ，否则就先填一个 \(4\)
val[1] = 4;
val[2] = 8;
val[3] = 48;
val[4] = 88;
....
题目给定的 \(sum\) 和 \(n\) ，计算出每个元素位置上可以填入的平均值 avg ，先填入平均值以下的洞数尽可能大的数
然后当剩余的 \(sum\) 足够填下平均值以上的数时，就填这些数进去
vector<LL> ans;
while (sum < val[base + 1] *(n - ans.size())){ans.push_back(val[base]);sum -= val[base];
}
while (ans.size() < n)ans.push_back(val[base + 1]);
F：
题目大意：
void solve(){int n;cin >> n;vector<int> a(n + 2, 0);for (int i = 1; i <= n; i ++) cin >> a[i];int ans = 0;stack<int> st;for (int i = 1; i <= n; i ++){int f = 0;while (st.size() && st.top() < a[i]){f = 1;st.pop();}if (st.size() && a[i] != st.top() && a[i] < st.top() && f) ans ++; st.push(a[i]);}while (st.size()) st.pop();for (int i = n; i >= 1; i --){int cnt = 0;while (st.size() && st.top() < a[i]){cnt ++;st.pop();}if (st.size() && a[i] != st.top() && a[i] < st.top() && f) ans ++; st.push(a[i]);}cout << ans << '\n';
}当一段区间满足除左右端点外的元素都小于左右端点的最小值时，这个区间为一个美丽数组
分为两种情况讨论：
-
\(a_l > a_r\) ，类似单调栈的形式从左到右遍历数组，当 \(a_i\) 大于了栈顶元素时，说明 \(a_i\) 是一个可能的右端点
依次弹出栈内小于 \(a_i\) 的元素，如果有栈不为空， \(a_l \ge a_i\) 且弹出的元素至少有 \(1\) 个
if (st.size() && a[i] != st.top() && a[i] < st.top() && f)说明在区间 \([l,i]\) 的子数组是一个美丽数组
-
\(a_r > a_l\) 同理，从右向左遍历数组即可