杂题选记

搜索杂题： 一、基础的BFS与DFS： 深搜和广搜都可以遍历出在一定限制下可能出现的所有情况，但是朴素的搜索一般复杂度极高，成指数级别，需要用到各种五花八门的优化方式，后面会一一介绍，但基础很重要，几乎不用考虑优化，直接模拟题意就可以了。这篇博文讲的是习题ing。 深搜一般处理有分支的情况，广搜一般 ......

二分答案杂题 二分答案适用于答案具有单调性/包含性的题，一般时间复杂度为\(O(nlogn)\)，最重要的是找准二分答案的对象，以及check的优化(包括但不限于差分、前缀和、单调队列)。 目前正确性可以保证并且可以覆盖到整个区间不出现死循环的二分只有两种： 1.\(mid=(l+r)/2\)，\( ......

想不到好标题了。 有句话怎么说来着，罗马不是一天建成的，是一天天建成的。 还有什么，Do in Rome as the Romans' do，还有一句，All roads leads to Rome。 A. 连续的零 zero http://222.180.160.110:1024/contest/ ......

题目传送门(at) 题目传送门(luogu) 简单期望。 算法一： 枚举全排列，时间复杂度 \(O(n!)\)。 算法二： 分别求出每一个硬币的期望。为 \((sum/2+1)/(sum+1)\)，\(sum\) 为已经翻面的硬币个数，时间复杂度 \(O(n^2)\)，可以通过此题。 参考代码： 点 ......

传送门(at) 传送门(luogu) 深搜 & 广搜的模板题。 这题深搜比较简单，只需要记忆化即可，我们来考虑一下广搜，实际上这题广搜的思路与记忆化差不多，开个结构体分别记录 \(x,y,minn\) 表示 \(x,y\) 坐标及到这个坐标的最小次数，容易证明每次搜到的一定就是这个坐标的最小值，时间 ......

好久没写博客了？ 今晚写爽。 P5311 成都七中 这有黑？ 对于一个点 \(x\)，设其子树任意一点为 \(y\)。 我们可以求出这 \(x\rightarrow y\) 这条路径经过节点的的 \(l,r\)。 遍历 \(x\) 的子树，我们可以得到一些三元组 \((l,r,c)\) 表示 \(x ......

To be a rock and not to roll. 这篇文章，以及以后可能的一些文章，会把同一个来源的题丢一块。 目录牛客挑战赛 72 C. Crying 与哈密顿路D. Crying 与 404E. Crying 与初中数学2nd Ucup Stage 16 A. Bracket-and- ......

Paw 不难发现最终的局面大概是 <<...>>，此时中间是确定的。那么考虑对于前 \(i\) 个空，形成 <<< 的局面，并且不影响后面的概率。发现有 \(2n\) 种操作，只有一种不可取，那么 \(f_i = f_{i - 1} (1 - \frac 1 {2n})\)，最后求和即可。 Squi ......

## 前缀和杂题思路： P3397：二维前缀和板子，直接暴力枚举 P3131：预处理前缀和，将7的余数用桶存进来，然后扫一遍取maxx（当两个位置的前缀和%7同余时，这一段整除7） P1387：:这是前缀和？建议使用DP P3406：手搓画图，使用差分将每一段走的次数预处理出来，然后使用贪心，判断哪 ......

1.CF1906G Grid Game 2 这是一个 multi-SG 游戏，考虑计算出 \(f(x,y)=1\oplus f(x-i,y-j)\) ，其中 \(i,j<\min(x,y)\) 且 \(i,j\) 不同时为 \(0\) 。尝试打表找规律，发现不可行。但考虑把 \(f(x,y)\) 移 ......

因为输入法没有给我满意的候选项所以这次就不取抽象标题了。 可恶每道题还要证明一下满足四边形不等式，真是难为我了。 A - Chef and Bitwise OR Operation https://vjudge.net/contest/602275#problem/A CodeChef - CHEF ......

Luogu-P5046 Ynoi2019 模拟赛 Yuno loves sqrt technology I 数据范围和实现指出本题复杂的几乎不可能带 \(\log\)，考虑一个分块做法。 对于散块可以直接每个块内点对求出是否有逆序对，然后做二维前缀和。 不带 \(\log\) 的逆序对处理方法只能是 ......

海亮01/04博弈论杂题 T1 AT_agc017_d 题意 有一棵 \(N\) 个节点的树，节点标号为 \(1,2,⋯,N\)，边用 \((x_i,y_i)\)表示。 Alice 和 Bob 在这棵树上玩一个游戏，Alice先手，两人轮流操作： 选择一条树上存在的边，把它断开使树变成两个连通块。然 ......

题目链接 题目链接（AT） 题目链接（Luogu） 解题思路 简单贪心，由于每个格子始终不超过 \(9\) 个史莱姆，因此对于每四个格子 \(a_{i-1,j},a_{i+1,j},a_{i,j-1},a_{i,j+1}\)，我们只需要减去 \(\min(a_{i-1,j},a_{i+1,j},a_ ......

CF61E \(f_{i,j}\) 表示以 \(i\) 为结尾，长度为 \(j\) 的严格下降子序列的数量。 则 \(f_{i,j}= \sum_{1 \le k < i,a_k>a_i}f_{k,j-1}\)。 用树状数组优化，所以要先离散化。 时间复杂度 \(\mathcal{O}(n \log ......

题目传送门（CF） 题目传送门（luogu） 容易发现，选择两个偶数对于答案没有任何影响，因此先手必然会优先选择两个奇数合并在一起，而后手必然会优先选择一个奇数和一个偶数在一起，我们举个例子，有一个序列 \(\{1,1,1,1,1,1\}\)，先手先取编号为 \(1,2\) 的两个数，后手再取编号为 ......

因为是月末，所以可能这篇博客只有极少量的题目。 Gym-101221B Buffed Buffet 离散和连续分别考虑。 离散看上去是一个闵可夫斯基和做 \((\max,+)\) 卷积的东西，问题是有定义的位置是 \(w\) 的倍数，显然是不能差分归并的。发现对于每个 \(w\) 只能取 \(\le ......

题目链接 舒服题。 考虑贪心，我们可以直接枚举到 \(10^7\)，然后将 \(n\) 一直除以 \(n\) 和 \(i(1\le i \le 10^7)\) 的最大公因数，若到 \(10^7\) 时 \(n\) 还不为 \(1\)，这时直接输出 \(n\) 即可。 参考代码： 点击查看代码 /* ......

题目链接 期望 dp 板子题，我们直接设 \(dp_i\) 为怪物血量只剩下 \(i\) 时的概率即可，状态转移方程也很简单了，详见代码。 参考代码： 点击查看代码 /* Tips: 你数组开小了吗？ 你MLE了吗？ 你觉得是贪心，是不是该想想dp？ 一个小时没调出来，是不是该考虑换题？ */ #i ......

[ABC324G] Generate Arrays 第一次知道 AtCoder 还有这种数据结构题。 首先，所谓的“切分序列”是假，实际上只需要记录每个操作后，具体取到的原始数组的值域、下标域是什么。对于给定的下标域，求值域内数的个数，可以使用可持久化线段树，很类似区间第 \(k\) 大数的思路。 ......

20231215 NOIP2022 sol + 4道杂题 A. [NOIP2022] 种花 [NOIP2022] 种花 小 C 决定在他的花园里种出 \(\texttt{CCF}\) 字样的图案，因此他想知道 \(\texttt C\) 和 \(\texttt F\) 两个字母各自有多少种种花的方案 ......

题目链接 CF1914E1 Game with Marbles (Easy Version) CF1914E2 Game with Marbles (Hard Version) 题意简述 小 \(A\) 和小 \(B\) 想要玩一个游戏，规则是这样的，每个人手里有 \(n\) 种类型的弹珠，每种类型 ......

20231212-sdfz 多校集训-杂题选讲 AT_arc132_e [ARC132E] Paw CF1610H Squid Game CF704C Black Widow CF839E Mother of Dragons CF1253F Cheap Robot CF1446D2 Frequenc... ......

题目链接 诈骗题。 容易证明，翻转任意一个“灵异区间”时，整个序列的“灵异区间”的数量总数都不会变，因此我们直接输出原数列的“灵异区间”的总数即可。 参考代码： 点击查看代码 /* Tips: 你数组开小了吗？ 你MLE了吗？ 你觉得是贪心，是不是该想想dp？ 一个小时没调出来，是不是该考虑换题？ ......

题目链接 一道简单区间 dp。 设 \(dp_i\) 为删到第 \(i\) 个数时的最大值，状态转移方程也挺好写的。 时间复杂度 \(O(n^2)\)。 参考代码： 点击查看代码 /* Tips: 你数组开小了吗？ 你MLE了吗？ 你觉得是贪心，是不是该想想dp？ 一个小时没调出来，是不是该考虑换题 ......

题目链接 简单贪心。 由于我们需要判断无解情况，于是我们可以在做的过程中记录答案。 比较容易发现，对于每个时间段，我们肯定是优先复习日期较近的考试的，贪心了这一点，就能轻松 AC 了。 参考代码： 点击查看代码 #include<bits/stdc++.h> using namespace std; ......

有一部分题目是模板题，就不放了。 D. Luogu-P5336 THUSC 2016 成绩单 考虑区间 DP，由于操作的特殊性，我们需要设计含有区间最值的状态，设 \(f_{l,r,i,j}\) 表示区间 \([l,r]\) 中的所有数只保留值域 \([i,j]\) 中的最小代价，\(g_{l,r} ......

题目链接 算法一： 直接暴力，时间复杂度 \(O(n^2)\)。 算法二： 使用双指针维护，时间复杂度 \(O(n)\)。 算法三： 是用前缀和维护，时间复杂度 \(O(n)\)。 这里提供算法二的代码： 点击查看代码 #include<bits/stdc++.h> using namespace ......

题目链接 一道 dp 板子题。 只需要设 \(dp_{i,j}\) 为前 \(i\) 位 \(\bmod 3\) 为 \(j\) 的方案数的数量即可。 剩下的就看代码了。 参考代码： 点击查看代码 #include<bits/stdc++.h> using namespace std; #defin ......

一道好题。 题目链接 考虑离线操作。 我们可以设 \(a_i\) 为当前 \(i\) 表示的数字，然后直接倒序操作，运用并查集的思想，可以 \(O(n)\) 通过此题。 参考代码： #include<bits/stdc++.h> using namespace std; long long n,a[ ......