AtCoder Grand Contest 046 – 解题报告

A – Takahashikun, The Strider

SB 题，不解释。

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

using namespace std;

int x;

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

int main()
{
    scanf("%d", &x), printf("%d\n", 360 / gcd(x, 360));
    return 0;
}

B – Extension

不难，直接容斥即可。

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

using namespace std;

const int MAX_N = 3030, mod = 998244353;

int n, m, a, b, dp[MAX_N][MAX_N];

int main()
{
    scanf("%d%d%d%d", &a, &b, &n, &m);
    dp[a][b] = 1;
    for (int i = a; i <= n; i++)
        for (int j = b; j <= m; j++)
            if (i != a || j != b)
                dp[i][j] = (0LL + 1LL * dp[i - 1][j] * j % mod + 1LL * dp[i][j - 1] * i % mod + mod - 1LL * dp[i - 1][j - 1] * (i - 1) % mod * (j - 1) % mod) % mod;
    printf("%d\n", dp[n][m]);
    return 0;
}

C – Shift

考虑把 0 看作分隔符，然后可以把操作看成把一个段内的 1 放到另外一个段里面然后造出一个新的字符串。这个东西可以考虑 DP，设置 dp[i][j][k] 为到前 ​\(i\) 个单元、放了 \(j\)​ 个\(1\)​ 且操作次数为 \(k\)​。考虑暴力转移 + 剪枝，就能过了。

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

using namespace std;

const int MAX_N = 330, mod = 998244353;

int threshold, len, n, pre[MAX_N], dp[MAX_N][MAX_N][MAX_N], units[MAX_N];
char str[MAX_N];

int main()
{
    scanf("%s%d", str + 1, &threshold), len = strlen(str + 1);
    int last_pos = 0, ones = 0;
    for (int i = 1; i <= len; i++)
        ones += str[i] == '1';
    for (int i = 1; i <= len + 1; i++)
        if (str[i] != '1')
            units[++n] = i - last_pos - 1, last_pos = i;
    for (int i = 1; i <= n; i++)
        pre[i] = pre[i - 1] + units[i];
    dp[0][0][0] = 1, threshold = min(threshold, ones);
    for (int i = 0; i < n; i++)
        for (int j = pre[i]; j <= pre[n]; j++)
            for (int k = 0; k <= threshold; k++)
                if (dp[i][j][k])
                {
                    for (int g = max(j, pre[i + 1]); g <= pre[n]; g++)
                        if (k + g - j - units[i + 1] <= threshold)
                        {
                            if (i + 1 == n && g - j > units[i + 1])
                                break;
                            int cost = g - j <= units[i + 1] ? 0 : g - j - units[i + 1];
                            dp[i + 1][g][k + cost] = (0LL + dp[i + 1][g][k + cost] + dp[i][j][k]) % mod;
                        }
                }
    int ans = 0;
    for (int i = 0; i <= threshold; i++)
        ans = (0LL + ans + dp[n][ones][i]) % mod;
    printf("%d\n", ans);
    return 0;
}

D – Secret Passage

大概是能想出来的，但是写起来有点麻烦。 先定下终串的长度 \(|T|\)，然后在前 \(|S| – |T|\) 个字符中选一半留下、一半抛弃（前两个中有一个必须要选，而且必须要合法），然后再找一个 \(|T| – \frac{|S| – |T|}{2}\) 的后缀当作子序列插到 \(T\) 里。然后求本质不同的串。 那么，我们先求一个方案数：有 \(j\) 个额外的 \(0\) 和 \(k\) 个额外的 \(1\)，然后有 \(i\) 后缀作子序列。求完这个之后，我们还需要判合法性。 判断合法性，我们可以维护一个 vis 数组来记录前 \(i\) 个字符被抽走了 \(j\) 个 \(0\)、\(k\) 个 \(1\) 之后还剩多少个字符给剩下的 \(|S|-(i-j-k)\) 的前缀。如果有余（指大于等于 0），那么就是合法的。

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

using namespace std;

const int MAX_N = 330, mod = 998244353;

int n, dp[MAX_N][MAX_N][MAX_N], vis[MAX_N][MAX_N][MAX_N];
bool verdict[MAX_N][MAX_N][MAX_N];
char str[MAX_N];

int main()
{
    scanf("%s", str + 1), n = strlen(str + 1);
    dp[n][0][0] = 1;
    for (int i = n; i >= 1; i--)
        for (int j = 0; j + (n - i) <= n - 1; j++)
            for (int k = 0; j + k + (n - i) <= n - 1; k++)
                if (str[i] == '0')
                {
                    dp[i - 1][j][k] = (0LL + dp[i - 1][j][k] + dp[i][j][k]) % mod;
                    dp[i][j][k + 1] = (0LL + dp[i][j][k + 1] + dp[i][j][k]) % mod;
                }
                else
                {
                    dp[i - 1][j][k] = (0LL + dp[i - 1][j][k] + dp[i][j][k]) % mod;
                    dp[i][j + 1][k] = (0LL + dp[i][j + 1][k] + dp[i][j][k]) % mod;
                }
    memset(vis, -1, sizeof(vis)), vis[0][0][0] = 0;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= (i >> 1); j++)
            for (int k = 0; j + k <= (i >> 1); k++)
                if (vis[i][j][k] != -1)
                {
                    int c = vis[i][j][k];
                    if (i + 1 <= n && c != 0)
                    {
                        if (str[i + 1] == '0')
                            vis[i + 1][j + 1][k] = max(vis[i + 1][j + 1][k], c - 1);
                        if (str[i + 1] == '1')
                            vis[i + 1][j][k + 1] = max(vis[i + 1][j][k + 1], c - 1);
                    }
                    if (i + 2 <= n)
                    {
                        if (str[i + 1] == '0' || str[i + 2] == '0')
                            vis[i + 2][j + 1][k] = max(vis[i + 2][j + 1][k], c);
                        if (str[i + 1] == '1' || str[i + 2] == '1')
                            vis[i + 2][j][k + 1] = max(vis[i + 2][j][k + 1], c);
                        vis[i + 2][j][k] = max(vis[i + 2][j][k], c + 1);
                    }
                }
    for (int i = 0; i <= n; i++)
        for (int j = n; j >= 0; j--)
            for (int k = n; k >= 0; k--)
            {
                verdict[i][j][k] = vis[i][j][k] != -1;
                if (i > 0)
                    verdict[i][j][k] |= verdict[i - 1][j][k];
                verdict[i][j][k] |= verdict[i][j + 1][k] || verdict[i][j][k + 1];
            }
    int ans = 0;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j + (n - i) <= n; j++)
            for (int k = 0; j + k + (n - i) <= n; k++)
                if (dp[i][j][k] && (n - i) + j + k != 0 && verdict[i][j][k])
                    ans = (0LL + ans + dp[i][j][k]) % mod;
    printf("%d\n", ans);
    return 0;
}

