链接：https://codeforces.com/contest/2152
A. Increase or Smash
算法：
贪心。
思路：
看样例猜的。
关键代码：
void miyan()
{
int n;
cin >> n;
set<int> s;
for (int i = 0; i < n; ++i)
{
int x;
cin >> x;
s.insert(x);
}
cout << s.size() * 2 - 1 << endl;
}B. Catching the Krug
算法：
博弈论，数学，切比雪夫距离。
思路：
定义 \(D\) 为追的人，\(K\) 为被追人。
先考虑 \(K\) 不能移动的情况，根据切比雪夫距离可得最短步数为 \(max(abs(Dx – Kx), abs(Dy – Ky))\)。
考虑 \(K\) 可以移动，由于他不能对角线移动，那么他的最优策略就是一直走某个可以远离 \(D\) 的方向，具体为：
- 考虑行维度：
- 如果 \(Dx < Kx\)，那么 \(K\) 在行维度的最优策略为往下跑，直到边界 \(n\)。
- 如果 \(Dx > Kx\)，那么 \(K\) 在行维度的最优策略为往上跑，直到边界 \(0\)。
- 如果 \(Dx = Kx\)，那么 \(K\) 在行维度的最优策略为不要动，动了只会变坏或者没有效果。
- 考虑列维度：
- 与行维度同理。
由于 \(K\) 只能朝一个最优的方向移动，那么在 \(K\) 可移动时 \(D\) 的最优策略既最小步数为：
- \(if Dx < Kx:\)
- \(ans = max(ans, n – Dx)\)
- \(else if Dx > Kx:\)
- \(ans = max(ans, Dx)\)
- \(if Dy < Ky:\)
- \(ans = max(ans, n – Dy)\)
- \(else if Dy > Ky:\)
- \(ans = max(ans, Dy)\)
关键代码：
void miyan()
{
ll n, x1, y1, x2, y2;
cin >> n >> x1 >> y1 >> x2 >> y2;
ll ans = 0;
if (x1 < x2)
ans = max(ans, x2);
else if (x1 > x2)
ans = max(ans, n - x2);
if (y1 < y2)
ans = max(ans, y2);
else if (y1 > y2)
ans = max(ans, n - y2);
cout << ans << endl;
}C. Triple Removal
算法：
贪心，前缀和，数学。
思路：
如果子数组内 \(0\) 或者 \(1\) 的个数不为 \(3\) 的倍数，那么此区间答案为 \(-1\)。
对于一个三元组答案只有 \(1\) 和 \(2\) 两种可能。由于数组元素只有两种可能，那么数组只有 \(010101\) 和 \(011010\) 这两种可能，既有相邻相同元素和无相邻相同元素。
对于一个子数组：
- 如果存在相邻相同元素的情况，答案为 \((r – l + 1) / 3\)。
- 如果不存在相邻元素相同的情况，既子数组为 \(01\) 交替情况，此时只需移除任意一对三元组即可，代价为 \(2\)，所有这种情况的代价为 \((r – l + 1) / 3 + 1\)
关键代码：
void miyan()
{
ll n, q;
cin >> n >> q;
vector<ll> a(n + 1, 0);
for (int i = 1; i <= n; ++i)
cin >> a[i];
vector<ll> pre(n + 1, 0);
for (int i = 1; i <= n; ++i)
pre[i] = pre[i - 1] + a[i];
vector<int> st(n + 1, 0);
for (int i = 1; i < n; ++i)
st[i] = (a[i] == a[i - 1]);
vector<ll> s(n + 1, 0);
for (int i = 1; i <= n; ++i)
s[i] = s[i - 1] + st[i];
while (q--)
{
int l, r;
cin >> l >> r;
ll cnt1 = pre[r] - pre[l - 1];
ll cnt0 = r - l + 1 - cnt1;
if (cnt1 % 3 != 0 || cnt0 % 3 != 0)
{
cout << -1 << endl;
continue;
}
if (s[r] - s[l] > 0)
cout << (r - l + 1) / 3 << endl;
else
cout << (r - l + 1) / 3 + 1 << endl;
}
}D. Division Versus Addition
算法：
博弈论，前缀和，贪心。
思路：
从二进制的角度考虑。
如果没有 \(R\) 的干扰，那么对于一个 \(a_i\) 其最高位 \(1\) 每降一位都需要 \(P\) 出手一次，降到最后一位需要 \(floor(log2 a_i)\) 次，那么对于一个区间 \([l, r]\) 一共需要 \(∑floor(log2 a_i)\)，对于这部分直接前缀和即可。
现在考虑有 \(R\) 的干扰。
先想什么时候 \(R\) 的 \(+1\) 可以让 \(P\) 多操作一次，那么就是让最高位向前移动了，既最高位产生了进位，有了更高的位，这种数字只有在有效位全为 \(1\) 的情况下存在。
那么数字可以分为三种情况：
- \((100000)\)，既 \(2 ^ k\)，这种数字固定为 \(k\) 次，如果想让其多一步需要 \(R\) 执行太多次，直接不管即可。
- \((100001)\)，既 \(2 ^ k + 1\)，这种数字只有一个的时候是增加不了次数的，需要两个及以上，既当两个人盯着一个数字处理的时候，\(R\) 转头来给某个第二类数字 \(+1\)，此时就变为第三类数字，既牺牲一个第二类数字将其转换为第三类数字。
- 其他情况，当两个人盯着这个数字进行操作时，必然会存在一个位置使得最高位产生进位。
- \(eq:\) \(10010\)
- \(P:\) \(1001\)
- \(R:\) \(1010\)
- \(P:\) \(101\)
- \(R:\) \(110\)
- \(P:\) \(11\)
- \(R:\) \(100\)
- 其余第三类情况的数字也必然满足这种情况。
- \(eq:\) \(10010\)
考虑每个数字的操作次数：
- 对于第一类数字其次数为不变。
- 对于第二类数字需要增加 \((cnt + 1) / 2\)，\(cnt\) 为区间内第二类数字个数。
- 对于第三类数字需要增加 \(cnt\)，\(cnt\) 为区间内第三类数字个数。
关键代码：
void miyan()
{
int n, q;
cin >> n >> q;
vector<ll> a(n + 1);
for (int i = 1; i <= n; ++i)
cin >> a[i];
auto lowbit = [](int x) -> int
{ return x & -x; };
vector<ll> s(n + 1, 0), pre1(n + 1, 0), pre2(n + 1, 0);
for (int i = 1; i <= n; ++i)
{
ll cnt = log2(a[i]);
s[i] = s[i - 1] + cnt;
pre1[i] = pre1[i - 1];
pre2[i] = pre2[i - 1];
if (lowbit(a[i]) == a[i])
continue;
if (lowbit(a[i] >> 1) * 2ll + 1ll == a[i])
++pre1[i];
else
++pre2[i];
}
while (q--)
{
int l, r;
cin >> l >> r;
cout << s[r] - s[l - 1] + pre2[r] - pre2[l - 1] + (pre1[r] - pre1[l - 1]) / 2ll << endl;
}
}E. Monotone Subsequence
交互以后再补。
