AtCoder Beginner Contest 251 Solution

更好的阅读体验戳此进入

题面链接

题面 Luogu 链接

老样子abc太水了就跳了

[ABC251D] At Most 3 (Contestant ver.)

题面

给你整数 $W(1\le W\le {10}^6)$$W(1 \le W \le 10^6)$。 你必须构造一个数组 $a$$a$，包含最多 $300$$300$ 个元素，使得小于等于 $W$$W$ 的所有正整数都可以被 $a$$a$ 数组的元素相加表示出来。

Solution

显然按照十进制拆分成三组即可，即 $[1,99],[100,9900],[10000,990000]$$[1, 99], [100, 9900], [10000, 990000]$ 即可，共 $99\times 3=297$$99 \times 3 = 297$ 个。

Code

xxxxxxxxxx
47
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int > 
23
inline T read(void);
24

25
int main(){
26
    printf("297\n");
27
    for(int i = 1; i <= 99; ++i)printf("%d %d %d ", i, i * 100, i * 10000);
28
    printf("\n");
29
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
30
    return 0;
31
}
32

33
template < typename T >
34
inline T read(void){
35
    T ret(0);
36
    int flag(1);
37
    char c = getchar();
38
    while(c != '-' && !isdigit(c))c = getchar();
39
    if(c == '-')flag = -1, c = getchar();
40
    while(isdigit(c)){
41
        ret *= 10;
42
        ret += int(c - '0');
43
        c = getchar();
44
    }
45
    ret *= flag;
46
    return ret;
47
}

[ABC251E] Takahashi and Animals

题面

有 $n$$n$ 只动物围成一圈，你可以花费 $a[i]$$a[i]$ 喂食动物 $i$$i$ 和 $i+1$$i+1$。特别地，你可以花费 $a[n]$$a[n]$ 喂食动物 $n$$n$ 和 $1$$1$。

输出喂食所有动物需要的最小花费。

Solution

DP 显然，令 $dp(i,0/1)$$dp(i, 0/1)$ 表示考虑前 $i$$i$ 个元素且最后一个元素不喂 / 喂的最小花费。转移显然，注意要考虑一下 $N$$N$ 和 $1$$1$ 之间，具体选择哪个即可。

Code

xxxxxxxxxx
63
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int N;
26
int a[310000];
27
ll dp[310000][2];
28

29
int main(){
30
    N = read();
31
    for(int i = 1; i <= N; ++i)a[i] = read();
32
    memset(dp, 0x3f, sizeof dp);
33
    dp[1][1] = a[1];
34
    for(int i = 2; i <= N; ++i)
35
        dp[i][0] = dp[i - 1][1],
36
        dp[i][1] = min(dp[i - 1][1], dp[i - 1][0]) + a[i];
37
    // for(int i = 1; i <= N; ++i)printf("%d: 0 = %lld, 1 = %lld\n", i, dp[i][0], dp[i][1]);
38
    ll ans = min(dp[N][1], dp[N][0]);
39
    dp[1][0] = 0;
40
    for(int i = 2; i <= N; ++i)
41
        dp[i][0] = dp[i - 1][1],
42
        dp[i][1] = min(dp[i - 1][1], dp[i - 1][0]) + a[i];
43
    ans = min(ans, dp[N][1]);
44
    printf("%lld\n", ans);
45
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
46
    return 0;
47
}
48

49
template < typename T >
50
inline T read(void){
51
    T ret(0);
52
    int flag(1);
53
    char c = getchar();
54
    while(c != '-' && !isdigit(c))c = getchar();
55
    if(c == '-')flag = -1, c = getchar();
56
    while(isdigit(c)){
57
        ret *= 10;
58
        ret += int(c - '0');
59
        c = getchar();
60
    }
61
    ret *= flag;
62
    return ret;
63
}

[ABC251F] Two Spanning Trees

题面

给定无向连通简单图，求其两个以 $1$$1$ 为根的生成树 $T_1,T_2$$T_1, T_2$，满足：

• 对于 $T_1$$T_1$，其任意一条非树边连结的两个节点均存在祖先关系，即一个点为另一个点的祖先。
• 对于 $T_2$$T_2$，其任意一条非树边连结的两个节点均不存在祖先关系。

Solution

前者对图 DFS，后者对图 BFS，证明显然。

Code

xxxxxxxxxx
83
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
struct Edge{
26
    Edge* nxt;
27
    int to;
28
    OPNEW;
29
}ed[410000];
30
ROPNEW(ed);
31
Edge* head[410000];
32

33
int N, M;
34
bool vis[210000];
35

