AtCoder Grand Contest 041 – 解题报告

A – Table Tennis Training

思博题,考虑两端和奇偶性即可。

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

using namespace std;

typedef long long ll;

int main()
{
    ll n, A, B, ans = 0x7fffffffffffffff;
    scanf("%lld%lld%lld", &n, &A, &B);
    ans = min(A - 1, n - B) + 1 + ((B - A - 1) >> 1);
    if (!((A^B) & 1))
        ans = min(ans, (B - A) >> 1);
    printf("%lld\n", ans);
    return 0;
}

B – Voting Judges

首先要意识到这个问题是可二分的,因为如果答案更大可行、那么小答案也可行。接下来考虑写一个 check。首先要判掉单独加上都无法入围的情况,然后算比 \(a_{mid}\) 小的那些 \(a_i\) 可以提供的票数。最后算这个票数是否能使之入围即可。

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

using namespace std;

const int MAX_N = 1e5 + 200;

int n, m, V, P, ai[MAX_N];

bool check(int mid)
{
    if (ai[mid] + m < ai[P])
        return false;
    long long acc = 0;
    for (int i = P; i <= n; i++)
        if (i != mid && ai[i] < ai[mid] + m)
            acc += min(m, ai[mid] + m - ai[i]);
    return acc >= 1LL * (V - 1) * m;
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &V, &P);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]);
    sort(ai + 1, ai + 1 + n), reverse(ai + 1, ai + 1 + n);
    V = max(1, V - P + 1);
    int l = P, r = n, res = P;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
            res = mid, l = mid + 1;
        else
            r = mid - 1;
    }
    printf("%d\n", res);
    return 0;
}

C – Domino Quality

首先可以找出 \(3\) 的、单元数为 \(2\) 的那个情况,这个情况直接输出即可;另外,我们能自己搞出来 \(4 \to 7\) 的、单元数为 \(3\) 的情况,之后如果 \(n > 7\),则表示成 \(n = 4x + y, y > 3\),然后拼在对角线上即可。

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

using namespace std;

int n;
char buffer[1010][1010];

const char m3[3][4] =
    {"aa.",
     "..a",
     "..a"};

const char m4[4][5] =
    {"aabc",
     "ddbc",
     "bcaa",
     "bcdd"};

const char m5[5][6] =
    {"aabba",
     "bcc.a",
     "b..cb",
     "a..cb",
     "abbaa"};

const char m6[6][7] =
    {"aabc..",
     "ddbc..",
     "..aabc",
     "..ddbc",
     "bc..aa",
     "bc..dd"};

const char m7[7][8] =
    {"aabbcc.",
     "dd.dd.a",
     "..d..da",
     "..d..db",
     "dd.dd.b",
     "..d..dc",
     "..d..dc"};

