剑锋所指,心之所向。

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) 的个数

\begin{cases} xy + x + y = \overline{xy} \\ 1 \leq x \leq a \\ 1 \leq y \leq b \end{cases}

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

数学


lx 在十进制下的位数

\because xy + x + y = \overline{xy} \\ \therefore xy + x + y = 10^lx + y \\ \therefore x(y + 1) = 10^lx \\ \therefore y + 1 = 10^l

发现方程只与 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, j) \leftarrow f(i, j) + f(i - 1, k) * (k - j + 1) \mid 0\leq j \leq k

即对于每种 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 的出现次数,那么我们有

\begin{cases} x_i \geq 0 \\ \sum_{i = 1}^{n} x_i = 2m \end{cases}

即将 2m 个元素划分成 n 个集合(允许存在空集),其方案数为

\binom{n + 2m - 1}{n - 1}

暴力阶乘即可

时间复杂度 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 + m01 序列,一开始 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 天之内就要把题解挂到博客上去

codeforces 1312/edu. 83 题解与总结
上一篇 «
codeforces 1295/edu. 81 题解与总结
» 下一篇