Posts by hostmaster

题意 在一个有一个圆形岛屿，半径为 $1$，有一个人在岛屿的正中央。一只鳄鱼在岛屿的一个边境上。鳄鱼每时每刻都想更靠近这个人一点，如果已经最近了就停下不动。问这个人如何逃离这个岛屿。鳄鱼的移动速度是人的 $4$ 倍。 题解 看题解之前最好先思考一下。 查看题解 在以岛屿中心为中心的，半径为 $\frac14$ 的小圆里，人有速度优势，就是…

题意 有冰火两种战士，每个战士有温度和能量两个属性。战场也有一个温度。 一个冰战士能够参赛，当且仅当战场温度不低于自身温度。 一个火战士能够参赛，当且仅当战场温度不高于自身温度。 开战时，冰系战士按自身温度从低到高排序，火系战士按自身温度从高到低排序，温度相同时能量大的战士排在前面。首先，双方的第一位战士之间展开战斗，两位战士消耗相同的能…

题意 有一个 $n$ 位的大数，有 $m$ 个限制。 每个限制 $\left[l1, r1, l2, r2\right]$ 表示大数的 从左往右数第 $l1$ 位 到 从左往右数第 $r1$ 位，与 大数的 从左往右数第 $l2$ 位 到 从左往右数第 $r2$ 位 完全一致。 求有多少数满足限制。 $1 \leq n, m \leq 10^5$…

CSP-S 分数刚好可以参加 NOIP，hzt 同学少了几分不能去，真惨。 这次去 NOIP 就是去熟悉一下环境，最好还能去省选玩一玩。 UPD，真的去省选了。 剩下的就不说什么了（

Day -1 早上去机房，教练讲了一些技巧和坑点。 回家之后一直在划水。 看了一下 CSP - S 的考纲，发现好像二分图最大匹配还不太熟，于是复习了一下。 有点紧张。 希望可以拿提高一等吧。 RP++ Day 0 由于没有公元 0 年，所以也没有 Day 0。 Day 1 顺利进入考场，解压密码 $\texttt{belief2022}$…

Day -1 早上去机房，教练讲了一些技巧和坑点。 回家之后一直在划水。 看了一下 CSP - S 的考纲，发现好像二分图最大匹配还不太熟，于是复习了一下。 希望可以 AK 普及吧。。。 RP++ Day 0 由于没有公元 0 年，所以也没有 Day 0。 Day 1 顺利进入考场，一边输对解压密码。第一题想到了在快速幂时判断，但其实可以…

比赛链接 题解 B 直接构造，显然答是 $1, n, \left(n - 1\right), \left(n - 2\right), \ldots, 2$。 C 可以 DP，也可以贪心。 D 因为位数越多数越大，所以第一个串一定全选。接下来看第二个串怎么选。 考虑尽可能让 $s$ 的高位变成 1。可以把第一个 0 找出来，然后发现只能在这…

比赛链接 题解 A 显然，如果数组不是全 $0$，就一定可以变成 $\left[1\right]$。 B 考虑最优情况一定是 $000...0 111...1$，所以要把数组里的 $1$ 都调到最后面。具体实现方法是遍历数组，一共有 $cnt$ 个 $1$，接着遍历数组的最后 $cnt$ 个元素，一共有 $k$ 个 $0$，则需要 $k$…

概述 费马小定理：$a^{p - 1} \equiv 1 \pmod p$ 当 $p$ 是质数且 $a$ 是小于 $p$ 的正整数。 但是费马小定理的逆定理不成立，比如 $2^{340} \equiv 1 \pmod{341}$，但是 $341 = 11 \times 13$。 Miller 和 Rabin 提出了二次探测定理： 假设有…

题意 有 $n$ 只奶牛和 $m$ 个食物，第 $i$ 个食物有价格 $c_i$ 和美味度 $d_i$。 第 $i$ 只奶牛要求吃一个价格至少为 $a_i$ 且美味度至少为 $b_i$ 的食物。 问最少花费。无解输出 -1。 题解 这是一个二维的问题，我们可以把其中一维排序，这个问题就变成了一维。 所以我们可以按照美味度排序，然后按美味度…