Educational Codeforces Round 136 (Rated for Div. 2)

A.Immobile Knight

题目大意

一个$n\times m$的棋盘，输出一个位置使得马(中国象棋里的马的移动方式)不能移动，如果没有这样的位置那就随便输出一个位置

解题思路

总共就几种情况，随便画画就出来了
棋盘还最多只有$8\times 8$这么大，暴力枚举也可以

具体代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
typedef long long LL;
typedef std::pair<int, int> PII;
const LL N = 2e5 + 10;
const LL M = 50;
const LL INF = 0x7f7f7f7f7f7f7f7f;
const LL MOD = 1e9 + 7;
LL n, m, q;
LL a[N];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    std::cin >> T;
    while (T--)
    {
        std::cin >> n >> m;
        if (n == 3 && m == 3)
            std::cout << "2 2\n";
        else if (n == 2 && m == 3)
            std::cout << "1 2\n";
        else if (n == 3 && m == 2)
            std::cout << "2 1\n";
        else
            std::cout << "1 1\n";
    }
    return 0;
}

B.Array Recovery

题目大意

对于一个非负的长度为$n$的整数数组$a$,我们可以构造出一个$d$数组，令$d_1=a_1,d_i=|a_i-a_{i-1}|,2\leq ileq n$
你的任务是根据一个给定的$d$数组，还原出$a$数组，如果有多个可能的$a$数组，输出$-1$

解题思路

可以发现如果没有那个绝对值那么$d$数组就是$a$数组的差分数组，也就对应了唯一的$a$
所以只要保证没有$d_i=a_{i-1}-a_i$这种情况就行了
即保证没有$a_i=a_{i-1}-d_i$
因为$a_i\geq 0$，所以没有$a_{i-1}-d_i\geq 0$

具体代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
typedef long long LL;
typedef std::pair<int, int> PII;
const LL N = 2e5 + 10;
const LL M = 50;
const LL INF = 0x7f7f7f7f7f7f7f7f;
const LL MOD = 1e9 + 7;
LL n, m, q;
LL a[N], d[N], b[N];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    std::cin >> T;
    while (T--)
    {
        std::cin >> n;
        for (int i = 1; i <= n; ++i)
        {
            std::cin >> d[i];
            a[i] = a[i - 1] + d[i];
        }
        bool flag = false;
        for (int i = 1; i <= n; ++i)
            if (a[i - 1] - d[i] >= 0 && a[i - 1] - d[i] != a[i])
            {
                flag = true;
                break;
            }
        if (flag)
            std::cout << "-1" << '\n';
        else
        {
            for (int i = 1; i <= n; ++i)
                std::cout << a[i] << ' ';
            std::cout << '\n';
        }
    }
    return 0;
}

C.Card Game

题目大意

给定$n$张卡牌(保证$n$为偶数)，卡牌上的数为$1\sim n$，两两不同。两个人玩卡牌游戏，一个人先打一张牌，然后后手必须打出比他更大的牌，否则他就输了。如果两个人都没有牌了，那么平手。两人轮流交换先打的顺序，求$n$张牌的情况下先手必胜和后手必胜和平手的方案数

解题思路

其实可以直接打表(
平局数显然是$1$，三者总数是$C(n,n/2)$，那么只求先手必胜就行了
求先手必胜，可以找规律
大概就是输入$n$时，先手必胜的数量是$C(n-1,n/2-1)+$(上一行$(n-2)$的后手必胜的数量)
为什么是这样的我也还不清楚(一直到比赛快结束才硬盯盯出来的)，可以等一手官方题解的证明

具体代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
typedef long long LL;
typedef std::pair<int, int> PII;
const LL N = 2e5 + 10;
const LL M = 65;
const LL INF = 0x7f7f7f7f7f7f7f7f;
const LL MOD = 998244353;
LL n, m, q;
LL c[M][M];
LL ans[N];
void init()
{
    // 预处理组合数的模板
    c[1][1] = c[1][0] = 1;
    for (int i = 2; i < M; ++i)
    {
        for (int j = 0; j <= i; ++j)
        {
            if (!j)
                c[i][j] = 1;
            else
                c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
        }
    }
    ans[2] = 1;
    for (int i = 4; i <= 62; i += 2)
    {
        ans[i] = c[i - 1][i / 2 - 1] % MOD;
        ans[i] += c[i - 2][(i - 2) / 2] - ans[i - 2] - 1;
        ans[i] = (ans[i] + MOD) % MOD;
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    std::cin >> T;
    init();
    while (T--)
    {
        std::cin >> n;
        std::cout << ans[n] % MOD << " " << (c[n][n / 2] - ans[n] - 1 + MOD) % MOD << " "
                  << 1 << '\n';
    }
    return 0;
}

D.Reset K Edges

题目大意

给定一棵有根树，有$n$个节点，节点编号$1\sim n$，根节点是$1$号节点
你可以作如下操作至多$k$次：
$1.$选择一条边$(v,u)$，其中$v$是$u$的父亲节点
$2.$移除掉$(v,u)$这条边
$3.$加上一条边$(1,u)$
问最后这棵树的深度最小是多少(根节点的深度视作$0$)

解题思路

容易看出是二分答案+贪心$check$的套路题
大概思路看代码就能看懂
说实话比$C$简单
要注意的是$vector$的清空方法
没想到直接$swap$二维$vector$会超时，莫名其妙罚时又上天了

具体代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
typedef long long LL;
typedef std::pair<int, int> PII;
const LL N = 2e5 + 10;
const LL M = 50;
const LL INF = 0x7f7f7f7f7f7f7f7f;
const LL MOD = 1e9 + 7;
LL n, m, q, k;
std::vector<int> son[N];
LL a[N];
LL w[N];
LL maxw, opt;
void dfs(int u, int fa)
{
    w[u] = 0;
    for (auto v : son[u])
    {
        if (v != fa)
        {
            dfs(v, u);
            if (u > 1 && w[v] + 1 == maxw)
                ++opt;
            else
                w[u] = std::max(w[u], w[v] + 1);
        }
    }
}
bool check(int x)
{
    opt = 0;
    maxw = x;
    dfs(1, 0);
    return opt <= k;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    std::cin >> T;
    while (T--)
    {
        std::cin >> n >> k;
        for (int i = 2; i <= n; ++i)
        {
            int x;
            std::cin >> x;
            son[x].push_back(i);
        }
        int l = 1, r = n;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (check(mid))
                r = mid;
            else
                l = mid + 1;
        }
        std::cout << l << '\n';
        for (int i = 1; i <= n; i++)
            std::vector<int>().swap(son[i]);
    }
    return 0;
}