【cf】Codeforces Round 885（ Div.2）题解 A - D

A. Vika and Her Friends

题目链接

题意

给出矩形长宽，给出Vika所在地坐标，给出她的 k 个朋友所在地坐标，每一步他们可以到达与他们坐标相邻的地方，每轮 Vika 先走一步，她的每个朋友再走一步，如果有一轮结束后，她的任意一个朋友和她的位置重合，输出“NO”，否则输出“YES”

思路

通过找规律可以发现，当 Vika 和另一个人的横竖坐标之差加起来是奇数，就不可能重合，偶数就一定有办法重合
但这里应该只判断偶数，只要 Vika 与他的任意一个朋友横竖坐标之差加起来是偶数，就一定会重合

代码

#include <bits/stdc++.h>

using namespace std;

void solve()
{
	int H, V; cin >> H >> V;
    int k; cin >> k;
    int x, y; cin >> x >> y;
    bool flag = true;
    for (int i = 0; i < k; i ++ )
    {
        int a, b; cin >> a >> b;
        int dist = abs(a - x) + abs(b - y);
        if (dist % 2 == 0) flag = false;
    }
    if (!flag) cout << "NO" << endl;
    else cout << "YES" << endl;
}

int main()
{
    int t; cin >> t;
    while (t -- )
    {
        solve();
    }
}

B. Vika and the Bridge

题目链接

题意

有一条路的不同位置被涂上不同颜色，Vika 只能走同一种颜色（遇到不同颜色就跳过去），但是她可以改变路的任意一个位置的颜色（也可以不改变），问她怎么走能让跳跃的距离最短，输出最短的跳跃距离

思路

首先记录所有颜色所在位置之间的差值，对这个数组排序
很容易理解，当我们选择这一种颜色时，会将改变距离最大的一段中点的颜色（如果这不是一段连续的颜色相同的路径的话），此时跳跃的最大距离即为距离最大的一段除以2和距离第二大的一段中更大的一个
所以我们选择每一种颜色需要跳跃的最大距离中最小的一个，输出即可

代码

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int n, k; cin >> n >> k;
    vector<vector<int>> location(k + 1); // 每个颜色所在位置
    vector<vector<int>> dist(k + 1); // 每个颜色相隔距离
    for (int i = 1; i <= k; i ++ ) location[i].push_back(0);
    for (int i = 1; i <= n; i ++ )
    {
        int x; cin >> x;
        location[x].push_back(i);
        dist[x].push_back(i - 1 - location[x][location[x].size() - 2]);
    }
    for (int i = 1; i <= k; i ++ )
    	dist[i].push_back(n - location[i][location[i].size() - 1]);
    for (int i = 1; i <= k; i ++ )
    	sort(dist[i].begin(), dist[i].end(), greater<int>());
    int minn = 0x3f3f3f;
    int color = 0;
    vector<int> res(k + 1);
    for (int i = 1; i <= k; i ++ )
    	res[i] = max(dist[i][0] / 2, dist[i][1]);
    for (int i = 1; i <= k; i ++ )
    	minn = min(minn, res[i]);
    cout << minn << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t; cin >> t;
    while (t -- )
    {
        solve();
    }
}

C. Vika and Price Tags

题目链接

题意

给出两个相同长度的数组 a 和 b，建立数组 c
每一轮操作将 a 和 b 每一项的差值赋给 c，再将 b 赋给 a，c 赋给 b
问多轮操作后能不能使 a 全部变为 0

思路

直接循环肯定T，所以需要找到变化中的规律
单独看每一项，观察得到三轮一循环的规律：
我们将 a 数组的数记为 x，b 数组的数记为 y

• 当 x >= 2 * y ，经过三轮后，x = x - 2 * y
• 当 y >= 2 * x ，经过三轮后，y = y - 2 * x

当然，如果 x 一直大于 2 y，那就会一直减下去，所以最后得到的其实是 `x % (2 y)`，第二种情况也一样
进行上述两项操作直到不满足上面的任何一条时，我们再进行简单的求 x y 差值的步骤

由于三轮一循环，我们记录回合数时只用 0 - 2 记录，每进行一次求x y 差值的步骤时，就将回合数 + 1（其实是+1%3）

根据上面的思路，我们可以得到 a b 数组的每一位变为 0 时需要的回合数，当不同位上所需回合数不同时，就一定不能将 a 全变为 0

代码

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

void solve()
{
    int n; cin >> n;
    vector<int> a(n);
    vector<int> b(n);

    for (int i = 0; i < n; i ++ ) cin >> a[i];
    for (int i = 0; i < n; i ++ ) cin >> b[i];

    int x, y;
    int t = -1;
    for (int i = 0; i < n; i ++ )
    {
        if (a[i] == 0 && b[i] == 0) continue;
        
        PII pt = {a[i], b[i]};
        tie(x, y) = pt;

        int round = 0;
        while (x != 0)
        {
            if (x >= 2 * y && y != 0) x %= 2 * y;
            if (y >= 2 * x && x != 0) y %= 2 * x;
            tie(x, y) = make_tuple(y, abs(x - y));
            round = (round + 1) % 3;
        }
        if (t != -1 && round != t)
        {
            cout << "NO" << endl;
            return;
        }
        t = round;
    }
    cout << "YES" << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t; cin >> t;
    while (t -- )
    {
        solve();
    }
}

D. Vika and Bonuses

题目链接

题意

给定一个 s 和一个 k，每次可以进行如下两个操作中的一个：

• 将 s 加上 s 最末尾的一个数字
• 将答案加上 s

问在 k 次操作后答案的最大值是多少

思路

首先明确一点，如果要进行操作1，那所有的操作1必须要在操作2之前进行
然后，我们可以找到规律，如果一直进行操作1，最后一定会陷入循环0、0…或者2、4、8、6、…

先处理陷入循环0、0、…的情况，如果末尾数字是5，直接先进行一轮操作1，让末尾变为0，之后全部进行操作2
然后处理陷入循环2、4、8、6、…的情况，记2 4 8 6为一次循环，设经过 x 次循环答案最大（每次循环可以让 s 增加 20），输出的答案则为ans = (s + 20 * x) * (k - 4 * x)，整理后得到ans = -80 * x^2 + (20 * k - 4 * s) * x + s * k，转换成了求一元二次函数最大值的问题，直接求解即可

代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

i64 cle(i64 n, i64 k)
{
    i64 ans = n * k;

    i64 a, b, c; // 系数
	a = -80;
	b = 20 * k - 4 * n;
	c = n * k;

	i64 x = -b / (2 * a);
	x = min(x, k / 4); // x不能大于 k / 4;

	if (x > 0)
	    ans = max(ans, a * x * x + b * x + c);
    // 因为x取了整数，所以x + 1和x - 1都检查一下
	x = min(x + 1, k / 4);
	if (x > 0)
	    ans = max(ans, a * x * x + b * x + c);
    x -= 2;
    if (x > 0)
        ans = max(ans, a * x * x + b * x + c);
	return ans;
}

void solve()
{
    i64 n, k;
    cin >> n >> k;

    i64 ans = n * k;

    if (n % 10 == 5)
    {
        n += 5;
        ans = max(ans, n * (k - 1));
    }
    else if (n % 10 > 0)
    {
        if (n % 2 != 0)
        {
            n += n % 10;
            k -- ;
        }
        for (int i = 0; i < 4; i ++ )
        {
            ans = max(ans, cle(n, k));
            k -- ;
            n += n % 10;
        }
    }
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t;
    cin >> t;
    while (t -- )
    {
        solve();
    }
}