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;
}