noip杂题选讲\(A\)CF1290CPrefixEnlightenment\(B\)CF1458DFlipandReverse\(C\)CF1389FBicoloredSegments\(D\)CF1580DSubsequence\(E\)CF1720D2Xor-Subsequence(hardversion)\(F\)CF1775ETheHumanEquation\(G\)CF1763CAnotherArray

反悔贪心杂题笔者水平有限，若有笔误望指出。笔者认为，反悔贪心其实质仅仅只是一类贪心策略，所谓反悔，仅为一个思维过程，体现为：拿出一个错误的贪心策略（很多时候体现为略去某些限制）并尝试使用更多的策略去修正它反悔贪心有一个很常见的应用场景：从\(i\)的答案修正到\(i+1\)的答案，并

图论系列：前言：欲买桂花同载酒，终不似，少年游。相关题单：戳我一.树上启发式合并前置知识：树的重儿子。1.引入启发式算法是基于人类的经验和直观感觉，对一些算法的优化。（其实就是感觉是对的就是对的），例如并查集的启发式合并，将小集合合并到大集合中。因为在路径压缩的时候，大集合的根

基本都抄的，窝怎么这么渺小啊AGC007F这种匹配可行性基本都是从后往前贪心，这样没有后效性。而我们考虑原序列的每个字符都对应了最后序列的一个区间（如果用上）。考虑把整个变化过程写成一个矩阵，并且将每个字符染上不同颜色。像这样：容易发现对于一条新的路径，我们尽可能与上一条

Lightswitches*2600tag：暴力枚举，meetinmiddle题目描述有\(n(1\le1000)\)盏灯和\(s(1\les\le30)\)个开关，每个开关能控制一些灯，并改变这些灯的状态。接下来有\(d(1\led\le1000)\)次询问，每次询问给出\(k_i\)盏亮着的灯，询问将所有灯全部熄灭最少需要按几次开关。

图论系列：前言：相关题单：戳我一.最小瓶颈路唉，前面4个题单里其实有不少题是最小瓶颈路的做法啊。讲解摘自wiki。1.定义无向图\(G\)中\(x\)到\(y\)的最小瓶颈路是这样的一类简单路径，满足这条路径上的最大的边权在所有\(x\)到\(y\)的简单路径中是最小的。（对于下面这张

图论系列：前言：相关题单：戳我算法讲解：戳我CF1829ETheLakes给定一张\(n*m\)的矩阵，询问正整数四联通块权值和的最大值。并查集维护即可，记录一下集合内的点的权值和。代码：constintM=1005;intT,n,m,ans;inta[M][M],fa[M*M],siz[M*M];intfx[5]={0,1,-1,0,0};intfy[5]

题目链接CF1288EMessengerSimulator解题思路发现向前移的部分普通维护比较困难，因此我们考虑通过某种方式来维护这个东西。考虑建立\(m\)个虚点来维护，每次询问都将实点移至虚点去。这里求答案我们需要支持单点加，区间求和，可以用树状数组轻松维护。参考代码#include<bits/s

题目链接CF1219GHarvester解题思路就是个嗯分讨题。发现最终选择的方案总共就以下五种情况：选\(4\)行\(0\)列。选\(3\)行\(1\)列。选\(2\)行\(2\)列。选\(1\)行\(3\)列。选\(0\)行\(4\)列。对于第一，五种情况，直接取每行或每列的前四大值

题目链接CF1354EGraphColoring(*2100)解题思路发现这个东西就是类似于二分图染色的东西。因为\(2\)只能和\(1,3\)链接。其余种类的点都不能连接。不妨把\(1,3\)都看成同一个点放到最后处理。那么我们就相当于是要找到一种方案使得选择每个联通快的黑点或白点，使得最

题目链接CF1370F2TheHiddenPair(HardVersion)(*2700)题目描述真的很难吗？我们首先考虑找出第一个特殊点。我们可以先求出这两个点路径中的任意一个点。发现询问\(1\simn\)就使我们需要的询问、接下来以这个路径中的一个点为根来确定每个节点的深度。接下来考虑二

图论系列：前言：相关题单：戳我算法讲解：戳我代码可能过多啊，到时候页面别卡死了，所以就把代码最前面的缺省源删了（反正就是几个头文件/defineintlonglong，自己加一下即可）。并查集记得初始化，最小生成树记得排序。P3367【模板】并查集板子题，给定\(n\)个元素，有2种操作，一种合并，

