【题解】前两年省选题选做

来自一条咸鱼最后的挣扎。

大概是补完了一下「九省联考 Day1」 的全部,「十二省联考 Day1T3 骗分过样例」的 $75$ 分和「十二省联考 Day2」 的 $70+100+36$ 分。

感觉自己打得稳一点,分数也还可以。

剩下的题可能是要等到很久很久以后才能做了。

九省联考 Day1

A 一双木棋

去年写过一个 alpha-beta 剪枝的版本,喜提了 70。现在选择重新再做。

一开始的时候完全没有任何思路,只知道 $2^{n\times m}$ 大概是可以最多 $50pts$。然后思考了一下一定是状态数过多,但是想了半天也不知道怎么压成一维的。之后突然想到可能合法的状态数并不多,然而自己并不太会算这个状态数,于是就打了个表发现确实不多,极限数据只有不到 $2\times 10^5$ 。于是就把所有状态都存到了 vector 里。

之后就喜提了 30 = =。原因可能是我这方面比较薄弱。大概是说虽然初始状态和终止状态,也就是第一步和最后一步的状态(包括位置和先后手)都是固定的,但是不能顺推,这样出来的是错的结果。原因也比较简单,顺推是假的「绝顶聪明」,真正的「绝顶聪明」都会是通过观察将来局面的可能结果再去判断如何行动。所以应该逆推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <map>

#include <cstdio>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std ;

typedef long long ll ;

const int N = 11 ;

const int Base = 233 ;

const int M = 1000010 ;

const int P = 998244353 ;

int tot ;
int n, m ;
int cnt[N] ;
int A[N][N] ;
int B[N][N] ;
int base[N] ;
map <ll, int> h ;
vector <int> s[M] ;

inline ll get_s(){
ll ret = 0 ;
for (int i = 1 ; i <= n ; ++ i)
ret = (ret * Base + cnt[i]) % P ;
return ret ;
}
int mn ;
int dep ;
int Id[M] ;
int rev[M] ;
int val[M] ;
int f[2][M] ;

void dfs(){
++ dep ;
if (!h[get_s()]){
++ tot ;
mn = m + 1 ;
h[get_s()] = tot ;
for (int i = 1 ; i <= n ; ++ i){
s[tot].push_back(cnt[i]) ;
mn = min(mn, cnt[i]) ;
val[tot] += cnt[i] ;
}
if (mn == m) return ;
}
else return ;
for (int i = 1 ; i <= n ; ++ i){
if (cnt[i] >= m || cnt[i] >= cnt[i - 1])
continue ; cnt[i] ++ ; dfs() ; cnt[i] -- ;
}
}
void out_put(const vector <int> & p, bool q = 0){
for (auto t : p){
if (q) putchar('#') ;
for (int j = 1 ; j <= t ; ++ j) putchar('1') ;
for (int j = t + 1 ; j <= m ; ++ j) putchar('0') ;
putchar('\n') ;
}
// puts("- - - - - - - - - - - - -") ;
}
int main(){
cin >> n >> m ; cnt[0] = m + 1 ; dfs() ;
for (int i = 1 ; i <= tot ; ++ i) Id[i] = i ;
sort(Id + 1, Id + tot + 1, [](int x, int y){ return val[x] > val[y] ; }) ;
for (int i = 1 ; i <= tot ; ++ i) rev[Id[i]] = i ;
// for (int i = 1 ; i <= tot ; ++ i) out_put(s[i]) ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= m ; ++ j)
scanf("%d", &A[i][j]) ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= m ; ++ j)
scanf("%d", &B[i][j]) ;
memset(f[1], 63, sizeof(f[1])) ;
memset(f[0], -63, sizeof(f[0])) ;
if ((n * m) & 1)
f[1][1] = 0 ;
else f[0][1] = 0 ; //f[1][1] = 0 ; // 0是先手,1是后手
for (int i = 1 ; i < tot ; ++ i){
int x = Id[i], y = 0, z, t = 0, o ;
for (auto p = s[x].begin() ; p != s[x].end() ; ++ p){
++ t ; y = 0 ; int mv = m ;
for (auto q = s[x].begin() ; q != s[x].end() ; ++ q){
int x = *q ; cnt[++ y] = x ;
if (p == q) -- cnt[y], o = cnt[y] ;
if (mv < cnt[y]) goto cccc ; mv = min(cnt[y], mv) ;
}
if ( !( z = h[get_s()] ) ) continue ;
if (f[0][i] < P) f[1][rev[z]] = min(f[1][rev[z]], f[0][i] - B[t][o + 1]) ;
if (f[1][i] < P) f[0][rev[z]] = max(f[0][rev[z]], f[1][i] + A[t][o + 1]) ;
cccc : continue ;
}
}
// cout << tot << '\n' ;
printf("%d\n", f[0][tot]) ; return 0 ;
}

正解似乎是轮廓线什么的= =。

B IIIDX

大概是先打了 $30pts$ 的暴力。之后莫名其妙地把这个图建成了一个 DAG 导致不可做。然后我就觉得似乎是只有另外 $15pts$ 的二叉树和树有关,推了一下,大概是最大化这棵树的 BFS 序的 $val$ 序列的字典序…感觉并不是很可做。然后就跑路了。

然后发现是个十分神奇的贪心+找性质…

