# Round #626

## D. Present¶

$(a_1 + a_2) \oplus (a_1 + a_3) \oplus \ldots \oplus (a_1 + a_n) \\ \oplus (a_2 + a_3) \oplus \ldots \oplus (a_2 + a_n) \\ \ldots \\ \oplus (a_{n-1} + a_n) \\$

// https://codeforces.com/contest/1322/submission/72634815
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int sum[1<<25],num[400005];

int main() {
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&num[i]);
int ans=0;
for(int len=2;len<=(1<<25);len<<=1) {
for(int i=0;i<len;i++) sum[i]=0;
int u=len>>1,v=len-1;
for(int i=1;i<=n;i++) sum[num[i]&v]++;
for(int i=1;i<len;i++) sum[i]+=sum[i-1];
ll s=0;
for(int i=1;i<=n;i++) {
int t=(num[i]&v);
int l=((u-t+len)&v),r=((v-t+len)&v);
if (l<=r) s+=sum[r]-sum[l-1];
else s+=n-(sum[l-1]-sum[r]);
if (((t+t)&v)>=u) s--;
}
s>>=1;
if (s&1) ans^=u;
}
printf("%d\n",ans);
return 0;
}

## 1324D - Pair of Topics¶

// https://codeforces.com/blog/entry/74714
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif

int n;
cin >> n;
vector<int> a(n), b(n);
for (auto &it : a) cin >> it;
for (auto &it : b) cin >> it;
vector<int> c(n);
for (int i = 0; i < n; ++i) {
c[i] = a[i] - b[i];
}
sort(c.begin(), c.end());

long long ans = 0;
for (int i = 0; i < n; ++i) {
if (c[i] <= 0) continue;
int pos = lower_bound(c.begin(), c.end(), -c[i] + 1) - c.begin();
ans += i - pos;
}

cout << ans << endl;

return 0;
}

## 1324D - Sleeping Schedule¶

Vova 有一定的自制力，在第$$i$$次睡眠之前他可以选择$$a_i$$小时后入睡或$$a_i-1$$小时后入睡。

• 按时睡觉：$$dp_{i+1, j} = \max(dp_{i+1, j}, dp_{i, j}+|(s-j)\mod h \in [l, r]|)$$
• 早睡早起：$$dp_{i+1, j+1} = \max(dp_{i+1, j+1}, dp_{i, j} + |s - j - 1 \mod h \in [l, r]|)$$

Don't forget to don't make transitions from unreachable states.

#include <bits/stdc++.h>

using namespace std;

bool in(int x, int l, int r) {
return l <= x && x <= r;
}

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif

int n, h, l, r;
cin >> n >> h >> l >> r;
vector<int> a(n);
for (auto &it : a) cin >> it;
vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MIN));
dp[0][0] = 0;
int sum = 0;
for (int i = 0; i < n; ++i) {
sum += a[i];
for (int j = 0; j <= n; ++j) {
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + in((sum - j) % h, l, r));
if (j < n) dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + in((sum - j - 1) % h, l, r));
}
}

cout << *max_element(dp[n].begin(), dp[n].end()) << endl;

return 0;
}

## 1409B - Minimum Product¶

#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int a, b, x, y, n;
cin >> a >> b >> x >> y >> n;
long long ans = 1e18;
for (int i = 0; i < 2; ++i) {
int da = min(n, a - x);
int db = min(n - da, b - y);
ans = min(ans, (a - da) * 1ll * (b - db));
swap(a, b);
swap(x, y);
}
cout << ans << endl;
}
return 0;
}

## 1404A - Balanced Bitstring¶

bitstring 是仅包含 0 和 1 的字符串。给定一个包含01?的字符串$$s$$和一个正整数$$k$$，求是否可以对$$s$$中的?赋值使其中每连续的$$k$$个字符都是一个 bitstring。

#include <bits/stdc++.h>
using namespace std;
int n, k, t;
string s;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> t;
while (t--) {
cin >> n >> k >> s;
int zer = 0, one = 0;
bool chk = true;
for (int i = 0; i < k; i++) {
int tmp = -1;
for (int j = i; j < n; j += k) {
if (s[j] != '?') {
if (tmp != -1 && s[j] - '0' != tmp) {
chk = false;
break;
}
tmp = s[j] - '0';
}
}
if (tmp != -1) {
(tmp == 0 ? zer : one)++;
}
}
if (max(zer, one) > k / 2) {
chk = false;
}
cout << (chk ? "YES\n" : "NO\n");
}
}

## 1405D - Tree Tag¶

Alice 和 Bob 分别站在一棵树的两个结点$$a, b$$上，Alice 每次可以走过$$da$$条边，Bob 可以走过$$db$$条边。Alice 先手，二人交替操作，经过足够多的步数后，当 Alice 和 Bob 落到同一个节点上 Alice 胜，否则 Bob 胜。另外已知 Bob 和 Alice 都是绝顶聪明的人，都会执行最佳操作，问谁最终获胜。

### 1. $$\mathrm{dist}(a, b) \le da$$¶

Alice 交出一个闪现大步一跃一把抓住 Bob，Bob，卒。

### 2. $$2da > 树的直径$$¶

Alice 首先到达树的重心，之后 Bob 插翅难逃。

### 4. $$db > 2da$$¶

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
int n, a, b, da, db, depth[N];
int diam = 0;

int dfs(int x, int p) {
int len = 0;
if(y != p) {
depth[y] = depth[x] + 1;
int cur = 1 + dfs(y, x);
diam = max(diam, cur + len);
len = max(len, cur);
}
}
return len;
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int te;
cin >> te;
while(te--) {
cin >> n >> a >> b >> da >> db;
for(int i = 1; i <= n; i++) adj[i].clear();
for(int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
}
diam = 0;
depth[a] = 0;
dfs(a, -1);
cout << (2 * da >= min(diam, db) || depth[b] <= da ? "Alice" : "Bob") << '\n';
}
}