【赛题整理】[NOIonline Round1] A~F题解

场上打的一点也不好…场后复盘了一下,其实六道题都不算难。自己缺乏比赛经验、基础不扎实、想题不认真、不专注等问题都十分影响发挥…

于是就打算整理一下这六道题。感觉…还是有点东西的吧。

题目难度按我自己心目中的升序排序。

心不摇于死生之变,气不夺于宠辱利害之交,则四者之胜败自然洞见。

A 文具订购

小明的班上共有 $n$ 元班费,同学们准备使用班费集体购买 $3$ 种物品:

  1. 圆规,每个 $7$ 元。
  2. 笔,每支 $4$ 元。
  3. 笔记本,每本 $3$ 元。

小明负责订购文具,设圆规,笔,笔记本的订购数量分别为 $a,b,c$,他订购的原则依次如下:

  1. $n$ 元钱必须正好用光,即 $7a+4b+3c=n$。
  2. 在满足以上条件情况下,成套的数量尽可能大,即 $a,b,c$ 中的最小值尽可能大。
  3. 在满足以上条件情况下,物品的总数尽可能大,即 $a+b+c$ 尽可能大。

请你帮助小明求出满足条件的最优方案。可以证明若存在方案,则最优方案唯一。

对于全部的测试点,保证 $0 \leq n \leq 10^5$。

考虑贪心。发现大概是 $14$ 元一套,于是就从 $\lfloor\frac{n}{14}\rfloor$ 枚举到 $0$ 。如果钱数不是 $14$ 的倍数,当然是把剩下的用来买 $3$ 和 $4$ 最合理。于是就模拟一遍即可,同时再去找 $a+b+c$ 的最大值。大概是 div2B 的难度?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main(){
cin >> n ;
ans = n / 14 ;
while (ans >= 0){
outp = 0 ;
a = b = c = ans ;
pq = a * 14, res = n - pq ;
for (int i = 0 ; i <= res / 3 ; ++ i)
if ((res - i * 3) % 4 == 0){
outp = 1 ;
if (3 * ans + i + (res - i * 3) / 4 > a + b + c)
b = ans + (res - i * 3) / 4, c = ans + i ;
}
if (outp)
return !printf("%d %d %d\n", a, b, c) ;
else ans -- ;
}
return !puts("-1") ;
}

B 冒泡排序

给定一个 $1 ∼ n$ 的排列 $p_i$,接下来有 $m$ 次操作,操作共两种:

  1. 交换操作:给定 $x$,将当前排列中的第 $x$ 个数与第 $x+1$ 个数交换位置。
  2. 询问操作:给定 $k$,请你求出当前排列经过 $k$ 轮冒泡排序后的逆序对个数。

对一个长度为 $n$ 的排列 $p_i$ 进行一轮冒泡排序的伪代码如下:

1
2
3
for i = 1 to n-1:
if p[i] > p[i + 1]:
swap(p[i], p[i + 1])

对于所有测试点:$2 \leq n,m \leq 2 \times 10^5$,$t_i \in \{1,2\}$,$1 \leq x < n$,$0 \leq k < 2^{31}$。

这题在考场上写了神必线段树…复杂度也不对…就很弱智。

大概就是首先要去洞见冒泡排序的一个性质。每轮冒泡排序会让每个元素排到他后面第一个比他大的元素之前,把最大的元素移到序列最后。假设这是一对 $(i,j)$ ,$j$ 是 $i$ 后面第一个大于 $i$ 的元素。那么考虑这个操作使得, $i$ 移动到 $j$ 前面一个位置,同时所有 $x$ 之间不会彼此交换。

回顾这一过程,发现 $i+1\le x\le j-1$ 的所有 $x$ 的逆序对(此处特指 $x$ 与 $1\sim x-1$ 形成的逆序对)数量都会向前移动一位且不变(中间只会进行跟 $i$ 有关的操作),且由于本质上 $i$ 与前面构成的逆序对数量等于 $j$ 与前面构成的逆序对数量 (因为此时并不存在一个比 $i$ 小的 $k$ 满足 $a_k>a_i$ ,因为根据冒泡排序这会让 $a_i$ 被 $a_k$ 换掉成为前面某个「对」的 $x’$) ,所以此时 $j$ 的逆序对数为 $0$,那么 $i$ 的逆序对数也为 $0$ 。

更进一步,本题相当于需要维护一个序列 $\{p_n\}$,支持:

1、单点加/减(维护初始逆序对数

2、询问

考虑这东西就拿一个树状数组维护一下权值就好了。复杂度 $m\log n$ 。

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
ll ans ;
int cnt ;
int b[N] ;
int n, m ;
int res[N] ;
struct a{
int v ;
int p ;
}base[N] ;

bool comp(a x, a y){
return x.v < y.v ;
}
bool comp2(a x, a y){
return x.p < y.p ;
}
void add(int p, int v){
for ( ; p <= n ; p += low(p)) b[p] += v ;
}
ll ask(int p){
ll ret = 0 ;
for ( ; p ; p -= low(p)) ret += b[p] ;
return ret ;
}
ll s[N * 3] ;
ll t[N * 3] ;

void update(int rt, int l, int r, int p, int c1, int c2){
if (l == r){
s[rt] += c1 ;
t[rt] += c2 ;
return void() ;
}
int mid = (l + r) >> 1 ;
if (p <= mid) update(rt << 1, l, mid, p, c1, c2) ;
else update(rt << 1 | 1, mid + 1, r, p, c1, c2) ;
s[rt] = s[rt << 1] + s[rt << 1 | 1] ;
t[rt] = t[rt << 1] + t[rt << 1 | 1] ;
}
ll ask1(int rt, int l, int r, int ql, int qr){
if (ql <= l && r <= qr) return s[rt] ;
ll ret = 0 ; int mid = (l + r) >> 1 ;
if (ql <= mid) ret += ask1(rt << 1, l, mid, ql, qr) ;
if (qr > mid) ret += ask1(rt << 1 | 1, mid + 1, r, ql, qr) ;
return ret ;
}
int ask2(int rt, int l, int r, int ql, int qr){
if (ql <= l && r <= qr) return t[rt] ;
ll ret = 0 ; int mid = (l + r) >> 1 ;
if (ql <= mid) ret += ask2(rt << 1, l, mid, ql, qr) ;
if (qr > mid) ret += ask2(rt << 1 | 1, mid + 1, r, ql, qr) ;
return ret ;
}
int main(){
cin >> n >> m ; int t, c ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%d", &base[i].v), base[i].p = i ;
sort(base + 1, base + n + 1, comp) ;
for (int i = n ; i >= 1 ; -- i){
res[base[i].p] = ask(base[i].p) ;
ans += res[base[i].p] ; add(base[i].p, 1) ;
}
for (int i = 1 ; i <= n ; ++ i)
update(1, 1, n, res[i], res[i], 1) ;
sort(base + 1, base + n + 1, comp2) ;
for (int i = 1 ; i <= m ; ++ i){
scanf("%d%d", &t, &c) ;
if (t == 1){
swap(res[c], res[c + 1]) ;
update(1, 1, n, res[c], -res[c], -1) ;
update(1, 1, n, res[c + 1], -res[c + 1], -1) ;
if (base[c].v < base[c + 1].v)
res[c + 1] ++ ; else res[c] -- ;
swap(base[c], base[c + 1]) ;
update(1, 1, n, res[c], res[c], 1) ;
update(1, 1, n, res[c + 1], res[c + 1], 1) ;
}
else{
ll ret ;
if (c >= n - 1) puts("0") ;
else{
ret = ask1(1, 1, n, c + 1, n) ;
ret -= (ll)c * ask2(1, 1, n, c + 1, n) ;
//cout << c << " " << ask1(1, 1, n, c + 1, n) << " " << ask2(1, 1, n, c + 1, n) << endl ;
printf("%lld\n", ret) ;
}
}
}
return 0 ;
}

最后还是写的线段树,略略略

C 跑步

小 H 是一个热爱运动的孩子,某天他想给自己制定一个跑步计划。小 H 计划跑 $n$ 米,其中第 $i(i \geq 1)$ 分钟要跑 $x_i$ 米($x_i$ 是正整数),但没有确定好总时长。

由于随着跑步时间增加,小 H 会越来越累,所以小 H 的计划必须满足对于任意 $i(i >1)$ 都满足 $x_i \leq x_{i-1}$。

现在小 H 想知道一共有多少个不同的满足条件的计划,请你帮助他。两个计划不同当且仅当跑步的总时长不同,或者存在一个 $i$,使得两个计划中 $x_i$ 不相同。

由于最后的答案可能很大,你只需要求出答案对 $p$ 取模的结果。

对于全部的测试点,保证 $1 \leq n \leq 10^5$,$1 \leq p < 2^{30}$。

发现就是整数拆分问题。分拆数问题本质上是 $n$ 也无标号的第二类斯特林数问题(第二类斯特林数是 $n$ 有标号但是 $k$ 无标号)。

那么对于这个问题,考虑两种 $dp$.

  • 1、令 $f_{i,j}$ 表示对于 $i$ 拆分成若干个不大于 $j$ 的数的方案数。则有转移:

后面一项 $f_{i-j,j}$ 可以看成一个背包一样,后面的状态对前面的状态有天然的累加效应,所以只需要考虑丢掉一个 $j$ 的情况;而前面一项则把我们转移从后一项的等于 $j$ 升级成为不大于 $j$ 。

  • 2、令 $g_{i,j}$ 表示对于 $i$ 拆分成 $j$ 个数的方案数。则有转移:

前面一项表示新拆出一个 $1$ 来,还是背包的那种“累加”思想,所以只需要考虑拆出一个 $1$ 的情况;后面一项则表示不拆,而是把拆出的数全体都 $+1$,即本来的 $5=3+1+1$ 转移到 $8=4+2+2$ 。注意此处不会存在“部分拆出来的数加了但是剩下的没加”或者“加的不一样”,因为这两个状态都是可以归约到 $i$ 较小的 $g$ 上去所以不需要额外转移。

ps:似乎某硬币xx的容斥题就用到了这个思想来着。。。实际上就是个背包吧qaq

但是上述做法是 $n^2$ 的。总结两个 $dp$ 的优劣,发现如果采用根号分治的策略,对于 $f$ 只转移 $< \sqrt n$ 的,对于 $g$ 只转移 $\geq \sqrt n$ 的,那么两者均只需要 $n\sqrt n$ 的时空代价(因为大于 $\sqrt n$ 的数不会用超过 $\sqrt n$ 个)。

具体的,考虑对先用 $f$ 求出来 $j< \sqrt n$ 的方案数,再魔改一下 $g$,让 $g$ 只转移那些 $\geq \sqrt n$ 的数字:就是第一维把 $\sqrt n$ 当作步长转移即可。

之后考虑如何合并答案。发现 $f,g$ 对于同一个 $n$,计数的部分互斥且互补,那么就可以直接乘法原理解决。合并是个卷积状物,但由于本题只需要求第 $n$ 项,所以直接算即可。

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
const int B = 403 ;
const int N = 200010 ;

int S ;
int ans ;
int n, p ;
int f[N][B] ;
int g[N][B] ;
int X[N], Y[N] ;

int main(){
cin >> n >> p ;
S = n / B + 1 ; X[0] = 1 ;
for (int i = 0 ; i < B ; ++ i) f[0][i] = 1 ;
for (int j = 1 ; j < B ; ++ j)
for (int i = 1 ; i <= n ; ++ i){
if (i < j) f[i][j] = f[i][j - 1] ;
f[i][j] = (f[i - j][j] + f[i][j - 1]) % p ;
X[i] = f[i][j] ; //cout << i << " " << X[i] << endl ;
}
g[B][1] = 1 ; Y[0] = 1 ;
for (int i = 0 ; i <= n ; ++ i)
for (int j = 1 ; j <= S && j <= i ; ++ j){
if (i >= B) (g[i][j] += g[i - B][j - 1]) %= p ;
if (i >= j) (g[i][j] += g[i - j][j]) %= p ;
}
for (int i = 0 ; i <= n ; ++ i)
for (int j = 1 ; j <= S ; ++ j)
(Y[i] += g[i][j]) %= p ;
for (int i = 0 ; i <= n ; ++ i)
(ans += 1ll * X[i] * Y[n - i] % p) %= p ;
cout << ans << endl ; return 0 ;
}

D 序列

小 D 有一个长度为 $n$ 的整数序列 $a_{1 \dots n}$,她想通过若干次操作把它变成序列 $b_i$。

小 D 有 $m$ 种可选的操作,第 $i$ 种操作可使用三元组 $(t_i,u_i,v_i)$ 描述:若 $t_i=1$,则她可以使 $a_{u_i}$ 与 $a_{v_i}$ 都加一或都减一;若 $t_i=2$,则她可以使 $a_{u_i}$ 减一、$a_{v_i}$ 加一,或是 $a_{u_i}$ 加一、$a_{v_i}$ 减一,因此当 $u_i=v_i$ 时,这种操作相当于没有操作。

小 D 可以以任意顺序执行操作,且每种操作都可进行无限次。现在给定序列与所有操作,请你帮她判断是否存在一种方案能将 $a_i$ 变为 $b_i$。题目保证两个序列长度都为 $n$。若方案存在请输出 YES,否则输出 NO

对于所有测试点:$1 \le T \le 10$,$1 \le n,m \le 10^5$,$1 \le a_i,b_i \le 10^9$,$t_i \in \{1,2\}$,$1\le u_i,v_i \le n$。

被教育了,我大概并查集这方面就是白痴中的战斗机了。

考虑大概能琢磨出这么几个没啥用的性质:1、如果 $a,b$ 和 $b,c$ 两对之间分别被 $1$ 相连,那么相当于 $a$ 和 $c$ 被 $1$ 相连;2、如果 $a,b$ 之间 $0$ 相连,$b,c$ 之间 $0$ 相连,那么可以知道 $a$ 和 $c$ 就相当于有一条 $1$ 边。

然后…大概就可以搞一个边带权并查集了。同一个集合内部如果只有 $1$ 边,那么总和可以随意分配;如果某个集合内部向自己连了 $1$ 边和 $0$ 边,那么就可以让某两个元素同时加减,只要和是偶数即可。

其实也不难吧…还是自己过于弱菜啊。

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
int T ;
ll f[N] ;
int A[N] ;
int B[N] ;
int D[N] ;
int n, m ;
int fa[N] ;
int val[N] ;
int res[N] ;

int find(int x){
if (x == fa[x])
return fa[x] ;
int dad = find(fa[x]) ;
val[x] ^= val[fa[x]] ;
return fa[x] = dad ;
}
void merge(int c, int x, int y){
int f1 = find(x) ;
int f2 = find(y) ;
if (f1 == f2)
res[f1] |= val[x] ^ val[y] ^ c ;
else {
val[f1] = val[x] ^ val[y] ^ c ;
fa[f1] = f2 ; res[f2] |= res[f1] ;
}
}
int get_sign(int x){
return x ? -1 : 1 ;
}
int main(){
cin >> T ;
while (T --){
cin >> n >> m ;
int t, u, v, ans = 0 ;
for (int i = 1 ; i <= n ; ++ i){
val[i] = f[i] = res[i] = 0 ;
fa[i] = i, scanf("%d", &A[i]) ;
}
for (int i = 1 ; i <= n ; ++ i)
scanf("%d", &B[i]), D[i] = A[i] - B[i] ;
for (int i = 1 ; i <= m ; ++ i){
scanf("%d%d%d", &t, &u, &v) ;
if (t > 1) t -= 2 ; merge(t, u, v) ;
}
for (int i = 1 ; i <= n ; ++ i){
int p = find(i) ;
if (p == i) {
f[i] += D[i] ;
continue ;
}
f[p] += get_sign(val[i]) * D[i] ;
}
for (int i = 1 ; i <= n ; ++ i){
int p = find(i) ;
if (p != i) f[i] = 0 ;
if (res[i] && f[i] % 2 == 0) continue ;
else if (f[i] != 0) { ans = 1 ; break ; }
}
puts(ans ? "NO" : "YES") ;
}
return 0 ;
}

E 魔法

C 国由 $n$ 座城市与 $m$ 条有向道路组成,城市与道路都从 $1$ 开始编号,经过 $i$ 号道路需要 $t_i$ 的费用。

现在你要从 $1$ 号城市出发去 $n$ 号城市,你可以施展最多 $k$ 次魔法,使得通过下一条道路时,需要的费用变为原来的相反数,即费用从 $t_i$ 变为 $-t_i$。请你算一算,你至少要花费多少费用才能完成这次旅程。

注意:使用魔法只是改变一次的花费,而不改变一条道路自身的 $t_i$;最终的费用可以为负,并且一个城市可以经过多次(包括 $n$ 号城市)。

$1 \leq n \leq 100$,$1 \leq m \leq 2500$,$0 \leq k \leq 10^6$。

$1 \leq u_i, v_i \leq n$,$1 \leq t_i \leq 10^9$。

其实也不难?考虑暴力做的话就是分层图最短路,状态数是 $O(nk)$ 的。可以拿到洛谷数据的 $70$ 分。大概就是先拿每条边预处理出 $f_{i,j,1}$ 表示 $(i,j)$ 之间只修改了 $1$ 次的答案。考虑转移的话,自然就是以 $1$ 为步长转移(小技巧,只用枚举最小规模的子问题)。

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
int main(){
int u, v ; ll w ;
cin >> n >> m >> pq ;
memset(A, -1, sizeof(A)) ;
memset(f, 127, sizeof(f)) ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= n ; ++ j)
if (i ^ j) dis[i][j] = (ll)1e12 ;
for (int i = 1 ; i <= m ; ++ i){
scanf("%d%d%lld", &u, &v, &w) ;
A[u][v] = w, dis[u][v] = min(dis[u][v], w) ;
edg[i][0] = u, edg[i][1] = v, edg[i][2] = w ;
}
for (int k = 1 ; k <= n ; ++ k)
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= n ; ++ j)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]) ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= n ; ++ j)
f[i][j][1] = dis[i][j] ;
for (int k = 1 ; k <= m ; ++ k){
int x = edg[k][0] ;
int y = edg[k][1] ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= n ; ++ j)
f[i][j][1] = min(f[i][j][1], dis[i][x] + dis[y][j] - (ll)edg[k][2]) ;
}
for (int k = 2 ; k <= pq ; ++ k)
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= n ; ++ j)
for (int o = 1 ; o <= n ; ++ o)
f[i][j][k] = min(f[i][j][k], f[i][o][k - 1] + f[o][j][1]) ;
if (!pq) cout << dis[1][n] << endl ;
else cout << f[1][n][pq] << endl ; return 0 ;
}