void writeBuffer(int id, int x, int y)
{
    for (int i = 0; i < id; i++)
    {
        const char *str;
        switch (id)
        {
        case 3:
            str = m3[i];
            break;
        case 4:
            str = m4[i];
            break;
        case 5:
            str = m5[i];
            break;
        case 6:
            str = m6[i];
            break;
        case 7:
            str = m7[i];
            break;
        }
        for (int j = 0; str[j]; j++)
            buffer[x + i][y + j] = str[j];
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            buffer[i][j] = '.';
    if (n <= 2)
        puts("-1"), exit(0);
    if (n <= 7)
        writeBuffer(n, 0, 0);
    else
    {
        int base = 0;
        writeBuffer(n % 4 + 4, base, base), base += n % 4 + 4;
        while (base < n)
            writeBuffer(4, base, base), base += 4;
    }
    for (int i = 0; i < n; i++)
        printf("%s\n", buffer[i]);
    return 0;
}

D – Problem Scores

这应该是本次最有意思的题目了,之前 lcx 的某个教练群里发过。

其实就是要满足其 \(k + 1\) 前缀和严格大于其 \(k\) 后缀和,写出来即:

\[ \sum_{i = 1}^{k + 1} a_i > \sum_{i = n – k + 1}^n a_i \]

一共会有 \(n\) 个这样的限制条件,我们尝试寻找性质来缩减之。首先,对于 \(k > \lfloor \frac{n}{2} \rfloor\) 的情况,存在前缀和后缀中间重叠的部分,这个可以直接移项消掉,转化成 \(k \leq \lfloor \frac{n}{2} \rfloor\) 的情况。

再考虑利用 \(a_i \leq a_{i + 1}\) 的性质,则发现当 \(k = \lfloor \frac{n}{2} \rfloor\) 时满足,\(k \leq \lfloor \frac{n}{2} \rfloor\) 的情况可以被充分满足。

那么我们现在只需要保证 \(\sum_{i = 1}^{k + 1} a_i > \sum_{i = n – k + 1}^n a_i, k = \lfloor \frac{n}{2} \rfloor\) 即可。

现在我们对这个序列进行差分,使得 \(a_k = 1 + \sum_{i = 1}^k \Delta_i\)。首先显然有 \(\Delta \geq 0\)。其次,带回式子时,发现前缀和可以被拆解为 \(\sum \Delta_i c_i\),其中这个 \(c_i\) 很好算。考虑带入:

\[ \sum_{i = 1}^{k + 1} 1 + \sum_{j = 1}^i \Delta_j > \sum_{i = n – k + 1}^n 1 + \sum_{j = 1}^i \Delta_j \\ 1 + \sum_{i = 1}^{k + 1} \sum_{j = 1}^i \Delta_j > \sum_{i = n – k + 1}^n \sum_{j = 1}^i \Delta_j \\ \sum_{i = 1}^{k + 1} \sum_{j = 1}^i \Delta_j \geq \sum_{i = n – k + 1}^n \sum_{j = 1}^i \Delta_j \\ \sum_{j = 1}^n \Delta_j \sum_{i = 1}^{k + 1} [j \leq i] \geq \sum_{j = 1}^n \Delta_j \sum_{i = n – k + 1}^n [j \leq i] \\ \sum_{j = 1}^{k + 1} \Delta_j (k + 2 – j) \geq \sum_{j = 1}^n \Delta_j (n – \max(j, n – k + 1) + 1) \]

得到:

\[ (k + 1) \Delta_1 + \sum_{j = 2}^{k + 1} \Delta_j (k + 2 – j) \geq k\Delta_1 + \sum_{j = 2}^n \Delta_j (n – \max(j, n – k + 1) + 1) \\ \Delta_1 \geq \sum_{j = 2}^n \Delta_j (n – \max(j, n – k + 1) + 1) – \sum_{j = 2}^{k + 1} \Delta_j (k + 2 – j) \\ \Delta_1 \geq \sum_{j = 2}^n \Delta_j (n – \max(j, n – k + 1) + 1) – \sum_{j = 2}^n \Delta_j \max(0, k + 2 – j) \\ \Delta_1 \geq \sum_{j = 2}^n \Delta_j (n + 1 – (\max(j, n – k + 1) + \max(0, k + 2 – j))) \\ \Delta_1 \geq \sum_{j = 2}^n \Delta_j (n + 1 – \max(j, k + 2, n – k + 1, n + 3 – j)) \\ \Delta_1 \geq \sum_{j = 2}^n \Delta_j (n + 1 + \min(-j, – k – 2, – n + k – 1, – n – 3 + j)) \\ \Delta_1 \geq \sum_{j = 2}^n \Delta_j \min(n – j + 1, n – k – 1, k, j – 2) \\ \]

提醒一下,\(k = \lfloor \frac{n}{2} \rfloor\):

区间是离散的,所以最后 \(\min(n – j + 1, n – k – 1, k, j – 2) = \min(j – 2, n – j + 1)\)。最后整个不等式形如:

\[ \Delta_1 \geq [\Delta_2, \Delta_3, \dots \Delta_n] \cdot [0, 1, 2, 3, \dots 3, 2, 1] \]

考虑设:

\[ a = \Delta_2 + \Delta_3 + \Delta_4 + \dots + \Delta_n \\ b = [\Delta_2, \Delta_3, \dots \Delta_n] \cdot [0, 1, 2, 3, \dots 3, 2, 1] \]

发现 \(\Delta_1 \leq n – 1 – a, \Delta_1 \geq b \),那么,\(\Delta_1\) 的选择方式有 \(\max(0, n – 1 – (a + b))\) 种。\(a + b = [\Delta_2, \Delta_3, \dots \Delta_n] \cdot [1, 2, 3, 4, \dots 4, 3, 2]\),所以我们用 \(DP\) 算下和为 \(j = a + b\) 的 \(\Delta_i\) 序列的方案数,然后用方案数乘上一个 \(\max(0, n – 1 – (a + b))\) 即为答案。

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

using namespace std;

const int MAX_N = 5050;

int n, mod, dp[MAX_N], coeff[MAX_N];

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



发表评论

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