Codeforces Round #522 (Div. 1, based on Technocup 2019 Elimination Round 3) – 解题报告

A – Barcelonian Distance

先把曼哈顿距离做答案,然后枚举这两个点初始的方向,然后取个最小值即可。

// CF1078A.cpp
#include <bits/stdc++.h>

using namespace std;

double a, b, c, x[3], y[3];

double calcByX(double x) { return (-1.0 * a * x - c) / b; }

double calcByY(double y) { return (-1.0 * b * y - c) / a; }

int main()
{
    scanf("%lf%lf%lf%lf%lf%lf%lf", &a, &b, &c, &x[1], &y[1], &x[2], &y[2]);
    double ans = fabs(x[1] - x[2]) + fabs(y[1] - y[2]);
    if (a != 0 && b != 0)
        for (int i = 0; i <= 1; i++)
            for (int j = 0; j <= 1; j++)
            {
                double pos1X, pos1Y, pos2X, pos2Y;
                double pans = 0;
                if (i == 0)
                    pos1X = calcByY(y[1]), pos1Y = y[1], pans += fabs(pos1X - x[1]);
                else
                    pos1X = x[1], pos1Y = calcByX(x[1]), pans += fabs(pos1Y - y[1]);

                if (j == 0)
                    pos2X = calcByY(y[2]), pos2Y = y[2], pans += fabs(pos2X - x[2]);
                else
                    pos2X = x[2], pos2Y = calcByX(x[2]), pans += fabs(pos2Y - y[2]);

                pans += sqrt((pos1X - pos2X) * (pos1X - pos2X) + (pos1Y - pos2Y) * (pos1Y - pos2Y));
                ans = min(ans, pans);
            }
    printf("%.10lf\n", ans);
    return 0;
}

B – The Unbearable Lightness of Weights

这道题要求计算最多能辨别多少个。可以发现:

  • 如果只有一种或者两种质量,那么答案就是 \(n\)。
  • 如果有更多种类的质量,那么最后答案肯定是单一质量的背包,因为我们需要确定到底是哪个种类。所以,如果这样单一质量 \(w\) 的有 \(k\) 个,且最终选法是 \(cnt_w \choose k\),那么 \(k\) 可以被作为答案。

然后做个背包就完事了。

// CF1078B.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 110, mod = 1e9 + 7;

int n, ai[MAX_N], cnt[MAX_N], binomial[MAX_N][MAX_N], ans = 1, upper, typ;
map<pair<int, int>, int> dp, pre;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]), upper = max(upper, ai[i]), typ += ((++cnt[ai[i]]) == 1);
    for (int i = 0; i <= n; i++)
    {
        binomial[i][0] = binomial[i][i] = 1;
        for (int j = 1; j < i; j++)
            binomial[i][j] = (0LL + binomial[i - 1][j - 1] + binomial[i - 1][j]) % mod;
    }
    dp[make_pair(0, 0)] = 1, pre = dp;
    for (int i = 1; i <= n; i++)
    {
        for (auto &x : pre)
        {
            pair<int, int> curt = make_pair(x.first.first + 1, x.first.second + ai[i]);
            dp[curt] = (0LL + dp[curt] + x.second) % mod;
        }
        pre = dp;
    }
    if (typ == 1 || typ == 2)
        printf("%d\n", n);
    else
    {
        for (int w = 1; w <= upper; w++)
            for (int i = 2; i <= cnt[w]; i++)
            {
                int val = dp[make_pair(i, i * w)];
                if (dp[make_pair(i, i * w)] == binomial[cnt[w]][i])
                    ans = max(ans, i);
            }
        printf("%d\n", ans);
    }
    return 0;
}

C – Vasya and Maximum Matching

考虑如何去构造一个有独特的完美匹配的图:我们可以把一些点作为孤点且孤点所在的连块只有自己,使得剩下的连通块都拥有完美匹配。一开始我们可以全部删去,然后我们再来考虑构造合法的连边方案:如果一个连通块拥有独特的完美匹配,那么我们在这个连通块上加长两条边的链,也能构成合法的连通块。根据这个性质进行 DP 即可。

// CF1078C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3e5 + 200, mod = 998244353;

int n, head[MAX_N], current, dp[MAX_N][3], tmp[3];

struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

