date: '2023-10-04'
title: 'Solution -「ARC 106E」Medals'

Desc.

Link.

你有 $n$ 个朋友，他们会来你家玩，第 $i$ 个人 $1...A_i$ 天来玩，然后 $A_i+1...2A_i$ 天不来，然后 $2A_i+1...3A_i$
又会来，以此类推;

每天你会选一个来玩的人，给他颁个奖，如果没人来玩，你就不颁奖。

你要给每个人都颁 $K$ 个奖，问至少需要多少天。

Sol.

前面的部分很套路了，主要看看建出二分图后我们应该做什么。首先根据 Hall's marriage theorem，我们要做的是判断任意子集的邻域大小是否大于等于该子集的大小。把 $n$ 个人拆成 $n\times k$ 个点，可以发现进行判断时不需要把同一类点（由同一个工人拆出来的 $k$ 个点）分开。设 $f(S)$ 为满足存在集合 $S$ 中任一工人会来打工的天数，则有解的一个充要条件为 $\forall S\subseteq 2^{\{1,\dots,n\}},m-f(U\setminus S) \geqslant |S|\times k$。

const int N = 18, K = 1e5;
int n, k, a[N + 5], f[2 * N * K + 5], g[1 << N];
bool check(int upp) {
    const int LIM = 1 << n, U = LIM - 1;
    for (int i=0;i<LIM;++i) g[i] = 0;
    rep (i,1,upp) g[f[i]]++;
    for (int j=0;j<n;++j) for (int i=0;i<LIM;++i) if (!(i&(1<<j))) g[i|(1<<j)] += g[i];
    for (int i=0;i<LIM;++i) if (upp - g[U^i] < __builtin_popcount(i) * k) return false;
    return true;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    rd(n, k); rds0i(a, n);
    for (int i=0;i<n;++i) {
        for (int t=0;;t+=2) for (int j=t*a[i]+1;j<(t+1)*a[i]+1;++j) {
            if (j > 2 * n * k) goto label;
            f[j] |= 1<<i;
        }
        label:;
    }
    int l = 0, r = 2 * n * k, res = -1;
    while (l <= r) {
        if (int mid = (l + r) / 2; check(mid)) r = mid - 1, res = mid;
        else l = mid + 1;
    }
    cout << res << "\n";
}

date: '2023-09-28'
title: 'Solution -「JOISC 2020」建筑装饰 4'

朴素的 DP 形式是定义 $f_{i, j, A/B}$ 表示前 $i$ 个元素选择了 $j$ 个 $A$ 的可达性. $\mathcal O(n^2)$. 交换状态与值域, 定义 $f_{i, A/B, A/B}$ 表示前 $i$ 个元素中的最后一个元素 (即 $i$) 选择了 $A/B$, 在最大化 $A/B$ 的数量的目标下求得的 $A/B$ 的数量.

转移在代码注释里, 答案倒着构造.

/**
 * dp[i][A/B][A/B]: 前 i 个, 第 i 个选 A 还是 B, 最大化 A/B 的数量
 * a[i] >= a[i-1]: dp[i-1][A][A]+1 -> dp[i][A][A]; dp[i-1][A][B] -> dp[i][A][B]
 * a[i] >= b[i-1]: dp[i-1][B][A]+1 -> dp[i][A][A]; dp[i-1][B][B] -> dp[i][A][B]
 * b[i] >= a[i-1]: dp[i-1][A][B]+1 -> dp[i][B][B]; dp[i-1][A][A] -> dp[i][B][A]
 * b[i] >= b[i-1]: dp[i-1][B][B]+1 -> dp[i][B][B]; dp[i-1][B][A] -> dp[i][B][A]
*/
enum Element {A, B};
const int N = 1e6;
int n, a[N + 100], b[N + 100], f[N + 100][2][2];
char ans[N + 100];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    rd(n), rds(a, 2 * n) , rds(b, 2 * n);
    rep (i, 1, 2 * n) {
        if (a[i] >= a[i - 1]) {
            chkmax(f[i][A][A], f[i - 1][A][A] + 1);
            chkmax(f[i][A][B], f[i - 1][A][B]);
        }
        if (a[i] >= b[i - 1]) {
            chkmax(f[i][A][A], f[i - 1][B][A] + 1);
            chkmax(f[i][A][B], f[i - 1][B][B]);
        }
        if (b[i] >= a[i - 1]) {
            chkmax(f[i][B][B], f[i - 1][A][B] + 1);
            chkmax(f[i][B][A], f[i - 1][A][A]);
        }
        if (b[i] >= b[i - 1]) {
            chkmax(f[i][B][B], f[i - 1][B][B] + 1);
            chkmax(f[i][B][A], f[i - 1][B][A]);
        }
    }
    int cnt[2] = {}, last = 1e9;
    drep (i, 2 * n, 1) {
        if (cnt[A] + f[i][A][A] >= n && cnt[B] + f[i][A][B] >= n && a[i] <= last) last = a[i], ans[i] = 'A', cnt[A]++;
        else if (cnt[A] + f[i][B][A] >= n && cnt[B] + f[i][B][B] >= n && b[i] <= last) last = b[i], ans[i] = 'B', cnt[B]++;
        else {
            cout << "-1\n"; return 0;
        }
    }
    copy_n(ans + 1, 2 * n, ostream_iterator<char>(cout, ""));
}