题目链接P11267【MX-S5-T1】王国边缘解题思路先考虑对于\(1\simn\)中的每一个点往后跳\(1\)次会跳的距离。那么为什么只用处理\(1\simn\)这些点而不去处理其余的点往后跳的距离呢？我们可以发现，由于字符串是无线循环的，所以对于位置模\(n\)的结果相同时，那么往后跳

图论系列：前言：もしも明日がくるのならあなたと花を育てたいもしも明日がくるのならあなたと愛を語りたい走って笑って転んで相关题单：https://www.luogu.com.cn/training/641352一.割点与桥双连通分量是针对无向图来说的，有向图是强连通分量。在了解双连通分量之前需要先

AGC029CLexicographicconstraints有\(n\)个字符串，现在告知它们的长度\(a_i\)，求使得\(\foralli\in[1,n),s_i<s_{i+1}\)的最小字符集大小。\(n\le2\times10^5,a_i\le10^9\)二分字符集大小\(|\Sigma|\)，分类讨论，设起始字符为a：\(a_i<a_{i+1}\)：显然\(s_{i+1}\leftarr

ABC186EThrone有\(n\)个圆形排列的椅子，一开始你在\(s+1\)上，每次可以向右移动\(k\)个位置，求移动到\(1\)的最小步数，或报告无解。\(2\len,k\le10^9\)很容易想到构造方程：\[s+qk\equiv0\pmodn\]\[q\equiv(n-s)k^{-1}\pmodn\]直接exgcd求逆元，算出在\([1,n-1]\)

杂题选做1[ARC112F]DieSiedler注意到如果存在某一个\(j\)满足这种牌的数量大于等于\(2j\)，那么一定会兑换为\(j\bmodn+1\)的牌。所以我们考虑这个过程的逆过程，就是将一张牌\(j\)换成\((j-1)!2^{j-1}\)张\(1\)号牌，最终全部的牌都被转化为了\(1\)号牌，但是结果并

由于是杂题乱记所以题目大多数不会太难。目录P2572[SCOI2010]序列操作题目内容思路代码P2572[SCOI2010]序列操作题目内容给你一个\(01\)序列，支持\(5\)种操作：0lr区间赋值为\(0\)；1lr区间赋值为\(1\)；2lr区间取反，即\(0\)变\(1\)、\(1\)变\(0\)；3lr询

https://www.luogu.com.cn/problem/AT_abc354_f题意：给定一个序列a，求出所有的i使得任意一个a的最长子序列包含i。解法：我们先求这个序列的LIS的长度maxx，然后再去正着求一遍最长上升子序列和反着求一遍最长下降子序列即可，如果拼起来等于maxx那么说明i这个点是满足要求的点。注意细

哎怎么必可公益赛被爆破了，怎么lifan还加了几道我们的训练题目作为补偿。CF不知道死了多久了，一上午都没有打成duel！今天上午精神状态明显好了很多，可能和咖啡有点关系吧。按照时间顺序写题吧。AT_arc070_b可以进行撤销背包，也可以算前后缀背包，都是记录方案数。不难的。AT_a

图论系列：前言：僕は明快さ故にアイロニー優柔不断なフォローミー後悔後悔夜の果て相关题单：戳我一.强连通分量相关定义基本摘自oiwiki，相关定义还是需要了解。(实际就是搬了个oiwiki)强连通分量主要在研究有向图可达性，针对的图类型为有向弱联通图。1.强连通定义强连通：对

最近在写abc375这场，最后的F和G是两道很典的图论题。https://atcoder.jp/contests/abc375/tasks/abc375_f题意：大致就是说给你一张图，有两种操作：第一种操作是把第i条边删掉，第二种操作是询问u,v两点的最短路。解法：这种题目印象里好像是考过几次了，把在线询问的顺序转变，倒着做，把减边

2024.10.23-25杂题P7323[WC2021]括号路径如果存在\((a,b,w)\),\((c,b,w)\)。那么\((a,c)\)就是一条合法路径。所以把\(a,c\)放入一个集合。然后合并新的的时候把\(w\)一样的合并了就行。最后统计每个"块"的数量，答案就是\(\sum_{i=1}^{n}C_{cnt_i}^{2}\)复杂度\(O(

吉米多维奇杂题选解——数列极限一、用定义证明数列极限等式T1.求证：\(\lim\limits_{n\to\infty}\dfrac{n^\alpha}{c^n}=0,(a>0,c>1)\)证明：令\(k=\left\lfloor\alpha\right\rfloor+1\)，则\(\dfrac{n^\alpha}{c^n}<\dfrac{n^k}{c^n}=\left(\dfrac{n}{(\sqrt[k]{c})^n}\