void dfs(int u, int fa)
{
    dp[u][0] = 1;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
        {
            dfs(edges[i].to, u);
            tmp[0] = 1LL * dp[u][0] * ((0LL + dp[edges[i].to][0] + dp[edges[i].to][2]) % mod) % mod;
            tmp[1] = (1LL * dp[u][0] * dp[edges[i].to][2] % mod + 1LL * dp[u][1] * ((dp[edges[i].to][0] + 2LL * dp[edges[i].to][2] % mod) % mod) % mod) % mod;
            tmp[2] = (1LL * dp[u][0] * (dp[edges[i].to][0] + dp[edges[i].to][1]) % mod + 1LL * dp[u][1] * (dp[edges[i].to][0] + dp[edges[i].to][1]) % mod + 1LL * dp[u][2] * ((dp[edges[i].to][0] + 2LL * dp[edges[i].to][2] % mod) % mod) % mod) % mod;
            swap(tmp, dp[u]);
        }
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 1, u, v; i <= n - 1; i++)
        scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
    dfs(1, 0);
    printf("%d\n", (dp[1][0] + dp[1][2]) % mod);
    return 0;
}

D – Chattering

刚想这题的时候想过一种很暴力的转移,最后发现有环所以就 GG 了。

我们可以考虑用双倍增(?)来搞定这个。我们可以把这个棋盘(?)左右各复制一份,然后在先用 ST 表处理出左右横跳的信息。处理好之后,在这个基础上再跳一次,然后回答询问的时候就在二进制位上从大到小处理即可。

// CF1078D.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3e5 + 200;

int n, ai[MAX_N], lft[20][MAX_N], rig[20][MAX_N], log2_[MAX_N];

struct ST
{
    int table[20][MAX_N], val[MAX_N], typ;

    int gmax(int x, int y) { return val[x] > val[y] ? x : y; }

    void build(int *arr, int len, int type)
    {
        typ = type;
        for (int i = 1; i <= len; i++)
            table[0][i] = i, val[i] = typ * arr[i];
        for (int i = 1; i <= 19; i++)
            for (int j = 1; j + (1 << i) - 1 <= len; j++)
                table[i][j] = gmax(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
    }

    int query(int l, int r)
    {
        int d = log2_[r - l + 1];
        return gmax(table[d][l], table[d][r - (1 << d) + 1]);
    }
} lrmq, rrmq;

int main()
{
    scanf("%d", &n);
    for (int i = 2; i <= 3 * n; i++)
        log2_[i] = log2_[i >> 1] + 1;
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]), ai[i + n] = ai[i + (n << 1)] = ai[i];
    if (n == 1)
        return puts("0"), 0;
    for (int i = 1; i <= 3 * n; i++)
        lft[0][i] = max(1, i - ai[i]), rig[0][i] = min(3 * n, i + ai[i]);
    for (int i = 0; i <= log2_[3 * n]; i++)
        lft[i][1] = 1, rig[i][3 * n] = 3 * n;
    lrmq.build(lft[0], 3 * n, -1), rrmq.build(rig[0], 3 * n, 1);
    for (int i = 1; i <= log2_[3 * n]; i++)
        for (int j = 1; j <= 3 * n; j++)
        {
            int posl = lrmq.query(lft[i - 1][j], rig[i - 1][j]);
            int posr = rrmq.query(lft[i - 1][j], rig[i - 1][j]);
            lft[i][j] = min(lft[i - 1][posl], lft[i - 1][posr]);
            rig[i][j] = max(rig[i - 1][posl], rig[i - 1][posr]);
        }
    for (int j = n + 1; j <= (n << 1); j++)
    {
        int wl = j, wr = j, ans = 0;
        for (int i = log2_[3 * n]; i >= 0; i--)
        {
            if (max(rig[i][wl], rig[i][wr]) - min(lft[i][wl], lft[i][wr]) + 1 >= n)
                continue;
            int wwl = lrmq.query(lft[i][wl], rig[i][wr]);
            int wwr = rrmq.query(lft[i][wl], rig[i][wr]);
            ans += (1 << i), wl = wwl, wr = wwr;
        }
        ans++;
        printf("%d ", ans);
    }
    puts("");
    return 0;
}

 


发表评论

邮箱地址不会被公开。 必填项已用*标注