date: '2023-09-28'
title: 'Solution -「模拟赛」草莓蛋糕'

$\max(a_x + a_y, b_y + b_x)$ 的贡献形式不是独立的，并不好进行分析。考虑通过分类讨论将 $\max$ 拆开。若令 $h_i = a_i - b_i$，$h'_i = b_i - a_i$，可以发现若 $h_x \geqslant h'_y$ 取值则为 $b_x + b_y$，反之亦然。

注意到 $h$ 本身自带一个一维偏序关系，于是放到数轴上用线段树维护，每个节点维护 $a_x$，$a_y$，$b_x$，$b_y$ 的最小值，以及区间的答案。修改操作在线段树的叶子节点维护四个 std::multiset 即可。

const int N = 1e6;
const int INF = numeric_limits<int>::max();
int Q, opt[N + 100], cat[N + 100], a[N + 100], b[N + 100];
using MSET = multiset<ll>;
struct node {
    ll mn[4], ans;
    node() : ans(INF) {
        for (int i = 0; i < 4; ++i) mn[i] = INF;
    }
};
struct SegmentTree {
#define NODE int u, int l, int r
#define mid (((l) + (r)) / 2)
#define ls (u * 2)
#define rs (u * 2 + 1)
#define LC ls, l, mid
#define RC rs, mid + 1, r
#define SetAcc(id, i) (*leaves[id][i].begin())
    const int __n;
    vector<node> body;
    vector<array<MSET, 4>> leaves;
    void pullup(int u) {
        body[u].ans = min({body[ls].mn[2] + body[rs].mn[0], body[ls].mn[1] + body[rs].mn[3], body[ls].ans, body[rs].ans});
        for (int i = 0; i < 4; ++i) body[u].mn[i] = min(body[ls].mn[i], body[rs].mn[i]);
    }
    void upd(int pos, NODE) {
        if (l == r) {
            for (int i = 0; i < 4; ++i) body[u].mn[i] = SetAcc(l, i);
            body[u].ans = min(SetAcc(l, 0) + SetAcc(l, 2), SetAcc(l, 1) + SetAcc(l, 3));
        } else mid >= pos ? upd(pos, LC) : upd(pos, RC), pullup(u);
    }
public:
    void upd(int pos) {upd(pos,1,1,__n);}
    int Ask() {return body[1].ans;}
    SegmentTree(int n) : __n(n), body(4 * n + 5), leaves(n + 5) {
        rep (j, 1, n) for (int i = 0; i < 4; ++i) leaves[j][i].emplace(INF);
    }
};
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    rd(Q);
    bsi dat;
    rep (i, 1, Q) {
        rd(opt[i], cat[i], a[i], b[i]);
        dat.pb(cat[i] == 0 ? a[i] - b[i] : b[i] - a[i]);
    }
    sort(allu(dat)), dat.resize(distance(dat.begin(), unique(allu(dat))));
    auto getter = [&](int x) -> int {
        return distance(dat.begin(), lower_bound(allu(dat), x)) + 1;
    };
    const int dataLength = dat.size();
    SegmentTree treeask(dataLength);
    rep (i, 1, Q) {
        int pos = getter(cat[i] == 0 ? a[i] - b[i] : b[i] - a[i]);
        assert(1 <= pos && pos <= dataLength);
        auto& cur = treeask.leaves[pos];
        int idx = 2 * cat[i];
        if (opt[i] == 1) cur[idx].emplace(a[i]), cur[idx + 1].emplace(b[i]);
        else cur[idx].erase(cur[idx].find(a[i])), cur[idx + 1].erase(cur[idx + 1].find(b[i]));
        treeask.upd(pos);
        int res = treeask.Ask();
        if (res >= INF) cout << "-1\n";
        else cout << res << "\n";
    }
}

date: '2023-09-22'
title: 'Solution -「HDU」Ridiculous Netizens'

Desc.

给定一棵 $N$ 个节点无根树，找出满足以下条件的集合 $S$ 的数量：

• $S \subseteq \{1,\dots,n\}$；
• $S$ 的导出子图联通；
• $\displaystyle\prod_{v \in S} a_v \leqslant M$。

Sol.

点分治，统计包括当前分治中心的集合数量，如果从子树的角度入手会发现并不好做——合并这一步就卡死了。考虑以 DFN 为状态，设 $f(i,j)$ 表示在子树中 DFN 序排后 $i$ 个节点中选出了乘积为 $j$ 的集合。这个状态实际上是很浪费空间的，那么使用根号分治，另令 $g(i, j)$ 表示乘积 $\frac{M}{j}$ 时的方案数，这样就开得下了。

