题解：AT_agc045_c [AGC045C] Range Set

Cadmus · 2026-01-15 12:38:46 · 题解

要去想怎么判断一个字符串能不能涂出来，可以贪心判断，有三个变量 x,p,q，初始 x=0,p=A,q=B，然后每次如果：

• 字符是 0
  • 如果 x=0，或者 p=0，那么 p--,q--；
  • 否则，p--，然后 q=B-1。
• 字符是 1 同理。
• 如果 p<0，p=0；如果 q<0，q=0。
• 把 x 改成现在的字符。

枚举的暴力代码如下：

int answer = 0;
for (int S = 0; S < 1 << n; S ++) {
    int x = 0, p = A, q = B;
    for (int i = 1; i <= n; i ++) {
        int v = (S >> (i - 1) & 1);
        if (v) {
            if (x || !p) p = max(p - 1, 0), q = max(q - 1, 0);
            else p = max(p - 1, 0), q = B - 1;
        } else {
            if (!x || !q) p = max(p - 1, 0), q = max(q - 1, 0);
            else q = max(q - 1, 0), p = A - 1;
        }
        x = v;
    }
    if (!p && !q) {
        answer ++;
    }
}

然后就可以把 x,p,q 全部用动态规划的状态记录（第一维 p，第二维 q，第三维 x），用一个滚动数组，dp1 是当前的,dp2 是下一个。转移方程式非常简单的，这都不知道可以不做这题了。有下面的代码：

for (int i = 1; i <= n; i ++) {
    dp2[0][0][0] += dp1[0][0][0] + dp1[0][0][1];
    dp2[0][0][1] += dp1[0][0][0] + dp1[0][0][1];
    for (int x = 1; x <= A; x ++) {
        dp2[x - 1][0][0] += dp1[x][0][0];
        dp2[x - 1][0][1] += dp1[x][0][1];
        dp2[x - 1][B - 1][1] += dp1[x][0][0];
        dp2[x - 1][0][0] += dp1[x][0][1];
    }
    for (int y = 1; y <= B; y ++) {
        dp2[0][y - 1][0] += dp1[0][y][0];
        dp2[0][y - 1][1] += dp1[0][y][1];
        dp2[0][y - 1][1] += dp1[0][y][0];
        dp2[A - 1][y - 1][0] += dp1[0][y][1];
    }
    for (int x = 1; x <= A; x ++) for (int y = 1; y <= B; y ++) {
        dp2[x - 1][y - 1][0] += dp1[x][y][0];
        dp2[x - 1][y - 1][1] += dp1[x][y][1];
        dp2[x - 1][B - 1][1] += dp1[x][y][0];
        dp2[A - 1][y - 1][0] += dp1[x][y][1];
    }
    for (int x = 0; x <= A; x ++) for (int y = 0; y <= B; y ++) {
        dp1[x][y][0] = dp2[x][y][0], dp1[x][y][1] = dp2[x][y][1];
        dp2[x][y][0] = dp2[x][y][1] = 0;
    }
}

这样的时间复杂度是 O(n^3)。

要维护矩阵每次向左下角移动，维护每行每列的和就可以了。优化之后时间复杂度变成 O(n^2)。