ARC149
没有 F 题
A
A
A
B
B
B
-
题意：
给定序列 A,B，每次可以同时交换
A
i
,
A
j
A_i,A_j
Ai,Aj 与
B
i
,
B
j
B_i,B_j
Bi,Bj，求 lis(A)+lis(B) 的最大值
-
题解：
对于每次交换最多对一个序列的 lis 的长度影响是 1
可以通过
n
−
l
i
s
(
A
)
n-lis(A)
n−lis(A) 次交换让 A 变成
1
，
2
，
3
⋯
n
1，2，3\cdots n
1，2，3⋯n，也就是每次交换都让 A 的 lis 加一，但不一定会让 B 的 lis 长度减少，故把 A 排成单调上升的一定最优
-
代码
C
C
C
-
题意：
构造
n
×
n
n\times n
n×n 的网格图，每个格子中的数为
1
∼
n
2
1\sim n^2
1∼n2 中的一个且每个数字均不相同，使两个相邻的数字之和不为质数
-
题解：
奇数与奇数、偶数与偶数一定满足条件，只需要考虑奇数与偶数间的情况即可
如果有奇数和偶数的格子相邻，令这两个数一定是 3 的倍数，最小化这种情况出现（一半奇数一半偶数，只让中间的为奇偶数交界），最多有
n
n
n 个这样的交界，让这 2n 个格子都是 3 的倍数即可
n
<
6
n<6
n<6 的情况打表即可
-
代码
D
D
D
-
题意：
给定 n 个数和 m 个
d
i
d_i
di，要求对每一个数做以下处里
求这 n 个数最后结果，若中途变成 0 输出变成 0 的时间
-
题解：
首先考虑到对于 x 与 -x，最终结果为相反数或同时变成 0
这样就直接维护一段的情况，从 0 将整个序列分成正负两部分，每次将长度较少的一半并到较长的一半上处理即可
-
代码
E
E
E
-
题意：
有一个环，第
i
i
i 次操作将
a
i
,
a
(
i
+
1
)
m
o
d
n
⋯
a
(
i
+
m
−
1
)
m
o
d
n
a_{i},a_{(i+1)\bmod n}\cdots a_{(i+m-1)\bmod n}
ai,a(i+1)modn⋯a(i+m−1)modn 排序，给定进行次数和操作序列长度，已知最终序列求初始序列的情况数
-
题解：
转化一下操作，改为有一个大小为 m-1 集合和一个队列，每次把队首加入集合，并且将集合最小元素加入队尾
这样就把操作固定为只有 n-m+1 次了，因为操作小于 n-m+1 次的可以将没有进入过集合的数字删掉，大于 n-m+1 次的操作相当于就是后面的队列一直翻转
还原到只进行 n-m+1 次后的状态，考虑有多少种原来的方案可以达成这样的情况
设现在为
{
L
}
(
R
)
\{L\}(R)
{L}(R)，初始为
{
X
}
(
Y
)
\{X\}(Y)
{X}(Y)
若有
R
i
−
1
>
R
i
R_{i-1}>R_i
Ri−1>Ri，则说明
R
i
R_i
Ri 这个数一定在加入集合的瞬间被弹出了，故有
Y
i
=
R
i
Y_i=R_i
Yi=Ri，故需要把
R
R
R 中这些数去掉，改为单调递增的
考虑剩余的情况
若
L
L
L 不为
(
n
−
m
+
1
)
∼
n
(n-m+1)\sim n
(n−m+1)∼n 这样的答案一定为 0
对于
R
i
R_i
Ri，初始可能在
X
X
X 集合或者在
Y
1
∼
i
Y_{1\sim i}
Y1∼i，处理完
R
R
R 后把
L
L
L 中所有数字全排列即可，故情况数为
m
R
s
z
×
(
m
−
1
)
!
m^{Rsz}\times (m-1)!
mRsz×(m−1)!。
代码
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
