置顶
什么？你也玩原神！？
2023-09-07 3.4k 字 12 分钟

什么？你也玩原神！？

困至极点 故作此文 以振精神引言我有一个惊为天人的特性，很多人都有，但是他们都没有发现过。然而就在今天，我，发现了！每个人都是由许许多多的原子构成的。这样好呀！我是由原子构成的！好耶好耶！咳咳，既然这样，我们就是有正电荷的生物。那么为什么我们对外不显电性呢？上过幼儿园的小朋友们应该都知道，原子核外有电子，电子带负电荷，正电荷吸引着负电荷围着它转，又或者两个原子之间有公共电子，这样整个环境就会成电中性，我们也就不带电。 但是！重点来了！ 首先说一些前置芝士： 电流是电子在导体中做定向移动产生的； 石墨的导电原理是其平面六边形结构可以使得一个电子在原子之间移动，去替换本身原子周围的电子，循环往复
题解 洛谷 CF1809D Binary String Sorting
2023-10-25 620 字 3 分钟

题解 洛谷 CF1809D Binary String Sorting

CF1809D Binary String Sorting简要题意给定一个 $01$ 串，要求你交换相邻两个数或删掉一个数，使得该串单调不降。其中交换相邻两个数的代价是 $10^{12}$，删除的代价是 $10^{12} + 1$，求最小代价。 策略分析本题需要我们发现一个重要的性质，因为我们需要把数列变成形如 00000...11111 的形式，所以必然存在一个分界点，这个分解点的两边的数可能是 $10$ 或 $01$。现在假设我们知道这个分界点在哪里了，那么我们就要把分界点左边的 $1$ 想办法弄到右边，或者直接扔掉。我们发现，除非是 $10$ 情况下的分界点左边的那个 $1$，其余的 $
题解 SP6285 NGM2 - Another Game With Numbers
2023-10-24 600 字 3 分钟

题解 SP6285 NGM2 - Another Game With Numbers

SP6285 NGM2 - Another Game With Numbers简要题意给定一个长为 $K$ 的数组 $a$，其中 $1 \le K \le 15$ 且 $a_i \le 100$，再给定一个数 $N$，其中 $1 \le N \le 10^9$，要求求出 $[1, N]$ 中有多少数不能被 $a$ 中任意一个数整除。 策略分析显然满足我们要求的数不能被 $a_i$ 整除，同时也不能被 $a$ 中任意 $p(2 \le p \le K)$ 个元素的最小公倍数整除。所以最朴素的想法是通过筛选出能够被整除的数的个数，再用 $N$ 减去它。如果你想到这里了，那么恭喜你这道题已经做完了。
题解 JZOJ5952. 【NOIP2018模拟11.5A组】凯旋而归
2023-10-03 1.7k 字 8 分钟

题解 JZOJ5952. 【NOIP2018模拟11.5A组】凯旋而归

JZOJ5952. 【NOIP2018模拟11.5A组】凯旋而归简要题意对于一个数列 $num$，一个函数 $f$ 定义如下：$$f(num) = \max{(a_1 \oplus a_2 \oplus \dots a_i) + (a_{i+1} \oplus a_{i+2} \oplus\dots a_n) | i \in [0, n] }$$现在给你一个数列，依次求出其所有前缀的 $f$ 的值。 策略分析首先我们需要一些前置知识，我们在求一个数列的子段异或和的时候，可以像其普通加法求和一样处理出前缀和并 $O(1)$ 求解。那么对于异或前缀和数组 $a$ 来讲，区间 $[l,r]
题解 AT_arc129_b Range Point Distance
2023-09-26 624 字 3 分钟

题解 AT_arc129_b Range Point Distance

AT_arc129_b Range Point Distance简要题意给定 $N$ 对 $L_i, R_i$，然后在每次给出后都要选一个 $x$ 使得 $x$ 到之前给出的所有区间的距离 $dist$ 的最大值最小。一个 $x$ 到区间 $l,r$ 的距离定义为 $dist=\max(0, l - x, x - r)$。 策略分析既然我们每次都要输出答案，那我们不妨从 $dist$ 的定义入手，我们发现在这个定义中，当其结果不为 $0$ 时只有两种情况，要么 $l$ 在 $x$ 右边，要么 $r$ 在 $x$ 左边。那么我们考虑现在有一堆区间，因为我们求的是 $x$ 到所有区间距离
题解 洛谷 P1486 [NOI2004] 郁闷的出纳员
2023-09-26 1.4k 字 7 分钟

