剑锋所指,心之所向。

edu 30 场 a2e 第 4 场

本来的第 4 场被咕了很久

这场是现场参加的 contest

然后人没了,rk 3000+

3.9 - 3.10


A. Two Regular Polygons

给出 a, b\ (a < b),求 a 边形与 b 边形是否有一种摆放方式,满足二者几何中心重合且顶点均重合

数学


等价于判断 a | b

时间复杂度 O(1)

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

void solve() {
    int n, m;
    scanf("%d %d", &n, &m);
    puts((n % m == 0 )? "YES" : "NO");
}

int main() {
    int t; scanf("%d", &t);
    while (t --) solve();
    return 0;
}

B. Bogosort

给出一个序列 a,求出一个序列的 shuffle 使得对于所有整数 i, j\ (1 \leq i, j \leq |a|),都满足 a_i - i \neq a_j - j

构造


按权值逆序输出即可

正确性如下:

不妨令 i < j

则上式等价于

a_j - a_i \neq j - i

由于 j - i > 0

则我们只要保证 a_j - a_i < 0 即可

时间复杂度 O(n\log n)

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

const int MAXN = 100 + 10;

int a[MAXN], vis[100000];

void solve() {
    int n;
    scanf("%d", &n);
    memset(vis, 0, sizeof vis);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    for (int i = n; i >= 1; --i) printf("%d ", a[i]);
    puts("");
}

int main() {
    int t; scanf("%d", &t);
    while (t --) solve();
    return 0;
}

歪打正着

C. Adding Powers

初始时有长度为 n 的,元素值均为 0 的序列,对于第 i 次操作,可以选择一个元素,将该位置的数加上 k^{i - 1} 或者跳过。求是否能通过若干次操作使得这个序列等于给定序列

数学,模拟


直接暴力分解即可

时间复杂度 O(n \log_{k} n)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 30 + 10, MAXLOG = 60 + 10;
int n;
ll k, x;
bool vis[MAXLOG];

void solve() {
    scanf("%d %lld", &n, &k);
    bool is_ok = true;
    memset(vis, 0, sizeof vis);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &x);
        if (x == 0) continue;
        ll tmp = 1; int cnt = 0;
        while (tmp <= x) cnt ++, tmp = tmp * k;
        tmp = tmp / k, cnt --;
        while (1) {
            if (tmp <= x) {
                if (vis[cnt]) { is_ok = false; break; }
                else {
                    vis[cnt] = true, x -= tmp;
                }
            }
            tmp = tmp / k, cnt --;
            if (cnt == -1) break;
        }
        if (x != 0) is_ok = false;
    }
    puts(is_ok ? "YES" : "NO");
}

int main() {
    int t; scanf("%d", &t);
    while (t --) solve();
    return 0;
}

D. Count the Arrays

求单峰,有且只有两个元素值相等,长度为 n,值域为 [1, m] 的序列个数

998244353 取摸

n \leq 2*10^5

组合计数


首先从 m 个值中选取 n - 1 个数,然后这 n - 1 个数中除峰外的 n - 2 个数都可以是重复的数,并且除了峰,重复的数的数要么在峰左要么在峰右

连乘起来就是

\binom{m}{n - 1} * (n - 2) * 2^{n - 3}

时间复杂度 O(n)

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

typedef long long ll;
const ll P = 998244353;

ll qpower(ll a, int x) { if (x < 0) return 0; ll ret = 1; for (; x; x >>= 1, a = a * a % P) x & 1 ? ret = ret * a % P : 0; return ret; }

int main() {
    ll n, m, ans = 1, r = 1;
    scanf("%lld %lld", &n, &m);
    for (int i = 1; i <= m; ++i) ans = ans * i % P;
    for (int i = 1; i <= m - n + 1; ++i) r = r * i % P;
    for (int i = 1; i <= n - 1; ++i) r = r * i % P;
    ans = ans * qpower(r, P - 2) % P;
    ans = ans * (n - 2) % P;
    ans = ans * qpower(2, n - 3) % P;
    printf("%lld\n", ans);
    return 0;
}

一开始竟没发现快速幂没判 x < 0 的情况挂了(

群友的组合计数水平竟如此扎实

E. Array Shrinking

在序列 a 上操作,每次选取一个整数 i,满足 a_i = a_{i + 1},将 a_ia_{i + 1}a_i + 1 替代。问操作若干次后序列 a 最小长度

|a| \leq 10^3

dp


重要的观察:一个确定的区间,全部合并后其值一定

那么我们令 f(i, j) 表示:

如果 [i, j] 能合成成一个元素,则表示其值

否则为 0

那么有:

f(i, j) = f(i, m) + 1 \ (f(i, m) = f(m + 1, j) \neq 0)

即枚举从哪里断开

则再令 g(i) 表示

考虑完 [1, i],合并后最小长度

那么有:

g(i) = \min_{j \in [0, i), f(j + 1, i) \neq 0} g(j) + 1

时间复杂度 O(n ^ 3 + n ^ 2)

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

const int MAXN = 1e3 + 10;

int n, a[MAXN], f[MAXN][MAXN], g[MAXN], ans;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), f[i][i] = a[i];
    for (int len = 2; len <= n; ++len) {
        for (int l = 1; l <= n - len + 1; ++l) {
            int r = l + len - 1;
            for (int mid = l; mid < r; ++mid) {
                if ((f[l][mid] == f[mid + 1][r]) && f[l][mid]) { f[l][r] = f[l][mid] + 1; break; }
            }
        }
    }
    memset(g, 0x3c, sizeof g);
    g[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (f[j + 1][i]) {
                g[i] = min(g[i], g[j] + 1);
            }
        }
    }
    printf("%d\n", g[n]);
    return 0;
}

好像合并问题枚举从哪里断开是一个常见的套路呢

总结

  • C, D 写挂了,代码精细度太低。估计是写少了,好多细节都没注意过。码力太低!!!
  • 组合水平过低,不会 D

CWOI2020 BZOJ-DP 杂题选讲 题解
上一篇 «
codeforces 1288/edu. 80 题解与总结
» 下一篇