ABC317

Arghariza · 2023-08-26 22:39:43 · 个人记录

• A
• B
• C
• D
• E
• F

数位 DP，直接设 f_{pos,o1,o2,o3,f1,f2,f3,p1,p2,p3} 表示二进制从高到低考虑到第 pos 位，x_1/x_2/x_3 是否顶上界/是否是 0，分别模 a_1,a_2,a_3 的值，枚举 x_1/x_2 这一位填啥转移即可。

// Problem: F - Nim
// Contest: AtCoder - GAMEFREAK Programming Contest 2023 (AtCoder Beginner Contest 317)
// URL: https://atcoder.jp/contests/abc317/tasks/abc317_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace vbzIO {
    char ibuf[(1 << 20) + 1], *iS, *iT;
    #if ONLINE_JUDGE
    #define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
    #else
    #define gh() getchar()
    #endif
    #define mt make_tuple
    #define mp make_pair
    #define fi first
    #define se second
    #define pc putchar
    #define pb emplace_back
    #define ins insert
    #define era erase
    typedef tuple<int, int, int> tu3;
    typedef pair<int, int> pi;
    inline int rd() {
        char ch = gh();
        int x = 0;
        bool t = 0;
        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
        return t ? ~(x - 1) : x;
    }
    inline void wr(int x) {
        if (x < 0) x = ~(x - 1), putchar('-');
        if (x > 9) wr(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace vbzIO;

const int P = 998244353;
int n, a[3], f[100][2][2][2][2][2][2][15][15][15];

int dfs(int pos, int o1, int o2, int o3, int f1, int f2, int f3, int p1, int p2, int p3) {
    if (pos < 0) {
        if (!f1 && !f2 && !f3 && !p1 && !p2 && !p3) return 1;
        return 0;
    }
    if (f[pos][o1][o2][o3][f1][f2][f3][p1][p2][p3]) return f[pos][o1][o2][o3][f1][f2][f3][p1][p2][p3];
    int ans = 0;
    for (int i = 0; i <= 1; i++) {
        for (int j = 0; j <= 1; j++) {
            int k = i ^ j;
            int P1 = (i * (1ll << pos) % a[0] + p1) % a[0];
            int P2 = (j * (1ll << pos) % a[1] + p2) % a[1];
            int P3 = (k * (1ll << pos) % a[2] + p3) % a[2];
            if (o1 && i > ((n >> pos) & 1)) continue;
            if (o2 && j > ((n >> pos) & 1)) continue;
            if (o3 && k > ((n >> pos) & 1)) continue;
            int O1 = o1 & (i == ((n >> pos) & 1));
            int O2 = o2 & (j == ((n >> pos) & 1));
            int O3 = o3 & (k == ((n >> pos) & 1));
            int F1 = f1 & (!i);
            int F2 = f2 & (!j);
            int F3 = f3 & (!k);
            (ans += dfs(pos - 1, O1, O2, O3, F1, F2, F3, P1, P2, P3)) %= P;
        }
    }
    return f[pos][o1][o2][o3][f1][f2][f3][p1][p2][p3] = ans;
}

signed main() {
    n = rd();
    for (int i = 0; i < 3; i++) a[i] = rd();
    wr(dfs(63, 1, 1, 1, 1, 1, 1, 0, 0, 0));
    return 0;
}

• G

网络流，相当于求 m 对匹配。

分 m 次跑二分图匹配即可。

// Problem: G - Rearranging
// Contest: AtCoder - GAMEFREAK Programming Contest 2023 (AtCoder Beginner Contest 317)
// URL: https://atcoder.jp/contests/abc317/tasks/abc317_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace vbzIO {
    char ibuf[(1 << 20) + 1], *iS, *iT;
    // #if ONLINE_JUDGE
    // #define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
    // #else
    #define gh() getchar()
    // #endif
    #define mt make_tuple
    #define mp make_pair
    #define fi first
    #define se second
    #define pc putchar
    #define pb emplace_back
    #define ins insert
    #define era erase
    typedef tuple<int, int, int> tu3;
    typedef pair<int, int> pi;
    inline int rd() {
        char ch = gh();
        int x = 0;
        bool t = 0;
        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
        return t ? ~(x - 1) : x;
    }
    inline void wr(int x) {
        if (x < 0) x = ~(x - 1), putchar('-');
        if (x > 9) wr(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace vbzIO;

const int N = 250;
const int inf = 1e18;

struct edge { int to, nxt, w; } e[(N * N) << 1];
int n, m, s, t, a[N][N], l[N], r[N], ans[N][N], tot = 1, dep[N], head[N];
int p[N], c[N];

void add_edge(int u, int v, int w) {
    e[++tot] = (edge) { v, head[u], w };
    head[u] = tot;
}

void add_flow(int u, int v, int w) {
    add_edge(u, v, w), add_edge(v, u, 0);
}

bool bfs() {
    memset(dep, 0, sizeof(dep));
    dep[s] = 1;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if (!dep[v] && e[i].w) {
                q.push(v);
                dep[v] = dep[u] + 1;
            }
        }
    } 
    return dep[t];
}

int dfs(int u, int in) {
    if (u == t) return in;
    int out = 0;
    for (int i = head[u]; i && in; i = e[i].nxt) {
        int v = e[i].to;
        if (e[i].w && dep[v] == dep[u] + 1) {
            int res = dfs(v, min(in, e[i].w));
            e[i].w -= res;
            e[i ^ 1].w += res;
            in -= res;
            out += res;
        }
    }
    if (!out) dep[u] = 0;
    return out;
}

signed main() {
    n = rd(), m = rd(), s = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) 
            a[i][j] = rd();
    for (int _ = 1; _ <= m; _++) {
        int cnt = s = 0;
        t = 2 * n + 1;
        for (int i = 0; i <= n * 2 + 1; i++) head[i] = 0;
        tot = 1;
        for (int i = 1; i <= n; i++) add_flow(s, i, 1);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (a[i][j] > 0) add_flow(i, a[i][j] + n, 1);
        for (int i = 1; i <= n; i++)
            add_flow(i + n, t, 1);
        int tp = 0;
        while (bfs()) tp += dfs(s, inf);
        if (tp != n) return puts("No"), 0;
        for (int i = 1; i <= n; i++)
            for (int j = head[i]; j; j = e[j].nxt)
                if (!e[j].w) p[i] = e[j].to - n;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a[i][j] == p[i]) {
                    ans[i][++c[i]] = p[i];
                    a[i][j] = -1;
                    break;
                }
            }
        }
    }
    puts("Yes");
    for (int i = 1; i <= n; i++, puts(""))
        for (int j = 1; j <= m; j++)
            wr(ans[i][j]), pc(' ');
    return 0;
}

• Ex

别想了，不会。