题解 洛谷 P1486 [NOI2004] 郁闷的出纳员

P1486 [NOI2004] 郁闷的出纳员简要题意给定 $n$ 次操作和一个阈值 $min$，每次操作包含一个字符 $opt$ 和一个整数 $k$，操作可以是一下四种之一： I k 如果 $k$ 小于 $min$ 不操作，否则将 $k$ 扔进一个集合 $s$ 中。 A K 把 $s$ 里所有元素值加上 $k$。 S k 把 $s$ 里所有元素值减去 $k$。 F k 查询 $s$ 里第 $k$ 大的值，如果 $k > \left | s \right | $ 输出 -1。 在每次操作中，一旦 $s$ 中有元素的值低于阈值 $min$，就要删除这个元素，程序最后要输出删除的元素总数（
题解 AT_arc129_a [ARC129A] Smaller XOR
2023-09-26 428 字 2 分钟

题解 AT_arc129_a [ARC129A] Smaller XOR

AT_arc129_a [ARC129A] Smaller XOR简要题意给你三个数 $N, L, R$，询问满足 $x \in [L, R]$ 且 $(x \oplus N) < N$ 的整数 $x$ 的个数。 策略分析我们考虑异或运算的性质，当某一位为 $0$ 时，它异或一个值可能增大或者不变，当某一位为 $1$ 时，它异或一个值可能减小或不变，也就是说一个数 $k$ 想要满足异或一个 $x$ 要比自己原来小，那么 $x$ 最高位的数值要是 $1$，且刚好要能对的上 $k$ 最高位那个 $1$。只要这一位变成 $0$ 了，后面 $x$ 的其它位想怎么取就怎么取，总之不管怎么取都一定比
题解 CF1204D2 Kirk and a Binary String (hard version)
2023-09-20 808 字 4 分钟

题解 CF1204D2 Kirk and a Binary String (hard version)

CF1204D2 Kirk and a Binary String (hard version)形式化题意给你一个长为 $n$ 的仅包含 $0$ 和 $1$ 的串，要求尽可能多地将里面的 $1$ 改成 $0$ 使得在得到的新串中，对于 $\forall l,r\in [1,n](l \le r)$，两个串的 $[l,r]$ 区间内的最长不降子序列等长。 策略分析题中给的数据范围是 $10^5$，我们很容易去思考一些 $O(n \log n)$ 的做法，从而去找数据结构来维护，但这是 CF 的题，所以我们坚信这一定是一道人类智慧题。所以我们充分发扬人类智慧，$O(n)$ 来构造这个题。 对于只有
题解 CF1204D1 Kirk and a Binary String (easy version)
2023-09-20 786 字 4 分钟

题解 CF1204D1 Kirk and a Binary String (easy version)

CF1204D1 Kirk and a Binary String (easy version)形式化题意给你一个长为 $n$ 的仅包含 $0$ 和 $1$ 的串，要求尽可能多地将里面的 $1$ 改成 $0$ 使得在得到的新串中，对于 $\forall l,r\in [1,n](l \le r)$，两个串的 $[l,r]$ 区间内的最长不降子序列等长。 策略分析题中给的数据范围完全可以 $O(n^2)$ 搜过，但这是 CF 的题，所以我们坚信这一定是一道人类智慧题。所以我们充分发扬人类智慧，$O(n)$ 来构造这个题。 对于只有 $0,1$ 的串来讲，一个序列想要不降其实只需要满足两个条件：
题解 CF1537E2 Erase and Extend (Hard Version)
2023-09-13 296 字 2 分钟

题解 CF1537E2 Erase and Extend (Hard Version)

CF1537E2 Erase and Extend (Hard Version)简要题意给你一个字符串，找到该字符串的一个前缀并不断复制，可以删除末尾元素，最终要使得得到的字符串长度为 $k$ 且字典序最小。 策略分析对于此类构造题，我们一般需要运用逆向思维，也就是说我们要从前往后扫而不是从后往前删。为什么这样想呢？我们可以发现，字典序最小当且仅当我们要找的前缀的第 $i$ 位比第 $i \bmod len$ 位的字典序小，这样拼接起来才能够使得字典序最小，这个结论是显然的，证明可以使用反证法。 参考代码123456789101112131415161718192021222324252627