codeforces 1288/edu. 80 题解与总结

30 场 edu a2e 第 3 场

2.26 - 2.28

A.Deadline

求函數 f(x) = x + \big\lceil \dfrac{d}{x + 1} \big\rceil 最小值与 n 的大小关系

数学

令 f'(x) = x + 1 + \big\lceil \dfrac{d}{x + 1} \big\rceil，则 f(x) 最小值为 f'(x) 最小值减 1

令 a = x + 1，则 f'(x) = \big\lceil \dfrac{a ^2 + d}{a} \big\rceil

由不等式 a ^ 2 + b ^ 2 \geq 2ab 可以得到 f'(x) 最小值为 \big\lceil \dfrac{2a\sqrt{d}}{a} \big\rceil，即 \big\lceil 2\sqrt{d} \big\rceil

时间复杂度 O(1)

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

void solve() {
    int a, b;
    scanf("%d %d", &a, &b);
    puts(ceil(2.0 * sqrt(b)) > a + 1 ? "NO" : "YES");
}

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

不会数学自闭了

B.Yet Another Meme Problem

求满足下列要求整数对 (x, y) 的个数

其中 \overline{xy} 表示将 y 拼接在 x 后形成的整数

数学

记 l 为 x 在十进制下的位数

发现方程只与 y 相关，即只要 y 为形如若干个 9 组成的整数，对于所有 x (1 \leq x \leq a) 都满足上述方程

则只要求出 [1, b] 内有多少个形如若干个 9 的数，乘上 a 即可

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

typedef long long ll;

void solve() {
    int a, b; ll ans = 0;
    scanf("%d %d", &a, &b);
    for (ll i = 10; ; i *= 10) {
        if ((i - 1) > b) break;
        ans += a;
    }
    printf("%lld\n", ans);
}

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

C.Two Arrays

求序列对 (A, B) 个数，满足：

1. |A| = |B| = m
2. A 单调不降，B 单调不升
3. A_i \leq B_i
4. 1 \leq A_i, B_i \leq n

DP，组合数学

DP 做法

由于不关心具体的值，所以对今后的选择有影响的只有 B_i - A_i ，所以我们令 f(i, j) 表示 1 \cdots i 位已经确定，且第 i 为的差为 j 的方案数，则有转移：

即对于每种 f(i - 1, k) 的方案都有 (k - j + 1) 种方法使得差变为 j

时间复杂度 O(nm^2)

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

typedef long long ll;

const int MAXM = 1e3 + 10, MAXN = 10 + 10, P = 1e9 + 7;

int n, m;
ll f[MAXN][MAXM], fans;

int main() {
    scanf("%d %d", &m, &n);
    for (int i = 0; i < m; ++i) f[1][i] = m - i;
    for (int i = 2; i <= n; ++i) {
        for (int j = 0; j < m; ++j) {
            for (int k = j; k < m; ++k) f[i][j] = (f[i][j] + (f[i - 1][k] * (k - j + 1)) % P) % P;
        }
    }
    for (int i = m - 1; i >= 0; --i) fans = (fans + f[n][i]) % P;
    printf("%lld\n", fans % P);
    return 0;
}

组合计数做法

考虑将 B 翻转并拼接在 A 后，可以得到一个序列 A_1, A_2 \cdots A_m, B_m, B_{m - 1} \cdots B_1，且该序列满足长度为 2m，单调不降，且 B_1 \leq n

则问题转化为求长度为 2m，值域为 [1, n] 的单调不降序列个数

令 x_i 表示序列中 i 的出现次数，那么我们有

即将 2m 个元素划分成 n 个集合（允许存在空集），其方案数为

暴力阶乘即可

时间复杂度 O(nm)

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

typedef long long ll;

const int P = 1e9 + 7;

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

ll n, m, ans;

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

妙死了

D.Minimax Problem

给出 n*m 矩阵 A，任意选择两个整数 i, j\ (1 \leq i, j, \leq n)， 使得 \displaystyle \min_{k = 1}^m \max(A_{i, k}, A_{j, k}) 最大。输出 i, j

n \leq 10^5, m \leq 8

二分答案，状压

一眼套路二分答案

二分这个最大的值 x，并将整个矩阵中大于等于 x 的数记为 1，否则记为 0

对于每列我们记录 S(i) 表示第 i 行为 1 的位组成的集合

这个二分出的值为真当且仅当存在至少两行 i, j 使得 S(i) \operatorname{or} S(j) = \{q \mid 1 \leq q \leq m\}

