2024.11.2模拟赛T1P11242碧树把\(n\)个点往外连即可。最终答案为\(n-\max_{i=1}^na_i+1\)T2P11243繁花感觉我的做法麻烦了，而且随机复杂度（）显然的，从左往右看可以分层，遇到一次大于号分一次。对于每段，遍历一遍，每遇到一次小于号计算一次答案。如果不考虑等于号，这段的

状压一类杂题P1896[SCOI2005]互不侵犯先预处理出一行的所有可能状态\(S\)，应当满足\(S\&(S≫1)=0\)，因为不能有相邻的国王。用\(f(i,S,j)\)表示考虑了前\(i\)行，第\(i\)行的状态是\(S\)，当前已经放了$$个国王的方案数。转移直接枚举第\(i−1\)行的状态\(T

P11208『STA-R8』轮回疯狂只执行操作一就是逆序对的个数，统计对于每一个\(a_i\)的逆序对个数为\(b_i\)，然后模拟执行删除操作，如果删除操作比换位操作更优就更新答案。复杂度\(O(n\logn)\)record将最小的删除可以等价成往里加最大的数，倒着模拟即可。至于操作一，每次往数

杂题AcWing5728.截取子串一眼dp，令\(f[i]\)表示考虑到第\(i\)位的答案。由于要求方案数，要么加法原理，要么乘法原理。观察样例二，用乘法原理可以解释但是很难扩展到\(f\)上，所以考虑加法原理。对于样例二，每一个位置字母都一样，不难发现\(f[3]=f[1]+f[2]\)。考虑将其一般化

2024.10.16模拟赛T1divide简要题意给定一棵树的\(n\)个结点以及每个结点的\(fa_i\)，每个点的点权\(v_i\)，删除树中的两条边，将树拆分为三个非空部分。每个部分的权值等于该部分包含的所有节点的权值之和。出一种合理的拆分方案。根节点的\(fa_i=0\)\(n≤10^6\)solution

2024.10.15模拟赛T1count简要题意给定一个长度为\(n\)的数组求其中正整数数量，\(n≤100\)solution哇，还是太难了输入的时候如果是正数就cnt++输出\(cnt\)即可人机题，不放代码了T2sigma简要题意给定\(n\)个双端队列，其中第\(i\)个队列内有\(c_i\)个整数元素。

2024.10.12模拟赛T1delete简要题意给定长度为\(n\)的数列\(a_i\)，每次操作需要选择\([l,r]\)，满足\(a_l,a_{l+1},...a_{r}\)按位与的结果为\(0\)，然后删去\([l,r]\)，删去后左边和右边合并起来。问最多能合并多少次。\(n≤63,a_i≤63\)solution显然的，由于这个操作是按

2024.10.13模拟赛T1「KDOI-10」商店砍价赛时直接口胡出一个错误的贪心。一开始的想法是按照\(v[i]\)排序，然后假设输入的长度为\(n\)位。那么对于排序后\(n-5\)位直接选择操作一。对于剩下的，直接bdfs所有情况选答案，复杂度\(O(n\logn)\)。貌似可行，结果随便一个数据

倍增&&LCA杂题倍增之前没研究过，甚至基础原理搞得都不太懂，只知道背个ST表和LCA的板子，补题补2022CSP发现T4根本学不懂，本来打算不学了，结果NOIP2018还考过类似的。所以补一下这个坑。倍增，字面意思就是成倍增长，这是指我们在进行递推时如果状态空间很大，通常的线性递推

T1.涂色游戏（paint）可以按照题意模拟，每一次暴力对于每一行列染色，时间复杂度\(O(qn)\)。可得60pts。因为颜色可以覆盖，某一格的颜色往往取决于最后一次被染到的颜色。于是我们采用打标记的方式。每一次染色（行或列）就在当前行列打标记，记操作时间戳\(t\)。最后输出答案时枚举每一格

KMP核心思想：在每次失配时，不是把p串往后移一位，而是把p串往后移动至下一次可以和前面部分匹配的位置，这样就可以跳过大多数的失配步骤。而每次p串移动的步数就是通过查找next数组确定的。KMP主要分两步：求next数组、匹配字符串，其难点在于如何求next数组for(inti=1,

2023.10.28[NOIP2018提高组]铺设道路题目传送门选择一个区间进行“填坑”操作；所以我们的贪心策略是：若a[i]>a[i-1],sum+=a[i]-a[i-1];假设现在有一个坑，但旁边又有一个坑。你肯定会选择把两个同时减1；那么小的坑肯定会被大的坑带着填掉。所以只要计算每个坑

背包dpAcWing278.数字组合\(n\)个数就是$n$个物品，每个物品的价值就是它本身的数值，只能用一次，要求价值和为\(m\)的方案数。直接01背包即可。intn,m;inta[N],f[M];signedmain(){cin>>n>>m;for(rinti=1;i<=n;i++)cin>>a[i];mem

线性dpSP15637GNYR04H按照编号从小到大摆放所有人每个人都只能放在已经存在的某个人的后面(除第一行外)任何一行的人数都不能比后一行多状态表示：\(f[a][b][c][d][e]\)表示第一行\(a\)个人，第二行\(b\)个人，...，第五行\(e\)个人的合法方案数然后在每个状态下

前言正常发挥。属于是\(4\)个月没搞OI，复健成功了！得分明细：ABCDEFGTotal√√√√√××1475改题明细：ABCDEFG√√√√√××第一次正式rated打AT，行吧！A.AtCoderLineProblemAtCoder铁路线有\(N\)个车站，编号为\(1

2024.4.20笔记SP4354Snowflakes记录所有的雪花，判断是否存在两个雪花是相同的。由于数据量较大，需要\(O(n)\)的复杂度来查询雪花，考虑哈希表定义一个哈希值的转换方式，让不同的雪花哈希值不相同，相同的雪花的六个角一定是相同的\(6\)个值且相同的顺序排列，只不过起点在不同的角

AcWing372.棋盘覆盖设每个格子为\((i,j)\)\(i+j\)为偶数和\(i+j\)为奇数的点的两个集合构成二分图的两个点集，和为偶数的边的四周全是和为奇数的点，满足二分图的性质，题目即求以和为偶数和奇数的点构成的二分图的最大匹配constintdx[]={0,0,1,-1};constintdy[]=

最小生成树AcWing.346走廊泼水节简要题意给定一个N个节点的树，要求增加若干条边，把这棵树扩充为完全图，并满足图的唯一最小生成树仍然是这棵树。求增加的边的权值总和最小是多少，保证边权位非负整数。题目分析考虑kruskal的过程，是把权值从小到大排序，依次扫描每一个边。那么

ARC167前言非常不可做的一场，全场数学，打得心累。[ARC167A]ToastsforBreakfastParty传送门link对于任意一个盘子价值形如\((x_i+x_j)^2\)的形式，那么所有的价值加起来一定是\(\sumx_i^2+\sumx_jx_k\)现在要最小化后面那个排个序即可。signedmain(){cin>>

ARC168前言输输输，只有A、B、D只有独立做出来了。C想到了的idea，但是指数是6次方级别的，没敢写。E看出来了是wqs二分，但是找不到凸，F根本不可做。麻了。[ARC168A]传送门link这种题放在A就别瞎想，简单问题简单解决，双指针扫一遍即可。intn;strings;intans;sign

ARC169前言学校晚饭后不让来机房，时间卡的很死。基本赶不上赛时AtCoder，更不能谈codeforces了。这就导致到现在一场ARC没参加过。于是今天VP了一下，A题很水十分钟碾过去了，B题先想到了一个假贪心，答题思路不变稍微改改改成dp就可以了。C题写的比B还快，比较套路，一眼dp。D

莫队基础莫队[SDOI2009]HH的项链这道题是卡莫队的，但是确实练习莫队的好题。首先想一下暴力：直接暴力枚举询问，然后再枚举区间，这样是O(n^2)的；想一下优化：如果说询问是按照左端点递增&&右端点递增的；那么我们就可以离线排序，用线性的时间扫过去所有询问，用桶记录一下就行，同

rint方法返回值最接近参数的整数。rint()-语法doublerint(doubled)这是参数的详细信息-d  - 它接受双精度值作为参数。rint()-返回值此方法返回值最接近参数的整数。rint()-示例publicclassTest{publicstaticvoidmain(Stringargs[]){do

2023.11.11模拟赛复盘前记通过四个半小时的努力，得到了41pts/400pts的高分。当时心态很爆炸，经过不断的反思，发现自己比赛意识太差，暴力打不出，正解想出来tmd不会写，这就是最大的问题。所以以后要多打比赛还得多复盘。比赛链接洛谷NOIP2023模拟赛T1种树简化题意：给定

随机化什么是随机化算法？随机化做法，就是基于当前算法而言，通过正确算法求解会TLE或者MLE，但是出于骗分的目的，我对可能答案中的一些序列或者值进行查找，在我随机瞎找的这些值中去找正确答案，最后，所得出的答案具有极大可能性为正确答案，甚至于百分之一百。如果题目要求最优解，但难以