- 博客(590)
- 收藏
- 关注
RSS订阅
原创 给2020年之后看到这篇博客的OIer们
当你看到这段文字，我已经AFO了很长时间了，而所有你们看到的在2019年之后发布的内容，都是我在竞赛时已经写好，但由于各种原因并未公开发布的内容。但现在我没有那么多顾虑了，因此我打算把这些内容陆续发出来，供更多的人学习，能帮一个是一个。我个人已经失去了学习ACM的兴趣，我也不知道在强基计划的形势下，还有没有人坚持学习OI，但如果屏幕前的你仍在坚持，那我希望我的文字能给你提供一点点帮助。就这样。...
2020-08-21 11:09:52
348
1
原创 小W的神奇口胡
这里会口胡一些乍一看会做，或者没时间写（或者懒得写）的题目，或者一道题目的其他解法，应该很少更新，不用等了……【BZOJ3456】城市规划-分治NTT 测试地址：城市规划 做法：本题需要用到分治NTT。 实际上这题做法挺多的，我用多项式求逆写了这一题，据说还可以用多项式求ln写，有待学习。 令f(n)f(n)f(n)为我们要求的答案，g(n)g(n)g(n)为不要求连通时的答案，显然g...
2018-06-20 19:38:27
418
原创 （2023-10-30编写）【CSP202309-5】阻击-动态点分治+一堆数据结构（无代码）
对于每棵可能受影响的分治子树，“从重心出发到子树中各点的路径边权和”这点在最开始进行的点分治中可以求出，而对于每次修改，我们发现受到影响的范围都是以重心为根的情况下的一棵子树，而且变化的值是同一个常数（新边权和原边权的差值），于是想到先将所有点按DFS序排列，这样一棵子树就和DFS序上的一个区间对应，而区间修改，以及之后要做的区间最值查询（查询某个“方向”，也就是某棵子树内，路径边权和的最大值），这些都提示了需要用“线段树”来处理这些数据。的路径边权和的最大值。，由点分治的性质可知，整个点分治的复杂度是。
2023-10-30 10:49:02
671
1
原创 （2023-10-30编写）【CSP202309-4】阴阳龙-map+set+模拟
个点，每次询问一个点，让你求在这个点左右最接近的点，你很快就会想到用set，而这道题只是把“数轴”换成了行、列和斜线而已。所以我们大可以对每行、每列、每条斜线都维护一个set，这样就能求出在这些方向上最接近的点了，然后就是模拟题目中所说的过程，进行插入、删除等操作即可。次“阴阳龙现身”事件，每次事件会选取一个旋转中心，从这个中心出发，向横、竖、斜线上的8个方向寻找最接近的人或边界，然后取出8个位置，将这8个位置上的人（如果有的话）进行某种旋转置换，最后还是回到这8个位置上，具体看题目。
2023-10-30 10:01:21
1267
原创 CCF CCSP2023参赛记 + 算法题题解
大家好啊，时隔多年，作为大四老年人，再次来到这个地方记录算法竞赛相关，可能也是最后一次参加这种算法赛事了，我觉得还是很有纪念意义的。虽然我高中搞OI被强基背刺，以至于到了大学有点躲着竞赛，但是我还是对算法题有一种玩解谜游戏一样的兴趣的。前年和去年都因为疫情原因，要么没能参加，要么只能线上参加，只能说比较遗憾。特别是去年线上参赛的那次，6个小时3道题，题目出的不咋地，唯一一道算法题正解是搜索剪枝，剩下两道系统题不管是大模拟还是什么，都没什么下手的空间，最后交样例骗了30分，还拿了块铜牌，不能说很光彩。
2023-10-26 23:52:28
566
原创 （2021-8-15编写）同学出的一道题
题目大意： 有两根管子，每根管子里装着nnn个球，每个球上面写着000到999其中之一。每次想要取球，都可以任选一根管子，然后选择是从管子的头部或尾部取一个球。现在已知两根管子里球的顺序，要求找到一种合法的取球顺序，使得取出的球按取球的顺序排列后，得到的2n2n2n位数最大（先取的球是高位）。T≤100T\le 100T≤100组测试数据，每组测试数据n≤50n\le 50n≤50。做法： 本题需要用到贪心。像这种要求最后取出的数连起来最大的问题，想到可以每次贪心地取出可能情况下能取出的最大的数。如果
2021-08-15 18:14:47
214
原创 （2021-3-19编写）【CSP202012-04】食材运输-状压DP+树形DP
测试地址：食材运输题目大意： n(n≤100)n(n\le 100)n(n≤100)个节点的树，有边权。每个点有的需求，一共可能有K(K≤10)K(K\le 10)K(K≤10)种需求，每个点也可以有多种需求。对于每种需求，需要派遣一个（且只能派遣一个）交通工具，从某点开始，顺着树边遍历所有有这种需求的点，从而满足这些点的需求，边权就是通过这条边所需的时间。现在要求安排M(M≤K)M(M\le K)M(M≤K)个点，使得当所有KKK个交通工具同时从这MMM个点中的某些点出发后，等待需求被满足的时间最长的点
2021-03-20 00:47:24
1013
1
原创 （2020-10-11编写）有趣的简单博弈/贪心一道
在我校历年入ACM队笔试（你没看错，是笔试）题里看到一道这样的题，挺有意思的，写出来分享分享。可能是一道非常经典的题，但我反正没见过，就写在这了。题目大意： 有2n2n2n颗石子，每颗石子有两个权值ai,bia_i,b_iai,bi。两个人甲、乙用这些石子玩游戏，两人轮流取石子，每一轮取一颗石子，最后每个人都取到nnn颗石子。此时，甲的分数为他取到的石子的aia_iai之和，乙的分数为他取到的石子的bib_ibi之和，谁分数高，谁就取得游戏的胜利。给定所有2n2n2n颗石子的ai,bia_i,b_
2020-10-11 13:46:22
209
1
原创 【BZOJ3167】SAO（HEOI2013）-高维树形DP+组合数学
测试地址：SAO题目大意： 给定一棵树边是有向边的树（边不一定从根指向儿子），求拓扑序数量。n≤1000n\le 1000n≤1000。做法： 本题需要用到高维树形DP+组合数学。如果边都是从根连向儿子的话，简单组合就可以树形DPO(n)O(n)O(n)做了，问题是这道题并不是这样的，而是一个“类树”的结构，但因为它还是棵树所以我们还是考虑树形DP。考虑用类似树形背包的做法，把子树一一合并...
2020-10-11 13:17:47
145
原创 【BZOJ2069】ZAW（POI2004）-最短路+二进制分组
测试地址：ZAW题目大意： 给定一张边是双向的图，一条边走不同的方向可能代价不同，代价都非负，求从点111出发，不经过重复的点或边的最小回路。n≤5000,m≤10000n\le 5000,m\le 10000n≤5000,m≤10000。做法： 本题需要用到最短路+二进制分组。不久前做过一道清华爷出的NOIP模拟题：给定一张边是双向的图，给定其中的一个点集CCC，求从CCC中某点出发，到与...
2020-10-11 13:16:36
273
原创 （2020-10-7编写）一道有趣的不难的题
没错，这篇文章不是在我学OI时写的，而是在实实在在的2020年写的。这似乎预示着我将不得不重回竞赛的怀抱了，祝我好运吧。题目大意： 对一个长为nnn的数列{an}\{a_n\}{an}，有以下两个操作：1.1.1.求和操作：数列{a1,a2,...,an}\{a_1,a_2,...,a_n\}{a1,a2,...,an}变为{a1,a1+a2,...,a1+a2+...+an}\{a_1,a_1+a_2,...,a_1+a_2+...+a_n\}{a1,a1+a2,...,a1+a2+
2020-10-07 12:54:13
189
原创 （据说是）鏼爷和吴凯路爷爷出的NOIP模拟神题集锦
鏼爷神题Day1T1 回文切割（pal）题目大意： 给定一个长为nnn（nnn是偶数）的01串sss，我们要反转里面的几位，使得这个01串能由若干偶数长度的回文串连接而成，反转第iii位的代价是wiw_iwi，求最小代价。n≤2000n\le 2000n≤2000。做法： 本题需要用到DP。显然有区间型DP的思路，令f(i)f(i)f(i)为使长为iii的前缀满足条件的最小代价，则有：...
2020-09-09 19:15:31
426
原创 NOIP2018模拟赛总结（2018.10.24-2018.11.5）
文章目录2018.10.24T1 BackpackT2 SortT3 Digit2018.10.24据说是九校联考的题（虽然不知道哪九校），老师拿来考了，考得还算不错吧…T1 Backpack题目大意： 给定n(≤106)n(\le 10^6)n(≤106)个物品，每个物品有体积a(≤100)a(\le 100)a(≤100)和价格b(≤100)b(\le 100)b(≤100)，同种物品...
2020-09-08 21:36:07
210
原创 NOI.AC之NOIP2018全国热身赛参赛实录
Day 1T1 Array题目大意： 给定一个长为n(≤107)n(\le 10^7)n(≤107)的数列
2020-09-08 21:27:01
302
原创 NOIP2017模拟赛总结（2017.11.6-2017.11.7）
2017.11.6 Problem A 题目大意：nn个人围成一个环，编号为11~nn，从11号开始从11报数，每次报到mm时，报11~m−1m-1的人出列，下一个人继续报11，问最后留下的人的编号。保证m−1|n−1m-1|n-1。 做法：本题需要用到递归。 nn个人进行这个游戏的话，如果就这样顺着报下去，那么剩下的就只有编号为mm的倍数的人和最后n%mn\%m个人，相当于把后n%mn\%
2020-09-08 21:22:53
139
原创 NOIP2017模拟赛总结（2017.11.2-2017.11.5）
2017.11.2 Problem A 做法：这题按照题意大模拟，题目太繁琐就不贴了……2017.11.2 Problem B 题目大意：对于一个排列，在每两个相邻的数写上符号，如果右边的大于左边的写，否则写>>，问有多少种11~n(≤1000)n(\le 1000)的排列中恰好有kk个？结果对大素数取模，多组询问。 做法：本题需要用到DP。 令f(i,j)f(i,j)为11~ii的排
2020-09-07 14:58:28
166
原创 NOIP2017模拟赛总结（2017.10.30-2017.11.1）
第三篇博客，放上2017.10.30-2017.11.1的题。2017.10.30 Problem A 题目大意：把一个长为nn的非负数列分成不超过kk个区间，使得每个区间内数的和都不大于ss，求满足条件的最小的ss。 做法：显然二分ss，然后从左往右扫一遍判定即可。 以下是本人代码：#include #include #include #include #include
2020-08-25 10:41:34
186
原创 NOIP2017模拟赛总结（2017.10.26-2017.10.29）
嗯，这次是10.26到10.29的题，因为10.27休息了一天，所以还是3天。2017.10.26 Problem A 题目大意：有一个容积为VV的背包和nn个物品，每个物品有两个参数ai,bia_i,b_i，表示要装下这个物品需要消耗aia_i的容积，但装进去后背包的容积会扩大bib_i，问存不存在一种装物品的顺序使得能装下所有物品。 做法：本题需要用到贪心。 首先对于ai≤bia_i
2020-08-25 10:36:16
144
原创 NOIP2017模拟赛总结（2017.10.23-2017.10.25）
在学校模拟赛中出现了一些比较有意思的题目，在这里写出来总结一下。一篇博客就写3天，也就是9题吧。2017.10.23 Problem A 题目大意：有一列数：11~nn，每次从其中选出两个求平均值，然后放回数列中，求最后剩下的数的最大值，对大素数取模。 做法：本题需要用到贪心+数学。 首先可以证明每次选最小的两个是最优的，那么最后得到的值要怎么计算呢？ 我们知道要求的式子是：((...
2020-08-21 11:04:22
177
原创 【LuoguP4719】动态DP模板-树链剖分+线段树+矩阵乘法
测试地址：动态DP做法： 本题需要用到树链剖分+线段树+矩阵乘法维护动态DP。动态DP这个东西以前听过，但当时没有看懂，现在想来觉得是卡在矩阵乘法这个地方。这里用的不是传统的矩阵乘法。一般的DP我们肯定会做，序列上的线性动态DP（可以用线性递推式递推的DP）很容易想到用线段树+矩阵乘法优化，但最大权值独立集这个经典树形DP模型要动态维护的话，有两个和上面问题不同的地方，第一是它不是序列，第二...
2020-01-22 12:13:20
221
原创 【CF856D】Masha and Cactus-树形DP+LCA+树状数组
测试地址：Masha and Cactus题目大意： 给定一棵树，再给定mmm条边，每条边有权值，从里面选出一些边加入树中，使得形成的图是仙人掌，即每个点至多处在一个环中的图，并使得加入的边的权值和最大，求出这个最大值。做法： 本题需要用到树形DP+LCA+树状数组。首先转化一下问题。不难想到，添加一条边会使得树上的一条路径上的点被一个环覆盖，那么要使一个点至多在一个环中，也就是要求添加的边...
2018-12-01 17:54:19
446
原创 NOIP2018差点退役+心态爆炸杂思
本篇文章负能量程度爆表，且文字间衔接逻辑完全混乱，强烈不建议阅读。是的，我并不打算在这里写我考场上怎么想题写题，我可能只是来抒发一下我可能真的即将要退役的感慨吧…（说是感慨，可能只是对自己失败人生的吐槽和牢骚）考试前我自以为我准备不错，专门请假一天颓废调整心态，通关了Undertale和Deltarune放出的Chapter 1（Toby Fox真是个游戏鬼才），不过这貌似不是重点啊…D1考下...
2018-11-12 22:49:36
1944
2
原创 【BZOJ2144】跳跳棋-二分+LCA
测试地址： 跳跳棋做法： 本题需要用到二分+LCA。一道神题。注意到三个棋子可以进行一下的跳跃：1.中间的棋子跳过两边的棋子向外跳跃；2.距离中间棋子较近的那个棋子跳过中间的妻子向内跳跃。因为限制了只能跳过一个棋子，所以上面的两种跳跃方式就是全部了。而我们发现，除非两边的棋子和中间的棋子距离相等，通过第二种跳跃都只能到达一种状态，而第一种跳跃和第二种跳跃是互逆的操作，于是我们惊奇地发现：...
2018-11-06 15:32:13
425
原创 【BZOJ3093】A Famous Game-概率论+组合数学
测试地址：A Famous Game题目大意： 一个袋子里有nnn个球，球的颜色只有红和蓝，红色球的数目为000 ~ nnn的概率都是相等的。现在已经从里面取出了ppp个球，其中qqq个是红色，求下一个取出的球是红色的概率。做法： 本题需要用到概率论+组合数学。通过这道题，我终于意识到概率论这个东西真的不可能靠直觉算对…想出来这种东西的贝叶斯真是个神人…本题需要用到的公式：P(A∣B)=...
2018-11-03 21:44:27
435
原创 【BZOJ3619】璀灿光华（ZJOI2014）-思维+建图
测试地址：璀灿光华（BZOJ没有题面，所以贴了洛谷的测试地址）做法： 本题需要用到思维+建图。首先吐槽一下，这个题目名字是不是应该叫“璀璨”啊…算了算了，强省大佬自有用意，我这种阅读理解000分选手还是不要妄加猜测了…注意到nnn很小，可以直接暴力枚举，O(a⋅6n)O(a\cdot 6^n)O(a⋅6n)解决这个问题。这个题最难的地方在于，如何通过这些点的相互连接，得出每个点在立方体中的...
2018-11-02 19:42:59
359
原创 【BZOJ3351】Regions（IOI2009）-分块+vector
测试地址：Regions题目大意： 给定一棵nnn个点的有根树，每个点有颜色，qqq个询问，每次询问给出两个颜色a,ba,ba,b，表示询问树中有多少对点(u,v)(u,v)(u,v)使得uuu颜色是aaa，vvv颜色是bbb，且uuu是vvv的祖先。做法： 本题需要用到分块+vector。好题。传统数据结构貌似做不了这道题，于是想到分块。很容易想到两种暴力：1.将aaa相同的询问一起处...
2018-11-02 11:00:23
286
原创 【BZOJ3131】淘金（SDOI2013）-数位DP+优先队列
测试地址：淘金做法： 本题需要用到数位DP。令F(x,y)F(x,y)F(x,y)为坐标(x,y)(x,y)(x,y)上的黄金数目，那么：F(x,y)=∑i=1n∑j=1n[f(i)=x]⋅[f(j)=y]F(x,y)=\sum_{i=1}^n\sum_{j=1}^{n}[f(i)=x]\cdot[f(j)=y]F(x,y)=∑i=1n∑j=1n[f(i)=x]⋅[f(j)=y]=(∑...
2018-11-01 17:13:42
257
原创 【BZOJ4513】储能表（SDOI2016）-数位DP
测试地址：储能表做法： 本题需要用到数位DP。显然地，我们可以把问题转化成，令SumSumSum为所有≥k\ge k≥k的i xor ji\space xor\space ji xor j之和，CntCntCnt为其个数，那么答案就为Sum−k⋅CntSum-k\cdot CntSum−k⋅Cnt。具体地，我们是要计算满足这些条件：i≤n−1,j≤m−...
2018-11-01 11:26:41
213
原创 【BZOJ3233】找硬币（AHOI2013）-DP+数论
测试地址：找硬币做法： 本题需要用到DP+数论。假设我们有了构造出了一个合法硬币序列xxx，怎么计算最少需要使用的硬币数量？显然，因为xkx_kxk为xk−1x_{k-1}xk−1的倍数，能用大的就应该用大的，那么对于最大的币值xkx_kxk，应该要使用⌊aixk⌋\lfloor\frac{a_i}{x_k}\rfloor⌊xkai⌋个，于是还剩下ai%xka_i\%x_kai%...
2018-10-31 22:34:49
291
原创 【51Nod1623】完美消除-数位DP+状态压缩+单调栈
测试地址：完美消除做法： 本题需要用到数位DP+状态压缩+单调栈。对于一个数字，如何求出它的最小消除次数？把每一位一一推入单调栈（栈顶元素最大），并在最后把所有的元素都出栈，那么元素出栈的总次数就是最小消除次数。这一点做过单调栈题的同学应该很容易能看出来了。那么对于这一题，显然看出是数位DP，而且数位DP也是从高位到低位转移。我们又发现数位只有000 ~ 999这101010个数字，于是我们...
2018-10-31 12:03:00
228
原创 【CF840C】On the Bench-DP+组合数学
测试地址：On the Bench题目大意： 给出一个长为nnn的序列AAA，问有多少种111 ~ nnn的排列ppp，满足对于任意1≤i&lt;n1\le i&lt;n1≤i<n，有APi⋅APi+1A_{P_i}\cdot A_{P_{i+1}}APi⋅APi+1不为完全平方数。做法： 本题需要用到DP+组合数学。直接状压DP的复杂度应该是O(n22n)O(...
2018-10-30 10:31:13
259
原创 【BZOJ4773】负环-倍增+Floyd
测试地址：负环做法： 本题需要用到倍增+Floyd。我们很快能想出O(n2m)O(n^2m)O(n2m)的算法：令f(i,j,k)f(i,j,k)f(i,j,k)为走iii条边，从jjj走到kkk的路径中最小的权值和。从小到大枚举iii转移即可。然而并过不了，而且我们发现，负环的长度似乎也不是单调的，即存在长为kkk的负环，不一定表示存在长为k+1k+1k+1的负环。实际上，我们只要给每个点...
2018-10-28 20:57:58
259
原创 【LuoguP4934】礼物（LGR-054）-Dilworth定理+优化建图+拓扑排序
测试地址：礼物做法： 本题需要用到Dilworth定理+优化建图+拓扑排序。对位运算感觉比较敏锐的话，可以看出，a&amp;ba\&amp;ba&b这个东西要么比a,ba,ba,b都小，要么就说明a,ba,ba,b中有一个在二进制位上是另一个数的子集。因为属于的关系是一种偏序关系，根据Dilworth定理，偏序反链最小覆盖等于最长偏序链，因此我们可以O(n2)O(n^2...
2018-10-24 21:11:26
217
原创 【LuoguP3616】富金森林公园-线段树
测试地址：富金森林公园做法： 本题需要用到线段树。一道好题，不看题解乍一下真的不知道怎么做…我们考虑直接维护水面在高度iii时能看见的连续段数cnt(i)cnt(i)cnt(i)，考虑一块石头高度的增减对cntcntcnt的影响。为了讨论方便，我们把修改操作都看成是，先把石头高度降到最低，再把石头高度升到新的高度，这样只用考虑两个过程就可以了，并且我们发现这两个过程产生的贡献完全相反，因此我...
2018-10-23 21:32:57
240
原创 【BZOJ1432】函数（ZJOI2009）-思维
测试地址：函数做法： 本题需要用到思维。如果在xxx坐标为负无穷时，把函数从下到上编号为111~nnn，那么在向右扫时，一旦遇到一个交点，就表示交的这两个函数上下位置进行交换。因为每两个函数间有且仅有一个交点，且不会有三个函数共点，因此这些交换是先后进行的，且一定是发生在下面的函数编号比上面的函数小时，那么最后在xxx坐标为正无穷时必定会换为从下到上nnn ~ 111的形式。于是现在要求第kk...
2018-10-22 19:41:45
238
原创 【BZOJ1190】梦幻岛宝珠（HNOI2007）-背包DP+思维
测试地址：梦幻岛宝珠做法： 本题需要用到背包DP+思维。这道题看上去是一个裸01背包，然而容量特别大，因此我们只能从其中唯一一个特殊条件入手：a⋅2ba\cdot 2^ba⋅2b形式的重量。我们考虑把这些物品分阶段来进行决策。我们首先对每个bbb，求出重量表示为a⋅2ba\cdot 2^ba⋅2b的那些物品中，取重量为k⋅2bk\cdot 2^bk⋅2b的物品能得到的最大总价值totval(...
2018-10-22 16:25:06
207
原创 【LuoguP2576】梦幻折纸（ZJOI2005）-思维
测试地址：梦幻折纸做法： 本题需要用到思维。考虑最后折出来的正方形，从上到下的各层中，有可能有两层在前后侧相连，也有可能有两层在左右侧相连。易知，无论怎么折前后侧的相连都不会成为左右侧，这启发我们分开判断两维是不是成立。要判断某一维是不是成立，需要观察出下面两个结论：1.如果两列i,ji,ji,j相邻，最后所有a(x,i)a(x,i)a(x,i)和a(x,j)a(x,j)a(x,j)相连的...
2018-10-22 10:51:29
536
1
原创 【BZOJ1483】梦幻布丁（HNOI2009）-链表+启发式合并
测试地址：梦幻布丁做法： 本题需要用到链表+启发式合并。首先，注意到颜色的段数等于，相邻的颜色不同的元素对数+1+1+1，而一对元素一旦颜色相同就不可能再变成不同，因此我们在改变颜色的时候，只要找到这个颜色的元素周围有没有修改后就变成颜色相同的元素即可。我们想到用链表来连接同颜色的那些点，但如果进行暴力修改的话，时间复杂度最坏为O(n2)O(n^2)O(n2)，怎么办呢？注意到一种颜色变成另...
2018-10-22 08:33:18
204
原创 【CF605C】Freelancer's Dreams-凸包
测试地址：Freelancer’s Dreams题目大意： 有nnn项工作，每项工作有两项属性ai,bia_i,b_iai,bi，表示做111单位时间可以获得aia_iai的经验和bib_ibi的钱，现在要攒够ppp的经验和qqq的钱，且任意一个时刻只能做一项工作，每项工作进行的时间可以是任意非负实数，问要达到目标最少需要工作多少时间？做法： 本题需要用到凸包。好题。我们把一项工作看...
2018-10-21 16:59:58
279
原创 【CF622F】The Sum of the k-th Powers-拉格朗日插值
测试地址：The Sum of the k-th Powers题目大意： 求∑i=1nik\sum_{i=1}^ni^k∑i=1nik对109+710^9+7109+7取模的值。做法： 本题需要用到拉格朗日插值。容易看出（或者用数学归纳法简单证明），答案f(n)f(n)f(n)是一个关于nnn的最高次为k+1k+1k+1的多项式。问题是，怎么得到这个多项式呢？这时候就要使用拉格朗日插值法。...
2018-10-19 17:47:15
455
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人