- 2024-11-02高一上十一月上旬日记
11.1闲话补\(whk\)。补完了英语。下午大课间时\(miaomiao\)突然跟我们说让回班拿冲锋衣,今年就不发冬季校服了。做题纪要11.2闲话上午补\(whk\)。补完了语文和数学。详见2024NOIP游记11.2。下午\(miaomiao\)跟我们说补一下没写完的\(whk\)作业,然后写字
- 2024-11-028.字符串
字符串开题顺序:\(HABE\)\(A\)luoguP3501[POI2010]ANT-Antisymmetry多倍经验:SP15569Antisymmetry题解\(B\)luoguP4555[国家集训队]最长双回文串题解\(C\)luoguP6114【模板】Lyndon分解\(D\)BZOJ2176Strangestring\(E\)CF471DMUHandCubeWalls题
- 2024-11-01[luogu P11189] 水杯降温
纯粹是自己太唐导致的我们发现其实这两种操作是独立的,并不需要考虑操作的相对顺序。这时候就有两种解决顺序:先子树加再链减先链减再子树加由于我一开始看错题了,所以我选了第一种思路,然后就爆炸了。所以我们选第二种,钦定\(d_x=a_{fa_x}-a_x\),那么最后子树加的时候
- 2024-10-31LUOGU_进阶算法思想
进阶算法思想单调数据结构单调队列,单调栈都是均摊\(O(1)\),是不支持撤销的,只能按照正常过程加入。单调栈求最近的大于小于其的值CF280BMaximumXorSecondary:枚举最大值,次大值并不容易确定,但枚举次大值的位置,这样最大值就是其左右两边第一个比其大的值,用单调栈可求出。其实就
- 2024-10-31LUOGU_图论
LUOGU_图论ST表+DFN序LCA每次在自己的DFN序位置放入自己的父亲询问的时候l+1ST表+欧拉序LCA\(u,v\)在欧拉序中的第一个位置之间的深度最小位置就是LCA树的直径相距最远的两个点\(\max_{u,v}dis(u,v)=\max_{u,v}(dep_u+dep_v-2dep_{lca(u,v)})\)边权非负:两次BFS边权有
- 2024-10-31LUOGU_进阶数据结构
LUOGU_进阶数据结构二叉堆P10977CuttheSequence:因为DP的值是单调递增的,所以可能的决策点只有最远的合法位置与那些后缀最大值段的左端点,用单调队列+可删除堆(懒标记)做。如果\(\exista<0\),怎么做?CDQ优化DP,可以做!!并查集P10350ModernizacjaBajtocji:把二选一的居民放进一
- 2024-10-25Luogu 的脚本
1. extend-luogu//==UserScript==//@nameextend-luogu//@namespacehttp://tampermonkey.net///@descriptionMakeluogumorepowerful.//@description:zh使洛谷拥有更多功能//@iconhttps://raw.fastgit.org/extend-luogu/extend-lu
- 2024-10-24AC自动机
今天复习了一下AC自动机,原理不再赘述,直接看其他优质博客讲解即可。本文更偏向于AC自动机的用法,记录一下模板题的代码:1.只检查模式串是否在主串中出现————https://www.luogu.com.cn/problem/P3808code:https://www.luogu.com.cn/record/1846121282.检查每个模式串在主串
- 2024-10-18【LGR-203-Div.4】洛谷入门赛 #28
【LGR-203-Div.4】洛谷入门赛#28\(A\)luoguB4042[语言月赛202410]顺序结构\(AC\)顺序结构。点击查看代码intmain(){lla;cin>>a;cout<<3*(5+a)<<""<<3*a+5<<endl;return0;}\(B\)luoguB4043[语言月赛202410
- 2024-10-17luogu P3842 [TJOI2007] 线段
link好题,考虑如何设定状态。设\(dp_{i,0/1}\)表示到了第\(i\)行走完后停在这一行的最左侧/最右侧。设定\(l_i\)表示这一行该线段的最左侧,\(r_i\)表示这一行的最右侧。思考如何转移。1.当我处在这一行的最左侧时,我需要从这一行的右端点转移过来,所以你的贡献要加上这个线段的长
- 2024-10-166.动态规划
动态规划\(A\)CF510DFoxAndJumping\(B\)CF459EPashmakandGraph\(C\)CF809CFindacar\(D\)luoguP4099[HEOI2013]SAO\(E\)CF559EGeraldandPath\(F\)luoguP4516[JSOI2018]潜入行动\(G\)HDU6566TheHangedMan\(H\)UOJ211.【UER#6】逃跑
- 2024-10-165.树上问题
树上问题开题顺序:\(AC\)\(A\)CF600ELomsatgelral题解\(B\)CF708CCentroids\(C\)CF1706EQpwoeirutandVertices题解\(D\)luoguP2491[SDOI2011]消防\(E\)luoguP4253[SCOI2015]小凸玩密室\(F\)luoguP8890[入门赛#7]打ACM最快乐的就是滚榜读队名
- 2024-10-15luogu 模拟赛
A.带余除法我们不难考虑找出\(q\)的上下界,不难发现范围是\([\lfloor\frac{n}{k+1}\rfloor+1,\lfloor\frac{n}{k}\rfloor]\)。当然这个区间可能为空。只需算出区间长度即可。B.奖牌排序不难考虑到分别按照三个关键字排序,然后对于每个小朋友找到每个关键字下的排名(同分取第一
- 2024-10-134.数学
数学1(容斥、组合数学、期望)\(A\)CF1613FTreeColoring\(B\)CF1466HFindingsatisfactorysolutions\(C\)Gym103415KMagusNight\(D\)luoguP8292[省选联考2022]卡牌\(E\)CF1139DStepstoOne\(F\)CF908DNewYearandArbitraryArrangement\(G\)CF749EIn
- 2024-10-09【笔记】杂题选讲 2024.10.5(DNF)
十一杂题选讲-VirtualJudge(vjudge.net)/mnt/e/codes/contests/20241008/sol.md目录[AGC004F]Namori[1406E]DeletingNumbers[1081G]MergesortStrikesBack[1033E]HiddenBipartiteGraph[1254E]SendTreetoCharlie[1012E]Cyclesort[1284F]NewYearandSocialN
- 2024-10-083.搜索、模拟
搜索、模拟\(A\)luoguP1120小木棍\(B\)luoguP2540[NOIP2015提高组]斗地主加强版\(C\)CF58EExpression\(D\)CF293BDistinctPaths\(E\)[ABC352F]EstimateOrder\(F\)[ABC336F]RotationPuzzle\(G\)CF525EAnyaandCubes\(H\)luoguP9234买瓜\(I\)
- 2024-10-08吃奶酪和最短Hamilton路径
吃奶酪&最短Hamilton路径以后者为例。定义\(f[i][S]\)表示走了集合\(S\)的点,最后在\(i\)。考虑从\(S\)中去掉\(i\),然后找到一个\(j\),则\(f[i][S]\leftarrowf[j][S\oplus2^j]+a_{i,j}\)。前者需要新加入一个\((0,0)\),共\(n+1\)个点。复杂度\(O(n^22^n)\)。
- 2024-10-042024.10.4 总结
自己做题太慢了。我在图论方面思维很不够灵活。主要表现在建立图论模型、建图、对图上的权值做神秘修改等方面。下午尝试证明某题“正正解”的正确性,花了非常多的时间。后来水哥[解决了问题](?)(我感觉挺对的,但没细想了)。今天最后一题结论的证明:https://www.luogu.com.cn/article
- 2024-10-04【题解】「CF765F」Souvenirs
https://www.luogu.com.cn/problem/CF765F首先有一个比较navie的\(O(n\sqrtm\logn)\)的做法(add和del的时候,用两个multiset维护一下。有一个bitset的做法来优化用multiset查询前驱后继的做法:https://www.luogu.com.cn/article/zcmco6hd首先考虑离线下来,将询问挂
- 2024-09-29Luogu P5663 CSP-J2019 加工零件 题解 [ 绿 ] [ 同余最短路 ]
加工零件:非常好的一道图论题。CCF普及组的题目大概也只有图论出的比较巧妙了。题意简述:给你一张无向图,\(q\)次询问,判断是否存在一条从\(a\)到\(1\)且长度为\(L\)的路径。看到\(L\)很大,我们立刻想到了要撇开\(L\)的限制思考问题。首先,对于一条路径,我们肯定能找到从
- 2024-09-24Luogu P10956 金字塔
Solution考虑区间dp。很容易想到定义\(dp_{l,r}\)表示区间\([l,r]\)对应的满足条件的子树的方案数。一般区间dp的套路无非就是枚举一个断点\(k\),使得这个大状态由两个小状态转移过来,我们现在需要考虑的就是如何划分每一个状态。状态对应的子树也有若干个子树。不妨只考
- 2024-09-24福建省历届夏令营-排序
https://www.luogu.com.cn/problem/P1347特殊情况很烦。如果出现条件\(A<A\),矛盾;然后我们每次加入一条新的边,就重新做拓扑排序,记为函数topo()。如果topo()\(=i\),表示总进队次数为\(i\)。由于要唯一确定,所以如果出现某一个时刻队列长度超过\(1\),就说明这两个点是平级的关
- 2024-09-21高一上九月下旬日记
9.21闲话详见2024CSP-S游记9.21。做题纪要luoguP6329【模板】点分树|震波luoguP4093[HEOI2016/TJOI2016]序列luoguP3345[ZJOI2015]幻想乡战略游戏luoguP3241[HNOI2015]开店
- 2024-09-19Luogu P6680
题目描述给定一张\(N\)个点,\(M\)条边的无向简单图。如果存在\(1\lea<b<c\leN\)满足存在边\((a,b),(a,c)\),并且不存在\((b,c)\),则加入边\((b,c)\)。求最后的边数。思路首先我们可以把边看做从小的连向大的。通过观察可以发现只有在这种情况下才会建边:这里红色的
- 2024-09-19luogu-P10596题解
简要题意一个有\(N\)个元素的集合有\(2N\)个不同子集(包含空集),现在要在这\(2N\)个集合中取出若干集合(至少一个),使得它们的交集的元素个数为\(K\),求取法的方案数,答案模\(10^9+7\)。数据范围:\(1\leK\leN\le10^6\)。题解我们设\(f(i)\)表示选出子集大小恰好为\(i\)的