大概是说先考虑 $d_i$ 都不相同的情况。此时由于这棵树满足堆性质,所以会有一个贪心,就是一棵子树内的权值必然在原序列里面是连续的,这一点不难证明,因为如果要在满足堆性质的前提下使得 BFS 序最大,连续是最好的方案。于是就可以以 $0$ 为根建个树,然后把所有的数从小到大排序来做。

然后考虑如果存在 $d_i$ 相同,那么这么贪心就会有问题。考虑此时的父子关系可以存在 $d_x=d_{fa_x}$ ,所以有时候可以把一个更大的数移到另一个和 $x$ 深度相同但编号靠后的位置上。但考虑贪心的本质还是不变的。即考虑提前计算贡献,考虑对于一个 $x$ ,如果他想选的话,至少要留出 $size_x-1$ 个位置来给它的子树。

考虑用线段树维护这个过程。先对所有数排个序,考虑用每个数去填满 $1\sim n$ 这些位置。线段树上维护 $seg_x$ 表示区间内 $v_i$ 的最小值,其中 $v_i$ 是位置 $i$ 左边还可以放的位置个数。那么每次可以线段树上二分出最靠左的合法位置。然后就是一个后缀加操作。

注意有两个细节:

1、二分时候的边界问题。二分完了需要判一下是否合法。

2、如果多个数相同,那么为了保证顺序固定,考虑每次选在原序列里面最靠右的那个位置就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <cmath>

#include <cstdio>

#include <vector>

#include <iostream>

#include <algorithm>

const int N = 500050 ;

using namespace std ;

int n ;
double k ;

int h, t ;
int q[N] ;
int fa[N] ;
int sz[N] ;
int ans[N] ;
int tmp[N] ;
int cnt[N] ;
int base[N] ;

vector <int> E[N] ;

void check_ans(){
for (int i = 1 ; i <= n ; ++ i)
if (ans[i] > base[tmp[i]]) return ;
else if (ans[i] < base[tmp[i]]) goto ccc ;
ccc :
for (int i = 1 ; i <= n ; ++ i)
ans[i] = base[tmp[i]] ;
}

bool comp(int a, int b){
return base[a] < base[b] ;
}
int dfs(int x){
sz[x] = 1 ;
for (auto y : E[x])
sz[x] += dfs(y) ;
return sz[x] ;
}
bool check(){
sort(base + 1, base + n + 1, [](int x, int y){ return x > y ; }) ;
for (int i = 1 ; i <= n ; ++ i) if (base[i] == base[i - 1]) return 0 ; return 1 ;
}
void solve(int l, int r, int x){
ans[x] = base[r --] ;
for (auto y : E[x])
solve(l, l + sz[y] - 1, y), l += sz[y] ;
}

bool vis[N] ;

int tag[N * 3] ;
int seg[N * 3] ;

#define lc (rt << 1)
#define rc (rt << 1 | 1)

void _up(int rt){
seg[rt] = seg[lc] > seg[rc] ? seg[rc] : seg[lc] ;
}
void _down(int rt){
if (tag[rt]){
seg[lc] += tag[rt] ;
seg[rc] += tag[rt] ;
tag[lc] += tag[rt] ;
tag[rc] += tag[rt] ;
tag[rt] = 0 ;
}
}
void build(int rt, int l, int r){
if (l == r)
return void(seg[rt] = r) ;
int mid = (l + r) >> 1 ;
build (lc, l, mid) ;
build (rc, mid + 1, r) ; _up(rt) ;
}
void upd(int rt, int l, int r, int ul, int ur, int v){
if (ul <= l && r <= ur)
return seg[rt] += v, void(tag[rt] += v) ;
int mid = (l + r) >> 1 ; _down(rt) ;
if (ul <= mid) upd(lc, l, mid, ul, ur, v) ;
if (ur > mid) upd(rc, mid + 1, r, ul, ur, v) ;
_up(rt) ;
}
int qry(int rt, int l, int r, int v){
if (l == r) return l + (seg[rt] < v) ;
int mid = (l + r) >> 1 ; _down(rt) ;
if (seg[rc] >= v)
return qry(lc, l, mid, v) ;
else return qry(rc, mid + 1, r, v) ;
}
int main(){
cin >> n >> k ;
for (int i = 1 ; i <= n ; ++ i) tmp[i] = i ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%d", &base[i]), fa[i] = floor(1.0 * i / k) ;
// for (int i = 1 ; i <= n ; ++ i) printf("%d\n", fa[i]) ;
if (n <= 10){
do{
// for (int i = 1 ; i <= n ; ++ i)
// cout << base[tmp[i]] << ' ' ; //puts("") ;
for (int i = 1 ; i <= n ; ++ i)
if (base[tmp[fa[i]]] > base[tmp[i]]) goto cccc ;
check_ans() ; //cout << 233 << '\n' ;
cccc : continue ;
}while (next_permutation(tmp + 1, tmp + n + 1)) ;
}
else if (check()){
for (int i = 1 ; i <= n ; ++ i) E[fa[i]].push_back(i) ;
dfs(0) ; solve(1, n + 1, 0) ;
}
else {
// cout << 233 << '\n' ;
for (int i = 1 ; i <= n ; ++ i) E[fa[i]].push_back(i) ;
dfs(0) ; build(1, 1, n) ; int x, y, z ;
for (int i = n - 1 ; i >= 1 ; -- i)
if (base[i] == base[i + 1])
cnt[i] = cnt[i + 1] + 1 ;
for (int i = 1, j ; i <= n ; ++ i){
j = fa[i] ;
if (j && !vis[j])
vis[j] = 1, upd(1, 1, n, ans[j], n, sz[j] - 1) ;
y = x = qry(1, 1, n, sz[i]) ;
x += cnt[y] ; z = x ;
z -= cnt[x] ++ ;
ans[i] = z ;
upd(1, 1, n, z, n, - sz[i]) ;
}
for (int i = 1 ; i <= n ; ++ i) ans[i] = base[ans[i]] ;
}
for (int i = 1 ; i <= n ; ++ i)
cout << ans[i] << " " ; return 0 ;
}