发现最后的转移形式为

这是一个扩展矩乘的形式。所以可以直接把预处理出来的 $f_{i,j,1}$ 作为矩阵的元素,快速幂即可。

F 最小环

给定一个长度为 $n$ 的正整数序列 $a_i$,下标从 $1$ 开始编号。我们将该序列视为一个首尾相邻的环,更具体地,对于下标为 $i$, $j(i \leqslant j)$ 的两个数 $a_i$, $a_j$,它们的距离为 $\min(j-i, i+n-j)$。

现在再给定 $m$ 个整数 $k_1$, $k_2$,…, $k_m$,对每个 $k_i(i=1$, $2$,…, $m)$,你需要将上面的序列 $a_i$ 重新排列,使得环上任意两个距离为 $k_i$ 的数字的乘积之和最大。

对于所有测试数据:$1 \leqslant m \leqslant n \leqslant 2 \times 10^5$,$0 \leqslant k \leqslant \lfloor n/2\rfloor$,$1 \leqslant a_i \leqslant 10^5$。

为什么把这题放在 F 呢?因为一方面我最优化比较菜,另一方面我一看这种题就有种「信我,你不会」感觉233

这居然是个贪心…我也是人傻掉… 感觉自己贪心真的是菜爆了啊!

首先考虑相邻的元素大概是 $t~,~t+k~,~t+2\times k~,~t+3\times k~,~t+4\times k\cdots \pmod{n}$ 这种。记这个数列为「$t$ 在模 $n$ 意义下关于 $k$ 的轨迹」。

