题解 CF1204D2 Kirk and a Binary String (hard version)
2023-09-20 726 字 2 分钟

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

CF1204D2 Kirk and a Binary String (hard version) 形式化题意 给你一个长为 的仅包含 和 的串，要求尽可能多地将里面的 改成 使得在得到的新串中，对于 ，两个串的 区间内的最长不降子序列等长。 策略分析 题中给的数据范围是 ，我们很容易去思考一些 的做法，从而去找数据结构来维护，但这是 CF 的题，所以我们坚信这一定是一道人类智慧题。所以我们充分发扬人类智慧， 来构造这个题。 对于只有 的串来讲，一个序列想要不降其实只需要满足两个条件： 如果当前位为 ，那么后面无论 都是不降的； 如果当前位为 ，
题解 AT_arc129_a [ARC129A] Smaller XOR
2023-09-26 375 字 1 分钟

题解 AT_arc129_a [ARC129A] Smaller XOR

AT_arc129_a [ARC129A] Smaller XOR 简要题意 给你三个数 ，询问满足 且 的整数 的个数。 策略分析 我们考虑异或运算的性质，当某一位为 时，它异或一个值可能增大或者不变，当某一位为 时，它异或一个值可能减小或不变，也就是说一个数 想要满足异或一个 要比自己原来小，那么 最高位的数值要是 ，且刚好要能对的上 最高位那个 。只要这一位变成 了，后面 的其它位想怎么取就怎么取，总之不管怎么取都一定比原来的数小。那么假设 的第 位为最高位，根据前面的分析， 就可以满足条件，又因为 ，二者取个交集即可。 上面我们讨论了能
题解 洛谷 P1486 [NOI2004] 郁闷的出纳员
2023-09-26 1.3k 字 5 分钟

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

P1486 [NOI2004] 郁闷的出纳员 简要题意 给定 次操作和一个阈值 ，每次操作包含一个字符 和一个整数 ，操作可以是一下四种之一： I k 如果 小于 不操作，否则将 扔进一个集合 中。 A K 把 里所有元素值加上 。 S k 把 里所有元素值减去 。 F k 查询 里第 大的值，如果 输出 -1。 在每次操作中，一旦 中有元素的值低于阈值 ，就要删除这个元素，程序最后要输出删除的元素总数（插入时就因为小于阈值没有插入进来的不算） 策略分析 我们看到插入，删除，查询排名理所当然地想到了平衡树；看到全加上，全减去，理所当
题解 AT_arc129_b Range Point Distance
2023-09-26 552 字 2 分钟

题解 AT_arc129_b Range Point Distance

AT_arc129_b Range Point Distance 简要题意 给定 对 ，然后在每次给出后都要选一个 使得 到之前给出的所有区间的距离 的最大值最小。一个 到区间 的距离定义为 。 策略分析 既然我们每次都要输出答案，那我们不妨从 的定义入手，我们发现在这个定义中，当其结果不为 时只有两种情况，要么 在 右边，要么 在 左边。那么我们考虑现在有一堆区间，因为我们求的是 到所有区间距离的最大值，所以其实我们需要关心的，能够对我们答案造成影响的值就是最靠右的 和最靠左的 。得到这个结论后剩下的就比较简单了，我们只需要每次输入一个区间都更
题解 JZOJ5952. 【NOIP2018模拟11.5A组】凯旋而归
2023-10-03 1.5k 字 5 分钟

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

JZOJ5952. 【NOIP2018模拟11.5A组】凯旋而归 简要题意 对于一个数列 ，一个函数 定义如下： 现在给你一个数列，依次求出其所有前缀的 的值。 策略分析 首先我们需要一些前置知识，我们在求一个数列的子段异或和的时候，可以像其普通加法求和一样处理出前缀和并 求解。那么对于异或前缀和数组 来讲，区间 的异或和就等于 。 知道了这个性质以后，我们就可以做出本题 50 分的做法，即对于每个位置 都去暴力枚举 或 区间（枚举这两个区间得到的答案是等价的）的最大答案。假设我们枚举到了位置 ，那么我们要求的就是答案 就等于 。也就是说，想让答案尽可
题解 SP6285 NGM2 - Another Game With Numbers
2023-10-24 520 字 2 分钟

题解 SP6285 NGM2 - Another Game With Numbers

SP6285 NGM2 - Another Game With Numbers 简要题意 给定一个长为 的数组 ，其中 且 ，再给定一个数 ，其中 ，要求求出 中有多少数不能被 中任意一个数整除。 策略分析 显然满足我们要求的数不能被 整除，同时也不能被 中任意 个元素的最小公倍数整除。所以最朴素的想法是通过筛选出能够被整除的数的个数，再用 减去它。如果你想到这里了，那么恭喜你这道题已经做完了。由于本题的 非常非常小，所以我们可以直接暴力枚举出 个数的所有组合的最大公约数， 求出 中能整除一个数 的数有多少，然后做容斥就能得出答案了。 具体来讲
题解 洛谷 CF1809D Binary String Sorting
2023-10-25 558 字 2 分钟

题解 洛谷 CF1809D Binary String Sorting

CF1809D Binary String Sorting 简要题意 给定一个 串，要求你交换相邻两个数或删掉一个数，使得该串单调不降。其中交换相邻两个数的代价是 ，删除的代价是 ，求最小代价。 策略分析 本题需要我们发现一个重要的性质，因为我们需要把数列变成形如 00000...11111 的形式，所以必然存在一个分界点，这个分解点的两边的数可能是 或 。现在假设我们知道这个分界点在哪里了，那么我们就要把分界点左边的 想办法弄到右边，或者直接扔掉。我们发现，除非是 情况下的分界点左边的那个 ，其余的 删掉的代价一定比一次一次交换过来少，因为删除只需要一次，而