- 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\)的
- 2024-09-17Luogu P10812
题目描述给定一根\(1\)到\(N\)的数轴。一开始有一个棋子在\(N\)。每次棋子\(x\)可以跳到\(x-1,x+1\)或\(x\)的因子处(不能超出\(1\)到\(N\))。每个点只能到达一次。求棋子到达\(1\)的方案数。思路由于求倍数比因子简单,所以把问题变成从\(1\)到\(N\),每次跳倍
- 2024-09-14OI海海
在pyq里看到了殿禾Wrose的“X的随波逐流”,附文是“我与OI的365天”,我才想到,我打OI也整整一年了有人或许不理解我这样的一个蒟蒻为什么这么喜欢喜欢写怀念类的东西,即使到现在我还没有取得任何的奖项以及未来也并没有概率拿牌因为我只觉得一步步走来,不记得的话,是很遗憾的,更何况我
- 2024-09-13Luogu P10179 水影若深蓝 题解 [ 绿 ] [ 并查集 ] [ 构造 ]
水影若深蓝:挺好的一道并查集构造题。观察不难发现“距离为\(2\)”这个条件我们可以通过黑白染色实现,我们把他们的中转点染成与他们相反的颜色,把这两个距离为\(2\)的点染成相同颜色。这个染色问题就很并查集。于是我们用并查集维护相同的种类。显然,当图上只有一个连通块的
- 2024-09-12高一上九月中旬日记
9.11闲话做题纪要9.12闲话做题纪要luoguP3806【模板】点分治1若边权都为\(1\),求出直径后判断即可。点分治板子。随意选择一个点作为根节点\(rt\),则所以完全位于当前其子树内的路径以是否经过\(rt\)分为两种。而经过\(rt\)的路径\(u\tov(u,v\nert)\)
- 2024-09-09Luogu P11036 GCD 与 LCM 问题 [ 蓝 ] [ 构造 ] [ 数论 ] [ adhoc ]
LuoguP11036GCD与LCM问题:梦熊的题真是又神又逆天。思路观察到有个奇数的特殊性质,我们尝试从奇数构造入手。先来尝试带入极端数据,对于\(\gcd\),我们可以把\(b=1\)的情况先带进去看看。\[a+b+c+d=\gcd(a,b)+\operatorname{lcm}(c,d)\]\[a+1+c+d=1+\operatorname{lcm}(c,
- 2024-09-092024ICPC网络赛前总复习 2024.2.29复盘
https://www.luogu.com.cn/problem/CF1934B此题有完全背包写法不再赘述意识到我们不可能用3个1去换一个3也不可能用2个3换一个6.。一次类推开几个for循环voidsolve(){ intlte=1e9; cin>>n; for(inti=0;i<=2;i++){ for(intj=0;j<=1;j++){ f