前言

随便写写

C. Vika and Price Tags

题意

给定数组 $a$, $b$，定义 $c_i$=$|a_i-b_i|$，然后将 $b$ 赋值给 $a$，将 $c$ 赋值给 $b$。问数组 $a$ 最终可不可以全都是 $0$

思路

相邻的数互相之间是不会影响的，所以只用考虑一对数 $(x, y)$，看 $x$ 最少操作几次后变成 $0$。

如果 $x>y$：

多画画，可以发现，经过若干次操作后，$(x, y)$ 会变成 $(y, x - (2k+1) * y)$，此时 $y > x - (2k+1) * y$，可以联想到最大公约数的求法，也是这样下降的，而且下降的很快，是 $log$ 级别的。

所以关键在于，求出多少次操作后，$(x, y)$ 会变成 $(y, x - (2k+1) * y)$。

显然，这个答案是 $3k+1$。

如果 $x<y$：

这个很简单，模拟一次之后，就会重新变成 $x>y$ 的情况了。

所以这题可以很完美的用递归去解决。

int a[N], b[N];
// 返回 x 变 0 的最小操作次数
int calc(int x, int y) {
    if (x == 0) {
        return 0;
    }
    if (y == 0) {
        return 1;
    }
    if (x < y) {
        return calc(y, y - x) + 1;
    }
    int c = x / y;
    if (c % 2 == 0) {
        c--;
    }
    int sum = c / 2 * 3 + 1;
    return sum + calc(y, x - c * y);
}
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    set<int> s;
    for (int i = 1; i <= n; i++) {
        if (a[i] == 0 && b[i] == 0) continue;
        s.insert(calc(a[i], b[i]) % 3);
    }
    if (s.size() > 1) {
        cout << "NO\n";
    }
    else {
        cout << "YES\n";
    }
}

B. Vika and the Bridge

没什么意思，就是歌阅读理解，代码懒得贴了。这题还不如 $A$ 有意思。

A. Vika and Her Friends

题意

薇卡和她的朋友玩捉迷藏，薇卡在 $(x, y)$，朋友在 $x_i, y_i$。每次她们都必须移动到相邻的格子。薇卡移动后，朋友看见薇卡去哪了，朋友们才进行新一步的移动。问朋友是否能抓住薇卡。

思路

刚拿到这题我先想到去年做过一场湖北的省赛的题，和这题很像，那题的抓捕者可以逗留，而兔子必须移动，所以抓捕者一定能够抓住兔子。

这里再怀念一下去年的暑假，好怀念那种无忧无虑的日子。

这题并不能逗留，所以直接看曼哈顿距离的奇偶性即可。如果是偶数一定能够抓住，反之则不可以。

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    int X, Y;
    cin >> X >> Y;
    bool ok = true;
    for (int i = 1; i <= k; i++) {
        int x, y;
        cin >> x >> y;
        if ((abs(x - X) + abs(y - Y)) % 2 == 0) {
            ok = false;
        }
    }
    if (ok) {
        cout << "YES\n";
    }
    else {
        cout << "NO\n";
    }
}