那么我们记录 c(S) 表示状态为 S 的集合可以与什么集合进行 \operatorname{or} 使得结果为 \{q \mid 1 \leq q \leq m\}，向下传递维护 c 即可

时间复杂度 O(knm^3)，其中 k 为在值域上二分的次数，大约为 32

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

const int MAXN = 3e5 + 10, MAXM = 8 + 10, MAXVAL = 5e5;

int n, m, val[MAXN][MAXM], ans1, ans2;

bool check(int x) {
    int num[MAXN], cnt[MAXVAL], MAXS = (1 << m) - 1; // cnt[S] 表示与状态为 S 的序列并起来合法的序列的编号
    memset(num, 0, sizeof num), memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) if (val[i][j] >= x) num[i] |= (1 << (j - 1));
        int cpm = MAXS ^ num[i];
        cnt[cpm] = i;
        for (int tmp = num[i]; tmp; tmp = (tmp - 1) & num[i]) cnt[tmp | cpm] = i;
    }
    for (int i = 1; i <= n; ++i) {
        if (cnt[num[i]]) { ans1 = i, ans2 = cnt[num[i]]; return true; }
    }
    return false;
}

int main() {
    scanf("%d %d", &n, &m);
    int l = 0, r = 0, ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) scanf("%d", &val[i][j]), r = max(r, val[i][j]);
    }
    while (l <= r) {
        int mid = (l + r) >> 1;
        check(mid) ? l = mid + 1, ans = mid : r = mid - 1;
    }
    printf("%d %d\n", ans1, ans2);
    return 0;
}

E.Messenger Simulator

维护一个长度为 n 的，初始是 1, 2, \cdots n 的序列中每一个元素的全局下标最上最下值，支持 m 次操作，操作为将某个元素移动至第一个位，剩下的元素向后补齐

n, m \leq 3e5

数据结构，单点修改，区间前缀和

维护最上十分简单，如果一个数 i 被操作了就是 1，否则是 i

首先是一个重要的观察：一个数最下下标只可能在两种情况中出现：

1. 在对与这个数的某次操作之前
2. 终态

以及一个非常关键的小 trick 是，对一个元素的操作可以转换为将一个元素的下标变为全局最上下标 -1，其在序列上的位置为比他小的下标的个数 +1

那么问题变为单点修改，全局求 rk

可以用平衡树实现，也可以使用 BIT

对于 BIT 做法，维护其下标的值域，具体而言，维护长度为 n + m 的 01 序列，一开始 m + 1, m + 2 \cdots m + n 这些位置为 1，记录一个 cur 为当前最小下标，记录值为 i 的元素的下标值 idx(i)。对于一次操作 x，首先更新 x 的最下值，查询 BIT 中 idx(x) 的前缀和（这就是 x 在序列中的真实下标）。将 BIT 中 idx(x) 这个位置置为 0，并将 cur - 1 置为 1，并更新 idx(x)

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

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

const int MAXN = 6e5 + 10;

int n, m, bit[MAXN], ansmax[MAXN], ansmin[MAXN], pos[MAXN];

void add(int pos, int val) { for (int i = pos; i <= n + m; i += (i & (-i))) bit[i] += val; }
int query(int pos) { int ret = 0; for (int i = pos; i; i -= (i & (-i))) ret += bit[i]; return ret; }

int main() {
    scanf("%d %d", &n, &m);
    iota(ansmax + 1, ansmax + n + 1, 1), iota(ansmin + 1, ansmin + n + 1, 1), iota(pos + 1, pos + n + 1, m + 1);
    for (int i = 1; i <= n; ++i) add(pos[i], 1);
    int idx = m;
    for (int _ = 1, x; _ <= m; ++_) {
        scanf("%d", &x);
        ansmin[x] = 1;
        ansmax[x] = max(ansmax[x], query(pos[x]));
        add(pos[x], -1);
        pos[x] = idx --;
        add(pos[x], 1);
    }
    for (int x = 1; x <= n; ++x) ansmax[x] = max(ansmax[x], query(pos[x])), printf("%d %d\n", ansmin[x], ansmax[x]);
    return 0;
}

这个小 trick 不明觉厉

总结

好

1. D 独立地，很快的写出来了
2. 做题速度加快了很多，3 天昨晚

不好

1. 数学能力有待加强
2. 写题解的非常之慢，以后应该是 3 天之内就要把题解挂到博客上去