Visits: 347

Codeforces Round #606 (Div. 1, based on Technocup 2020 Elimination Round 4)

As Simple as One and Two

贪心：碰到 twone 删 o，碰到 two 删 w，碰到 one 删 n。

const int N = 1.5e5 + 7;
const string t[] = {"twone", "two", "one"};
const int l[] = {5, 3, 3};
int n, v[N];
char s[N];

inline void solve() {
    vi ans;
    rds(s, n);
    for (int i = 1; i <= n; i++) v[i] = 0;
    for (int j = 0; j < 3; j++)
        for (int i = 1; i <= n; i++) {
            bool ok = 1;
            for (int k = 0; ok && k < l[j]; k++)
                if (v[i+k] || s[i+k] != t[j][k]) ok = 0;
            if (ok) {
                for (int k = 0; k < l[j]; k++) v[i+k] = 1;
                ans.pb(i + (j ? 1 : 2));
            }
        }
    print(ans.size());
    for (ui i = 0; i < ans.size(); i++)
        print(ans[i], " \n"[i+1==ans.size()]);
}

int main() {
    int T;
    rd(T);
    while (T--) solve();
    return 0;
}

Two Fairs

由于保证图连通，所以 dfs 找出从一个点出发不经过另外一个点无法到达的点数，两个答案相乘即可。

const int N = 2e5 + 7;
int n, m, a, b, v[N];
vi e[N];

void dfs(int x, int z) {
    v[x] = 1;
    for (ui i = 0; i < e[x].size(); i++) {
        int y = e[x][i];
        if (v[y] || y == z) continue;
        dfs(y, z);
    }
}

inline void solve() {
    rd(n), rd(m), rd(a), rd(b);
    for (int i = 1; i <= n; i++) e[i].clear();
    for (int i = 1, x, y; i <= m; i++) rd(x), rd(y), e[x].pb(y), e[y].pb(x);
    int c = 0, d = 0;
    for (int i = 1; i <= n; i++) v[i] = 0;
    dfs(a, b);
    for (int i = 1; i <= n; i++) c += !v[i];
    for (int i = 1; i <= n; i++) v[i] = 0;
    dfs(b, a);
    for (int i = 1; i <= n; i++) d += !v[i];
    print(1ll * (c - 1) * (d - 1));
}

int main() {
    int T;
    rd(T);
    while (T--) solve();
    return 0;
}

Beautiful Rectangle

不妨设 $r \le c$。

根据抽屉原理，若选择的数中重复个数最多为 $k$，则一个矩阵 $r \times c$ 有解当且仅当：

1. $r \times c \le n$
2. $k \le r$

必要性显然，充分性可以构造证明。

考虑将所有选择的数从小到大依次斜项填入矩阵中，可以发现这样不会造成冲突。

const int N = 4e5 + 7;
int n, a[N], b[N], d[N], t;
map< int, int > c;
set< pi > s;

inline int get() {
    if (!b[t]) --t;
    return --b[t], a[t];
}

int main() {
    rd(n);
    for (int i = 1, x; i <= n; i++) rd(x), ++c[x];
    for (auto x : c) s.insert(mp(x.se, x.fi));
    for (auto x : s) a[++t] = x.se, b[t] = x.fi;
    for (int i = 1; i <= t; i++) d[i] = d[i-1] + b[i];
    int ans = 0, p, q;
    for (int i = 1; i * i <= n; i++) {
        int o = upper_bound(b + 1, b + t + 1, i) - b - 1, x = d[o] + (t - o) * i;
        x = x / i * i;
        if (x / i >= i && ans < x) ans = x, p = i;
    }
    print(ans), print(p, ' '), print(q = ans / p);
    for (int i = 1; i <= t; i++) b[i] = min(b[i], p);
    vi e[p];
    for (int i = 0; i < p; i++) e[i].resize(q);
    for (int j = 0; j < q; j++)
        for (int i = 0; i < p; i++)
            e[i][(i+j)%q] = get();
    for (int i = 0; i < p; i++)
        for (int j = 0; j < q; j++)
            print(e[i][j], " \n"[j+1==q]);
    return 0;
}

Tree Elimination

首先，不同的序列数量等同于消除标记的方案数。

考虑树形 dp。我们称一个点被一条边覆盖，表示这个点在考虑到这条边时选择消除了这个点上的标记。

设 $f_{x,0/1/2/3}$ 分别表示：点 $x$ 是被自己的父亲边之前的边覆盖的、点 $x$ 是被自己的父亲边覆盖的、点 $x$ 是被自己的父亲边之后的边覆盖的、点 $x$ 没有被覆盖。

那么对于点 $y \in \operatorname{son}_ x$，考虑 $f_ {x,0/2}$：

• 点 $y$ 不能被覆盖，即 $f_{y,2/3}$。
• 定义点 $z (\in \operatorname{son}_ x) < y$ 是指边 $(x,z)$ 在边 $(x,y)$ 之前，则点 $z$ 一定要被覆盖，即 $f_ {z,0/1}$。
• 定义点 $z (\in \operatorname{son}_ x) > y$ 是指边 $(x,z)$ 在边 $(x,y)$ 之后，则点 $z$ 可以被覆盖也可以不被覆盖，但不能被边 $(x,z)$ 覆盖，即 $f_ {z,0/2/3}$。

因此有转移：

$$
f_ {x, 0/2} = \sum_ {y \in \operatorname{son}_ x} \left( f_ {y, 2 / 3} * \prod_ {z<y} f_ {z, 0 / 1} * \prod_ {z>y} f_ {z, 0 / 2 / 3} \right)
$$

考虑 $f_{x,1}$，有转移：

$$
f_{x, 1} = \prod_{y < fa_x} f_{y, 0 / 1} * \prod_{y > fa_x} f_{y, 0 / 2 / 3}
$$

考虑 $f_{x,3}$，有转移：

$$
f_{x,3} = \prod_{y} f_{y,0/1}
$$

时间复杂度 $\mathcal O(n)$。

const int N = 2e5 + 7;
int n, m, k;
vi e[N];
modint f[N][4], a[N], b[N], c[N];

void dfs(int x, int fa) {
    for (int y : e[x]) if (y != fa) dfs(y, x);
    a[m=k=0] = 1;
    for (int y : e[x])
        if (y == fa) k = m;
        else  ++m, a[m] = a[m-1] * (f[y][0] + f[y][1]), b[m] = f[y][2] + f[y][3], c[m] = f[y][0] + b[m];
    c[m+1] = 1;
    for (int i = m; i; i--) c[i] *= c[i+1];
    for (int i = 1; i <= m; i++) f[x][(i>k)<<1] += a[i-1] * b[i] * c[i+1];
    f[x][1] = a[k] * c[k+1], f[x][3] = a[m];
}

int main() {
    rd(n);
    for (int i = 1, x, y; i < n; i++) rd(x), rd(y), e[x].pb(y), e[y].pb(x);
    dfs(1, 0), print(f[1][0] + f[1][2] + f[1][3]);
    return 0;
}

Four Stones

题目太神仙了，先咕咕咕着。

Asterisk Substrings

题目太神仙了，先咕咕咕着。