2018 程序设计能力实训第一次机考分析(部分)

ultmaster edited 1 年,10 月前

本题解为民间(非官方)题解。粗线条。不明白也不要问我。

上午

C.

按顺序模拟就可以。注意类似 0x30xq0x80x 这样的情况。(写得好的话根本就不需要考虑)

D.

充要条件是:每个点出度至多为 1,如果有出度不能有入度。注意删掉重边。

E.

暴力似乎有 70 分。正解是数位 DP。拆位以后考虑每一位上 是否是自由的(可以随便乱取),自由的含义是由于更高位已经取了更少的了,这一位可以随便取 0 和 1:

LL dfs(int x, int af, int bf, int kf) {
    if (x < 0) return 1;
    LL ret = 0;
    for (int i = 0; i <= (af ? 1 : a[x]); ++i)
        for (int j = 0; j <= (bf ? 1 : b[x]); ++j) {
            if (kf || (i & j) <= k[x])
                ret += dfs(x - 1, af || i < a[x], bf || j < b[x],
                           kf || ((i & j) < k[x]));
        }
    return ret;
}

在此基础上加上记忆化就好了。

如果还不明白的话可以使用搜索引擎学习数位 DP(这一常见技巧)。

下午

D.

直接模拟就不用说了。注意到可以达到的点一定是若干个周期 + 最后一段。可以考虑对于每一个询问,枚举到底是哪一个操作最终到达它。然后得到的差值是否能使用若干个周期完成。注意判断除 0。

E.

把每段字符串都分割成若干个同一个字母的区间,显然这些区间是相互对应的。只需要将每个区间同步到中位数数量就好了。

Comments

Master X

以后再也不奶什么“实训绝对不考dp”这种话……



下次考图论不?

qqqqqcy

感觉上午的题比下午的难。

下午的的E原来找中位数就能保证差的绝对值的和最小,学习了。考试的时候交了个二分过的。

10175102214

我怎么感觉是下午的难一些。。。

你当前正在回复 博客/题目
存在问题!