AtCoder Grand Contest 043 – 解题报告

A – Range Flip Find Route

思博题。考虑最后的路径肯定是多个黑白子路径的拼接,那么路径的代价就是进入黑色子路径的次数,那么我们只需要建图的时候给白色入黑色的边赋 \(1\) 的权即可。

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

using namespace std;

const int MAX_N = 110, dx[2] = {0, 1}, dy[2] = {1, 0};

typedef pair<int, int> pii;

int n, m, idx[MAX_N][MAX_N], head[MAX_N * MAX_N], current, dist[MAX_N * MAX_N], start_pos;
char str[MAX_N][MAX_N];
bool vis[MAX_N * MAX_N];

struct edge
{
    int to, nxt, weight;
} edges[MAX_N * MAX_N << 3];

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

void shortestPath()
{
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<pii> pq;
    pq.push(make_pair(0, start_pos)), dist[start_pos] = 0;
    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (dist[edges[i].to] > dist[u] + edges[i].weight)
                dist[edges[i].to] = dist[u] + edges[i].weight, pq.push(make_pair(-dist[edges[i].to], edges[i].to));
    }
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%s", str[i] + 1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            idx[i][j] = m * (i - 1) + j;
    start_pos = n * m + 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int d = 0; d < 2; d++)
            {
                int dstx = i + dx[d], dsty = j + dy[d];
                if (str[dstx][dsty] != 0)
                    if (str[i][j] == '.')
                        if (str[dstx][dsty] != str[i][j])
                            addpath(idx[i][j], idx[dstx][dsty], 1);
                        else
                            addpath(idx[i][j], idx[dstx][dsty], 0);
                    else
                        addpath(idx[i][j], idx[dstx][dsty], 0);
            }
    addpath(start_pos, idx[1][1], str[1][1] == '#');
    shortestPath(), printf("%d\n", dist[idx[n][m]]);
    return 0;
}

B – 123 Triangle

算贡献 + 找规律的题。

首先我们可以把输入的 \(1, 2, 3\) 转换成 \(0, 1, 2\)(做差结果不会变)。然后我们先来考虑判断答案的奇偶性,这个子问题的本质其实是若干个 \(0, 1\) 进行异或。这个三角形其实就是 Pascal 三角形,所以贡献就是 \({n – 1 \choose i}\)。所以,可以考虑用 Lucas 算这个组合数的奇偶性,然后放答案里。

如果最后判断出来是奇数,那么显然就是 \(1\);如果不是奇数,有性质:如果 \(1\) 出现在原序列中,则答案是 \(0\),否则为 \(2\)。如果原序列中只有 \(0, 2\),那么这个题完全可以看成 \(0, 1\) 的子问题,然后给答案乘回来一个 \(2\)。

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

using namespace std;

const int MAX_N = 1e6 + 200;

int n, ai[MAX_N], fac[MAX_N];
char str[MAX_N];

int binomial(int n_, int k_) { return fac[n_] - fac[k_] - fac[n_ - k_]; }

int main()
{
    scanf("%d%s", &n, str + 1);
    bool flag = false;
    for (int i = 1; i <= n; i++)
        ai[i] = str[i] - '1', flag |= (ai[i] == 1);
    for (int i = 1; i <= n; i++)
    {
        int acc = i;
        while (!(acc & 1))
            fac[i]++, acc >>= 1;
        fac[i] += fac[i - 1];
    }
    if (!flag)
        for (int i = 1; i <= n; i++)
            ai[i] >>= 1;
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if ((ai[i] & 1) && (!binomial(n - 1, i - 1)))
            ans ^= 1;
    if (!flag)
        ans <<= 1;
    printf("%d\n", ans);
    return 0;
}

C – Giant Graph

这个题是真你妈的屌。

首先肯定知道一点,因为这个指数设置的贼大,所以我们要用位运算贪心的思想,让 \(i + j + k\) 从大到小进行确定,这个图就可以连成一个 DAG 了。我们现在需要找一个独立集出来。

然后这个题开始变骚了,这是个博弈图,最优解的状态点本身就是最大独立集。我们可以考虑算出来这些 SG 函数值,然后算图里的 \(SG(x) \oplus SG(y) \oplus SG(z) = 0\) 的价值。发现 \(SG(x) \leq \sqrt{m}\),可以考虑直接暴力去算。

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

using namespace std;

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

