题解1203 div cf

`2023-09-01 11:29:13 solution` ## 题意： 每次询问 $[l,r]$ 内有多少个数满足可以被所有非 $0$ 数位整除。 ## 思路 看到这个数据范围和题目描述，显然是数位 dp。 因为 $1\sim 9$ 的最小公倍数是 $2520$，并且 $2520$ 是其他所有 ......

`2023-09-01 15:59:41` # $$前言$$ 太菜了，第一题都打成那样了没发现是 MST，第三题数据范围没有很仔细看，以为是乱搞（组合之类的）题就直接跳了。 不得不说这次比赛题目的一些思路还是挺妙的，一些想法确实我这种成分想不太到。 # $$A$$ ## $$题意$$ 给出了 $m$ ......

`2023-08-08 23:01:17` 2023.8.8 # 前言 $Div_3$ 太简单了，但是因为我太菜了想到了但来不及写最后一题，然后 F 题因为用 unordered_map 被卡哈希 hack T 了，最后结果出来只过了 $5$ 题，排到了 $rk1365$。 # A ## 题意： 给 ......

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

`2023-08-13 18:17:37` # 前言 本来想着至少 A 四道的，但是 T4 因为我《卓越》的运用 stl 的能力挂掉了。不过还好，至少 rated 没掉（困死了困死了）。 # A ## 题意： 把长度为 $n$ 的数组 $a$ 分成两个非空部分 $b,c$ 使得 $c$ 中任意数都不 ......

`2023-08-08 23:00:07 solution` ## 题意： 求有多少个有 $n$ 个节点的无向图，使其满足以下条件： - 无重边自环。 - 有且只有一个最小生成树，且为给定树。 - 最大边权不大于 $S$。 对 $998244353$ 取模。 ## 思路： 其实就是让我们在给定的树加 ......

`2023-08-22 10:55:44` # 前言 注：这场比赛全是 dp 题，时长 3 小时。 第一眼看到 A 题这种奇葩题面直接跳了，感觉不是自己这种成分能写的，结果我旁边两个呆呆鸟 zyx,cf 居然觉得我直接上来把 A 秒了，然后他们死磕 A 题嗑了两个多小时？？？离谱。 最后我只 A 了 ......

`2023-08-07 16:29:49` ## 题意 有一个 $n\times m$的矩阵，求使得每个 $n\times n$的矩阵中都有正好 $k$个点的方案数，方案数对 $1e9+7$ 取模。 $1\le n\le100,n\le m\le10^{18},0\le k\le n^2$。 ## ......

`2023-08-08 22:58:04 solution` ## 思路： 考虑到一个最小值对答案的贡献，发现如果是序列最小值，因为配对了 $n-1$ 次，而每次配对的结果都是它，所以在 $b$ 中会出现 $n-1$ 次。 同理，次小值（可能与最小值相同）出现 $n-2$ 次，第三小出现 $n-3$ ......

`2023-08-08 22:59:22 CF1857E solution` ## 思路 我们发现每个点的答案其实是它与之前的点的答案加上与后面的点的答案加上与自己的答案。而与前面和与后面的前后缀答案都是可以通过递推的方式得到的，我们令 $pre_i$ 表示 $i$ 点的前缀答案，$sub_i$ 表 ......

`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 16:14:50` [原题](https://www.luogu.com.cn/problem/CF797F) ## 思考 考虑如何暴力转移，观察到老鼠之间的路线如果交叉或者包含都不是最优的，所以我们可以设计状态 $f[i][j]$ 表示把前 $j$ 只老鼠全部放在前 $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-26 14:35:10 solution` # 思路 第一眼看以为是个图论，结果发现缩点之后就是个多重背包裸题。 我们把原连通块变成一个重量为连通块大小的物体，然后发现只需要找在容量为幸运数的情况下，放满容量所选物体数量的最小值。 考虑背包，但是复杂度为 $O(n^2)$，观察到这 ......

`2023-07-25 20:41:07 solution` [原题链接](https://www.luogu.com.cn/problem/CF401D) # 思路 看到这个数据和范围，果断数位 dp。 因为同一个数字交换顺序是一样的，所以我们直接把它们合并即可。 设计状态，观察到每个数字的个数不 ......

`2023-07-18 20:49:31` ## 思路： 一开始的思路是每次存两个值，因为任意两个斐波那契数列合并之后仍然满足斐波那契的基本性质 $f[x]=f[x-1]+f[x-2]$。 但是发现这样子每次修改直接的总和得暴力递推求，复杂度爆炸。 为了解决这个突破口，稍微借鉴了一下题解的斐波那契数 ......

`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 ......

`2023-07-19 10:59:11` 思路来源于题解:https://www.luogu.com.cn/problem/solution/CF1806E 算法：根号分治+记忆化搜索。 因为每一个查询都是同层的，我们可以只记忆层数少的（小于$\sqrt n$）,对于层数多的层，如果大于$ \sq ......

`2023-03-01 16:50:41` ```cpp #include using namespace std; typedef long long ll; inline ll read(){ ll x=0;char c=getchar(); for(;!isdigit(c);c=getchar ......

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

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

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

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

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