Codeforces Round 858 (Div. 2)（A~E）

A. Walking Master

在坐标系中，每次只能向右上和左行走，给出起点和终点，问最少的步数是多少。

思路：显然因为走的方向被固定，所以只能走到从左向右135°的位置。判断一下，直接计算即可。

AC Code：

#include <bits/stdc++.h>
 
typedef long long ll;
#define int long long
const int N = 2e5 + 5;
int t, a, b, c, d;
 
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin >> t;
    while(t --) {
        std::cin >> a >> b >> c >> d;
        if(b > d) {
            std::cout << -1 << '\n';
            continue;
        }
        if(c > a && d >= b && c - a > d - b) {
            std::cout << -1 << '\n';
            continue;
        }
        int ans = d - b;
        a += ans, b += ans;
        ans += (a - c);
        std::cout << ans << '\n';
    }
    return 0;
}

B. Mex Master

给出一个数组a，我们可以随意排列这个数组，得到的数组相邻两项相加得到的数组中，求最小的MEX值。

思路：显然，如果0的个数不大于n的一半，那隔一个0放一个非零数字，得到的答案是0；如果0很多，在最后得到的数组中无法避免0的相邻，则判断1的个数，若没有1或者除了1还有别的数字存在，那答案是1，因为我们可以把0全放在前面，然后放上非1的数字，使得两个数的和大于1；其他情况，答案是2。

AC Code：

#include <bits/stdc++.h>
 
typedef long long ll;
const int N = 2e5 + 5;
int t, n;
int a[N];
 
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin >> t;
    while(t --) {
        std::cin >> n;
        int cnt0 = 0, cnt1 = 0;
        for(int i = 1; i <= n; i ++) {
            std::cin >> a[i];
            if(!a[i])
                cnt0 ++;
            else if(a[i] == 1)
                cnt1 ++;
        }
        if(cnt0 <= (n + 1) / 2) {
            std::cout << 0 << '\n';
            continue;
        }
        if(cnt0 == n || cnt0 + cnt1 != n) {
            std::cout << 1 << '\n';
            continue;
        }
        std::cout << 2 << '\n';
    }
    return 0;
}

C. Sequence Master

给出一个长度为2*m的数组p，现在要求构造一个同样长度的数组q，使得q满足存在一个大小为m的子序列，使得子序列内的数的乘积等于不在这里面的数的和。定义两个数组的距离是相同位置两个数的差的绝对值的和，最小化p和q的距离，求这个距离。

思路：显然，当m==1时，两个相同的数可以满足条件；m>1时，通用的解是2*m个0。其他的情况，看大佬的思路和证明。

AC Code：

#include <bits/stdc++.h>
 
typedef long long ll;
const int N = 2e5 + 5;
int t, n;
ll a[N << 1];
 
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin >> t;
    while(t --) {
        std::cin >> n;
        for(int i = 1; i <= 2 * n; i ++) {
            std::cin >> a[i];
        }
        std::sort(a + 1, a + 1 + 2 * n);
        ll ans = 0;
        for(int i = 1; i <= 2 * n; i ++) {
            ans +=abs(a[i]);
        }
        if(n == 1) {
            ans = std::min(ans, abs(a[1] - a[2]));
        }
        else if(n == 2) {
            ll res = 0;
            for(int i = 1; i <= 2 * n; i ++) {
                res += abs(a[i] - 2);
            }
            ans = std::min(ans, res);
        }
        if(n % 2 == 0) {
            ll res = 0;
            for(int i = 1; i < 2 * n; i ++) {
                res += abs(a[i] + 1);
            }
            res += abs(a[2 * n] - n);
            ans = std::min(ans, res);
        }
        std::cout << ans << '\n';
    }
    return 0;
}

os：要命，读题都读不明白

D. DSU Master

给出一个长度为n-1的01序列，一开始n个点每个点都是独立的，根据一个长度为n - 1的permutation来进行连边，这个permutation的价值是连边后顶点的入度数，对于1~n-1，每个permutation都是阶乘数个，求每一个的贡献之和。

连边方式：对于permutation的每个数p[i]和p[i] + 1进行连边，a[p[i]]为1则从p[i]向p[i] + 1连边，否则反向连边，每次连完之后保证每个连通分量只有一个出度为0的顶点，而下一次向这个连通分量的连边也是与这个顶点进行的。

思路：Codeforces Round 858 (Div. 2) A - E - 知乎 (zhihu.com)