E – Permutation Cover

这个题很好啊。

我们首先要知道，有解需要满足 \(2\min\{a_i\} \geq \max\{a_i\}\)，考虑在出现最大值的分界点会出现三个相同的数，这样就 GG 了。

如果有解，我们可以先考虑构造第一个前缀出来，这样我们后面就可以贪心的去拼接了。每次我们枚举拼在上一个段后面的段长，然后找字典序最小的。如果我们在 \(a_i\) 中先扣除掉这个前缀的频数，然后再来判：如果满足 \(2\min\{a_i\} \geq \max\{a_i\}\)，那我们可以先直接 1、2、3、4 这样去搞，这样字典序最小且对 \(a_i\) 只有 1 的扣除。这样下去会出现 \(2\min\{a_i\} + 1 = \max\{a_i\}\) 的情况，然而这种情况下也是有解法的：我们可以考虑让 \(a_i\) 最大的 \(i\) 排在让 \(a_j\) 最小的 \(j\) 前面，然后再和剩下的那些项去归并。

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

using namespace std;

const int MAX_N = 1050;

int n, sum, ai[MAX_N], res[MAX_N], candid[MAX_N], pos[MAX_N];
int upper, lower, sa[MAX_N], sb[MAX_N], ans[MAX_N], ansptr;

bool compare(const int &x, const int &y)
{
    if ((ai[x] == lower) == (ai[y] == lower))
        return x < y;
    else
        return (ai[x] == lower) < (ai[y] == lower);
}

void solve(int len)
{
    bool found = false;
    for (int i = 1; i <= len; i++)
        ai[pos[i]]--;
    int min_val = *min_element(ai + 1, ai + 1 + n), max_val = *max_element(ai + 1, ai + 1 + n);
    if ((min_val << 1) >= max_val)
    {
        for (int i = 1; i <= len; i++)
            res[i] = pos[i];
        sort(res + 1, res + 1 + len), found = true;
    }
    else if (((min_val << 1) | 1) == max_val)
    {
        upper = max_val, lower = min_val;
        int ptra = 1, ptrb = 1, la = 0, lb = 0, ptr = 0;
        for (int i = 1; i <= len; i++)
            if (ai[pos[i]] == min_val || ai[pos[i]] == max_val)
                sa[++la] = pos[i];
            else
                sb[++lb] = pos[i];
        sort(sa + 1, sa + 1 + la, compare), sort(sb + 1, sb + 1 + lb);
        // merge;
        while (ptra <= la && ptrb <= lb)
            if (sa[ptra] < sb[ptrb])
                res[++ptr] = sa[ptra++];
            else
                res[++ptr] = sb[ptrb++];
        while (ptra <= la)
            res[++ptr] = sa[ptra++];
        while (ptrb <= lb)
            res[++ptr] = sb[ptrb++];
        found = true;
        for (int i = len + 1; i <= n; i++)
            if (ai[pos[i]] == min_val)
                found = false;
        found |= (ai[sa[1]] == max_val);
    }
    for (int i = 1; i <= len; i++)
        ai[pos[i]]++;
    if (!found)
        res[1] = 0;
}

bool lexicographicalCompare(int *s1, int *s2)
{
    int ptr = 1;
    while (s1[ptr] == s2[ptr])
        ptr++;
    return s1[ptr] < s2[ptr];
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]), sum += ai[i], pos[i] = i;
    if (((*min_element(ai + 1, ai + 1 + n)) << 1) < *max_element(ai + 1, ai + 1 + n))
        puts("-1"), exit(0);
    solve(n);
    for (int i = 1; i <= n; i++)
        ans[++ansptr] = res[i], ai[res[i]]--, pos[i] = res[i];
    while (ansptr < sum)
    {
        memset(candid, 0, sizeof(candid)), candid[1] = n + 1;
        int len = 0;
        for (int i = 1; i <= n; i++)
        {
            solve(i);
            if (res[1] != 0 && lexicographicalCompare(res, candid))
            {
                len = i;
                for (int j = 1; j <= i; j++)
                    candid[j] = res[j];
            }
        }
        for (int i = 1; i + len <= n; i++)
            pos[i] = pos[i + len];
        for (int i = 1; i <= len; i++)
            ans[++ansptr] = pos[n - len + i] = candid[i], ai[candid[i]]--;
    }
    for (int i = 1; i <= ansptr; i++)
        printf("%d ", ans[i]);
    puts("");
    return 0;
}