C 秘密袭击

毒瘤 DP…

一开始想的是要枚举每个点计算贡献,后来写了半天一直挂…也不民白为啥。

不过学了一波,觉得可能还是枚举每个权值来 DP 更有道理。考虑对于一个权值 $w$ ,问题变成了有多少种选择的方式使得连通块内大于等于 $w$ 的权值有 $k$ 个。设 $f_{x,v}$ 表示在点 $x$ 的子树内选择一个连通块,大于等于 $w$ 的权值有 $v$ 个的方案数。转移就是比较平常的背包转移。然后用一点上下界优化可以把复杂度优化到 $O(n^2w)$ 。

然后大概是需要一些技巧才能通过此题。都在代码里了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <cstdio>

#include <vector>

#include <cstring>

#include <iostream>

using namespace std ;

#define p_b push_back

typedef unsigned int ui ;

const int N = 2010 ;

const int M = 2010 ;

const int P = 64123 ;

ui ans ;
int num ;
int sz[N] ;
int cnt[N] ;
int base[N] ;
int n, k, m ;

ui g[N] ;
ui f[N][M] ; // i is root, \leq j is k

vector <int> E[N] ;
/*
void do_up(int x, int fa){
sz[x] = 1 ;
for (int i = 1 ; i <= m ; ++ i)
f[x][i][1] = (i <= base[x]), f[x][i][0] = 1 ;
for (auto y : E[x]){
if (y == fa) continue ;
do_up(y, x) ; sz[x] += sz[y] ;
memset(g, 0, sizeof(g)) ;
for (int i = 1 ; i <= base[x] ; ++ i)
for (int j = 1 ; j <= sz[x] ; ++ j)
for (int k = 0 ; k <= sz[y] ; ++ k)
(g[i][j + k + 1] += f[x][i][j] * f[y][i][k] % P) %= P ;
for (int i = base[x] + 1 ; i <= m ; ++ i)
for (int j = 1 ; j <= sz[x] ; ++ j)
for (int k = 0 ; k <= sz[y] ; ++ k)
(g[i][j + k] += f[x][i][j] * f[y][i][k] % P) %= P ;
for (int i = 1 ; i <= m ; ++ i)
for (int j = 1 ; j <= sz[x] ; ++ j)
f[x][i][j] = g[i][j], g[i][j] = 0 ;

printf("###%d###\n", y) ;
for (int i = 1 ; i <= m ; ++ i)
for (int j = 0 ; j <= sz[x] ; ++ j)
printf("%d %d %d %u\n", x, i, j, f[x][i][j]) ;
puts("o o o o o o o o o o o o") ;

}
puts("- - - - - - - - - - - - - - -") ;
}*/
void solve(int x, int fa){
sz[x] = cnt[x] ;
for (int i = 0 ; i <= k ; ++ i)
f[x][i] = 0 ; f[x][cnt[x]] = 1 ;
for (auto y : E[x]){
if (y == fa)
continue ; solve(y, x) ;
for (int i = 0 ; i <= sz[x] ; ++ i)
for (int j = 0 ; j <= sz[y] ; ++ j)
(g[min(i + j, k)] += f[x][i] * f[y][j] % P) %= P ;
sz[x] += sz[y] ; sz[x] = min(sz[x], k) ;
for (int i = 0 ; i <= sz[x] ; ++ i)
(f[x][i] += g[i]) %= P, g[i] = 0 ;
}
// printf("%d- - - - - - - - - - - - - -\n", x) ;
// for (int i = 0 ; i <= k ; ++ i)
// cout << f[x][i] << " " ; puts("") ;
}
int main(){
int x, y ; cin >> n >> k >> m ;
for (int i = 1 ; i <= n ; ++ i) scanf("%d", &base[i]) ;
for (int i = 1 ; i < n ; ++ i)
scanf("%d%d", &x, &y), E[x].p_b(y), E[y].p_b(x) ;
/*
for (int root = 1 ; root <= n ; ++ root){
memset(f, 0, sizeof(f)) ; do_up(root, 0) ;
cout << root << " " << f[root][base[root]][k] << '\n' ;
(ans += base[root] * f[root][base[root]][k] % P) %= P ;
}
*/
for (int v = 1 ; v <= m ; ++ v){
for (int i = 1 ; i <= n ; ++ i)
if (base[i] >= v) ++ num, cnt[i] = 1 ; else cnt[i] = 0 ;
if (num < k) break ; solve(1, 0) ;
for (int i = 1 ; i <= n ; ++ i) (ans += f[i][k]) %= P ; num = 0 ;
// puts("") ; puts("") ;
}
cout << ans << '\n' ; return 0 ;
}

