比赛场次 | 641 |
---|---|
比赛名称 | 梦熊NOIP第一场 |
比赛状态 | 已结束比赛成绩 |
开始时间 | 2024-11-10 15:00:00 |
结束时间 | 2024-11-11 11:11:11 |
开放分组 | 全部用户 |
注释介绍 | 重现赛,可以交交代码补补题! |
题目名称 | IMAWANOKIWA |
---|---|
输入输出 | popc.in/out |
时间限制 | 3000 ms (3 s) |
内存限制 | 512 MiB |
测试点数 | 25 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|
给你一个初始长度为 n,只包含 0,1,2 的序列 a1∼n,你可以执行以下操作:选择相邻的两个位置 j 和 j+1,删去 aj,aj+1,并在原位置插入 popc(aj+aj+1),后半部分序列因此向前移动一位。其中,popc(x) 表示 x 在二进制表示下 1 的个数。显然每次操作后序列长度都会减少 1,所以执行 n−1 次操作后,这个序列会恰好剩下一个数。
记在所有可能的 n−1 次操作之后剩下的数的最小值为 t,定义一个好的操作序列 p 为一个长度为 n−1 的正整数序列,其中 pi 表示第 i 次操作所选择的 j(显然 1≤pi≤n−i),且满足按照这个操作序列操作之后剩下的数为 t,你需要求出 t 与字典序最小的好的操作序列。
如果你不会求出字典序最小的好的操作序列也可以获得部分分数,详见【评分方式】。
为了避免输出量过大,你只需要输出字典序最小的好的操作序列按照某种哈希方式得到的哈希值即可,详见【输出格式】。
本题有多组测试数据。
第一行,一个正整数 T,表示数据组数。接下来,对于每组数据:仅一行,一个长度为 n 的字符串,其中第 i 个字符表示 ai。
对于每组测试数据:输出一行,两个自然数 t, Hash(p′),其中第一个数表示剩下的数的最小值;第二个数表示字典序最小的好的操作序列 p′ 的哈希值 Hash(p′),定义见下。如果你输出的第二个数不正确,也可以获得部分分数,本题将使用自定义校验器做到这一点,详见【评分方式】。令 B=13331,M=264,我们定义一个正整数序列 c1∼l 的哈希值 Hash(c) 为 ∑i=1lBl−ici 对 M 取模的结果。
提示:代码实现时可以使用 C++ 的 unsigned long long 类型的自然溢出来实现对 2^64 取模的效果。
7 110121 120202 1202 1121212 000 010101110 0112210112
1 31589928355420248 1 31587559229276557 2 177728893 2 15233797274127957404 0 13332 1 4098728445451629840 1 892964726593242284
对于第一组数据,字典序最小的好的操作序列 p 为 [1,3,2,1,1],按照该操作序列操作时,a 序列的变化过程如下:
[1,1,0,1,2,1]
[1,0,1,2,1]
[1,0,2,1]
[1,1,1]
[1,1]
[1]
所以你应输出的哈希值为Hash([1,3,2,1,1])=(1×13331^4+3×13331^3+2×13331^2+1×13331^1+1×13331^0) mod 2^64=31589928355420248。
对于第二组数据,字典序最小的好的操作序列 p 为 [1,2,2,1,1],按照该操作序列操作时,a 序列的变化过程如下:
[1,2,0,2,0,2]
[2,0,2,0,2]
[2,1,0,2]
[2,1,2]
[2,2]
[1]
在此键入。
在此键入。