题解sorting binary string

`2023-08-22 16:15:06` # 前言 现在的比赛怎么都开始向 CF Div.2 的遍地结论题看齐了，感觉打下来 3 题都是结论题？ # A 这么秒的题我一开始猜结论居然猜错了啊啊啊。 看了题目以后，毫无头绪，准备从部分分入手。 $p=2$？奇奇偶偶互配即可，找不出什么性质。 $p=3 ......

`2023-08-06 15:18:08 solution` [双倍经验](https://www.luogu.com.cn/problem/P1290) 这种有限轮游戏的博弈通常都是有两种状态，必胜态和必败态。 对于必胜态，指的是从它可以转移到必败态。 对于必败态，指的是从它不论如何只能转移到必胜 ......

`2023-08-05 16:22:13` ## 总结 这次打下来，由于 T2 贪心不够完全，T3 模拟 $5$ 个时不是最优，T4 想到暴力做法但是来不及打，加之全都是捆绑测试点，导致我 T2,T3 虽然加起来有不少点对了，但是还是判全错，最后也只剩下 T1 的 100。 感觉这次前三题也不难，都 ......

`2023-08-03 18:18:03` ### 前言 好家伙，很少完整订正一场比赛，可能是因为这个比赛相对来说确实不难吧（至少正解不难）。 # 总结与反思 这场比赛其实没有我想象的那么难，只是觉得题目可能不简单，就没有往简单的思路想，反而是被之前讲过的题疑惑，以为要用到一些很奇特的算法，结果打完 ......

`2023-07-30 19:35:02` ## 前言 因为我实在是太菜了，没时间也不会做最后两题，所以这里只有前 $5$ 道签到题的题解。 之后我有时间看了后两题的题解再来更新吧~ # A 先不用看那么多七七八八的，搞清楚下面几点即可： - 高度不能相同。 - 高度差得被整除。 - 高度差不能太大 ......

`2023-07-30 18:55:15` 水平有限，等我有时间看懂了后面的题再写后面的吧。 写完三题太困了直接睡了（AT和CF一起打真的非常累啊啊啊）。 # A 题意：给你一个排列找使其 $\forall i \in [1,n],a_i\ne i$ 的最小交换次数。 发现偶数个相同就直接两两交换答 ......

`2023-07-26 14:58:54 solution` ## 简化题意： 给你一个 $n\times n$ 的只有黑白两种颜色的棋盘，每次修改把某格的黑白互换，求每次修改后黑白各自的连通块个数。 ## 解法 将棋盘转化成 $n$ 行，每行单独处理，处理出黑色和白色分别的连通块个数(可用并查集) ......

`2023-07-25 16:12:57 洛谷题解` # 思路 看到这道题是统计相邻交换之后操作次数，我第一反应就是求逆序对。 考虑最淳朴的暴力做法，枚举颜色之前的大小顺序关系，然后每次做一次求逆序对，复杂度 $O(n\log n |c|!)$ ($|c|$ 表示颜色种类数)。 但是光是 $20!$ ......

`2023-07-24 20:16:31 AT_dp_v 题解` [AT_dp_v Subtree](https://www.luogu.com.cn/problem/AT_dp_v) # 思路 考虑树形 dp，假设根左右子树的连通块已经算出来了，我们用 $f[x]$ 表示强制将 $x$ 染色，$x ......

`2023-07-21 15:02:47` ### 写不动数据结构了，下午打打D班的模拟赛玩玩。 # C. [2023暑假D班第一场模拟赛]爱新撅罗 ## 题面： 小X穿越了，发现自己成为了一个小人，正准备为一位清朝王爷服务。只要好好地服务，王爷就有赏。 一开始，小X的赏赐是 $a_0$，满足 $0 ......

`2022-09-02 15:14:44 P6037 题解` ### 闲话 当我看见这道绿题的时候，一时没有任何思路（没有看懂作者让我们干什么），看过一些题解的题意分析的我还是不是很清楚（语文太差了），于是，通过对样例的分析，我终于看懂了，题意明白后代码还是好写的（自己模拟才是最靠谱的）。 ## 题 ......

`2023-05-20 14:34:56 P6273 题解` 原题链接 [魔法](https://www.luogu.com.cn/problem/P6273) ## 题目分析 题目的意思就是让我们求每个字母出现次数相同且不为空的子串的个数。 ## 基本思路 然后我们能想到维护一个前缀和数组，然后判 ......

`2022-08-26 12:34:22` [原题戳这！](https://www.luogu.com.cn/problem/P8481) ## 题意分析 不难看出，这道题是一个对于二分查找中 $mid$, $l$, $r$ 如何取值使得总查询次数最少问题。 这个 $w$ 是影响最终结果的决定性因素 ......

`2022-08-26 13:02:02` [原题戳这！](luogu.com.cn/problem/P8482) ## 如何求最大乘积 我们令 $num1$ 为前几位较大的数， $num2$ 为前几位相对较小的数。 ### 浅浅地证明 首先我们肯定得使高位尽可能大，那么在高位都尽可能大的情况下，两 ......

`2022-08-11 16:45:02 洛谷题解` 比赛的时候乍眼一看这么多 $2$ 直接不想写了,结果在重现赛重现看的时候感觉没有那么难了，就勇敢去贪就好了。 ## 贪心思路 首先，我们很容易得到,无论前面有重复出现了多少次该位的数，不管它前面是被异或了还是或了,我们只需要在该位最后一次出现的时 ......

# 思路 任意两个序列都有至少一个相同的元素，但相同的元素不必在相同的位置。 保证每两个之间都要有相同的元素？ 我们先考虑一下 $n=k\times 2$ 的情况，此时如果你左边取一半,右边取一半,这时两边的元素才可能不一样。 那么当 $n using namespace std; typedef ......

一道贪心题。 根据题意，我们需要在原序列中找出一条从 $1$ 到 $n$ 的路径，这条路径能被分成几个长度为 $k$ 且颜色相等的连续段。我们可以将这个问题简单化，那么这个问题就能被转化为从 $1$ 开始向后找一个颜色连续段，从 $n$ 开始向前找一个颜色相同的连续段，只要这两个连续段不相交即可，代 ......

我们首先可以观察到这道题的 $m$ 很大，所以要考虑这么多列里面是否存在一个性质，让我们求出前 $n$ 列之后快速求出后 $m$ 列的答案。观察一下可以发现第 $i,j$ 两列的答案等价时满足 $i \equiv j \pmod n$。这样的话我们只需要求出前 $n$ 列的答案即可。记 $s_i$ ......

这道题显然是一道 dp。转移方程式也很好推，我们记 $f_{i,j}$ 为前 $i$ 位且第 $i$ 位为 $j$ 的 DNA 序列数量。而对于输入的字符串，我们用 $vis_{i,j}=0$ 表示第 $i$ 个字母后面不能放第 $j$ 个字母。那么转移方程式即为： $$f_{i,j}= \sum ......

# CF1178F1题解 根据题意，每次选择一个区间染色，我们可以发现这道题满足了区间 dp 的一些性质，即区间答案可以合并，大区间的答案可以由小区间的答案更新而来。那么我们就可以设 $f_{i,j}$ 表示区间 $i$ 到 $j$ 的答案，那么接下来就考虑如何转移。然后考虑到题目要求从 $1$ 到 ......

这是一道比较板子的数位 dp 。 首先观察到 $k$ 很大，肯定不能用枚举的方法求，然后就考虑用数位 dp 。对于这道题来说，我们可以在用记忆化搜索做数位 dp 的时候存一个当前各数位之和对 $d$ 取余的余数，当把数填完之后判断余数是否为 $0$ 就能判断这个数是否符合条件。 ```cpp #in ......

这是一道~~比较简单~~的博弈论。 我们假设 $x \ge y$，那么此时可以分两种情况讨论： - $x using namespace std; #define int long long inline int read(){ int f=1,w=0; char c=getchar(); whil ......

简要题意： 对于一张$n$条边的无向完全图，每条边有两个权值$a_i,b_i$,求一棵最小生成树使其$\frac{\sum{a_i}}{\sum{b_i}}$最小。 这道题如果没见过这种技巧可能不好想，但我们也可以考虑一个朴素的想法，那就是猜！ 我们猜这个答案是$ mid$,然后就可以推一下柿子。 ......

显然，我们可以先忽略两个串已经一样的部分，只考虑剩下不一样的部分，然后我们就可以将它抽象成一个链上游走问题。我们记 $g_i$ 为从第 $i-1$ 个到第 $i$ 个点的期望步数，此时 $g_1=1$。且 $g$ 满足： $$g_i=\frac{n}{n-i}+\frac{i \cdot g_{i- ......

题目[传送门](https://www.luogu.com.cn/problem/P8481) ## 思路提供 由于题目中询问的是最小需要的查找次数，但是正常的二分查找是不满足我们这道题目的（标准的二分是自定义向下取整，但是没有考虑向上取整的情况），但是只要我们便利出每一种情况（即向上取整和向下取整 ......

## A.Ekiden Race ### 题目描述： 有 $n$ 个人参加了往返赛跑，每个人有一个编号 $1$ 到 $n$。已知以下信息： - 如果按照往路的成绩排序，那么任何两个人的成绩都不相同。同时第 $i$ 个人在往路中排名第 $i$。 - 如果按照往返的成绩排序，那么任何两个人的成绩都不相同 ......

## Description 奶牛旅馆可以被看作一个 $N$ 个节点 $M$ 条边的无向简单图，其中每个房间有一个颜色 $C_i$，以及一个钥匙，颜色为 $S_i$， FJ 最初在 $1$ 号节点，手上一把钥匙都没有。 FJ 可以进行无数次以下操作： - 捡起当前房间的钥匙。（FJ 可以同时手持多个 ......

在 Go 语言中，反引号（`）用于创建原始字符串字面量（raw string literals）。原始字符串字面量是不包含转义序列的字符串，其中的内容会保持原样，包括换行符和特殊字符。 反引号的主要用途之一是编写多行的文本或正则表达式，而不需要使用转义字符。这在处理包含大量特殊字符或格式化要求的文本 ......

双倍经验 [CF559C](https://www.luogu.com.cn/problem/CF559C) 前置知识：网格图内任意两点间的路径数量。这个我们可以通过组合数的方法计算出来。假设我们从点 $(1,1)$ 走到点 $(i,j)$，在这个过程中我们的移动步数是 $|i-1+j-1|=|i+ ......

被 C 卡了。 最后被 E 的各种分讨劝退，但是同时也学习到了一种换根 dp 的简单写法。 评价：It's educational for me. ## A.Typical Interview Problem ### 题目描述： 有一个包含 F 和 B 的字符串，最开始是空的。我们开始从 $1$ 向 ......