某島

… : "…アッカリ~ン . .. . " .. .
August 15, 2022

AtCoder Beginner Contest 264

傳送門

Problem C. Matrix Reducing

數據範圍很小,隨便做。

#include <lastweapon/io>
using namespace lastweapon;
const int N = 10;
int A[N][N], B[N][N];
int h1, w1, h2, w2; VI H;

bool dfs(int k1 = 0, int k2 = 0, int h0 = 0, int w0 = 0) {
    if (k1 == h2) {
        if (k2 == w2) {
            return 1;
        } else {
            FOR(w, w0, w1-(w2-1)+k2) {
                bool ok = 1;
                REP(i, h2) if (A[H[i]][w] != B[i][k2]) {
                    ok = 0;
                    break;
                }
                if (!ok) continue;
                if (dfs(k1, k2+1, h0, w0+1)) return 1;
            }
        }
    } else {
        FOR(h, h0, h1-(h2-1)+k1) {
            H.push_back(h);
            if (dfs(k1+1, k2, h0+1, w0)) return 1;
            H.pop_back();
        }
    }
    return 0;
}


int main(){
#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
#endif
    RD(h1, w1); REP(i, h1) REP(j, w1) RD(A[i][j]);
    RD(h2, w2); REP(i, h2) REP(j, w2) RD(B[i][j]);
    puts(dfs() ? "Yes" : "No");
}

Problem D. “redocta”.swap(i,i+1)

暴力求下逆序對。

Problem E. Blackout 2

離線後倒敘並查集做法顯然。。

#include <lastweapon/io>
#include <lastweapon/dsu>
using namespace lastweapon;
const int N = int(5e5) + 9;

int n, m, en, qn;
struct edge {
    int a, b; bool ok;
    void in() {
        RD(a, b); ok = 1;
        if (a > n) a = 0;
        if (b > n) b = 0;
    }
} E[N];
int Q[N], Z[N];


int main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    RD(n, m, en); REP(i, en) E[i].in();
    RD(qn); REP(i, qn) E[--RD(Q[i])].ok = 0;
    dsu d(n+1); REP(i, en) if (E[i].ok) d.merge(E[i].a, E[i].b);

    DWN(i, qn, 0) {
        Z[i] = d.size(0);
        d.merge(E[Q[i]].a, E[Q[i]].b);
    }

    REP(i, qn) printf("%d\n", Z[i]-1);
}

atl 的 dsu 居然還帶 size 函數。。。
至於能不能在線嘛。。。。。。
https://twitter.com/kyopro_friends/status/1558460630847594496

Problem F. Monochromatic Path

比賽時狀態設計的時 dp[2][n][m] 然後轉移寫爆了。。浪費了大量時間。。
果然狀態要 dp[2][2][n][m] 才行囧。。。

Problem G. String Fair

暴力自動機 dp,估計出一個字元串長度的上界,如果答案一直有更新就認為是無窮。

Problem Ex. Perfect Binary Tree

有點像是動態 dp。。。(但是這個題只有加葉子沒有修改。。比如我們都直到加葉子求直徑是有簡單演算法的。。)
那麼我們只要每次加一個葉子去更新向上的所有路徑即可,中間維護一下 delta 。。每次向上更新的深度不會超過 log(n)。。深度大於這個數的葉子直接跳過即可。

#include <lastweapon/number>
using namespace lastweapon;
const int N = int(3e5) + 9, LOGN = 20;
VI adj[N]; Int f[N][LOGN], s[N][LOGN]; int p[N], d[N];
int n;

void upd(int x) {
    int y = p[x]; d[x] = d[y] + 1; if (d[x] >= LOGN) return;
    Int d = f[x][0] = 1; for (int i=0;x;++i) {
        s[y][i] += d; d *= (s[y][i] - f[x][i]); f[y][i+1] += d;
        x = y; y = p[x];
    }
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    MOD = 998244353;
    RD(n); cout << (f[0][0] = 1) << endl;
    FOR(i, 1, n) {
        adj[--RD(p[i])].PB(i); upd(i);
        Int z = 0; REP(i, LOGN) z += f[0][i];
        cout << z << endl;
    }
}