分类: 题解

58 篇文章

P7878 「SWTR-07」My rating is 1064(hard version) 题解
题目链接。 解析 首先第一个帖子肯定会由某一个账号发出。大力观察可以发现当第二个账号发帖之后,接下来一定可以至少两个账号交替发帖,即安全系数不再会有损失。我们仅需要解决第二个账号第一次发帖在哪一个位置即可。 假设我们确定了第二个账号第一次发帖的位置 $i$,那么剩下的 $k-2$ 个账号一定会在 $[i+1,n]$ 中选择 $k-2$ 的最大值进行…
P7099 [yLOI2020] 灼 题解
题意 题目链接。 数轴上有 $n$ 个虫洞,有 $q$ 个按坐标升序给出的飞船,保证飞船一定在不会在第一个虫洞左边或最后一个虫洞右边。每个飞船每秒会等概率左移一格或右移一格,对于每个飞船,求到达任意一个虫洞的期望时间。 解析 记 $f_i$ 为位置在 $i$ 的飞船的期望时间,只要 $i$ 位置没有虫洞(有虫洞期望时间显然为 $0$),就有 $f_…
CF1601A Array Elimination 题解
题意 题目链接。 有一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$,每次操作选择 $k$ 个数,将这 $k$ 个数减去他们的与(二进制运算中的与)的和。求哪些 $k$ 可以在有限次操作内使所有数变成 $0$。 解析 蛮有趣的。把所有数化成二进制后,你考虑每一位。如果共有 $x$ 个数在某一位上为 $1$,那么考虑如果指定了一个 …
P7716 「EZEC-10」Covering 题解
题目链接。 解析 后边的 dp 方式似乎和已有题解有一些差异。 首先考虑从第 $1$ 张纸片开始一张张放,计算出每张纸片有多少种放法,这分为三种情况: 最后局面该纸片占两格,显然只有 $1$ 种放法。 最后局面该纸片占一格,那么可能的放法有 $4$ 种,去除其中会覆盖最终局面的放法即可。 最后局面不存在该纸片,那么可能的放法为所有未被覆盖的位置的放…
CF1381C Mastermind 题解
题意 题目链接。 给你一个序列 $a$,让你输出一个序列 $b$ ,这个 $b$ 满足跟 $a$ 有 $x$ 个位置上的元素一样。有 $y$ 个元素跟 $a$ 里边的元素一样。值域是 $1\le v \le n+1$。 解析 先考虑这么一件事情:假如你已经确定了这 $x$ 个位置是什么,那么问题转化为:你需要将若干个元素交换位置,使得与原来元素相同…
2021牛客提高第二场 B.方格计数 题解
题意 在左下角是 $(0,0)$,右上角是 $(W,H)$ 的网格上,有 $(W+1)\times (H+1)$ 个格点。 现在要在格点上找 $N$ 个不同的点,使得这些点在一条直线上。并且在这条直线上,相邻点之间的距离不小于 $D$。求方案数模 $10^9+7$。 解析 纯组合方法求方案数,是我不会的东西。所以赛时就考虑用 dp 来统计方案数。 …
P7883 平面最近点对(加强加强版) 题解
题意 题目链接。 给定 $n$ 个二维欧几里得平面上的点 $p_1, p_2, \dots, p_n$,请输出距离最近的两个点的距离。 解析 在这题下给一篇正经的分治做法,已有的分治做法是用 vector 实现的,可能对于部分同学来说代码实现不便。其他题解都是非分治的。 我们将所有点按照 $x$ 坐标排序后标号为 $1,2,\dots n$,记 $…
SP10050 POWTOW – Power Tower City 题解
题意 题目链接。 洛谷这题的评测似乎炸掉了,这里有 Znloye 提供的临时测试点。 求 $a^{a^{a^{\dots}}}(b\ 个\ a)$ 的末 $9$ 位数,$t$ 组数据。 解析 保留末 $9$ 位数等价于对于 $10^9$ 取模,再补全前边的 $0$ 即可。 而对于这种 Power Tower,一种常用的方法是使用扩展欧拉定理,再在快…
P1477 [NOI2008] 假面舞会 题解
题目链接。 发现题解区说大多都是直接说再连一条边权为 $-1$ 的边,在这里略微证明一下正确性。​ 解析 首先发现若图中没有环,最大答案为所有联通块的最长链长度之和,最小答案为 $3$。 若存在环,则最大答案为所有环的 $\gcd$​​。为了在可接受的时间内找到所有环,我们对于每一条边的 $u\rightarrow v$​​,从 $u$​​ 向 $…
CF1557D Ezzat and Grid 题解
题意 题目链接。 给定 $n$ 行 01 串,其中有 $m$ 个区间为 $1$​。删除若干 01 串使剩余串美丽,若干条 01 串美丽当且仅当任意相邻两个 01 串至少有相同的一位均为 $1$。 $n,m\le 3\times10^5$。 解析 考虑记 $f_i$ 为以第 $i$ 串结尾的最长美丽串的长度。发现 $f_i=f_j+1,j\in[1,…