const int MN = 2e3, B = 1e3;
int n, m, a[MN + 100], f[MN + 100][B + 100], g[MN + 100][B + 100];
int sz[MN + 100], res, rev[MN + 100], Time, mxsb[MN + 100], rt;
bool vis[MN + 100];
vvi grp;
void getsz(int u, int Fu) {
    sz[u] = 1; for (int v : grp[u]) if (v != Fu && !vis[v]) getsz(v, u), sz[u] += sz[v];
}
void getrt(int u, int Fu, int all) {
    mxsb[u] = all-sz[u];
    for (int v : grp[u]) if (v != Fu && !vis[v]) {
        getrt(v, u, all); chkmax(mxsb[u], sz[v]);
    }
    if (rt == 0 || mxsb[u] < mxsb[rt]) rt = u;
}
void dfs(int u, int Fu) {
    rev[Time++] = u;
    for (int v : grp[u]) if (v != Fu && !vis[v]) dfs(v, u);
}
void solve(int u) {
    rt = 0; getsz(u, n); getrt(u, n, sz[u]); vis[rt] = 1; Time = 0; dfs(rt, n); getsz(rt, n);
    rep(Time+1) {
        memset(f[i], 0, sizeof f[i]);
        memset(g[i], 0, sizeof g[i]);
    }
    f[Time][1] = 1;
    drep(i,Time-1,0) {
        int w = a[rev[i]];
        // Putting @i into the component.
        rep(j,1,B+1) {
            if (j <= B / w) add_eq(f[i][j * w], f[i+1][j]);
            else if ((m / j) / w > 0) add_eq(g[i][(m / j) / w], f[i+1][j]);
        }
        rep(j,w,B+1) add_eq(g[i][j/w], g[i+1][j]);
        // Putting @i out of the component, skipping its subtree.
        rep(j,1,B+1) {
            add_eq(f[i][j], f[i+sz[rev[i]]][j]);
            add_eq(g[i][j], g[i+sz[rev[i]]][j]);
        }
    }
    rep(i,1,min(B, m)+1) add_eq(res, add(f[0][i], g[0][i]));
    rep(i,min(B, m),B+1) add_eq(res, g[0][i]);
    sub_eq(res, 1);
    for (int v : grp[rt]) if (!vis[v]) solve(v);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> m;
    grp = vvi(n);
    rep(n) cin >> a[i];
    rep(n-1) {int u,v; cin >> u >> v; u--; v--; grp[u].pb(v); grp[v].pb(u);}
    solve(0); cout << res << "\n";
}

poj 2888

n 种轮换（$|G|=n$）

第 i 种可以分成长度为 $\frac{n}{\gcd(n,i)}$ 的 $\gcd(n,i)$ 个轮换

$\forall g\in G$，$|X^g|$（不定点个数）等于规模为 $\gcd(n,i)$ 的环的答案然后搞一搞

傻逼poj

P4916

枚举 $d$

转化成有 $d$ 个球，要染 $\frac md$ 个，不能有连续 $k$ 个被染色

考虑插板，有 $\frac{m}{d}$ 个色球，$d-\frac{m}{d}$ 个无色球，把色球插入无色球之间

断换成链的手段是枚举首尾之间插入的色球数量

$\displaystyle \sum_{i=0}^k(i+1)\times f(\frac{m}{d}-i,\frac nd-\frac{m}{d}-1,k)$

$f(n,m,k)$ 表示把 $n$ 个球分成 $m$ 组，每组不超过 $k$ 个的方案数（容斥）

p4128

把点置换转化成边置换，再用 Polya（大体思路）

设点置换群 $\lang G,\cdot \rang$，取某个 $g \in G$，$g=\prod_i (a_{i,1},a_{i,2},...,a_{i,n_i})$

• $\forall i\neq j$，研究 $(a_i)$ 和 $(a_j)$

  比如 $(u,v)$，会被置换成 $(u+1,v+1)$，$(u+2,v+2)$，直到 $(u+\mathrm{lcm}(n,m),v+\mathrm{lcm}(n,m))$。置换的长度就是两个环的长度的 $\mathrm{lcm}$，一共有 $n\times m$ 个元素，所以一共 $\frac{nm}{\mathrm{lcm}(n,m)}=\gcd(n,m)$ 个循环

• 研究 $(a_i)$（同一个循环节里面）

  $\frac n2$ 个循环

设 $g$ 拆成 $k$ 个循环

边循环个数 $\sum_{i}^k \frac{n_i}2+\sum_{i=1}^{k-1}\sum_{j=i+1}^k \gcd(n_i,n_j)$

不能枚举 $n!$ 种点排列

发现如果 $\{n_k\}$ 相同，贡献相同

$\{n_k\}$ 加起来是 $n$，枚举 $n$ 的分拆数（妙）

算 $\{n_k\}$ 的贡献系数：钦定 $n_1 \leqslant n_2 \leqslant \dots \leqslant n_k$，把每个循环看作圆排列，设 $t_i$ 为长度为 $i$ 的循环数，则系数为 $\frac{n!}{\prod n_i \prod t_i!}$

dfs+Polya 计算