AtCoder Beginner Contest 196

比赛链接

D Hanjo

Description

题目链接

Solution

由于数据规模很小，可以直接暴搜，搜索的时候记录每一层的状态，当这一层都被填满时才搜下一层。具体的，对于第 $i$ 行第 $j$ 列，可以放一个 $1*1$ 的，也可以横着向右放一个 $2*1$ 的，或者竖着向下放一个 $2*1$ 的。时间复杂度大概是 $O(HW2^A\binom{HW}A)$ 吧。

Code

Hanjo

#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << #x << " = " << x << endl
#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); \
stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) { cout << endl; }

template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << " ";
    err(++it, args...);
}

constexpr int MAXN = 1e5 + 5, MOD = 1e9 + 7;

int h, w, a, b, ans;
int st[16];

void Search(int r, int c, int a, int b) {
    if (a < 0 || b < 0) return;
    if (r == h) {
        if (a || b) return;
        for (int i = 0; i < h; i++)
            if (st[i] != (1 << w) - 1) return;
        ans++;
        return;
    }
    if (st[r] == (1 << w) - 1) {
        Search(r + 1, 0, a, b);
        return;
    }
    if (c < w && (st[r] >> c) & 1) Search(r, c + 1, a, b);

    if (b > 0) {
        int pre = st[r];
        st[r] |= (1 << c);
        Search(r, c + 1, a, b - 1);
        st[r] = pre;
    }

    if (a > 0 && c < w - 1 && !((st[r] >> (c + 1)) & 1)) {
        int pre = st[r];
        st[r] |= (1 << c);
        st[r] |= (1 << (c + 1));
        Search(r, c + 2, a - 1, b);
        st[r] = pre;
    }

    if (a > 0 && r != h - 1 && !((st[r + 1] >> c) & 1)) {
        int pre1 = st[r], pre2 = st[r + 1];
        st[r] |= (1 << c);
        st[r + 1] |= (1 << c);
        Search(r, c + 1, a - 1, b);
        st[r] = pre1;
        st[r + 1] = pre2;
    }
}

signed main() {
    boost;
    cin >> h >> w >> a >> b;
    Search(0, 0, a, b);
    cout << ans << endl;
    return 0;
}

Bonus

将题目中 $HW \le 16$ 改为 $HW \le 140$（题解中提到 $HW$ 可以到 $200$，但我暂时没想到进一步优化的方法）。

Solution

使用轮廓线 $DP$。不妨设 $H \ge \ W$，将格子按 $i*W+j$ 编号。设 $dp[i][s][a][b]$ 表示考虑前 $i$ 个方格，从这个方格开始前 $W$ 个方格填充状态为 $s$，除了这些方格外其余方格全部被填满，一共用了 $a$ 个 $2*1$ 的方块和 $b$ 个 $1*1$ 的方块的方案数。现在考虑第 $i+1$ 个方格，我们很容易根据 $s$ 获取其上方的方格和左边的方格的填充状态 $s_u$ 和 $s_l$，同时获取从方格 $i+1$ 开始前 $W$ 个方格填充状态，记为 $s'$。根据 $s_u$ 和 $s_l$ 的取值，有如下转移：

• $s_u = 0$，则必须竖着放一个 $2*1$ 的方块，于是有：

