题解1525f cf

如果两种方案末尾两数有一数相同，那么答案较大的方案不劣于答案较小的方案。答案较大的方案只需\textbf{模仿}答案较小的方案即可，在状态变成相同之前答案最多只会少 \(1\)。 所以只需要考虑末尾两数 \(a,b\) 与新进来的数 \(c\) 各不相同时该替换哪个。 假设 \(a\) 下次出现的位 ......

题目链接 刚从 modinte 那里学到的广义 dijkstra。注意到一定不会有路径形如 \(x \to y \to x\)，这样等价于 \(x\) 在原地等上两个时刻，我们记 \(d_i\) 表示到达 \(i\) 节点需要的最少时间。建图，边权为当前这一条边在哪一个历史时刻。然后用一个 set ......

思路 最开始都错题了，以为是不能通过另一种子串的选择方法得到这个子串就算做独特字串，实际上，是需要不能通过选择子序列的方式得到这个子串才满足条件，导致赛时没做出来（悲）。 实际上，如果一个子串满足条件，那么一个必要条件就是子串左侧没有与该子串左端一样的数字并且子串右侧也没有与该子串右端一样的数字。 ......

思路 考虑从大到小给每一个 \(b_i\) 匹配一个 \(a_j\)，那么如果对于 \(b_i\)，\(a_j\) 不能匹配，那么对于后续更小的 \(b_i\)，\(a_j\) 同样无法匹配，所以可以直接忽略，跳到下一个，一直匹配，直到无法匹配为止，那么无法匹配的 \(b_i\) 的数量就是需要的操 ......

思路 大体上的思路应该和简单版本一致，建议先看本人关于简单版本的题解。 与简单版本不同的是，困难版本的 \(m\) 可以不为 \(1\)，而是取遍 \([1,m]\) 中的整数，所以答案的总值会变大很多倍。 如果直接枚举 \(m\) 次，时间复杂度将会达到 \(O(mn\log n)\) 显然过不了 ......

思路 性质题，因为可以随便排序，所以只需要考虑数量满不满足条件即可。 一个回文串，应该满足所有的字符的数量都是偶数或者其中一个字符的数量是奇数。 所以可以直接扫一遍字符串，统计每个字符的数量，然后再统计数量是奇数的个数，如果这个个数大于 \(k+1\) 就无解，否则有解。 AC code #incl ......

思路 最开始晃眼一看，感觉很难，仔细一读题，哦，原来 \(k\in [2,5]\) 啊。 首先如果 \(k\) 是质数，也就是 \(k\) 不等于 \(4\) 的情况，必须要有一个数是 \(k\) 的倍数，那么计算每个数需要的操作数，取最小即可。 如果 \(k\) 不是质数，也就是 \(k\) 等于 ......

思路 Step1. 贪心 拿到题后，第一时间想到贪心，如果这个区间加上会使答案变小或不变就不加。 但是很显然，这个贪心是错误的。 如果答案的最大值在区间 B，但是先加了区间 A，导致加区间 B 使答案不变，那么这样就会使答案变劣。 所以贪心是错误的。 Step2. 枚举 接着，想到了可以枚举最小值， ......

