题解914b cf

样是一道水题， \(N \le 21\)? 这么小的数据还在等什么，直接三重循环暴力枚举即可通过此题。 #include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; for(int i=0;i<=n;i++){ for ......

更好的阅读体验 CF1801F Another n-dimensional chocolate bar 高妙的数论分块优化 DP。 第一步设计状态就有很大问题，如果直接设 \(f_{i,j}\) 表示前 \(i\) 个数成绩为 \(j\) 那就死了。这完全没有利用到整除的性质。正确做法是设 \(f_ ......

题解\(^2\) 阿巴阿巴阿巴…… 看题解后 抖动序列就是一大一小交替循环的序列。 若 \(\large x\) 与 \(\large x+1\) 不相邻（ \(\large x\) 为山峰高度），则交换 \(\large x\) 与 \(\large x+1\) 后依旧是抖动序列。所以 $$\La ......

题解 %%% 其实就是个板子（ \(exlucas\) ）。 一开始以为直接用 \(lucas\) 就可以过了，但是显然不是这样的。这道题需要用到欧拉定理和 \(exlucas\) （ \(lucas+crt\) ）。 首先质数 \(999911659\) 的欧拉函数是 \(999911658\) ......

题解 思路 计算有多少个 \(x(0\leq x<m)\) 使得 \(\gcd(a,m)=\gcd(a+x,m)\) 事实上就是求有多少个 \(x(1\leq x\leq m)\) 使得 \(\gcd(x,m)=\gcd(a,m)\) 所以可以将 \(m\) 除以 \(\gcd(a,m)\) ，于是 ......

题意简述 其实就是每次将相邻两个数替换为它们的和，代价为两个数的和，直到只剩一个数，求最小代价和以及操作方式。 思维路径 我们可以先求出最小代价，很明显可以用 dp 来做。定义 \(f_{i,j}\) 为合并第 \(i\) 个数和第 \(j\) 个数的最小代价，\(s_i\) 表示前 \(i\) 个 ......

思维路径 根据映射，我们可以发现数字的规律必定是两两互换，即若 \(f_a\) 是 \(b\) ，那么 \(f_b\) 一定是 \(a\) 。 我们可以通过手算 \(1\) 到 \(4\) 的数据，观察规律。 观察第 \(4\) 行的数据。 以 \(1\) 为始的数据后面跟的三个数据正好与第三行的顺 ......

题意简述 给定两个点（即 FJ 和 Bessie）和两条路径，让这两个点沿着路径移动，求每移动一次的能量总和。 思维路径 典型的动态规划题，我们设计状态，设 \(f_{i,j}\) 表示 FJ 走到第 \(i\) 个点，Bessie 走到第 \(j\) 个点最少的能量总和。 因为他们两个都可以在某一 ......

题意简述 给出一棵无根树，求以那些节点为根时，与它直接相连的节点，它们的子树大小都相同。 思维路径 首先，显而易见的是，在 \(1 \le n \le 10^6\) 的数据范围下，我们不可能通过对每个节点作为根判断一次。因此，我们考虑选取一个节点为根计算全部。 我们作图来分析一下。 如上图，我们针对 ......

题目简述 给定一个字符串 \(t\)，由一个字符串 \(s\) 和这个字符串去掉所有 a 组成。求字符串 \(s\)。 思路 首先我们分析给定的字符串 \(t\)，它由 \(s\) 和 \(s\) 去掉所有 a 形成的字符串 \(s'\) 组成。那么当整个字符串 \(t\) 去掉 a 后，就得到了 ......

其实很简单的一道题。 思维路径 其实题目主要要考虑的就是以下三个条件。 每个人都要送一样多的硬币。 每个硬币都必须是不同的。 所有人送的硬币至少有 \(L\) 个是 Ivan 没有的。 我们一个一个来看。 每个人都要送一样多的硬币。 一共有 \(M\) 个朋友，所以说总共送的硬币的个数为 \(M\) ......

题目链接：洛谷 或者 CF 不是特别难的题，抽象下题意就是算区间次数出现的次数 mex 和带单点修改。看到范围 \(1e5\) 还带修改，传统的 mex 求法里貌似就莫队类算法好带修，考虑带修莫队。 然而涉及到 mex 问题，你可能不由自主地想到回滚莫队求 mex 只删不加的板子题：P4137 Rm ......

题目链接：洛谷 或者 CF 不是特别难的题，抽象下题意就是算区间次数出现的次数 mex 和带单点修改。看到范围 \(1e5\) 还带修改，传统的 mex 求法里貌似就莫队类算法好带修，考虑带修莫队。 然而涉及到 mex 问题，你可能不由自主地想到回滚莫队求 mex 只删不加的板子题：P4137 Rm ......

cf goodbye 2023(A-C) A - 2023 算法分析： 多组答案输出一组即可 先累乘，如果不是2023的除数也就是2023的因子就直接no 如果是2023的因子 先输出1 再输出2023/累乘的除数 #include<bits/stdc++.h> using namespace st ......

Preface 咕咕咕咕咕咕咕了半年有余。不得不说这题真的会把你调炸！！！！！！11 本题解中的所有 Hints 以白字显示。所以它可能不适合手机观看。 以及，首黑，2022 年 7 月 31 日 15:51。 Solution 算法一 询问次数 $2^h - 2$，适用于 $h \leq 4$。 ......

Question LOJ2294 银河英雄传说 Solution 算是带权并查集一个比较典的题目了 定义 \(d[x]\) 表示战舰 \(x\) 与 \(fa[x]\) 之间边的权值，在路径压缩把 \(x\) 的 \(fa[x]\) 修改为根节点时，把 \(d[x]\) 更新成从 \(x\) 到树根 ......

CF1665E 直接做不是很好下手，考虑找些性质。 有一个比较显然的贪心，就是按位从高到低的考虑，如果当前位至少有 \(2\) 个 \(0\)，就可以去掉该位为 \(1\) 的数。但是时间上显然是不行的。 假如没有重复的数，可以发现扫到最后一位时，剩下的数的数量是 \(\log V\) 的，证明省去 ......

P8512 直接做不好做，考虑离线。这个覆盖操作和这道题很像，可以直接对某些段暴力修改，可以直接上 ODT。发现当 ODT 执行这些操作时，是容易求出不执行某些操作后带来的值的影响的，即可以直接用树状数组维护每个位置现在是被那个操作覆盖，求出 \(1\) 到 \(x\) 操作还覆盖了那些位置，以及这 ......

CF1870F 题意：给一个长度为 \(n\) 的排列，求在其在 \(k\) 进制下按字典序排序后 \(\sum[p_i=i]\) 的值（\(n\le10^{18}\)）。 直接做是不好办的，只能在一些数中找到 \(p_i\) 的大小关系。 在手摸的过程中会发现一些长度相等的数之间会插入一些其它长度 ......

P4700 简单的，但是考试的时候没看到是平面图，就只想到了缩点后 DAG 判断能到达哪些点。用 bitset 维护做到 \(\mathcal{O}(\frac{nm}{w})\) 的时空复杂度，但是空间会炸。 由于这个图是平面图，稍微推一下就可以知道所有能它最终所能到达的点一定是从西侧出发所能到达 ......

P4657 树形 dp。 首先，追逐者遇到的铁球的数量显然不会少于逃亡者遇到的铁球数量。 令 \(ss_i\) 表示与 \(i\) 相邻的点的权值之和。\(\mathcal{O}(n^2v)\) 的 dp 是很简单的。 令 \(dp_{i,j,0/1}\) 表示根节点到 \(i\) 的路径上，用了 ......

P9715 不一样的线段树做法。 假如只有 \(t=1\) 的操作是容易的。考虑加上 \(t=0\) 后怎么做。显然地，我们对每一个操作附上一个时间 \(tim\)，不妨令 \(tim\) 小的数能覆盖掉 \(tim\) 大的数。这时候就只需要维护区间取 min 和最后的 \(n\) 次求 \(c\ ......

P8386 platelett 讲的题欸。 先考虑给定序列怎么做。 问题显然可以转化为能否将序列分成若干个子序列。令 \(f_i\) 表示前 \(i\) 个数是否能够删完。则有 \(f_i = f_j[a_i=a_j, f_j=1]\)。这样是 \(n^2\) 的，也无法扩展至所有数列的情况。 建立 ......

P4067 因为不能直接减去 \(nmk\)，先把题目中的式子转化为求 \(i\oplus j \ge k\) 的数的个数与和。 这样就可以进行数位 dp 了。令 \(f_{bt,un,um,lk}\) 表示当前考虑到第 \(bit\) 位，\(n\) 有没有达到上界，\(m\) 有没有达到上界，\ ......

UVA12170 7 月份的题了，补一补。场上写挂了一点还是很遗憾的。 容易想到 dp。 但是由于值域非常大，直接 dp 是不行的。但是 \(n\) 非常小，容易想到离散化。 但是离散化后是不能直接加减的。有用的数值初看是有 \(\mathcal{O}(n^2d)\) 的，即 \(h_i + kd( ......

P9755 upd on 2023.11.20：增加细节说明。 刚开始浪费太多时间了，导致赛时没调出来，有点火大。 如果一开始没有头绪的话可以先看一下特殊性质，链是直接贪心。 考虑一下菊花，发现直接贪心是不可做的，但是发现树的高度随时间增大而增大，可以用二分转化为判定性问题解决。 对于任意的树来说， ......

P9753 法一： 这是赛时想法。 考虑 dp。 令 \(f_i\) 表示 \(i\) 为右端点的合法子串个数，则答案为 \(\sum\limits_{i=1}^{n}f_i\)。 赛时想过匹配指针不断跳的，但当时没敢写，用了一种更直观的方法。 仿照于括号序列，合法的子串只能为 \(cAc\) 或 ......

P8315 T3 写太慢了，就没看这道/gg。错过简单题+1。 不好直接对边或路径进行考虑，但是发现 \(m\) 非常小，考虑容斥。 即每次钦定集合 \(S\)，强制包含在 \(S\) 内的路径不合法，其它的都可以，容斥系数就是 \(-1^{|S|}\)。每次可以暴力覆盖染色，然后用一个并查集进行维 ......

CF1610F P7816 *3000 令 \(w_u\) 表示与 \(u\) 直接相连的边的权值和。显然当 \(2\mid w_u\) 时，这个节点是无法满足条件的，因为每次调整只能对 \(\mid d^+(u)-d^-(u)\mid\) 的值造成偶数的影响。 这时候肯定会猜答案就是 \(\sum ......

P9340 记一下。称 \(\forall j\in[l,r]\) 的 \(c_j\) 为关键点。 法一： 最好想的。 有个显然的结论，将所有关键点按 DFS 序排序，走过的边的数量为排序后相邻的点之间的距离。记走过的边的数量为 \(cnt_e\)，则此时这些关键点所构成的虚树的大小为 \(\fra ......