2021.4.23 校内模拟赛游记

体验十分糟糕的校内模拟赛。感觉这一天真是啥也没干,郁郁寡欢。

即使打得不好也要以昂扬的斗志面对生活鸭!

A

本来就是一个模拟平衡三进制的题,也就普及组一二题难度,结果比赛时题目改来改去,然后我又一时手残居然统计的时候从 22 开始,于是 1000100 \rightarrow 0

B

反而这是比赛时体验最好的一题了,虽然题目长,但没有什么思维难度,就是最短路套上背包的板子。

C

后面两题似乎都没有被很好的思考过了,我既然得出了 1515 以上一定没解的结论,看这数据范围,总应该想到是状压的,结果居然搞了半天还是写暴力。

其实状压的思路也挺好想的,搞可行性 dp,f[S][i]f[S][i] 表示当前状态能否合成 ii, 然后转移挺显然的,bitset 优化也应该容易想到。

然后主要的问题在于输出方案。判断当前这个是否可选还是有一些细节的。

代码。

#include <cstdio>
#include <bitset>
int n, m, C[55][55];
std::bitset<100005> f[(1 << 15)+5];
int count(int x) { return (x != 0) ? (count(x & (x-1)) + 1) : 0; }
int main() {
    scanf("%d%d", &n, &m);
    if(n >= 15 || m < (1 << n)) return puts("No Answer"), 0;
    for(int i = 0; i <= n; i++) {
        C[i][0] = C[i][i] = 1;
        for(int j = 1; j < i; j++) C[i][j] = C[i-1][j-1] + C[i-1][j];
    }
    m -= (1 << n);
    f[0][0] = 1;
    for(int i = 0; i < (1 << (n+1)); i++)
        for(int j = 0; j <= n; j++)
            if(~i & (1 << j)) f[i | (1 << j)] |= f[i] << (j * C[n][count(i)]);
    if(f[(1 << (n+1)) - 1][m]) {
        int now = (1 << (n+1)) - 1, v = m;
        while(now) {
            for(int i = n; i >= 0; --i)
                if(now & 1 << i && v - i * C[n][count(now ^ 1 << i)] >= 0 &&
                    f[now ^ 1 << i][v - i * C[n][count(now ^ 1 << i)]]) {
                    v -= i * C[n][count(now ^= 1 << i)];
                    printf("%d%c", i+1, (now == 0) ? '\n' : ' ');
                    break;
                }
        }
    } else puts("No Answer");
    return 0;
}

D

我忏悔:在这做这题时,我背弃了正气和信仰。

非常浮躁地搞了一个错的贪心,然后就去看了原题别人的代码,而甚至没有自己好好的思考过做法以及其时间复杂度。

刚刚写过那篇文章,写过那段《无言》,这样又如何去面对内心的逼问?

下不为例。