题解与反思

D. Permutation Game

刚开始以为是博弈论，我也没学过呀，做鸡毛呀，哈哈哈哈。看了一下大佬的题解，so easy！！！

首先p是一个排列（多轮之后肯定会循环），所以我们只需要确定出min(n, k) 这几步里面的最大值即可。
最优的走法肯定是我们走几步之后停下来，然后一直呆在这。（当时做题也想到了，但是后边的暴力搜索不知道怎么写-__-）
我们假设走i步后停下来了，前i步的积分为presum，那么res = presum + a[i] * (k - i)
其实presum表示的就是我们前i步每个都走了一次，所以每个只需要累加一次即可。，

#include <iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int a[N],p[N];
LL get_value(int n, int k, int beg)
{
    LL res = 0, presum = 0;
    int now = beg;
    for(int i = 1; i <= min(n, k); i ++, now = p[now])
    {
        presum += a[now];
        res = max(res, presum + (LL)a[now] * (k - i));//注意要转化为long long ,不然爆int
    }
    return res;
}
int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        int n, k, pb, ps;
        cin >> n >> k >> pb >> ps;
        for(int i = 1; i <= n; i ++) cin >> p[i];
        for(int i = 1; i <= n; i ++) cin >> a[i];
        LL max_b = get_value(n ,k, pb);
        LL max_s = get_value(n, k, ps);
        if(max_b == max_s) cout << "Draw" << endl;
        else if(max_b < max_s) cout << "Sasha" << endl;
        else cout << "Bodya" << endl;
    }
    return 0;
}

E. Cells Arrangement

感觉这个题像是猜测题，怪不得说codeforces的题考验思维的，确实体会到了。

首先有几个点是要弄明白的，n * n 的格子中组成的曼哈顿距离最多有多少种情况，我们可一思考最大值，就是从左上角到右下角，distance = n - 1 + n - 1 = 2 * (n - 1) = 2n - 2, 所以总的可能情况就是（0, 1 , 2, ..., 2n - 2）
现在我们考虑一下如何用n个格子表示出来这些距离，偷一张大佬的图通过图片可以得知，我们只要选（1，1）和（2，2）在加上对角线上的点即可凑出所有距离
解释一下图上的距离，（1，1）和（2，2）距离为1，然后（1，1）到每个对角线上格子的距离比（1，2）是要大1的，（1，2）--> （3，3） == 3 （1，2）--> （4，4） == 5 （1，2）--> (n, n) == 2n - 3 同理可以得到（1，1）到这些点的距离，总的距离可以涵盖3 ~ 2n-2 ，对角线上的两个格子的距离等于2，综上，总的距离集合可以涵盖（0，2n-2）

#include <iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while(t --)
    {
        int n;
        cin >> n;
        cout << "1 " << "1 " << endl;
        cout << "1 " << "2 " << endl;
        for(int i = 3; i <= n; i ++)
        {
            cout << i << ' ' << i << endl;
        }
    }
    return 0;
}

Codeforces Round 943 (Div. 3)

题解与反思

D. Permutation Game

E. Cells Arrangement