十二省联考 Day2

A 皮配(70 分)

$50$ 分大概是 $O(nM^2)$ 的 DP。然而一开始自己想的是 $O(nM^3)$ 的,写着写着突然发现 $c_0,c_1$ 只用记一个,$d_0,d_1$ 只用记一个,然后相同颜色的放在一起做背包就好了。

$70$ 分比较神仙,$k=0$ 。学习了一波。发现此时相当于给每个城市分配一个阵营,给每个学校分配一个派系,且两者无关。于是就可以分别 dp。设 $f_{i,j}$ 表示前 $i$ 个学校,有 $j$ 个选手选了鸭派系的方案数;同理设 $g_{i,j}$ 表示前 $i$ 个城市,有 $j$ 个城市选了红阵营的方案数。这就是一个比较普通的背包转移。最后答案就是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <map>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define fr first

#define sc second

#define il inline

using namespace std ;

typedef long long ll ;

const int N = 1050 ;

const int M = 2505 ;

const int P = 998244353 ;

template <typename T>
void debug(T x, char c = '\n'){ cerr << x << c ; }

template <typename T>
void debug(T *const tp, int minn, int maxn, char v = ' ', char c = '\n'){
for (int i = minn ; i <= maxn ; ++ i) debug(tp[i], v) ; cerr << c ;
}

int ans ;
int T, d ;
int id[N] ;
int nl[N] ;
int sum[N] ;
int n, m, k ;
int c_0, c_1 ; //0,1 2,3
int d_0, d_1 ; //0,2 1,3
//d_1 = c_0 - d_0 + c_1 = sum - d_0
int f[2][M][M] ;
int g[2][M][M] ;
map <int, int> ncol[N] ;
struct person{
int id ;
int col ;
int val ;
} ;
person tmp[N] ;
person base[N] ;

template <typename T>
il void add(T &x, ll y, int mod = P){
x += y ; x = x >= mod ? x - mod : x ;
}

bool comp(const person & a, const person & b){ return a.col < b.col ; }

void clear(int t[2][M][M]){
for (int i = 0 ; i <= c_0 ; ++ i)
for (int j = 0 ; j <= d_0 ; ++ j)
t[d][i][j] = 0 ;
}

void do_dp(int l, int r, int c){
int s, v, k, np, nq ;
for (int i = l ; i <= r ; ++ i, d ^= 1){
s = sum[i] ;
k = base[i].id ;
v = base[i].val ;
// cout << i << " " << d << '\n' ;
if (!c) clear(f) ; else clear(g) ;
for (int p = c_0 ; p >= 0 ; -- p){
np = s - p ; if (np > c_1) break ;
for (int q = d_0 ; q >= 0 ; -- q){
nq = s - q ; if (nq > d_1) break ;
if (c == 0){
if (nl[k] != 0 && p >= v && q >= v)
add(f[d][p][q], f[d ^ 1][p - v][q - v]) ;
if (nl[k] != 1 && nq >= v && p >= v)
add(f[d][p][q], f[d ^ 1][p - v][q]) ;
}
if (c == 1){
if (nl[k] != 2 && np >= v && q >= v)
add(g[d][p][q], g[d ^ 1][p][q - v]) ;
if (nl[k] != 3 && np >= v && nq >= v)
add(g[d][p][q], g[d ^ 1][p][q]) ;
}
}
}
}
}

int fs[M] ;
int gs[M] ;
int scol[N] ;

void solve0(int o, int oo){
memset(fs, 0, sizeof(fs)) ;
memset(gs, 0, sizeof(gs)) ;
fs[0] = gs[0] = 1 ; ans = 0 ;
for (int i = 1 ; i <= oo ; ++ i)
for (int j = c_0 ; j >= scol[i] ; -- j)
if (scol[i]) add(fs[j], fs[j - scol[i]]) ;
for (int i = 1 ; i <= o ; ++ i)
for (int j = d_0 ; j >= base[i].val ; -- j)
add(gs[j], gs[j - base[i].val]) ;
for (int i = max(sum[o] - c_1, 0) ; i <= c_0 ; ++ i)
for (int j = max(sum[o] - d_1, 0) ; j <= d_0 ; ++ j)
add(ans, 1ll * fs[i] * gs[j] % P) ;
cout << ans << '\n' ;
}
int main(){
cin >> T ;
while (T --){
memset(f, 0, sizeof(f)) ;
memset(g, 0, sizeof(g)) ;
memset(nl, -1, sizeof(nl)) ;
memset(scol, 0, sizeof(scol)) ;
scanf("%d%d", &n, &m) ; int x, z ;
scanf("%d%d%d%d", &c_0, &c_1, &d_0, &d_1) ;
for (int i = 1 ; i <= n ; ++ i)
ncol[i].clear(), base[i].id = i ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%d %d", &base[i].col, &base[i].val) ;
memcpy(tmp, base, sizeof(base)) ;
sort(base + 1, base + n + 1, comp) ;
for (int i = 1 ; i <= n ; ++ i){
scol[base[i].col] += base[i].val ;
sum[i] = sum[i - 1] + base[i].val ;
}
cin >> k ; d = 1 ; int td ;
g[0][0][0] = f[0][0][0] = 1 ;
if (k == 0){ solve0(n, m) ; continue ; }
for (int i = 1 ; i <= k ; ++ i)
cin >> x, cin >> nl[x], ncol[tmp[x].col][nl[x]] ++ ;
// debug(nl, 1, n) ; debug(sum, 1, n) ;
for (int l = 1, r, c ; l <= n ; l = r + 1){
r = l ; c = base[l].col ;
while (base[r + 1].col == c) ++ r ;
td = d ; do_dp(l, r, 1) ;
d = td ; do_dp(l, r, 0) ;
for (int i = 0 ; i <= c_0 ; ++ i)
for (int j = 0 ; j <= d_0 ; ++ j){
add(f[r & 1][i][j], g[r & 1][i][j]) ;
g[r & 1][i][j] = f[r & 1][i][j] ;
}
}
ans = 0 ;
for (int i = 0 ; i <= c_0 ; ++ i)
for (int j = 0 ; j <= d_0 ; ++ j)
add(ans, f[n & 1][i][j]) ; //, cout << f[n & 1][i][j] << '\n' ;
cout << ans << '\n' ;
}
}