$dp[i+1][s'|1][a+1][b] \leftarrow dp[i][s][a][b]$

• $s_l s_u = 01$，则可以横着放一个 $2*1$ 的方块，或者放一个 $1*1$ 的方块，或者不放，从而：

$\begin{aligned} dp[i+1][s'|3][a+1][b] \leftarrow dp[i][s][a][b] \\ dp[i+1][s'|1][a][b+1] \leftarrow dp[i][s][a][b] \\ dp[i+1][s'][a][b] \leftarrow dp[i][s][a][b] \\ \end{aligned}$

• $s_l s_u = 11$，则可以放一个 $1*1$ 的方块，也可以不放，故有：

$\begin{aligned} dp[i+1][s'|1][a][b+1] \leftarrow dp[i][s][a][b] \\ dp[i+1][s'][a][b] \leftarrow dp[i][s][a][b] \\ \end{aligned}$

最后答案为 $dp[H*W][(1<<W)-1][A][B]$。

注意：

• $dp$ 数组第一维可以用滚动数组滚掉，从而减少空间开销。

• 为了简便，我们规定第 $0$ 行和第 $0$ 列全部被填满。

• 为了避免重复计算，要严格定义方块放置的方向和位置。

时间复杂度为 $O(2^{min(H,W)}(HW)^3)$。

Code

Hanjo

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MOD = 1E9 + 7;
int H, W, A, B;

void add(int& a, int b) { a = (a + b) % MOD; }

signed main() {
    cin >> H >> W >> A >> B;
    if (W > H) swap(H, W);
    int dp[2][1 << W][A + 1][B + 1];
    memset(dp, 0, sizeof(dp));
    dp[0][(1 << W) - 1][0][0] = 1;
    bool tag = 0;
    for (int i = 1; i <= H; i++)
        for (int j = 1; j <= W; j++) {
            tag ^= 1;
            memset(dp[tag], 0, sizeof(dp[tag]));
            for (int s = 0; s < (1 << W); s++)
                for (int a = 0; a <= A; a++)
                    for (int b = 0; b <= B; b++) {
                        int nxtS = ((s << 1) & ((1 << W) - 1));
                        int sUp = (s >> (W - 1)) | (i == 1);
                        int sLeft = (s & 1) | (j == 1);
                        if (!sUp) {
                            if (a)
                                add(dp[tag][nxtS | 1][a][b],
                                    dp[tag ^ 1][s][a - 1][b]);
                        } else if (!sLeft) {
                            if (a)
                                add(dp[tag][nxtS | 3][a][b],
                                    dp[tag ^ 1][s][a - 1][b]);
                            if (b)
                                add(dp[tag][nxtS | 1][a][b],
                                    dp[tag ^ 1][s][a][b - 1]);
                            add(dp[tag][nxtS][a][b], dp[tag ^ 1][s][a][b]);
                        } else {
                            if (b)
                                add(dp[tag][nxtS | 1][a][b],
                                    dp[tag ^ 1][s][a][b - 1]);
                            add(dp[tag][nxtS][a][b], dp[tag ^ 1][s][a][b]);
                        }
                    }
        }
    cout << dp[tag][(1 << W) - 1][A][B];
    return 0;
}

E Filters

Description

题目链接

Solution

记 $F(x) = f_n(...f_2(f_1(x))...)$，猜想 $F(x)$ 可以表示成 $min(p,max(q,x+r))$，接下来进行证明：

• $f(x)$ 可以表示成 $min(p_1,max(q_1,x+r_1))$，具体如下：

  • $t_i = 1$，则 $f(x) = min(+\infty,max(-\infty,x+a_i))$。
  • $t_i = 2$，则 $f(x) = min(+\infty,max(a_i,x+0))$。
  • $t_i = 3$，则 $f(x) = min(a_i,max(-\infty,x+0))$。

• 设 $g(x) = min(p_2,max(q_2,x+r_2))$，则有：

  $\begin{aligned} g(f(x)) &= \min(p_2, \max(q_2, \min(p_1, \max(q_1, x + r_1)) + r_2))\\ &= \min(p_2, \max(q_2, \min(p_1 + r_2, \max(q_1 + r_2, x + r_1 + r_2))))\\ &= \min(\min(p_2, \max(q_2, p_1 + r_2)), \max(\max(q_2, \min(p_1 + r_2, q_1 + r_2)), x + (r_1 + r_2))),\\ \end{aligned}$

设 $f_0(x) = x$，按照上面的式子做 $n$ 次复合运算即可得到 $F(x)$，之后便可 $O(1)$ 实现单次查询。

Code

Filters

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const LL INF = 1E15;
int n, q;

signed main() {
    ios::sync_with_stdio(false);
    LL c = INF, b = -INF, a = 0;
    LL c2, b2, a2;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        LL v, t;
        cin >> v >> t;
        switch (t) {
            case 1:
                c2 = INF, b2 = -INF, a2 = v;
                break;
            case 2:
                c2 = INF, b2 = v, a2 = 0;
                break;
            case 3:
                c2 = v, b2 = -INF, a2 = 0;
                break;
            default:
                break;
        }
        b = max(b2, min(c + a2, b + a2));
        c = min(c2, max(b2, c + a2));
        a = a + a2;
    }
    cin >> q;
    for (int i = 1; i <= q; i++) {
        LL x;
        cin >> x;
        cout << min(c, max(b, x + a)) << endl;
    }
    return 0;
}

F Substring 2

Description

题目链接

Solution

$FFT$ 处理子串匹配板子题，只需要对 $0$ 和 $1$ 分别求匹配数。记 $m[i][0/1]$ 表示 $S_{i...i+|T|-1}$ 与 $T_{0...|T|-1}$ 中字符 $0/1$ 的匹配次数，那么有 $m[i][0/1] = \sum \limits_{k=0}^{|T|-1} (S[i+k]==0/1)(T[k]==0/1)$，把 $T$ 翻转后求卷积即可，一共需要 $4/6$ 次 $dft$。最后答案为 $\max \limits_{0 \le i \le |S|-|T|} {|T|-m[i][0]-m[i][1]}$。

另外，我们也可以直接对每个起始位置 $i$ 求未匹配数 (同样需要将 $T$ 翻转)，即 $\sum \limits_{k=0}^{|T|-1} (S[i+k]-T[T.size()-k-1])^2$。把平方打开后求一次卷积以及两次平方和即可，这样只需要 $2/3$ 次 $dft$。

Code

Substring 2

#include <bits/stdc++.h>

using namespace std;
const double PI = acos(-1.0);

struct Complex {
    double x, y;
    Complex(double _x = .0, double _y = .0) : x(_x), y(_y) {}
    Complex operator*(Complex other) {
        return Complex(x * other.x - y * other.y, x * other.y + y * other.x);
    }
    Complex operator+(Complex other) {
        return Complex(x + other.x, y + other.y);
    }
    Complex operator-(Complex other) {
        return Complex(x - other.x, y - other.y);
    }
};

void expand(int &sz) {
    if (__builtin_popcount(sz) != 1) sz = 1 << (1 + (int)log2(sz));
}

int rev(int x, int sz) {
    int ans = 0;
    for (int i = 0; i < sz; i++)
        if ((x >> i) & 1) ans |= (1 << (sz - i - 1));
    return ans;
}

int R[4000001];
void dft(Complex a[], int sz, int type) {
    for (int i = 0; i < sz; i++)
        if (i < R[i]) swap(a[i], a[R[i]]);
    for (int m = 2; m <= sz; m <<= 1) {
        Complex wm(cos(2 * PI / m), type * sin(2 * PI / m));
        for (int k = 0; k < sz; k += m) {
            Complex w(1);
            for (int j = 0; j < m / 2; j++) {
                Complex t = w * a[k + j + m / 2];
                Complex u = a[k + j];
                a[k + j] = u + t;
                a[k + j + m / 2] = u - t;
                w = w * wm;
            }
        }
    }
}

int main() {
    char c[] = {'0', '1'};
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    int N = n;
    expand(N);
    Complex a[N];
    for (int i = 0; i < N; i++) R[i] = rev(i, log2(N));
    int matched[n] = {0};
    for (int type = 0; type < 2; type++) {
        int f[n] = {0};
        for (int i = 0; i < m; i++) a[i].x = (t[i] == c[type]);
        for (int i = 0; i < n; i++)
            if (s[i] == c[type]) f[i] = 1;
        for (int i = 0; i < n; i++) a[i].y = f[n - i - 1];
        dft(a, N, 1);
        for (int i = 0; i < N; i++) a[i] = a[i] * a[i];
        dft(a, N, -1);
        for (int i = 0; i < n - m + 1; i++)
            matched[i] += int(a[i + m - 1].y / 2.0 / N + 0.5);
        for (int i = 0; i < N; i++) a[i].x = a[i].y = 0;
    }
    int ans = 1E9;
    for (int i = 0; i < n - m + 1; i++) ans = min(ans, m - matched[i]);
    cout << ans << endl;
    return 0;
}

做法2

#include <bits/stdc++.h>

using namespace std;

#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 1e6 + 5, MOD = 1e9 + 7;

namespace NTT {
    constexpr int NR = 1 << 22, g = 3, gi = 332748118, mod = 998244353;

    long long qpow(long long a, long long b) {
        long long res = 1;
        while (b) {
            if (b & 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }

    int R[4000001];
    void init(int& sz) {
        if (__builtin_popcount(sz) != 1) sz = 1 << (1 + (int)log2(sz));
        for (int i = 0; i < sz; i++) R[i] = (R[i >> 1] >> 1) | ((i & 1) ? (sz >> 1) : 0);
    }

    void dft(long long a[], int sz, int type) {
        for (int i = 0; i < sz; i++)
            if (i < R[i]) swap(a[i], a[R[i]]);
        for (int m = 2; m <= sz; m <<= 1) {
            long long gn = qpow(type == 1 ? g : gi, (mod - 1) / m); // 单位原根 g_n
            for (int k = 0; k < sz; k += m) {
                long long g0(1);
                for (int j = 0; j < m / 2; j++) {
                    long long t = g0 * a[k + j + m / 2] % mod;
                    long long u = a[k + j];
                    a[k + j] = (u + t) % mod;
                    a[k + j + m / 2] = (u - t + mod) % mod;
                    g0 = g0 * gn % mod;
                }
            }
        }
        if (type == -1) {
            long long inv = qpow(sz, mod - 2);
            for (int i = 0; i < sz; i++) a[i] = a[i] * inv % mod;
        }
    }
}

namespace Polynomial {
    using namespace NTT;

    void Convolution(int n, int m, int a[], int b[], int c[]) { // a[0, n] b[0, m]
        int N = n + m + 1;
        init(N);
        long long f[N], g[N];
        for (int i = 0; i < N; i++) f[i] = g[i] = 0;
        for (int i = 0; i <= n; i++) f[i] = a[i];
        for (int i = 0; i <= m; i++) g[i] = b[i];
        dft(f, N, 1), dft(g, N, 1);
        long long res[N];
        for (int i = 0; i < N; i++) res[i] = 0;
        for (int i = 0; i < N; i++) res[i] = f[i] * g[i] % mod;
        dft(res, N, -1);
        for (int i = 0; i <= n + m; i++) c[i] = res[i];
    }
};

string s, t;
int a[MAXN], b[MAXN], c[MAXN << 1], f[MAXN], pres[MAXN], pret[MAXN];

int main() {
    boost;
    cin >> s >> t, reverse(t.begin(), t.end());
    int n = s.size(), m = t.size();
    for (int i = 1; i <= n; i++) a[i] = s[i - 1] - '0', pres[i] = pres[i - 1] + a[i];
    for (int i = 1; i <= m; i++) b[i] = t[i - 1] - '0', pret[i] = pret[i - 1] + b[i];
    Polynomial::Convolution(n, m, a, b, c);
    int ans(INT_MAX);
    for (int i = 1; i <= n - m + 1; i++) {
        f[i] = -2 * c[i + m] + (pres[i + m - 1] - pres[i - 1]) + (pret[m]);
        ans = min(ans, f[i]);
    }
    cout << ans << "\n";
    return 0;
}