剑锋所指,心之所向。

自闭 T2。

IOI 赛制,rk 4, AK 了。

提高 1 在路上了!


A. 讨论

n \times m 个小正方形组成的 n \times m 矩形,等概率随机选择一个小矩形,求面积期望值(\bmod 998244353 意义下)。


答案即为 p * q^{-1},其中 p 为所有小正方形的面积和,q 为个数。

考虑如何计算个数:

确定一个小矩形,只需要确定其相邻两边。

对于横着的边,若其长度为 i,则有 m - i + 1 种选法。

对于竖着的边,若其长度为 j,则有 n - j + 1 种选法。

\begin{aligned} q &= \sum_{i = 1} ^ m (m - i + 1) \times \sum_{j = 1} ^ n (n - j + 1) \\ &= \dfrac{m(m + 1)}{2} \times \dfrac{n(n + 1)}{2} \\ &= \dfrac{nm(n + 1)(m + 1)}{4} \end{aligned}

而面积则是其加权形式

\begin{aligned} p &= \sum_{i = 1} ^ m i(m - i + 1) \times \sum_{j = 1 } ^ n j(n - j + 1) \\ &= \Big ((m + 1) \times \dfrac{m(m + 1)}{2} - \dfrac{m(m + 1)(2m + 1)}{6}\Big ) \times \Big( (n + 1) \times \dfrac{n(n + 1)}{2} - \dfrac{n(n + 1)(n + 1)}{6}\Big) \\ &= \dfrac{m(m + 1)(m + 2)}{6} \times \dfrac{n(n + 1)(n + 2)}{6} \\ &= \dfrac{mn(m + 1)(m + 2)(n + 1)(n + 2)}{36} \end{aligned}

\dfrac{p}{q}

\dfrac{(n + 2)(m + 2)}{9}

快速幂即可。

(懒,写的 py)

C++ 的话需要边读边模。

from math import * 

P = int()
P = 998244353

def qpower(a, x):
    ret = 1
    while x > 0:
        if x & 2:
            ret = ret * a % P
        a = a * a % P
        x = floor(x / 2)
    return ret

s = input().split()

print((int(s[0]) + 2) * (int(s[1]) + 2) % P * qpower(9, P - 2) % P)

B. 战斗

有 6 种攻击方式:分别为普通攻击,4 种技能与 1 种连招。普通攻击回复 p 点蓝,造成 h 点伤害,第 i 种技能消耗 p_i 点蓝,造成 h_i 伤害,当连续依次放出 1, 2, 3 技能后,使用 4 技能可在本次攻击内造成 4 \times h_4 的伤害,消耗不变。求是否能在 n 次攻击内造成大于 m 点伤害。


考虑将普攻与 combo 都看做一种特殊的技能看待,便于处理。

可以将放出 combo 的整个过程看做一个技能,消耗 1, 2, 3, 4 的蓝,造成 1, 2, 3, 与 4 \times h_4 的攻击。

f(i, j) 表示在 i 回合后 boss 剩下 j 点血剩下最多多少蓝。

枚举技能种类转移:

f(i, j) \leftarrow f(i - 1, j + h_k) - p_k

对于 combo:

f(i, j) \leftarrow f(i - 4, j + h_5) - p_5

还需要滚动数组一下。

时间复杂度 O(nm)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXM = 1e4 + 10, MAXN = 1e3 + 10;

int n, m, h[6], p[6];
ll f[5][MAXM];
bool ans;

void chkmax(ll& a, ll b) { if (a < b) a = b; }

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i <= 4; ++i) {
        scanf("%d %d", &h[i], &p[i]);
        p[5] += p[i], h[5] += h[i];
    }
    h[5] += h[4] * 3;
    memset(f, -1, sizeof f);
    f[0][m] = 0;
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (i >= 4 && j + h[5] <= m && f[i % 4][j + h[5]] - p[5] >= 0) {
                chkmax(f[i % 4][j], f[i % 4][j + h[5]] - p[5]);
            }
            int pre = (i - 1) % 4;
            for (int k = 0; k <= 4; ++k) {
                if (j + h[k] <= m && f[pre][j + h[k]] >= max(p[k], 0)) {
                    chkmax(f[i % 4][j], f[pre][j + h[k]] - p[k]);
                }
            }
            if (i + 4 <= n && f[i % 4][j] >= p[5] && j <= h[5]) {
                puts("yes");
                return 0;
            }
            for (int k = 0; k <= 4; ++k) {
                if (f[i % 4][j] >= max(p[k], 0) && j <= h[k]) {
                    puts("yes");
                    return 0;
                }
            }

        }
    }
    puts("no");
    return 0;
}

C. 魔法

给出 n[1, k] 的排列,与 x \in [1, k]。你可以按 1n 的顺序选择任意个排列,并且 x 将会变为 p_{i, x}(第 i 个排列的第 x 个数)。求最后可以得到的 x 的最大值。


不关心 x 是怎么来的,记录哪些 x 是可以到达的,每次扫一遍更新即可。

时间复杂度 O(nk)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500 + 10, MAXK = 2e4 + 10;

int n, x, k, ans[MAXK], f[MAXN][MAXK], tmp[MAXK];

void read(int& x) {
    int f = 1; char ch = getchar();
    for (; ch < '0' || '9' < ch; ch = getchar()) if (ch == '-') f = -f;
    for (; '0' <= ch && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    x = f == 1 ? x : -x;
}

int main() {
    read(n), read(x), read(k);
    ans[x] = true;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= k; ++j) {
            read(f[i][j]);
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= k; ++j) {
            if (ans[j]) {
                tmp[f[i][j]] = true;
            }
        }
        for (int j = 1; j <= k; ++j) ans[j] |= tmp[j];
    }
    for (int j = k; j >= 1; --j) if (ans[j]) {
        printf("%d\n", j);
        return 0;
    }
    return 0;
}

总结

  • AK 了

  • 调 T2 的时候,电脑上有两份代码。编辑器打开的是第一份,命令行编译的是第二份,这样搞了半个多小时之后才发现,浪费了很多时间...

已有 2 条评论

  1. 好强啊~问一下您现在还需要上文化课吗/kk

    1. bwt bwt

      感谢 lcy 大爷关心我~现在我是在机房集训,可能过几周再去文化受苦吧...

cdq 分治学习笔记
上一篇 «
codeforces 1354/edu. 87 题解与总结
» 下一篇