1 条题解
-
0
A
使用桶进行储存,然后从最大的分数从小历遍,当现在是第三个有值的,这就是第三,然后输出分数和人数就可以了。
B
使用 dfs 和 bfs 搜出来所有可以走到的格子即可,然后按题意计算价值。
C
40pts
一共只有 个点,手动讨论两个人的选择情况,时间复杂度为 。
80pts
考虑 表示 Alice 目前把 集合染成了黑色,Bob 目前把 集合染成了白色两人采取最优策略的最终答案。
如果为 Alice 的回合,一定选所有后继状态中的最大值,如果为 Bob 的回合,一定选后继状态的最小值,每个点只有黑色/白色或还未被染色,时间复杂度不超过 。
100pts
如果一条边最终不是黑边也不是白边,我们看成两人分别得到了这条边边权的一半。
所以把每个点的点权看作所有邻边的边权之和的一半,按照点权两人从大到小依次取即为最优策略。
D
考虑求出使得 不同的第一个位置 ,有如下限制:
-
需要修改的位置数量不能超过 。
-
没有考虑到的位置数量不能小于还需要修改的位置。
具体地,对于每一位 ,求出 表示在第 位之前有多少 的位置。 合法的必要条件是 ,先判掉。由于上述限制要求修改位置数量既不能太小,也不能太大,所以需要考虑当前位置是否修改:
-
若 ,说明可以不修改。此时若 且 ,则 合法。
-
若 或 ,说明可以强制修改(因为当 时不能修改)。此时若 且 ,则 合法。
若找不到合法的 则无解。
输出答案的过程中时刻维护变量 ,表示还需要修改的位置数:
-
若当前位 ,输出 。
-
若当前位 ,若 且 ,输出 ,否则输出 ,前者因为这一位必须修改(否则将导致剩余位数小于要修改位数,不合法)。
-
若当前位 ,若 且 输出 8 ,否则输出 9 。
-
若输出的数字与 不同,则令 自减 。
-
若 ,则输出 。
时间复杂度线性。
E
10pts
暴力枚举所有可能的情况,进行判定。
30pts
可能满足要求的 至多 种,枚举哪些 满足条件作容斥,把相同的数放在一起,答案为 ,把所有可能的情况的答案加在一起即可。
100pts
我们考虑对于一个 而言,满足要求的字符串有 ,但是答案会算重。
因此我们考虑对于一个 ,计算 是所有满足要求的 中最小的一个时的方案数。
这意味着不存在 ,使得 。
又由于 成立,因此 。
对比两个式子,可以得到 。
即如果 是所有满足要求的 中最少的一个,等价于 是一个不好的字符串,但在这里 ,而原问题中 ,有细微差异。
记 为长度为 的字符串中好的个数(), 为好的个数(),那么有
上述表达式可以利用前缀和进行优化,时间复杂度为 。
$$g[n]=m^n -(\sum_{2i \leq n} g[i] \times m^{-2i}) \times m^n$$ -
- 1
信息
- ID
- 192
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 3
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者