备战
更新至I、K、B、F、E、D、C
I.Cyclic Apple Strings
题意：给定一个 $01$ 串，每次操作可以选择一个连续段使该范围内字符连续左移若干次，求使得整串严格非递减的最少操作数。
解：显然统计从左到右需操作的段数即可。
Code
#include"bits/stdc++.h"
using namespace std;
#define pb(x) push_back(x)
typedef long long ll;
const int N = 2e5 + 10, MOD = 1e9 + 7;
int main(){
string s; cin >> s;
int n = s.size(), ans = 0;
s = " " + s; s += "1";
for(int i = 1; i <= n; ++ i){
if(s[i] == '1' && s[i + 1] == '0') ans ++;
}
cout << ans;
}
K.Party Games
题意：定义一个长度为 $n$ 的数组为 $1 - n$ 的排列，两个人轮流进行操作，每次操作可以从该数组的头部或尾部拿走一个数，当且仅当剩下的数组异或和为 $0$ 时判定当前操作人为输。
解：通过打表得
i = 1, sum = 1
i = 2, sum = 3
i = 3, sum = 0
i = 4, sum = 4
i = 5, sum = 1
i = 6, sum = 7
i = 7, sum = 0
i = 8, sum = 8
i = 9, sum = 1
i = 10, sum = 11
i = 11, sum = 0
i = 12, sum = 12
i = 13, sum = 1
i = 14, sum = 15
i = 15, sum = 0
i = 16, sum = 16
可以发现其中异或和 $sum$ 四个数一个周期，、且 $sum = 1$ 时通过拿走头数字先手必胜， $i\ mod\ 4 = 0$ 时通过拿走队尾数字先手必胜，其余情况先手必败。
Code
#include "bits/stdc++.h"
using namespace std;
#define pb(x) push_back(x)
typedef long long ll;
const int N = 2e5 + 10, MOD = 1e9 + 7;
int main(){
int T; cin >> T;
while(T --){
int x; cin >> x;
if(x % 4 == 0 || x % 4 == 1) cout << "Fluttershy\n";
else cout << "Pinkie Pie\n";
}
}
B.Countless Me
题意：给定长度为 $n$ 的 $a\ (a_i\le1e9)$ 数组，使用不超过 $n$ 次操作，每次操作选择两个不同的元素 $a_i, a_j$ 和一个不大于 $a_j$ 的 $x$ 使得 $a_i = a_i + x, a _j = a_j - x$。 问最终数组的
$按位或$ 后最小值为多少。
解：通过 $n$ 次操作我们可以使得数组变成任意的数组组合，且满足于数组的总和 $sum$ 不变。因此我们可以从高到低位判断是否需要在 $1<<i$ 这个位置上放数，一旦放数后即可尽量把 $n$ 个 $1<<i$ 填满即可。
Code
signed main(){
int ans = 0, sum = 0;
int n; cin >> n;
for(int i = 1; i <= n; ++ i) {
int x; cin >> x;
sum += x;
}
for(int i = 30; i >= 0; -- i){
int x = 1ll << i;
if(sum > (x - 1) * n){
int y = sum / x;
sum -= 1ll * x * min(y, n);
ans |= x;
}
}
cout << ans;
}
F.Custom-Made Clothes
交互题
题意：存在一个 $n*n\ (n\le 1000)$ 的正整数矩阵，其中的正整数满足 $a_{i,j}\ge a_{i,j-1},\ a_{i,j}\ge a_{i - 1,j}$， 最多 $50000$ 次询问，每次询问 $i, j, x$ 返回 $a_{i,j}\le x$ 的结果，求问该矩阵中第 $k$ 大的值。
解：间接转化成求矩阵中第 $n * n - k$ 个小的值，可以二分这个答案 $x$, 并根据矩阵的特性每次通过 $n$ 次询问查找矩阵中小于 $x$ 的个数而更新二分边界。
Code
int n, k;
bool ask(int x, int y, int s){
cout << "? " << x << ' ' << y << ' ' << s << '\n';
int xx; cin >> xx;
return xx;
}
int ok(int mid){
int sum = 0;
for(int i = 1, j = n; i <= n; i ++){
while(j >= 1 && !ask(i, j, mid)) j --;
sum += j;
}
return sum;
}
int main(){
cin >> n >> k;
k = n * n - k + 1;
// cout << k << '\n';
int l = 1, r = n * n;
while(l < r){
int mid = l + r >> 1;
if(k > ok(mid)) l = mid + 1;
else r = mid;
}
cout << "! " << l;
}
E.Boomerang
题意：给定一个 $n$ 大小的无向树，一个谣言起始点 $r$ 和 开始消除谣言的时间 $t_0$，存在谣言的结点每个时间单位向边上的结点扩散， $t_0$ 时间之后可以选择一个结点以个时间单位里 $k$ 的步长向边沿结点辟谣，问分别当 $k=1 \sim n$ 时辟完所有谣的最小时间单位。
解：通过根节点 $r$ 预处理求出经过每个时间单位树中被谣言覆盖的直径，随后对于每个 $k$ 二分查找花费最少时间辟谣的时间 $t$，此时答案就是 $t_0 + t$
Code
#include"bits/stdc++.h"
using namespace std;
#define pb(x) push_back(x)
typedef long long ll;
const int N = 2e5 + 10, MOD = 1e9 + 7;
vector g[N], g0[N];
int dist[N], f[N][30], lg[N], d[N];
void build(int u, int pre){
f[u][0] = pre;
dist[u] = dist[pre] + 1;
g0[dist[u]].push_back(u);
for(int i = 1; f[u][i - 1]; i ++){
f[u][i] = f[f[u][i - 1]][i - 1];
}
for(auto v: g[u]){
if(v != pre) build(v, u);
}
}
int lca(int u, int v){
if(dist[u] < dist[v]) swap(u, v);
while(dist[u] > dist[v]) u = f[u][lg[dist[u] - dist[v]] - 1];
if(u == v) return v;
for(int i = lg[dist[u]] - 1; i >= 0; -- i){
if(f[u][i] != f[v][i]){
u = f[u][i];
v = f[v][i];
}
}
return f[u][0];
}
int get(int u, int v){
int tt = lca(u, v);
return dist[u] + dist[v] - 2 * dist[tt];
}
int main(){
for(int i = 1; i <= N; ++ i){
int x = i;
while(x){
lg[i] ++;
x /= 2;
}
}
int n, r, t0; cin >> n;
for(int i = 1; i < n; ++ i){
int u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
cin >> r >> t0;
dist[0] = -1;
build(r, 0);
for(int i = 1; i <= n; ++ i){
d[i] = d[i - 1];
if(g0[i].size() != 0){
int x = g0[i][0];
int mx = d[i] + 1;
for(int j = 1; j < g0[i].size(); ++ j){
mx = max(mx, get(x, g0[i][j]));
}
d[i] = max(mx, d[i]);
}
}
for(int i = 1; i <= n; ++ i){
d[i] ++;
// cout << d[i] << " \n"[i == n];
}
for(int i = n + 1; i <= n + n; ++ i) d[i] = d[i - 1];
for(int k = 1; k <= n; ++ k){
int l = 1, r = n;
while(l < r){
int mid = l + r >> 1;
if(d[t0 + mid] / 2 <= 1ll * mid * k) r = mid;
else l = mid + 1;
}
cout << t0 + l << " \n"[k == n];
}
}
D.ICPC
题意：有一个长度为 $n$ 的餐桌每个位置有一个权值为 $a_i$ 的食物，初始位于 $s$ 处的小M每秒可以向左或向右移动一个单位并立即吃掉该食物，假设 $F[i][j]$ 表示初始位于位置 $i$ 的小M经过 $j$ 秒吃到权值和最大的值，那么求
$\oplus \ _{i=1}^n$ $(i+\oplus$ $\ _{j=1}^{2n}*F[i][j])$
解：从公式看出本题的重点在于求出 $F[i][j]$，而思考后显然移动的情况要么一直往一个方向，要么最多折返一次。
当一直往一个方向时 $F[i][j] = max(sum[i + j] - sum[i - 1], sum[i] - sum[i - j - 1])$, 此时求出直线运动的最大值。
当折返一次时，$F[i][j] = max(F[i+1][j-1], F[i-1][j-1])$, 由于转移过程中一直调用 $j-1$ 的状态，所以 $j$ 应在第一层枚举。
Code
#include"bits/stdc++.h"
using namespace std;
#define pb(x) push_back(x)
typedef long long ll;
const int N = 2e5 + 10, MOD = 1e9 + 7;
ll dp[5010][2 * 5010], sum[N];
int main(){
int n; cin >> n;
for(int i = 1; i <= n; ++ i){
cin >> sum[i];
sum[i] += sum[i - 1];
}
for(int i = 1; i <= n; ++ i){
dp[i][0] = sum[i] - sum[i - 1];
for(int j = 1; j <= n + n; ++ j){
dp[i][j] = dp[i][j - 1];
if(i + j <= n + n){
dp[i][j] = max(dp[i][j],sum[i + j] - sum[i - 1]);
}
if(i - j >= 1){
dp[i][j] = max(dp[i][j], sum[i] - sum[i - j - 1]);
}
}
}
for(int j = 1; j <= n + n; ++ j){
for(int i = 1; i <= n; ++ i){
if(i + 1 <= n)
dp[i][j] = max(dp[i][j], dp[i + 1][j - 1]);
if(i - 1 >= 1)
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1]);
}
}
ll ans = 0;
for(int i = 1; i <= n; ++ i){
ll res = 0;
for(int j = 0; j <= n + n; ++ j){
// cout << dp[i][j] << " \n"[j == n + n];
res ^= 1ll * j * dp[i][j];
}
ans ^= res + i;
}
cout << ans;
}
C:TreeBag and LIS
题意：给定一个数 $x(x\le 10^13)$， 要求构造一个长度不超过 $10^5$ 的数字序列，使得里面严格递增的所有最长子序列和为 $x$。
比如 $x=494$，可以构造$001243$，此时序列中$0124+0123+0124+0123=494$。
发现可以通过012012012012的摆法，使得和为 $(12*等差数列求和数量sum)$，通过在每一对 $”012”$ 后边放 “2”，并且从大到小凑这个 $sum$ 即可。当然这里的前提是将 $x$ 变成 $12$ 的倍数，这里通过暴力枚举三个数即可。
不用 $12$ 也可以，下面代码以13为例。
Code
int main(){
ll x; cin >> x;
string s = "";
if(x == 0) s += '0';
else if(x <= 99910){
s += '0';
while(x --) s += '1';
}else {
for(int a = 3; a < 10; ++ a){
for(int b = a + 1; b < 10; ++ b){
for(int c = b + 1; c < 10; ++ c){
int k = a * 100 + b * 10 + c;
if(x % 13 != 0 && (x - k) % 13 == 0){
s += '0' + a;
s += '0' + b;
s += '0' + c;
x -= k;
}
}
}
}
x /= 13;
int t = 0;
while(1ll * t * (t + 1) * (t + 2) / 6 <= x) t ++;
t --;
x -= 1ll * t * (t + 1) * (t + 2) / 6;
vector p(t + 1);
for(int i = t; i >= 1; -- i){
ll d = 1ll * (1 + i) * i / 2;
p[i] = x / d;
x -= 1ll * d * p[i];
}
for(int i = 1; i <= t; ++ i){
s += "013";
while(p[i] --) s += '3';
}
}
cout << s;
}