36
void dfs(int p = 1){
37
    vis[p] = true;
38
    for(auto i = head[p]; i; i = i->nxt){
39
        if(vis[SON])continue;
40
        printf("%d %d\n", p, SON);
41
        dfs(SON);
42
    }
43
}
44
void bfs(void){
45
    memset(vis, false, sizeof vis);
46
    queue < int > cur;
47
    cur.push(1), vis[1] = true;
48
    while(!cur.empty()){
49
        int tp = cur.front(); cur.pop();
50
        for(auto i = head[tp]; i; i = i->nxt){
51
            if(vis[SON])continue;
52
            printf("%d %d\n", tp, SON);
53
            vis[SON] = true, cur.push(SON);
54
        }
55
    }
56
}
57

58
int main(){
59
    N = read(), M = read();
60
    for(int i = 1; i <= M; ++i){
61
        int s = read(), t = read();
62
        head[s] = new Edge{head[s], t};
63
        head[t] = new Edge{head[t], s};
64
    }dfs(), bfs();
65
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
66
    return 0;
67
}
68

69
template < typename T >
70
inline T read(void){
71
    T ret(0);
72
    int flag(1);
73
    char c = getchar();
74
    while(c != '-' && !isdigit(c))c = getchar();
75
    if(c == '-')flag = -1, c = getchar();
76
    while(isdigit(c)){
77
        ret *= 10;
78
        ret += int(c - '0');
79
        c = getchar();
80
    }
81
    ret *= flag;
82
    return ret;
83
}

G 是计算几何，暂时跳了，以后有机会再回来做

[ABC251Ex] Fill Triangle

题面

存在序列 $a_n$$a_n$，将其压缩后给定。具体地，给定序列 $P$$P$ 以如下形式：$((a_1,c_1),(a_2,c_2),\cdots ,(a_m,c_m))$$((a_1, c_1), (a_2, c_2), \cdots, (a_m, c_m))$，表示序列 $a$$a$ 中有 $c_1$$c_1$ 个 $a_1$$a_1$，$c_2$$c_2$ 个 $a_2$$a_2$，以此类推，且按序拼接。令序列 $a_n$$a_n$ 为三角金字塔 $B$$B$ 的第 $n$$n$ 层，即 $B(n,i)=a_i$$B(n, i) = a_i$。特别地，该三角金字塔的递推式为 $B(i,j)=(B(i+1,j)+B(i+1,j+1))mod7$$B(i, j) = (B(i + 1, j) + B(i + 1, j + 1)) \bmod{7}$。给定 $k$$k$，求该三角金字塔第 $k$$k$ 层的序列。

Solution

首先可以尝试随意给定一个序列 $a_n$$a_n$ 并打表，或手推一下，假设 $n=5$$n = 5$，有：

不难发现这玩意每一项实际上就是二项式系数，或者说杨辉三角。并且还能发现，对于每一行的元素，它们的系数均相同，不同的只是将下标整体向右平移了一位。

此时我们便可以根据这个性质，求出对于第 $k$$k$ 层，第 $x$$x$ 列的元素，有：

显然我们想要算出 $k$$k$ 层的所有元素，但是直接套这个式子暴力算是肯定过不了的。考虑优化。

显然序列 $a$$a$ 是由一段一段的相同元素构成的，而我们的查询就是在 $a$$a$ 里的查询一个区间然后按序将组合数乘上去。当我们从 $B(k,x)$$B(k, x)$ 到 $B(k,x+1)$$B(k, x + 1)$ 的时候，通过我们之前的结论可知需要将下标向右平移一位，而所有组合数的值不变，大概的过程如图：

观察发现，这个东西平移之后，对于大多数的 $(\genfrac{}{}{0ex}{}{n-k}{i})\times a_{x+i}$${n - k \choose i} \times a_{x + i}$ 变成 $(\genfrac{}{}{0ex}{}{n-k}{i})\times a_{x+i+1}$${n - k \choose i} \times a_{x + i + 1}$，都存在 $a_{x+i}=a_{x+i+1}$$a_{x + i} = a_{x + i + 1}$，而对于这些的贡献是完全不变的。不难想到这个变化操作的复杂度最多是 $O(m)$$O(m)$ 的。所以当我们确定了 $B(k,1)$$B(k, 1)$ 之后，后面的 $B(k,2)$$B(k, 2)$ 到 $B(k,k)$$B(k, k)$ 就都可以每次 $O(m)$$O(m)$ 求解，故这步的复杂度优化为 $O(mk)$$O(mk)$。