typedef long long ll;

int n, m[3], base, vis[MAX_N], sg[MAX_N];
vector<int> G[MAX_N], sum[3];

int fpow(int bas, int tim)
{
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % mod;
        bas = 1LL * bas * bas % mod;
        tim >>= 1;
    }
    return ret;
}

int main()
{
    scanf("%d", &n), base = fpow(ll(1e18) % mod, mod - 2);
    for (int rd = 0; rd < 3; rd++)
    {
        scanf("%d", &m[rd]);
        for (int i = 1; i <= n; i++)
            G[i].clear();
        for (int i = 1, u, v; i <= m[rd]; i++)
        {
            scanf("%d%d", &u, &v);
            if (u > v)
                swap(u, v);
            G[u].push_back(v);
        }
        memset(sg, 0, sizeof(sg)), memset(vis, -1, sizeof(vis));
        int cbase = fpow(10, 18 * n);
        for (int i = n; i >= 1; i--)
        {
            for (int v : G[i])
                vis[sg[v]] = i;
            while (vis[sg[i]] == i)
                sg[i]++;
            while (sum[rd].size() <= sg[i])
                sum[rd].push_back(0);
            sum[rd][sg[i]] = (0LL + sum[rd][sg[i]] + cbase) % mod, cbase = 1LL * cbase * base % mod;
        }
    }
    int ans = 0;
    for (int i = 0, siz1 = sum[0].size(); i < siz1; i++)
        for (int j = 0, siz2 = sum[1].size(); j < siz2; j++)
        {
            int k = i ^ j;
            if (k < sum[2].size())
                ans = (0LL + ans + 1LL * sum[0][i] * sum[1][j] % mod * sum[2][k] % mod) % mod;
        }
    printf("%d\n", ans);
    return 0;
}

D – Merge Triplets

考虑生成后的序列的性质。原序列 \(A_i = (X_1, X_2, X_3)\),如果满足 \(X_i > X_{i + 1}\),那么这两个元素在 \(P\) 序列中铁定连续;当然,如果满足 \(X_1 > X_2, X_1 > X_3 \),那么也是铁定连续的。那么一个这样的 \(X_i\) 可以作为块起点,把三元组进行细分。那么这些小块其实就是目标序列的一个个子串。

所以如果一个目标排列 \(P\) 要能被计数,当且仅当存在一种分块方式,使得若干个块拼成若干个单元,且每个单元的元素个数为 \(3\)。

如果分块方式确定了,是不是元素就被固定了?显然是这样的。首先块内的大小已经被确定,且每次放置一个块,则这个块的第一个数肯定大于之前的所有块的第一个数。又因为第一个数是块的最大数,那么至少块间的大小关系已经被确认;且,块内的数字也是递减的,所以块内的关系也确定了。这个肯定是个唯一的排列。

所以只需要算分块方案即可。怎样的分块方案合法?要么分 \(3, 2, 1\) 块,但是注意长度为 \(2\) 块数量一定要少于长度为 \(1\) 的块数,这样有完美匹配。设置 \(dp[i][j]\),\(i\) 为最后位置,\(j\) 为长度为 \(1\) 的块的块数减去长度为 \(2\) 的块的块数,设置方式有点像 CSP-S 2019 D2T1。最后取 \(\geq 0\) 的即可。

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

using namespace std;

const int MAX_N = 2020, base = MAX_N;

int n, mod, dp[MAX_N * 3][MAX_N * 4];

int main()
{
    scanf("%d%d", &n, &mod), dp[0][base] = 1;
    for (int i = 0; i < 3 * n; i++)
        for (int j = -n; j <= 3 * n; j++)
        {
            dp[i + 1][j + 1 + base] = (0LL + dp[i + 1][j + 1 + base] + dp[i][j + base]) % mod;
            dp[i + 2][j - 1 + base] = (0LL + dp[i + 2][j - 1 + base] + 1LL * dp[i][j + base] * (i + 1) % mod) % mod;
            dp[i + 3][j + base] = (0LL + dp[i + 3][j + base] + 1LL * dp[i][j + base] * (i + 2) % mod * (i + 1) % mod) % mod;
        }
    int ans = 0;
    for (int i = 0; i <= 3 * n; i++)
        ans = (0LL + ans + dp[3 * n][i + base]) % mod;
    printf("%d\n", ans);
    return 0;
}

发表评论

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