AC Code：

#include <bits/stdc++.h>
 
typedef long long ll;
const int N = 5e5 + 5;
int t, n;
int a[N];
 
template<const int T>
struct ModInt {
    const static int mod = T;
    int x;
    ModInt(int x = 0) : x(x % mod) {}
    ModInt(ll x) : x(int(x % mod)) {} 
    int val() { return x; }
    ModInt operator + (const ModInt &a) const { int x0 = x + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }
    ModInt operator - (const ModInt &a) const { int x0 = x - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }
    ModInt operator * (const ModInt &a) const { return ModInt(1LL * x * a.x % mod); }
    ModInt operator / (const ModInt &a) const { return *this * a.inv(); }
    void operator += (const ModInt &a) { x += a.x; if (x >= mod) x -= mod; }
    void operator -= (const ModInt &a) { x -= a.x; if (x < 0) x += mod; }
    void operator *= (const ModInt &a) { x = 1LL * x * a.x % mod; }
    void operator /= (const ModInt &a) { *this = *this / a; }
    friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x;}
    
    ModInt pow(int64_t n) const {
        ModInt res(1), mul(x);
        while(n){
            if (n & 1) res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }
    
    ModInt inv() const {
        int a = x, b = mod, u = 1, v = 0;
        while (b) {
            int t = a / b;
            a -= t * b; std::swap(a, b);
            u -= t * v; std::swap(u, v);
        }
        if (u < 0) u += mod;
        return u;
    }
    
};
typedef ModInt<998244353> mint;
 
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin >> t;
    while(t --) {
        std::cin >> n;
        for(int i = 1; i < n; i ++) {
            std::cin >> a[i];
        }
        mint f = 1, ans = 0;
        for(int i = 1; i < n; i ++) {
            ans = ans * i + f * (a[i] == 0);
            std::cout << ans << " \n"[i == n - 1];
            f *= (i - a[i]);
        }
    }
    return 0;
}

os：感觉官方题解虽然是英文的，但每次的题解还都是很详细的

E. Tree Master

给出一棵以1为根的树，和每个节点的权值，每次询问两个深度相同的节点，求题目中所给的值。

思路：官方题解：

每次询问暴力向上求解，但是注意会在一路询问的求解过程中记录答案，也就是cnt数组和h数组的作用，直接用数组模拟，官方题解给出了证明。

简单来说我们需要证明的是为什么可以采用记忆化搜索的方式解决这个问题，这样我们需要计算所有的询问可以得到的(x, y)有多少种。我们可以设第i层有a[i]个节点，显然，（我们在此考虑的是对于深度最大的一层的状态数），因为第i层有a[i]个节点，所以可以提供的(x, y)组有a[i] * a[i]种，而对于查询的上限，一共有q次查询，因为q与n数量级相同，完全可以用n代替q。所以每多一层，提供的状态数就是min(a[i] * a[i], n)，那么a[i]最大就是，而对于a[i] = ，可以计算得到共有层，那么总状态就是种，这样的类似记忆化搜索的复杂度即可被证明可以通过。

代码中的320实际上是1e5开方得到的近似值，并不是说每一层有320个节点，是对于询问次数q来说，每一层最多有320个点能提供二元组来询问。

AC Code：

#include <bits/stdc++.h>
 
typedef long long ll;
const int N = 1e5 + 5;
int n, q;
ll a[N], dep[N], f[N][325];;
ll p[N], h[N], cnt[N];
std::vector<int> vec[N];
 
void getdeep(int u) {
    h[u] = ++ cnt[dep[u]];
    for(auto v : vec[u]) {
        dep[v] = dep[u] + 1;
        getdeep(v);
    }
}
 
ll getans(int x, int y) {
    if(!x && !y) return 0;
    if(cnt[dep[y]] <= 320 && f[x][h[y]])
        return f[x][h[y]];
    ll ans = getans(p[x], p[y]) + a[x] * a[y];
    if(cnt[dep[y]] <= 320)
        f[x][h[y]] = ans;
    return ans;
}
 
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin >> n >> q;
    for(int i = 1; i <= n; i ++) {
        std::cin >> a[i];
    }
    for(int i = 2; i <= n; i ++) {
        std::cin >> p[i];
        vec[p[i]].push_back(i);
    }
    getdeep(1);
    while(q --) {
        int x, y;
        std::cin >> x >> y;
        std::cout << getans(x, y) << '\n';
    }
    return 0;
}