具体地当我们移动询问区间的时候，遍历所有段，如果某一段的右端点在当前区间内，那么显然指向这一段的组合数会移动到下一段中，所以需要减掉前面的加上现在的。注意移动这步实际上是 $O(mk\log n)$$O(mk \log n)$ 的，而且这只 $\log$$\log$ 不小，所以会 TLE，则我们考虑预处理 Lucas。显然直接预处理 ${10}^9$$10^9$ 范围肯定不行，于是这里有个高妙的思路，我们本身的模数为 $7$$7$，那么我们可以先让值对 $7^k$$7^k$ 取模，然后再对 $7$$7$ 取模，这个显然是等价的。而如果我们搞一个 ${10}^5$$10^5$ 左右的 $7^k$$7^k$ 的话，那么一步 Lucas 之后需要求的组合数就都在 ${10}^5$$10^5$ 以内了，所以这个时候我们只需要预处理 ${10}^5$$10^5$ 以内的组合数，那么对于每次求 Lucas 直接拆一次但是不递归，直接查值乘起来取模即可，这样复杂度就是 $O(1)$$O(1)$ 了，或者说 $O(2)$$O(2)$，于是复杂度会变成 $O(mk)$$O(mk)$。同时不难发现，存在 $ $

于是现在的问题就仅剩如何求 $B(k,1)$$B(k, 1)$，也就是求：

首先还是考虑之前的思路，一定会有很多段的相同的 $a$$a$，假设我们存在一段 $[l,r]$$[l, r]$ 满足 $\mathrm{\forall }i\in [l,r),a_i=a_{i+1}$$\forall i \in [l, r), a_i = a_{i + 1}$，那么显然此处的值即为：

所以这个东西显然需要快速处理一段组合数，可以考虑做一个组合数的前缀和，这样即可 $O(1)$$O(1)$ 查询一段组合数的求和，然后乘上 $a_l$$a_l$ 即可，这样每次的复杂度也就是 $O(m)$$O(m)$ 了。当然我们肯定不能对于 $n-k$$n - k$ 以内的每个数求前缀和，所以可以对 $m$$m$ 段相同的分别求出对应的前缀和，然后查询即可。求的时候前面段的直接求和，最后剩下的不足一段的单独计算即可。

于是现在问题再次转化为如何快速求这种形式的组合数前缀和，可以参考该题：LG-P4345 [SHOI2015]超能粒子炮·改。

具体地，对于求 $F(n,k)=\sum _{i=0}^k(\genfrac{}{}{0ex}{}{n}{i})modp$$F(n, k) = \sum_{i = 0}^k {n \choose i} \bmod p$，且 $p$$p$ 为质数，可以尝试通过 Lucas 进行处理（后面的式子最终都需要取模，这里省略）：

然后发现对于前面的 $\lfloor {\displaystyle \frac{i}{p}}\rfloor$$\lfloor \dfrac{i}{p} \rfloor$，这个就是个数论分块，也可以按照这个思想，将原式化为：

然后继续转化：

此时对比我们之前设的 $F(n,k)=\sum _{i=0}^k(\genfrac{}{}{0ex}{}{n}{i})modp$$F(n, k) = \sum_{i = 0}^k {n \choose i} \bmod p$，所以原式可以再次化为：

然后我们只要随便与处理一下 $p$$p$ 以内的 $F$$F$，这样 $F(nmodp,p-1)$$F(n \bmod{p}, p - 1)$ 和 $F(nmodp,kmodp)$$F(n \bmod{p}, k \bmod{p})$ 即可 $O(1)$$O(1)$ 查表，然后组合数直接用 Lucas 暴力算一下即可，对于 $F(\lfloor {\displaystyle \frac{n}{p}}\rfloor ,\lfloor {\displaystyle \frac{k}{p}}\rfloor -1)$$F(\lfloor \dfrac{n}{p} \rfloor, \lfloor \dfrac{k}{p} \rfloor - 1)$ 递归下去即可。

考虑这个东西的复杂度，用主定理推导一下即可：

$O(n)$$O(n)$ 处理一下组合数，则 $f(n)$$f(n)$ 的复杂度只有 Lucas 的一只 $\log$$\log$，所以最终这里单次求解的复杂度为 $O({\log }^{2}n)$$O(\log^2 n)$，然后我们要处理 $m$$m$ 个，则最终这步的复杂度为 $O(m{\log }^{2}n)$$O(m \log^2 n)$。最终复杂度为 $O(mk+m{\log }^{2}n+k\log n)$$O(mk + m \log^2 n + k \log n)$，显然能过。

至此我们就终于完成了这道题。

