U189344 11.15归档
题目描述
```
第一题
选民
时间限制：1秒
空间限制：512MB
源程序名：voter.cpp/c/pas
【题目描述】
拜登和伯尼桑德斯的总统选举，有n个选民，每个人有一个权势值ai，选民可以自由的选择自己喜欢的候选人，甚至可以两个候选人都选。找出一个权势值总和最大的选民集合，使得其
中不低于半数人投了乔拜登，并且不低于半数人也投了伯尼桑德斯。
【输入格式】
第一行输入一个整数 n(n≤10^5)，表示某一州中参与选举的民众个数。
接下来 n 行，第 i 行共有一个字符串 si 和一个正整数 ai (0 < ai ≤ 5000)。
其中 si = 00 表示这个选民既没有投乔拜登，也没有投伯尼桑德斯；
si = 01 表示这个选民没有投乔拜登，但有投伯尼桑德斯；
si = 10 表示这个选民有投乔拜登，但没有投伯尼桑德斯；
si = 11 表示这个选民既有投乔拜登，也有投伯尼桑德斯。
【输出格式】
输出一行一个非负整数——可能采访到选民集合的权势最大值。
第二题
hihocoder
时间限制：1秒
空间限制：512MB
源程序名：hihocoder.cpp/c/pas
给定 n, k，计算有多少长度为 k 的数组 a1, a2, ..., ak,(ai ≥ 0) 满足：
• a1 + a2 + ... + ak = n
• ∀i ∈ [1, k)，有 a[i] AND a[i+1] = a[i+1] 成立，其中 AND 是按位与操作。
k ≤ 5 · 10^6 , n ≤ 5 · 10^6
【输入格式】
输入只有一行，包含两个整数 k, n 。
【输出格式】
输出一行表示对应的答案，由于答案可能很大，答案对 998244353 取模。
第三题
IMO
时间限制：1秒
空间限制：512MB
源程序名：imo.cpp/c/pas
在 IMO2019 中，有一道这样的题：
巴斯银行发行的硬币在一面上铸有 H，在另一面上铸有 T。哈利有 n 枚这样的硬币并将这些硬币从左至
右排成一行，他反复地进行如下操作：如果恰有 k (k > 0) 枚硬币 H 面朝上，则他将从左至右的第 k 枚硬币
翻转；如果所有硬币都是 T 面朝上，则停止操作。
例如：当 n = 3，并且初始状态是 T HT，则操作过程为 T HT → HHT → HTT → TTT，总共进行了
三次操作后停止。
(a) 证明：对每个初始状态，哈利总在有限次操作后停止。
(b) 对每个初始状态 C，记 L(C) 为哈利从初始状态 C 开始至停止操作时的操作次数，例如：L(T HT) = 3，
L(T T T) = 0，求 C 取遍所有 2
n 个可能的初始状态时得到的 L(C) 的平均值。
这道题目的问法实在是太无趣了，所以 Niyiz 换了种问法：
• 给定一个包含 H, T, ? 的字符串 s，其中 ? 表示该位可能是 H 或者 T，求 ? 取遍所有情况时 L(C) 的平
均值。
你能解决这个问题吗？
【输入格式】
输入一行字符串 s。|s|≤10^6
【输出格式】
输出一行表示 L(C) 的平均值，对 998244353 取模。
第四题
序列交换
时间限制：1秒
空间限制：512MB
源程序名：swap.c/cpp/pas
【题目描述】
给出一个长度为 n（n≤2·10^5） 的数列 a1, a2, · · · , an，以及一个整数 x，定义一次操作为：
• 选择一个下标 i (1 ≤ i ≤ n) ，交换 ai 与 x 的值。
你的目标是用最少的操作使得数列 a 单调不降（注意不需要考虑 x）。
你还能解决这个问题吗？
【输入格式】
第一行包含两个整数 n, x, type。其中 n, x 的含义如题面所示，type 是数据类型提示，它可以帮你获取部
分分，这个参数的含义在【数据范围与提示】中有具体的描述。
第二行包含 n 个整数，分别表示 a1, a2, · · · , an。
【输出格式】
输出一个整数，表示最少的操作次数。
```
输入格式
无
输出格式
无
说明/提示
每一组样例对应一题，时间问题没有分开，草草归档\
T1有1组，T2,T3各有3组，T4有1组\
sample.zip中有大样例