Codeforces Round 885 (Div. 2)
A. Vika and Her Friends
题目大意
太长了 click
思路
可以手动模拟一下，可以发现当两个人的 \(x+y\) 值就行相同的就能抓到了
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin >> T;
while (T--)
{
int n, m, k;
cin >> n >> m >> k;
bool flag = false;
int a, b;
cin >> a >> b;
for (int i = 1; i <= k; i++)
{
int c, d;
cin >> c >> d;
if ((a + b - (c + d)) % 2 == 0)
flag = true;
}
if (!flag)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}
B.Vika and the Bridge
题目大意
有 \(n\) 块木板排成一排，第 \(i\) 块木板的颜色是 \(c_i\)，你站在第一块木板前面，需要跳跃到第 \(n\) 块木板后面，每一次只能跳相同颜色的木板。现在你可以更改一块木板的颜色，使得你每一次跳跃的距离(指两块木板中间部分，不计两端点)的最大值最小，请求出这个值。
思路
首先我们知道一个结论，当一个点到另一个与它相同颜色的点的距离是最大的，那么，我们只要在中间插上一个与其颜色相同的点就能让最大长度的除以 2 。
我们考虑维护最大距离 \(fmax\) 和次大距离 \(smax\)，最后统计 \(\min\{\max\{\frac{fmax_i}{2},smax_i\}\}\) 即可
int distance = i - last[a[i]] - 1;
if (distance > fimax[a[i]])
{
smax[a[i]] = fimax[a[i]];
fimax[a[i]] = distance;
}
else if (distance > smax[a[i]])
smax[a[i]] = distance;
---------------------------------------
last[a[i]] = i;
int ans = 1e9 + 7;
for (int i = 1; i <= m; i++)
ans = min(ans, max(smax[i], fimax[i] / 2));
C.Vika and Price Tags
题目大意
给定 \(n\) \((1≤n≤1×10^5)\) 对整数 \(a,b\) \(( 1≤a,b≤1×10^9 )\)，每次使 \(a←b\)，\(b←∣a−b∣\)，求是否能实现让所有的 \(a\) 在有限次同步操作后都变为 \(0\)。
思路
这道题显然用到了“更相减损法”，既然是更相减损，那么就会想到词 \(\gcd\)
对于 \(a,b(a>b)\) 的最大公因数 \(\gcd(a,b)\), 有
\(\gcd(a,b)=\gcd(b,a-b)\)
在更相减损法的过程中 \(\gcd(a,b)\) 显然不变，最后使得 \(a=0\) ，此时 \(\gcd(a,b)\) 为 \(b\)
最终满足题目序列的序列的是这样的
| \(0\) | \(0\) | \(0\) | \(0\) |
|---|---|---|---|
| \(\gcd(a_1,b_1)\) | \(\gcd(a_2,b_2)\) | \(\gcd(a_3,b_3)\) | \(...\) |
我们只需要讨论所要的 \(\gcd(a_i,b_i)\) 能不能同时出现。
对于满足条件的数对 \((0,b)\) 在操作过程中的状态可能是 \((0,b),(b,b),(b,0)\) ，并在三种状态中有序循环
考虑简化，对于数对 \((a,b)\)，在进行 \(k\) 此操作后可以形成 \((0,x)\) 满足条件的数对，那么对于数对 \((qa,qb)\) 可以在进行 \(k\) 次操作后，一定变成 \((0,qx)\) ，在所有操作中 \(q\) 可以当成公因数提出
同理，数对 \((a,b)\) 与 数对 \((\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)})\) 等价
接下来用互质给数对 \((a,b)\) 进行分类，当 \(a\) 与 \(b\) 互质时，会有
| \(a\) | 奇 | 偶 | 奇 |
|---|---|---|---|
| \(b\) | 偶 | 奇 | 奇 |
如何证明以上就是我们所需的三种分类呢？
设 \(a=2k,b=2k+1\)
| \(a\) | \(2k\) | \(2k+1\) | \(1\) | \(2k\) | \(2k−1\) | \(1\) | \(2k−2\) | ... |
|---|---|---|---|---|---|---|---|---|
| \(b\) | \(2k+1\) | \(1\) | \(2k\) | \(2k−1\) | \(1\) | \(2k−2\) | \(2k−3\) | ... |
发现数对 \((a,b)\) 总是在给出的三种情况反复循环
以奇奇，奇偶开始同理
所以我们证明了，数列能否合法，只与其间数对的奇偶性有关。如果数对的奇偶性有且仅有唯一的一种，那么就能成立。
int work(int x, int y)
{
int gcc = gcd(x, y);
x /= gcc, y /= gcc;
if (x % 2 == 0)
return 0;
if (y % 2 == 0)
return 1;
return 2;
}
-------------------------------
for (int i = 1; i <= n; i++)
{
if (a[i] == 0 && b[i] == 0)
continue;
res = work(a[i], b[i]);
if (res == 0) sum0 = 1;
if (res == 1) sum1 = 1;
if (res == 2) sum2 = 1;
}