7.19
peidi
·
·
个人记录
無题
题目限制
2000 ms 1024 M
题目描述
空不是无，空是一种存在，你得用空这种存在填满自己。
有一条无限长的数轴，上面有 n 个坑，第 i 个坑的位置为 x_i。你将要在数轴上再放置 n 个球，第 i 个将要放到的位置为 y_i。每当有一个球被放上去之后，它就会滚落到离它最近的一个坑里并填上那个坑。如果有两个坑都离它最近，那么它会落到左边的里面。
现在 xuanxuan001 可以决定 n 个球的放置顺序，为了节省时间，xuanxuan001 希望球的滚动距离总和尽量短，但他太菜了，所以需要你来帮他求出最短总距离并构造一个对应方案。
输入格式
第一行一个正整数 n ，即为球 / 坑的数量。
第二行 n 个正整数，第 i 个数即为 x_i，表示每个坑的位置。
第三行 n 个正整数，第 i 个数即为 y_i，表示每个球的位置。
输出格式
第一行一个正整数，表示最短总距离。
第二行 n 个正整数，即为依次放置的球的编号，显然需要是一个排列。
输入样例 1
3
1 2 3
11 12 13
输出样例 1
30
3 2 1
输入样例 2
2
1 10
9 20
输出样例 2
18
2 1
输入样例 3
2
1 20
9 10
输出样例 3
18
1 2
输入样例 4
4
1 2 14 15
10 11 12 13
输出样例 4
22
3 4 2 1
数据范围
对于所有数据， 1 \le n \le 2 \times 10^5，0 \le a_1 < a_2 < \cdots < a_n \le 10^9，0 \le b_1 < b_2 < \cdots < b_n \le 10^9，所有的 a_i 与 b_i 这 2n 个数都互不相同。
| 子任务编号 |
n \le |
分值 |
| 1 |
10 |
10pts |
| 2 |
2000 |
50pts |
| 3 |
2 \times 10^5 |
40pts |
排列
题目限制
1000 ms 512 M
题目描述
给定正整数 n，你需要构造 k 组 (0,1,\dotsc,n-1) 的排列（记为 F_1\sim F_k，其中 F 排列的下标从 0 开始计数），使得其满足以下条件：
-
0\leq k\leq \lceil\log_2n\rceil+1
-
-
在这里，\circ 表示函数的复合，当 k=0 时 (G_k\circ G_{k-1}\circ\dotsc\circ G_1) 视为恒等函数。
输入格式
一行一个正整数 n。
输出格式
若无合法构造方案，输出一行一个整数 -1。
否则第一行输出一个整数 k，其中 k 应满足 0\leq k\leq \lceil\log_2n\rceil+1。
接下来 k 行每行 n 个整数表示 F_{i,0}\sim F_{i,n-1}，你需要保证给出的 F_i 是一个 (0,1,\dotsc,n-1) 的排列。
数据范围及提示
本题下发 checker.exe 和 checker 可执行文件，使用方法 ./checker <input-file> <output-file> <answer-file>，在答案不为 -1 时，你可以使用任意一个下发的 .ans 文件来代替 <answer-file>。
对于所有数据，1 \le n \le 1000。
| 子任务编号 |
n \le |
特殊性质 |
子任务依赖 |
分值 |
| 1 |
10 |
无 |
无 |
20pts |
| 2 |
1000 |
保证 n=2^i |
无 |
20pts |
| 3 |
1000 |
保证 n\bmod 2=0 |
无 |
20pts |
| 4 |
1000 |
保证 n\bmod 2=1 |
无 |
20pts |
| 5 |
1000 |
无 |
1,2,3,4 |
20pts |
输入样例 1
3
输出样例 1
3
0 2 1
1 2 0
2 0 1
样例解释
当 x=0 时，有：
其余同理。
输入样例 2
4
输出样例 2
3
3 2 0 1
0 3 1 2
1 3 0 2
输入样例 3
6
输出样例 3
4
5 3 1 0 4 2
0 1 4 5 3 2
2 3 4 5 1 0
1 2 3 4 5 0
样例 4
见下发文件。
Random
题目限制
3000 ms 512 M
题目描述
你有一个随机数生成器，可以生成一个 1 到 n 的随机整数，生成 i 的概率为 \frac{A_i}{S}，其中 S = \sum_{i = 1}^{N} A_i。生成器的每次生成是独立的。
你有一个整数 X，初始为 0。你要一直进行如下操作直到 X 变为 K：
使用生成器生成一个随机数 v 并将 X 改为 X + v \mod M。
请求出操作次数的期望值，对 998244353 取模。
输入格式
第一行三个正整数 N，M，K。
第二行 N 个正整数，第 i 个数为 A_i。
输出格式
输出答案。
数据范围
对于所有数据，1 \leq N \leq 500, N < M \leq 10^{18}, 1 \leq K < M, 1 \leq A_i \leq 100。
| 子任务编号 |
依赖子任务 |
N \leq |
M \leq |
特殊性质 |
分值 |
| 1 |
|
500 |
500 |
|
10 |
| 2 |
|
10 |
100000 |
|
15 |
| 3 |
|
500 |
10^{18} |
保证 A_i = 1 |
20 |
| 4 |
2 |
100 |
10^{18} |
|
25 |
| 5 |
1, 3, 4 |
500 |
10^{18} |
|
30 |
输入样例 1
2 3 1
1 1
输出样例 1
2
输入样例 2
5 10 1
1 2 3 4 5
输出样例 1
100529834
Cookies
题目限制
2000 ms 512 M
题目描述
你有 n 个饼干, 第 i 块甜度是 A_i, 有 m 个小朋友来家里做客, 每个人会带一块甜度为 B_i 的饼干, 每个人还有一个口味偏好 S_i. 考虑如下过程:
- 你先将你的饼干 [1,k] 放在桌子上
- 小朋友按 1,2,3,\dots,n 的顺序逐个过来, ta 会先把自己带的饼干放到桌上, 然后根据 ta 的偏好, 若 S_i 为
B, 那么 ta 会把桌上甜度最小的饼干带走; 如果为 S, ta 会把甜度最大的拿走
你需要每个 k=1,2,\dots,n, 求出最后留在桌子上的饼干的甜度值之和
你需要先得出 k=i 的答案, 才能得出 A_{i+1}, 具体见输入格式
输入格式
第一行一个正整数 n
第二行一行 n 个非负整数 A'_1,A'_2,\dots,A'_n
第三行一个正整数 m
第四行一行 m 个非负整数 B_1,B_2,\dots,B_m
第五行一个长度为 m 的字符串 S
A'_i$ 为 $A_i$ 的加密值, 真实值可计算为 $A_i = (A'_i + lastans) \mod 10^9 $, $lastans$ 初始为 $0
输出格式
输出一行 n 个数, 依次为 k=1,2,\dots,n 时的答案
数据范围
对于所有数据， 1 \le n,m \le 2 \times 10^5 , 1 \le A'_i,B_i < 10^9
| 子任务编号 |
n \le |
m \le |
分值 |
特殊性质 |
| 1 |
10^3 |
10^3 |
10 |
|
| 2 |
2 \times 10^5 |
2 \times 10^5 |
15 |
S 仅包含一种字符 |
| 3 |
2 \times 10^5 |
2 \times 10^5 |
25 |
S 的极长相同字符连续段数不超过 20 |
| 4 |
5 \times 10^4 |
5 \times 10^4 |
10 |
|
| 5 |
10^5 |
10^5 |
10 |
|
| 6 |
2 \times 10^5 |
2 \times 10^5 |
30 |
|
输入样例 1
3
3 999999999 0
2
4 2
BS
输出样例 1
2 5 9
输入样例 2
10
810737462 262894941 12979345 90139935 834123271 768745833 928886601 144082546 35547099 840309069
10
854737038 93768450 848842263 62613614 800833082 316988396 203584286 283415773 762732633 756024517
SBSSSBSSBS
输出样例 2
756024517 959608803 1243024576 1560012972 1893177483 2287313726 2503514053 3151110652 3337768403 3515845875
样例解释
对于样例1 ,解密后 A=(3,1,5)
- 你将甜度为 $3$ 和 $1$ 的两块饼干放在桌子上
- 第一个小朋友带来甜度为 $4$ 的饼干, 拿走甜度为 $1$ 的饼干
- 第二个小朋友带来甜度为 $2$ 的饼干, 拿走甜度为 $4$ 的饼干
- 留在桌子上的饼干甜度分别为 $2$ 和 $3