传送门

• https://atcoder.jp/contests/abc264

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;
    }
}

Posted by xiaodao
Category: 日常