Code

xxxxxxxxxx
115
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define MOD (7)
23
#define SPL (117649) //7^6
24

25
template < typename T = int >
26
inline T read(void);
27

28
int f[10][10];
29
int N, M, K;
30
int origin(0);
31
int sumf[210];
32
int lucas_div[SPL + 10], lucas_mod[SPL + 10];
33
struct Blk{int l, r; int val;} blk[210];
34

35
int qpow(int a, int b){
36
    int ret(1), mul(a);
37
    while(b){
38
        if(b & 1)ret = ret * mul % MOD;
39
        b >>= 1;
40
        mul = mul * mul % MOD;
41
    }return ret;
42
}
43
int fact[10], inv[10];
44
void Init(void){
45
    fact[0] = 1;
46
    for(int i = 1; i < MOD; ++i)fact[i] = fact[i - 1] * i % MOD;
47
    inv[MOD - 1] = qpow(fact[MOD - 1], MOD - 2);
48
    for(int i = MOD - 2; i >= 0; --i)inv[i] = inv[i + 1] * (i + 1) % MOD;
49
}
50
int GetC(int n, int m){
51
    if(n < m)return 0;
52
    return fact[n] * inv[m] % MOD * inv[n - m] % MOD;
53
}
54
int Lucas(ll n, ll m){
55
    if(n < MOD && m < MOD)return GetC(n, m);
56
    return Lucas(n / MOD, m / MOD) * GetC(n % MOD, m % MOD) % MOD;
57
}
58
int O1Lucas(ll m){
59
    return (lucas_div[m / SPL] * lucas_mod[m % SPL]) % MOD;
60
}
61
void InitF(void){
62
    for(int i = 0; i <= MOD - 1; ++i)f[i][0] = f[0][i] = 1;
63
    for(int i = 1; i <= MOD - 1; ++i)
64
        for(int j = 1; j <= MOD - 1; ++j)
65
            f[i][j] = (f[i][j - 1] + Lucas(i, j)) % MOD;
66
}
67
int F(ll n, ll k){
68
    if(n < 0 || k < 0)return 0;
69
    if(n < MOD && k < MOD)return f[n][k];
70
    return (f[n % MOD][MOD - 1] * F(n / MOD, k / MOD - 1) % MOD + Lucas(n / MOD, k / MOD) * f[n % MOD][k % MOD] % MOD) % MOD;
71
}
72

73
int main(){
74
    Init(), InitF();
75
    N = read(), M = read(), K = read();
76
    for(int i = 0; i <= SPL; ++i)lucas_div[i] = Lucas((N - K) / SPL, i), lucas_mod[i] = Lucas((N - K) % SPL, i);
77
    int curl(1);
78
    for(int i = 1; i <= M; ++i)blk[i].val = read(), blk[i].l = curl, blk[i - 1].r = blk[i].l - 1, curl += read();
79
    blk[M].r = N; int lim = N - K + 1;
80
    for(int i = 1; i <= M; ++i)
81
        sumf[i] = (F(N - K, blk[i].r - 1) - F(N - K, blk[i].l - 2) + MOD) % MOD;
82
    for(int i = 1; i <= M; ++i){
83
        int l = blk[i].l, r = blk[i].r;
84
        if(l > lim)break;
85
        if(r <= lim)(origin += sumf[i] * blk[i].val % MOD) %= MOD;
86
        else (origin += (F(N - K, lim - 1) - F(N - K, l - 2) + MOD) % MOD * blk[i].val % MOD) %= MOD;
87
    }printf("%d ", origin);
88
    int cl = 1, cr = lim;
89
    for(int i = 2; i <= K; ++i){
90
        for(int m = 1; m <= M; ++m){
91
            int r = blk[m].r;
92
            if(cl <= r && r <= cr)
93
                origin = (origin - O1Lucas(r - cl) * blk[m].val % MOD + O1Lucas(r - cl) * blk[m + 1].val % MOD + MOD) % MOD;
94
        }++cl, ++cr;
95
        printf("%d ", origin);
96
    }printf("\n");
97
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
98
    return 0;
99
}
100

101
template < typename T >
102
inline T read(void){
103
    T ret(0);
104
    int flag(1);
105
    char c = getchar();
106
    while(c != '-' && !isdigit(c))c = getchar();
107
    if(c == '-')flag = -1, c = getchar();
108
    while(isdigit(c)){
109
        ret *= 10;
110
        ret += int(c - '0');
111
        c = getchar();
112
    }
113
    ret *= flag;
114
    return ret;
115
}

UPD

update-2022_12_02 初稿