2024 ICPC National Invitational Collegiate Programming Contest, Wuhan Site
B - Countless Me
Solution
显然，只能执行 \(n\) 次操作是没用的条件
我们只需要把和 \(sum\) 分给 \(n\) 个数，使得 \(n\) 个数的或和最小即可
从高到低考虑每一位，假设此时枚举到第 \(i\) 位
如果这一位可以不放 \(1\)，即后面的位能组成 \(sum\)，则肯定不放
如果这一位要放 \(1\)，考虑放几个 \(1\)，显然，最大值 \(max=\min(n,\frac{sum}{2^i})\)
按照贪心的思想，放 \(max\) 个 \(1\) 即可
模拟此过程
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ll sum = 0; ll n = 0; cin >> n;
ll ans = 0;
for (int i = 1; i <= n; i++) { ll x; cin >> x; sum += x; }
for (ll i = 30; i >= 0; i--) {
if (((1ll << i) - 1) * n >= sum) continue;
ll num = min(1ll * n, sum / (1ll << i));
if (num == 0) continue;
sum -= num * (1ll << i);
ans |= 1ll << i;
}
cout << ans << '\n';
return 0;
}
D - ICPC
Solution
定义 \(g[i][j]\) 表示从 \(i\) 点出发，向右移动不超过 \(j\) 次的和的最大值
定义 \(f[i][j]\) 表示从 \(i\) 点出发，先向左走，然后向右走的最大值，显然只会发生一次调头
不妨设在向左走了 \(l\) 步折返，那么 \(f[i][j]=\max_{l=0}^{i-1}\{g[i-l][j-l]\}\)
显然这个用前缀最大值处理就好了
对于先向右走然后折返的情况，只需要把 \(a\) 倒过来处理一次就好了
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void calc(vector<ll> &a, vector<vector<ll> > &dp) {
int n = a.size() - 1;
vector<vector<ll> > g(n + 1, vector<ll>(n + 1, 0));
for (int x = 1; x <= n; x++) {
g[x][0] = a[x];
for (int j = 1; j <= n; j++) {
g[x][j] = g[x][j - 1];
if (x + j <= n) g[x][j] += a[x + j];
}
}
for (int s = 1; s <= n; s++)
for (int j = 1; j <= 2 * n; j++) {
dp[s][j] = max(dp[s][j], max(dp[s - 1][j - 1], g[s][min(j, n)]));
}
}
int main() {
int n; cin >> n;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
vector<vector<ll> > dp(n + 1, vector<ll>(2 * n + 1, 0));
calc(a, dp);
reverse(a.begin() + 1, a.end());
reverse(dp.begin() + 1, dp.end());
calc(a, dp);
reverse(dp.begin() + 1, dp.end());
ll ans = 0;
for (int i = 1; i <= n; i++) {
ll now = 0;
for (int j = 1; j <= 2 * n; j++)
now ^= 1ll * j * dp[i][j];
ans ^= (now + i);
}
cout << ans << '\n';
return 0;
}
E - Boomerang
Solution
显然，我们先按照 \(r\) 为根节点建树，对于每个时刻 \(tim\)，谣言传播到 \(dep\) 小于等于 \(tim\) 的节点
我们在每个时刻辟谣时，只需要观察直径，从直径的中点开始辟谣
所以我们需要维护每个时刻树的直径
有一个比较显然的结论，我们按深度从小到大加点，设深度为 \(x\) 的点在时刻 \(x\) 加入，对于一个新加入的点，它肯定时新的直径的一端，另外一端是老直径的一段
所以我们只需要维护直径的两端，对于新加入的点，用 LCA 算出新直径，看是保留那一端
求出每个时刻的直径后，对于每个 \(k=i\)，我们用二分找一个时刻 \(t'\) 使得，\(k(t'-t0)\) 能覆盖整个 \(k'\) 的直径
当然这里用双指针也是可以的，因为 \(k\) 增加时，答案肯定递减
Code
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > g;
vector<int> dep;
vector<array<int, 20> > fa;
int n, rt, t0;
int max_dep;
void dfs(int u, int f, int dp) {
max_dep = max(max_dep, dep[u] = dp);
fa[u][0] = f;
for (int i = 1; i < 20; i++)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for (auto &v : g[u]) {
if (v == f) continue;
dfs(v, u, dp + 1);
}
}
int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i = 19; i >= 0; i--)
if (dep[x] - (1 << i) >= dep[y])
x = fa[x][i];
if (x == y) return x;
for (int i = 19; i >= 0; i--)
if (fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
int dis(int x, int y) { return dep[x] + dep[y] - 2 * dep[lca(x, y)]; }
int main() {
// freopen ("E.in", "r", stdin);
cin >> n;
g.assign(n + 1, vector<int>());
dep.resize(n + 1); fa.resize(n + 1);
for (int i = 1; i < n; i++) {
int u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
cin >> rt >> t0;
dfs(rt, 0, 0);
vector<int> id (n + 1);
for (int i = 1; i <= n; i++) id[i] = i;
auto cmp = [&](int x, int y) {return dep[x] < dep[y];};
sort (id.begin() + 1, id.end(), cmp);
int pos = 2, max_tim = 2 * n;
vector<int> log_dep (max_tim + 1);
int d1 = rt, d2 = rt;
auto insert = [&] (int x) {
int d1_x = dis(d1, x), d2_x = dis(d2, x);
if (d1_x > d2_x) { d2 = x; return d1_x; }
else { d1 = x; return d2_x; }
};
for (int i = 1; i <= max_dep; i++) {
while (pos <= n && dep[id[pos]] == i)
log_dep[i] = max(log_dep[i], insert(id[pos++]));
}
for (int i = max_dep + 1; i <= max_tim; i++)
log_dep[i] = log_dep[i - 1];
for (int k = 1; k <= n; k++) {
auto check = [&] (int t) {
int l = log_dep[t] / 2 + (log_dep[t] & 1);
if (1ll * k * (t - t0) >= 1ll * l) return true;
return false;
};
int l = t0 - 1, r = max_tim;
while (l + 1 < r) {
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid;
}
cout << r << ' ';
}
return 0;
}
F - Custom-Made Clothes
Solution
交互题
我把题转化成求方阵中第 \(k\) 小的数 \(x\)
显然开始时二分答案，二分 \(mid\)，然后去 check 在 \(mid\) 在方阵中有多少小于等于 \(mid\) 的
显然，小于等于 \(mid\) 的区域肯定是在左上角的某块区域，而有一条折的分界线
我们只需要得到这条分界线就可以得到小于等于 \(mid\) 的个数了
具体假设此时询问，\((x,y)\) 是否小于等于 \(mid\)，如果返回 \(1\)，则 \(y+1\)，否则 \(x-1\)
Code
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k; cin >> n >> k;
int l = 0, r = n * n; k = n * n - k + 1;
auto check = [&](int x) {
int res = 0;
int pos_x = n, pos_y = 1;
while (pos_x >= 1 && pos_y <= n) {
cout << "? " << pos_x << " " << pos_y << " " << x << endl;
int rely; cin >> rely;
if (rely == 1) {
res += pos_x;
pos_y++;
}
else {
pos_x--;
}
}
return res;
};
while (l + 1 < r) {
int mid = (l + r) / 2;
if (check(mid) >= k) r = mid;
else l = mid;
}
cout << "! " << r << endl;
return 0;
}
I - Cyclic Apple Strings
Solution
签到题，只需要输出除了 \(1\) 的连通块的个数 \(-1\)
Code
#include <bits/stdc++.h>
using namespace std;
int main() {
string s; cin >> s;
s = " " + s;
int lst_0 = -1;
for (int i = 1; i < s.size(); i++)
if (s[i] == '0')
lst_0 = i;
int ans = 0;
for (int i = 1; i <= lst_0; i++)
if (s[i] == '1' && s[i - 1] != '1')
ans += 1;
cout << ans << endl;
return 0;
}
K - Party Games
Solution
观察 \(\oplus_{i=1}^n i\)
当 \(i\ mod\ 4 = 1\) 时，\(\oplus_{i=1}^n i=1\) ，显然先手必胜
当 \(i\ mod\ 4 = 2\) 时，\(\oplus_{i=1}^n i=n+1\) ，无论先手拿 \(1\) 还是 \(n\)，后手拿另外一个，异或和位 \(0\)，先手必败
当 \(i\ mod\ 4 = 3\) 时，\(\oplus_{i=1}^n i=0\) ，显然先手必胜
当 \(i\ mod\ 4 = 0\) 时，\(\oplus_{i=1}^n i=n\) ，先手拿走 \(n\) 让异或和为 \(0\)，先手必胜
Code
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n; cin >> n;
int x = n % 4;
if (x == 0 || x == 1) puts("Fluttershy");
else puts("Pinkie Pie");
}
int main() {
int t; cin >> t;
while (t--) solve();
return 0;
}