那么可以解一下方程求得循环节的长度:

根据同余的基本性质可以得出

那么可以知道最小的循环长度为 $\frac{n}{(n,k)}$ 。那么最多就会有 $(n,k)$ 条不同的轨迹。

另一方面,如果存在两个不同的 $t_0,t_1$,他们某一刻轨迹产生了相交,即

那么会有

因为这个式子等价于一个一元二次不定方程,可知如果这个式子可以解出一组整数解,必须满足

那么也就是说,如果两个 $t$ 的轨迹有相交,那么需要这两个 $t$ 之间的距离是 $(n,k)$ 的倍数。这也间接证明了,至多只会有 $(n,k)$ 条本质不同的轨迹。

考虑根据排序不等式,乘积方面一定是大的和大的拼在一起,小的和小的拼在一起更优。所以可以预处理每个不同的环长 $\zeta$ ,对于每一个 $\zeta$,把从大到小排好序的 $a_i$ ,$a_1\sim a_{\zeta}$ 分到第一组,$a_{\zeta+1}\sim a_{2\cdot \zeta}$ 分到第二组,以此类推。考虑对于同一组,最好的放的方式就是类似这样:

于是就可以按照奇偶性分个类预处理了。复杂度 $O(nd(n)+m\log n)$ 。后面那个 $\log$ 是求 $\gcd$ 的。

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
ll ans ; 
int n, m ;
ll res[N] ;
int base[N] ;

int gcd(int a, int b){
return !b ? a : gcd(b, a % b) ;
}
int main(){
cin >> n >> m ; int k ;
for (int i = 0 ; i < n ; ++ i)
scanf("%d", &base[i]) ;
sort(base, base + n) ;
for (int i = 1 ; i <= n ; ++ i){
if (n % i == 0){
for (int j = 0 ; j < n ; j += i){
for (int k = 0 ; k < i - 2 ; ++ k)
res[i] += (ll)base[j + k] * (ll)base[j + k + 2] ;
res[i] += (ll)base[j] * (ll)base[j + 1] ;
res[i] += (ll)base[j + i - 1] * (ll)base[j + i - 2] ;
}
}
}
for (int i = 0 ; i < n ; ++ i)
ans += (ll)base[i] * (ll)base[i] ;
while (m --){
scanf("%d", &k) ;
if (!k) printf("%lld\n", ans) ;
else printf("%lld\n", res[n / gcd(n, k)]) ;
}
return 0 ;
}

树状数组