B 春节十二响

暴力比较好想。大家都说不是很容易证明…我还真没发现(x

大概通过链的部分分,很容易发现合并两条链的时候应该大找大,小找小。然后我是直接把所有链都找了出来,排了个序然后拿了个 set 维护。然后试图在树上用神必的方式忽略相同的信息发现失败…

之后知道了正确做法觉得挺 rz。大概就是把我那个过程换成对 set 的启发式合并就好了。想了想感觉十分有道理。

「My-75pts-Code」
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
//75分
#include <set>

#include <cstdio>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std ;

typedef long long ll ;

const int N = 300010 ;

int n ;
int cnt ;
int mxd ;
int fa[N] ;
int deg[N] ;
int val[N] ;
int tmp[N] ;
int base[N] ;

ll ans ;
int stk[N], tp ;
multiset <int> s ;
vector <int> E[N] ;
vector <int> L[N] ;
vector <int> zscv ;

namespace _tree{
int sum ;
int sz[N] ;
int dep[N] ;
int dfn[N] ;
int son[N] ;
int top[N] ;
void dfs1(int x, int da){
dep[x] = dep[da] + 1, sz[x] = 1 ;
for (auto y : E[x]){
if (y == da) continue ;
dfs1(y, x) ; sz[x] += sz[y] ;
if (sz[y] > sz[son[x]]) son[x] = y ;
}
}
void dfs2(int x, int tp){
top[x] = tp ;
dfn[x] = ++ cnt ;
if (son[x])
dfs2(son[x], tp) ;
for (auto y : E[x])
if (y != fa[x] && y != son[x]) dfs2(y, y) ;
}
int lca(int x, int y){
if (!y) return 0 ;
while (top[x] != top[y]){
if (dep[top[x]] < dep[top[y]])
std :: swap(x, y) ; x = fa[top[x]] ;
}
if (dep[x] > dep[y])
std :: swap(x, y) ; return x ;
}
}

using namespace _tree ;

void dfs_l(int x){
tmp[++ cnt] = base[x] ;
for (auto y : E[x]) dfs_l(y) ;
}
void solve(int x){
stk[++ tp] = x ;
for (auto y : E[x]) solve(y) ;
if (deg[x] <= 1 && x > 1){
int t = tp ;
while (stk[t]) L[x].push_back(stk[t --]) ;
}
stk[tp --] = 0 ; mxd = max(mxd, dep[x]) ;
}
bool comp(int a, int b){ return a > b ; }


int main(){
cin >> n ;
for (int i = 1 ; i <= n ; ++ i) scanf("%d", &base[i]) ;
for (int i = 2 ; i <= n ; ++ i){
scanf("%d", &fa[i]), E[fa[i]].push_back(i) ;
// printf("%d %d\n", fa[i], i) ;
deg[i] ++, deg[fa[i]] ++, mxd = max(mxd, max(deg[fa[i]], deg[i])) ;
}
dfs1(1, 0) ; dfs2(1, 1) ; cnt = 0 ;
if (mxd <= 0){
dfs_l(E[1][0]) ;
memcpy(val, tmp, sizeof(tmp)) ;
memset(tmp, 0, sizeof(tmp)) ;
if (E[1].size() <= 1){
for (int i = 1 ; i <= n ; ++ i)
ans += val[i] ; printf("%lld\n", ans) ; return 0 ;
}
else {
mxd = cnt ;
cnt = 0 ; dfs_l(E[1][1]) ;
sort(tmp + 1, tmp + cnt + 1, comp) ;
sort(val + 1, val + mxd + 1, comp) ;
if (mxd > cnt) swap(val, tmp), swap(mxd, cnt) ;
// for (int i = 1 ; i <= n ; ++ i)
// printf("%d %d\n", tmp[i], val[i]) ;
for (int i = 1 ; i <= mxd ; ++ i)
ans += max(tmp[i], val[i]) ;
for (int i = mxd + 1 ; i <= cnt ; ++ i)
ans += tmp[i] ;
printf("%lld\n", ans + base[1]) ; return 0 ;
}
}
else if (n <= 300000){
for (int i = 2 ; i <= n ; ++ i)
if (deg[i] <= 1) val[++ cnt] = i ;
sort(val + 1, val + cnt + 1, [](int x, int y){ return dfn[x] < dfn[y] ; }) ;
for (int i = 2 ; i <= cnt ; ++ i)
tmp[val[i]] = lca(val[i], val[i - 1]) ;
solve(mxd = 1) ;
// for (int i = 1 ; i <= n ; ++ i) cout << dep[i] << '\n' ;
for (int i = 1 ; i <= mxd ; ++ i) s.insert(0) ;
for (int i = 1 ; i <= cnt ; ++ i)
sort(L[val[i]].begin(), L[val[i]].end(), [](int x, int y){ return base[x] > base[y] ; }) ;
// for (int i = 1 ; i <= cnt ; ++ i){
// cout << val[i] << '\n' ;
// for (auto t : L[val[i]]) cout << t << " " ; puts("") ;
// }
for (int i = 1 ; i <= cnt ; ++ i){
// cout << i << '\n';
for (auto j : L[val[i]]){
auto p = s.lower_bound(base[j]) ;
if (p == s.end())
s.erase(-- p), zscv.push_back(base[j]) ;
else s.erase(p), zscv.push_back(*p) ;
}
for (auto j : zscv) s.insert(j) ; zscv.clear() ;
}
for (auto p : s) ans += p ; //, cout << p << " " ;
cout << ans << '\n' ; return 0 ;
}
}
「My-Code」
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <queue>

#include <cstdio>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std ;

const int N = 300010 ;

typedef long long ll ;

ll ans ;
int n, base[N] ;
vector <int> E[N], mg ;
priority_queue <int> h[N] ;

void solve(int x){
for (auto y : E[x]){
solve(y) ;
if (h[y].size() > h[x].size()) swap(h[x], h[y]) ;
while (h[y].size())
mg.push_back(max(h[y].top(), h[x].top())), h[y].pop(), h[x].pop() ;
while (mg.size()) h[x].push(mg.back()), mg.pop_back() ;
}
h[x].push(base[x]) ;
}

int main(){
cin >> n ; int x, y ;
for (int i = 1 ; i <= n ; ++ i) scanf("%d", &base[i]) ;
for (int i = 2 ; i <= n ; ++ i) scanf("%d", &x), E[x].push_back(i) ;
solve(1) ;
while (h[1].size())
ans += h[1].top(), h[1].pop() ;
cout << ans << '\n' ; return 0 ;
}

C 希望(36 分)

鸽了。

十二省联考 骗分过样例

过程比较曲折,没啥时间写了。就先放一下代码吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
#include <cmath>

#include <bitset>

#include <cstdio>

#include <cstring>

#include <iostream>

#define us unsigned

#define rg register

#define ll long long

using namespace std ;

const int NR = 1000010 ;
const int MAX = 150000010 ;
const int MAXP = 10000100 ;
const int MAX2 = 50000010 ;
const int mod = 998244353 ;
const int phm = 998244352 ;

int N ;
char In[10000] ;

namespace Sub1{
inline ll expow(ll a, ll b){
ll res = 1 ;
while (b){
if (b & 1) res = res * a % mod ;
a = a * a % mod, b >>= 1 ;
}
return res % mod ;
}
// const char *Muban = "1_998244353" ;
inline bool check1(char *A){
int Len = strlen(A) ;
if (Len == 11) return 1 ; else return 0 ;
}
inline ll qr(){
char c = getchar() ; ll ret = 0 ;
while (!isdigit(c)) c = getchar() ;
while (isdigit(c)){
ret = (ret << 1) + (ret << 3) + c - 48, c = getchar() ;
if (ret > mod) ret = ret % phm + phm ;
}
return ret ;
}
inline void Solve1(){
cin >> N ; int i ; ll q ;
for (i = 1 ; i <= N ; ++ i) q = qr(), printf("%lld\n", expow(19, q)) ;
}
}
namespace Sub2{
int mod = 1145141, phm = 1145140 ;
inline ll expow(ll a, ll b){
ll res = 1 ;
while (b){
if (b & 1) res = res * a % mod ;
a = a * a % mod, b >>= 1 ;
}
return res % mod ;
}
inline ll get_phi(ll x){
ll rt = sqrt(x) + 1, ret = x ;
for (ll p = 2 ; p <= rt ; ++ p){
if (!(x % p)) { ret = ret * (p - 1) / p ; while (!(x % p)) x /= p ;}
}
if (x > 1) ret = ret * (x - 1) / x ;
return ret ;
}
inline bool check2(char *A){
int Len = strlen(A) ;
if (Len == 2 && In[1] == '?') return 1 ; else return 0 ;
}
inline ll qr(){
char c = getchar() ; ll ret = 0 ;
while (!isdigit(c)) c = getchar() ;
while (isdigit(c)){
ret = (ret << 1) + (ret << 3) + c - 48, c = getchar() ;
if (ret > mod) ret = ret % phm + phm ;
}
return ret ;
}
inline void Solve2(){
cin >> N ; int i ; ll q ;
for (i = 1 ; i <= N ; ++ i) q = qr(), printf("%lld\n", expow(19, q)) ;
}
}
namespace Sub3{
#define ull unsigned long long
ull mod = 5211600617818708273LL, phm = mod - 1 ;
inline ull mul(ull a, ull b){
register ull res = 0 ;
while (b){
if (b & 1) res = (res + a) % mod ;
a = (a + a) % mod, b >>= 1ull ;
}
return res % mod ;
}
inline ull expow(ull a, ull b){
register ull res = 1 ;
while (b){
if (b & 1) res = mul(res, a) % mod ;
a = mul(a, a) % mod, b >>= 1ull ;
}
return res % mod ;
}
inline ull get_phi(ull x){
ull rt = sqrt(x) + 1, ret = x ;
for (ull p = 2 ; p <= rt ; ++ p){
if (!(x % p)) { ret = ret * (p - 1) / p ; while (!(x % p)) x /= p ;}
}
if (x > 1) ret = ret * (x - 1) / x ;
return ret ;
}
inline bool check3(char *A){
int Len = strlen(A) ;
if (Len == 3 && In[1] == '?' && In[2] == '+') return 1 ; else return 0 ;
}
inline ull qr(){
char c = getchar() ; ull ret = 0 ;
while (!isdigit(c)) c = getchar() ;
while (isdigit(c)) ret = (ret << 1) + (ret << 3) + c - 48, c = getchar() ;
return ret ;
}
inline void Solve3(){
cin >> N ; int i ; ull q ;
for (i = 1 ; i <= N ; ++ i) q = qr(), printf("%lld\n", expow(19, q)) ;
}
}
这里是一张表,防止博客卡顿于是塞到了 paste bin 里面,链接: https://paste.ubuntu.com/p/WS9Vm2J3BR/
namespace Sub4{
const ll mod = 998244353 ;
const ll phm = mod - 1 ;
inline int expow(int a, int b){
int res = 1 ;
while (b){
if (b & 1) res = (int)((unsigned)res * (unsigned)a) % mod;
a = (int)(((unsigned)a * (unsigned)a) )% mod ; b >>= 1 ;
}
return res % mod ;
}
inline bool check4(char *A){
int Len = strlen(A) ;
if (Len == 13 && In[1] == 'w' && In[2] == 'a') return 1 ; else return 0 ;
}
inline ll qr(){
char c = getchar() ; ll ret = 0 ;
while (!isdigit(c)) c = getchar() ;
while (isdigit(c)) ret = (ret << 1) + (ret << 3) + c - 48, c = getchar() ;
return ret ;
}

int pwp[NR] ;
long long t ;
inline void Solve4(){//55245 45699
cin >> N ; pwp[0] = 1 ;
for (int i = 1 ; i < NR ; ++ i)
pwp[i] = pwp[i - 1] * 19 % mod ;
while (N --){
t = qr() ;
if (t <= 55245)
printf("%d\n", pwp[t]) ;
else printf("%d\n", pwp[(t - 55245) % 45699 + 55245]) ;
}
}
}

int cnt ;
int pr[MAXP + 10] ;
int phi[MAXP << 1] ;
bool vis[MAX + 10] ;
bool vis2[NR + 10] ;
bool chk[MAXP << 1] ;

namespace Sub5{
inline bool check5(char *A){
int Len = strlen(A) ;
if (Len == 2 && A[0] == '2' && A[1] == 'p') return 1 ; else return 0 ;
}
inline void Euler(){
vis[0] = vis[1] = 1 ;
for (int i = 2 ; i <= MAX ; ++ i){
if (!vis[i]) pr[++ cnt] = i ;
for (int j = 1 ; j <= cnt ; ++ j){
if (i * pr[j] > MAX) break ;
vis[i * pr[j]] = 1 ; if (i % pr[j] == 0) break ;
}
}
}
inline void Jie(us ll L, us ll R){
if (L >= 99999999999900000LL)
for (int i = 0 ; i <= 4370 ; ++ i) vis2[wa[i]] = 1 ;
for (int i = 1 ; i <= cnt ; ++ i){
for (us ll j = L / pr[i] - 1 ; j <= R / pr[i] + 1 ; ++ j){
if (j * pr[i] > R || j * pr[i] < L) continue ;
vis2[j * pr[i]- L] = 1 ;
}
}
}

inline ll qr(){
char c = getchar() ; ll ret = 0 ;
while (!isdigit(c)) c = getchar() ;
while (isdigit(c)) ret = (ret << 1) + (ret << 3) + c - 48, c = getchar() ;
return ret ;
}
inline void Solve5(){
Euler() ;
cin >> N ; us ll L, R ;
for (int i = 1 ; i <= N ; ++ i){
L = qr() ;
R = qr() ;
if (R <= MAX)
for (us ll j = L ; j <= R ; ++ j)
if (vis[j]) putchar('.') ; else putchar('p') ;
else{
Jie(L, R) ;
for (us ll j = L ; j <= R ; ++ j)
if (vis2[j - L]) putchar('.') ; else putchar('p') ;
}
cout << '\n' ;
}
}
}
namespace Sub6{
short mu[MAX + 10] ;
inline bool check6(char *A){
int Len = strlen(A) ;
if (Len == 2 && A[0] == '2' && A[1] == 'u') return 1 ; else return 0 ;
}
inline void Euler(){
vis[0] = vis[1] = 1 ; mu[1] = 1 ;
for (int i = 2 ; i <= MAX2 ; ++ i){
if (!vis[i]) pr[++ cnt] = i, mu[i] = -1 ;
for (int j = 1 ; j <= cnt ; ++ j){
if (i * pr[j] > MAX2) break ;
vis[i * pr[j]] = 1 ;
if (i % pr[j] == 0) break ;
mu[i * pr[j]] = - mu[i] ;
}
}
}
long long trv[NR] ;
short mu2[MAX + 10] ;
inline void Jie(us ll L, us ll R){
for (ll i = L ; i <= R ; ++ i) trv[i - L] = i ;
for (int i = 1 ; i <= cnt ; ++ i){
for (us ll j = L / pr[i] - 1 ; j <= R / pr[i] + 1 ; ++ j){
if (j * pr[i] > R) continue ;
if (j * pr[i] < L) continue ;
vis2[j * pr[i]- L] = 1 ;
if (j % pr[i] == 0)
mu2[j * pr[i] - L] = -10000 ;
else mu2[j * pr[i] - L] ++ ;
trv[j * pr[i] - L] /= pr[i] ;
}
}
for (int i = 0 ; i <= (int)(R - L + 1) ; ++ i)
if (!vis2[i]) mu2[i] = 1, trv[i] = 1 ;
}
inline ll qr(){
char c = getchar() ; ll ret = 0 ;
while (!isdigit(c)) c = getchar() ;
while (isdigit(c)) ret = (ret << 1) + (ret << 3) + c - 48, c = getchar() ;
return ret ;
}
inline void Solve6(){
Euler() ;
cin >> N ; us ll L, R ; //return void() ;
for (int i = 1 ; i <= N ; ++ i){
L = qr(), R = qr() ;
//cerr << i << " " << L << " " << R << '\n' ;
if (R <= MAX2){
for (us ll j = L ; j <= R ; ++ j){
if (mu[j]) putchar(~mu[j] ? '+' : '-') ;
else putchar('0') ;
}
}
else{
Jie(L, R) ;
for (us ll j = L ; j <= R ; ++ j){
// cerr << trv[j - L] << '\n' ;
if (mu2[j - L] >= 0)
putchar(( ( mu2[j - L] + (trv[j - L] > 1) ) & 1) ? '-' : '+') ;
else putchar('0') ;
}
}
putchar('\n') ;
}
}
}

namespace Sub7{
inline bool check7(char *A){
int Len = strlen(A) ;
if (Len == 2 && A[0] == '2' && A[1] == 'g') return 1 ; else return 0 ;
}
void sieve(int x){
phi[1] = 1 ;
for (int i = 2 ; i <= x ; ++ i){
if (!vis[i])
pr[++ cnt] = i, phi[i] = i - 1 ;
for (int j = 1 ; j <= cnt ; ++ j){
if (i * pr[j] > x) break ;
vis[i * pr[j]] = 1 ;
if (i % pr[j] == 0) {
phi[i * pr[j]] = phi[i] * pr[j] ; break ;
}
else phi[i * pr[j]] = phi[i] * (pr[j] - 1) ;
}
}
}
#define ctz __builtin_ctz
int gcd(int a, int b){
if (!(a * b)) return a + b ;
int t = ctz(a | b) ; a >>= ctz(a) ;
do { b >>= ctz(b) ; if (a > b) swap(a, b) ; b -= a ; } while(b) ;
return a << t ;
}
int expow(int a, int b, int p){
int res = 1 ;
while (b){
if (b & 1)
res = 1ll * res * a % p ;
a = 1ll * a * a % p ; b >>= 1 ;
}
return res ;
}
long long L, R, P ;

int ctn, tot ;
int fac[NR], rt, po ;
int dmod[3] = {2, 7, 17} ;

void Solve7(){
cin >> N ;
sieve((MAXP << 1) - 1) ;
while (N --){
cin >> L >> R >> P ;
if (P == mod){
for (int i = L ; i <= R ; ++ i){
bool rr = 0 ;
for (int j = 0 ; j < 3 ; ++ j)
rr |= (bool)(expow(i, phm / dmod[j], mod) == 1) ;
putchar(rr ? '.' : 'g') ;
}
}
else if (P < MAXP << 1){
int p = phi[P] ; ctn = tot = 0 ;
for (rg int i = 2 ; i * i <= p ; ++ i){
if (p % i == 0){
fac[++ tot] = i ;
while (p % i == 0) p /= i ;
}
}
if (p > 1) fac[++ tot] = p ; po = phi[P] ;
for (rg int i = 1 ; i <= P ; ++ i){
rg bool ans = 0 ;
for (int j = 1 ; j <= tot ; ++ j)
if (expow(i, po / fac[j], P) == 1){ ans = 1 ; break ; }
if (!ans && expow(i, po, P) == 1) { rt = i ; break ; }
}
for (rg int j = 1, i = 1 ; i <= po ; ++ i){
j = 1ll * j * rt % P ;
if (gcd(i, po) == 1) chk[j] = 1 ;
}
for (rg int i = L ; i <= R ; ++ i)
putchar(!chk[i] ? '.' : 'g') ;
}
putchar('\n') ;
}
}
}

int main(){
scanf("%s", In) ;
if (Sub1 :: check1(In)) Sub1 :: Solve1() ;
else if (Sub2 :: check2(In)) Sub2 :: Solve2() ;
else if (Sub3 :: check3(In)) Sub3 :: Solve3() ;
else if (Sub4 :: check4(In)) Sub4 :: Solve4() ;
else if (Sub5 :: check5(In)) Sub5 :: Solve5() ;
else if (Sub6 :: check6(In)) Sub6 :: Solve6() ;
else if (Sub7 :: check7(In)) Sub7 :: Solve7() ;
}