分析 首先对于最后一个元素为1的数组，显然不存在合法构造方式。为什么？因为每个1都需要至少一个数插入在它后面对它完成翻转，如果最后一个数为1，这时没有数在它后面翻转它，所以这时无法构造。 然后我们很naive地想让每个1都只被翻转一次，那么很好想到，对于一个形如\(11\dots100\dots0\ ......

CSP-S 2023 消消乐-题解 闲话 省流：long long 模拟pair 好抽象的题，可惜考场上没做出来。感觉其实是一个挺有趣的题的。 题目描述 小 L 现在在玩一个低配版本的消消乐，该版本的游戏是一维的，一次也只能消除两 个相邻的元素。 现在，他有一个长度为 \(n\) 且仅由小写字母构成 ......

分析 根据题意，对于亮度为\(a\)的灯，我们最多可以一次开\(a\)盏。 显然我们选\(b\)最大的\(a\)盏灯就行，注意到\(b\)最大为\(1e9\)，所以开long long。 代码 #include <iostream> #include <vector> #include <algor ......

分析 可以很容易地想到如果只有1要求的话答案就是 \(\lceil \frac{n}{k} \rceil\)。 最优策略显然是在每个整除分块的第一位放一个1。 思考加入2条件如何修改。 显然当最后一块的大小不为1时，大于1的部分后缀和为0。 所以需要在最后一位加入一个1。 所以答案为\(\begin ......

将操作按右端点从小到大排序，这样对于当前值相同的点，只有最右边的那一个是有用的。 令 \(f_i\) 表示当前值为 \(i\) 最靠右的点的位置，转移直接暴力判断能否取 \(\max\) 即可，时间复杂度 \(O(nq)\)。 这个东西看起来就不好优化。 不妨调换状态和值，令 \(f_{i,j}\) ......

A1. Dances (Easy version) 把 \(a,b\) 序列都从小到大排序，\(a\) 贪心删大的，\(b\) 贪心删小的，二分答案并 \(O(n)\) \(\text{check}\)。 Code ```cpp const int N=1e5+5; int T,n,m; int a ......

目录DescriptionSolutionCode Description 有一个 \(n\times m\) 的停车场，每个坐标有一辆车或一块空地，每辆车面朝一个方向，用 N（北）、E（东）、S（南）、W（西），代表面朝的方向（上北下南左西右东），否则用 .表示空地。 每辆车能被移开，当且仅当它面 ......

前言 基本是官方题解的思路。 分析 先考虑不用纠结的情况。假设第 \(n+1\) 大价值的物品的价值小于第 \(n\) 大的。 此时物品名称集合可以确定。 对于每类名称，恰好拿到的概率为 \(1/\dbinom{k_i}{a_i}\)，\(a_i\) 为选择的物品数量，\(k_i\) 为总数。 对于 ......

1.定义$$ 2.定义数列\(\{a\}\)：\(a_1=1,a_{n+1}=a_n^2+1\) 1.证明：当\(n\)能被\(3\)整除，\(a_n\)能被\(5\)整除。 写出\(\{a\mod 5\}\)的前四项：\(1,2,0,1\)，所以数列的循环节为3，且\(a_{3k}\mod 5=0 ......

2023年6月19日决定对rust做一个重新的梳理，整理今年4月份做完的rustlings，根据自己的理解来写一份题解，记录在此。 周折很久，因为中途经历了推免的各种麻烦事，以及选择数据库作为未来研究方向后的一段适应过程，耽搁了很久。 2023年10月份秋冬季的开源操作系统训练营又开始了，所以我回来 ......

输在 D 上了，呜呜呜。 首先显然环是没有用的，因此我们只用考虑简单路径。 先思考一个弱化版：如果所有边都已经定向了怎么做。对于每条路径 \(u\to v\)，如果它是一个括号序列，那么我们就用并查集将这条路径上第一条边和最后一条边合并起来，那么颜色数就是并查集连通块数。考虑如何快速合并这个连通性。 ......

题意： 给定一个无向图，边权为 \([0,1]\) 之间的随机变量。求图最小生成树最大边权的期望。 \(n\le 10\)。 Soluion: Meatherm口诏：我都不知道这个东西怎么想出来的 针对这道题，好像正常的方法是转计数然后斯特林反演+dp。但是如果想到概率理论，你就已经赢了 很遗憾，我 ......

Link 此题目可以从两个方向考虑，正着和倒着，倒着考虑比较容易，首先把所有的数放到一块，如果是'<'或者'>'，就是去掉最左边或者最右边的数，这样显然只有一种可能,答案不变。 如果是'?'，那么显然可以去掉中间的任意一个，所以答案就是\(\times l-2\)，那么对于\(s_n-i\)位置的\ ......

Description 你是一个森林养护员，有一天，你接到了一个任务：在一片森林内的地块上种树，并养护至树木长到指定的高度。 森林的地图有 \(n\) 片地块，其中 \(1\) 号地块连接森林的入口。共有 \(n-1\) 条道路连接这些地块，使得每片地块都能通过道路互相到达。最开始，每片地块上都没有 ......

这次 CCF 的行为过于迷惑了。 思路 首先发现只会有 \(10^5\) 种密码，考虑枚举它们，然后去 check。 假设当前密码是：\(p_1,p_2,p_3,p_4,p_5\)。如果它能从对于所有 \(1 \sim n\) 种错误的密码按照题目所述的操作得到，那么此密码就是合法的。 假设我们现在 ......

正文 对于每个选择题，都有两种状态，因此总状态数为 \(2^n\)。 请注意初始所有选择题都不选也是一个状态，不计入贡献，因此答案为 \(2^n-1\)。 代码： #include<iostream> using namespace std; int main(){ long long n; cin ......

CSP-S 2023 题解 密码锁 发现总状态数只有 \(10^5\) 个，枚举 \(O(n)\) 暴力判断即可，复杂度 \(O(10^5 n)\)。 或者每一个状态只对应了 \(81\) 个状态，枚出来，取交集即可，复杂度 \(O(81 n)\)。 消消乐 好的，来一波抽象做法 QwQ 我看到这道 ......

目录题目翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1样例 #2样例输入 #2样例输出 #2样例 #3样例输入 #3样例输出 #3题目简化题目思路AC代码 题目翻译 【题目描述】 你决定用素数定理来做一个调查. 众所周知, 素数又被称为质数，其含义就是除了数字一和本身之外不能被其 ......

题目传送门 一道贪心题。 感觉很裸啊，模拟赛时随便乱写了个暴力递归就能过。每次找最接近钱数 \(x\) 的面额 \(num\)，如果比钱数少那么答案为剩下 \(x \bmod num\) 钱数的答案加上 \(x \div num\)。否则答案则为剩下 \(num-x\) 钱数的答案加上 \(1\)。 ......

题目传送门 一道枚举题。 暴力枚举数字位数、首位、等差数列的公差即可。注意公差的枚举范围，并且需要看看末尾合不合法。顺便提一下，我是用字符串存储枚举的数字的，所以写了一个 check 函数代替大于号。 Code #include <bits/stdc++.h> using namespace std ......

题目传送门 一道 dp 题。 在 dp 之前，我们需要明确以下几个东西： 状态的表示，状态转移方程，边界条件跟答案的表示。 状态的表示 \(dp_i\) 表示恰好用完 \(i\) 根火柴能拼出来的最大数字。 状态转移方程 \[dp_i = \max\{j \times 10^{len(dp_{i-w ......

ABC323D Merge Slimes 题目简述 小 A 有 \(N\) 种橡皮泥。对于第 \(i\) 种橡皮泥，它的大小为 \(S_i\) 且一共有 \(C_i\) 个。 小 A 可以合成两个大小相同的橡皮泥，若这两个橡皮泥大小为 \(X\)，则新和成的橡皮泥大小为 \(2X\)。 小 A 想知 ......