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

ultmaster edited 6 年，8 月前

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

上午

C.

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

D.

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

E.

暴力似乎有 70 分。正解是数位 DP。拆位以后考虑每一位上 $a,b,k$ 是否是自由的（可以随便乱取），自由的含义是由于更高位已经取了更少的了，这一位可以随便取 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

6 年，8 月前

以后再也不奶什么“实训绝对不考dp”这种话……
。
。
。
下次考图论不？

回复 2 0

qqqqqcy

6 年，8 月前

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

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

回复 2 0

10175102214

6 年，8 月前

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

回复 1 2