- 博客(74)
- 收藏
- 关注
RSS订阅原创 2021CSP-S总结
这次依然没有把能拿的分都拿到，这是值得警惕的。考虑到这是自己的最后一个赛季了，内心难免有一些紧张，但总的来说其实也没什么。密码已经忘了，也不知道有什么含义。考场是在我们学校，所以也没有什么新奇的东西，只看到了比赛前老师努力的准备工作。废话不多说，进入正题：由于上一个赛季的惨痛教训，这一次我一开始只看前两题，发现难度都不高，想了想细节就开始码了。代码其实特别短，但由于自己小心谨慎，花了不少的时间，还好码代码的过程是比较顺利的，只是中途自己T2DP有一个式子推错了，不过没多久就迅速找到了正确的解决方案
2021-10-28 21:56:12
1063
原创 2021CSP-S初赛小结
单项选择题T1：自己不知道的常识题，知道的话就是阳间签到题。T5：自己粗心大意弄错的题，没想到还有更优的策略。总的来说这次单项选择题还是比较简单的。阅读程序题T19：自己SB把pi=3.14代入计算，结果最后一位不太对的上就以为错了。T25：不知道为什么自己弄错了时间复杂度。T28：有可能会解密出一个换行符。T31：没有搞清楚.size()和strlen()的区别。T32：自己不懂的电脑常识。这一次阅读程序题的难度比上次简单一些，但由于自己作死过多，扣了大量
2021-09-22 21:36:44
719
原创 组合数详解
定义从nnn个物品中选出mmm个并考虑取出的先后顺序的方案数为AnmA_n^mAnm。从nnn个物品中选出mmm个不考虑先后顺序的方案数为CnmC_n^mCnm，同时也可以表示为(nm)\binom{n}{m}(mn)。其中CnmC_n^mCnm在计数题中出现更为频繁，所以接下来将基本围绕CnmC_n^mCnm展开。如何求？递推式(nm)=(n−1m−1)+(n−1m)\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}(mn)=(m−
2021-08-25 09:53:43
366
原创 2021杭电“MINIEYE杯”(10) 部分题目题解
T2：拼题怪，前一个部分显然需要找一个简单明显的结论为后一个部分作铺垫。经过不懈的手玩不难发现假设当前玩的人数为n(n>1)n(n>1)n(n>1)，当nnn为偶数的时候要么（当前）奇数编号的人全灭，要么偶数编号的人全灭，人数会刚好减少一半。当nnn为奇数是无论如何刚好以两轮为单位不断循环。由于第一轮比较特殊，所以从第二轮开始将人数不断除以二，如果最后变为1那么其FFF值就是0，否则为当前值的两倍。这样后一个部分就很好做了，由于是路径问题所以考虑点分治，由于是二进制上的问题所以可.
2021-08-20 22:04:44
175
原创 2021杭电“MINIEYE杯”(9) 部分题目题解
solutionT1：老套路，想一想把xxx分成二进制，然后就可以在O(logx)O(logx)O(logx)复杂度求出答案。但是这样子做一定操作会超过50次，所以考虑不是二进制，而是某个kkk进制。这样子，我们需要先预处理出[1,k][1,k][1,k]的数——实际上我们只要预处理[1,k/2][1,k/2][1,k/2]和kkk，因为有减法。T4：首先把曼哈顿距离转化成切比雪夫距离，这样xxx轴和yyy轴坐标就独立了。转化成一维问题以后，发现可以再次转化成那个经典的卡特兰数的向上
2021-08-18 16:39:25
158
原创 JOISC2021极简略总结
D2T1似乎可以用spfa/floyd，按管制时间从晚到早的顺序加进去，每次都更新一下。D2T2先二分出第KKK大的值，然后在找出所有距离小于这个值的点对的距离。全程可以用二维偏序解决。D2T3考虑建出笛卡尔树然后在上面分治。直接边分治的话比较暴力，考虑用一下奇技淫巧尽量让A每输出一个字符就让可能性砍半。D3T1考虑保留第一个X，最后一个Z，以及它们中间的“YX”（Y和X一定要粘起来）。接着把没有保留的按从左往右的顺序删除，可以发现“YZ”虽然没有被保留，但是这样删
2021-03-31 09:20:32
508
原创 多项式exp-ln学习小结
前言其实多项式exp/ln好像考的频率不算很高不过总得来说只要多做生成函数计数题的话，多多少少还是会遇到的。ln(x)ln(x)ln(x)的展开式通过泰勒展开，可以得到：−ln(x)=x1+x22+x33+...-ln(x)=\frac{x}{1}+\frac{x^2}{2}+\frac{x^3}{3}+...−ln(x)=1x+2x2+3x3+...ln(x)ln(x)ln(x)的导数ln(x)ln(x)ln(x)有一个特殊的性质，就是如果f(x)=ln(x)f(x
2021-03-29 22:24:06
913
原创 THUPC2020爆炸记
赛前zsjz的一名蒟蒻中学生。也没有什么好说的，和同校的cotton，YYT组了一个摸鱼队伍。刚刚经历二段考，心态爆炸，本来想通过打场信息学比赛来达到转移注意力，放松心态的作用，但结局正如标题所说一般，梅开二度。比赛时先随手切了M题（不会吧不会吧，不会真的有人没有切M题的吧？）接着我们三个人就分工好， 每个人看四道题——虽然没有过多久就打破队形了——没过多久大家就开始做题了。当时我看到A题，哎！这不是水题吗？接着怒敲了40min代码。然后就发现自己看错题意了。这个时候，cotton把F
2020-12-13 10:49:09
581
原创 NOIP2020游记
Day0我们学校又双叒叕是考场。比赛前两天我打篮球的时候手指还受了轻伤，当天晚上打起代码那叫一个爽。之前的模拟赛是越做越崩，信心赛做成了信心消失赛，主要的问题是自己发挥不是很稳定，这次NOIP与以往不同，只有一场，所以不像以往：“别以为你能翻盘，你连盘长什么样都不知道”现在是：“盘都没有，你翻毛翻”Day1 第一篇章一堆人发了”rp++“。“考好这场比赛我就回老家结婚！”怀着复杂的心情，我一边祝福出题人身体安康，一边默默等待比赛的开始。密码：选手加油1205。接下来的4个半小时
2020-12-06 21:54:38
370
1
原创 2020CSP-S爆炸旅程
比赛前总得来说对自己还是挺有信心的，前一个星期的模拟赛做得都不错，不过有点鬼畜的是最后几场比赛不知道为什么越打越烂，希望这种趋势不会延续到比赛。考虑到题目应该会偏简单，所以应该认真细心一点，不要犯一些低级错误。最后几个小时也没干什么别的事情，就改了一下之前模拟赛没有AC的题目，老师还组织我们开了个小会，让我们分享一些比赛技巧和常犯的错误。中午和晚上都睡了个好觉，感觉一切都在往好的方向发展。比赛时我们学校（zsjz）是比赛的场地之一，老师都鼓励我们说有主场优势，但其实在这种情况下往往会放松心
2020-11-11 21:22:28
251
2
原创 2020CSP-S初赛小结
个别题目分析单项选择题第2题：看哪个选项更高大上就选哪个。第14题：带堆优化的Dij时间复杂度是O(m∗logn)O(m*logn)O(m∗logn)，而没有任何优化的Dij时间复杂度应该是O(m+n2)O(m+n^2)O(m+n2)的，因为在简单图中mmm的复杂度级别没有n2n^2n2高，所以就是O(n2)O(n^2)O(n2)的。第15题：只要你不知道这个东西是谁发现的，就说是欧拉发现的。 这一道题好像在之前考过。A显然不对，剩下的选项会的就都会，不会的只能蒙一个了。总结：这一次的单项选择题
2020-10-14 21:59:37
2141
3
原创 6821. 【2020.10.08提高组模拟】winner(xxx)
题目描述有关图的连通性统计问题这一类题目之前一直是我的天敌。见一次爆一次（也不知道为什么）。考虑设一个DPf[i]f[i]f[i]表示含iii个点的连通块的方案数。直接算的话比较麻烦，我们可以拿总方案数减去不是连通块的方案数。我们枚举第iii个点所在的连通块的大小k(1<=k<i)k(1<=k<i)k(1<=k<i)。很明显我们要从前i−1i-1i−1个点中选出k−1k-1k−1个点，即(k−1i−1)(^{i-1}_{k-1})(k−1i−1)，这个连
2020-10-11 14:54:04
95
原创 2020/2021省选作业题目反思
废话不要这么多T2 cf674G(2020.9.5)这一道题是之前在OJ上做过的原题。主要的问题就是思维很容易陷在如何求区间众数上面，其实这道题要求的是绝对众数，并且p>=20p>=20p>=20是一个很关键的突破口。考虑⌊100p⌋<=1\left \lfloor {\frac{100}{p}} \right \rfloor<=1⌊p100⌋<=1的情况，剩下的同理。发现可以在线段树上面维护一个答案和附带的权值，合并的时候假如答案相同就将权值相加，如.
2020-09-22 21:21:32
267
原创 ISIJ被虐记
一如既往地线上比赛。教室前后架了两个摄像头，用来监考。可以光明正大地逃课了。Day1&2没什么特别安排，就参加了学校的模拟考试。没刷题感觉没有进入状态啊……总得来说还是有一点紧张的，因为不知道难度，自己又菜，感觉可能会做崩。Day3第一场训练赛。早上还在教室上课，草草睡了个午觉，就赶紧去机房做比赛。打开题目一看，有三道题，前两道很水，感觉自己能AK了，心态稳健地打了前两题的代码。结果第三题想了半天硬是想不出来，打了两次代码都发现自己的方法是假的，最后苟了个72分。一看S.
2020-07-03 21:33:50
584
原创 GDOI2020摸鱼记
DAY0快要中考了，班主任一刻也不肯放松。都省选前一天了还在教室里做作业，感觉就好像没有省选一样。已经预感到今年的GDOI要摸鱼了……今年在我们学校考，也比较好，不会腐败得太欢，也正好收拾一下心情。不过不知为什么也没有什么紧张的感觉，可能太菜了已经知道自己会考炸了。DAY1直接弃掉早读来机房准备。复习了一下一些常见的高难度算法，借此抱一抱佛脚，不要被打个措手不及。旁边还有一个在玩手机的，这就是巨犇吗？搞得还挺正式的，仔细检查有没有带违规电子产品，和以前一样。果然在疫情之间也不能放松啊
2020-06-22 21:11:23
492
原创 （易懂）浅谈2-SAT
啥是2-SAT？SAT的定义：百度百科，布尔可满足性问题。但百度百科上面的解释又臭又长，比较专业，难以看懂。实际上，2-SAT是SAT的一个特殊化的版本，这里有一个通俗化的解释：有多个布尔元素（只能为truetruetrue或falsefalsefalse），给出多个条件，每个条件形如(not)x opt (not)y=true/false(not) x\ opt\...
2020-01-08 21:25:19
2144
原创 家喻户晓的数学小技巧——欧几里得算法
背景1给定两个数xxx与yyy。求出这两个数的最大公因数。暴力1直接从1到min(x,y)min(x,y)min(x,y)枚举，找出最大的能分别整除它们两个的数即可。时间复杂度：O(min(x,y))O(min(x,y))O(min(x,y))。暴力2求出xxx的所有约数，再求出yyy的所有约数。从中查找出公共的数，在所有公共的数中找出最大值即可。时间复杂度O(max(...
2019-12-07 17:07:48
300
原创 CSP-S2 Emiya 家今天的饭
题目描述题目分析这一道题本身算法并不难，但思考难度也不低。“烹饪方法互不相同”这个条件用DP可以很好解决，关键是每一个食材出现次数不超过k2\frac{k}{2}2k，接下来我们所说的不合法均指不满足该条件。本题最关键的一点便是——容斥。考虑先求出总的方案数，再减去不合法的方案数。总数求法很简单，那么如何求不合法的方案数呢？我们考虑先枚举超出限制的食材。因为超限的食材会出现超过k...
2019-11-30 11:06:42
327
原创 CSP-S2 括号树
题目分析题目分析这一道题我一开始看觉得应该是DP。对于点i的答案，显然是它的父亲的答案加上以它为结尾的合法括号串的个数。如何求以i为结尾的合法括号串的个数呢？我们设f[i][j]f[i][j]f[i][j]代表的是以iii点为结尾，目前有jjj个左括号没有配对的方案数。显然如果iii是左括号...
2019-11-30 10:43:21
371
原创 CSP-J2 纪念品
题目描述题目分析对于T=2T=2T=2，显然我们可以设一个DP：f[i]f[i]f[i]表示第一天买卖前你有iii元，第二天买卖后最多可以有多少钱。状态转移也是比较显然的：f[i]=max(i,f[i−a[k][1]]+a[k][2])f[i]=max(i,f[i-a[k][1]]+a[k][2])f[i]=max(i,f[i−a[k][1]]+a[k][2])其中kkk表示的是纪念品...
2019-11-22 18:42:38
453
原创 CSP-J2 加工零件
题目描述题目分析假设存在一种路径，从iii点出发走kkk步走到1号点，那么显然若1号点有出边的话，肯定也存在一种路径，从iii点出发走k+2k+2k+2步走到1号点。证明：1号点随便选一个出边走出去，再走回来，就可以了（显然）。前提的处理非常简单，直接输出NO即可。但也非常坑人，我在考场的时候就没有想到有这种情况。处理完特殊情况后，我们就可以运用上面的性质了。对于一个点iii，如果...
2019-11-21 18:35:56
789
原创 CSP-J/S游记
DAY -27CSP的第一轮认证以为跟以往NOIP的初赛难度差不多，就做了一下以往的题目，感觉海星。但在不久之前得知题型改了，只有选择题和判断题，觉得题目难度应该降低了，兴奋至极。然后..................上午先是提高级。嗯？毒瘤的电脑系统题全都没了？只剩下一些常识题和鬼畜计算题？爽哉！在草稿纸上计算了一下计数题，很快就把第一大题怼完了。阅读程序：？？？没有阅读程序...
2019-11-19 18:58:39
587
2
原创 判断素数的方法(Miller_Rabin)
序言willson定理：https://blog.csdn.net/fengqiyuka/article/details/100007632普通篇：https://blog.csdn.net/fengqiyuka/article/details/99963246背景“还有没有判断素数的方法？”“当然有，那就是Miller_Rabin！”这个算法能做到O(logn)O(logn)O...
2019-11-09 16:59:32
247
原创 判断素数的方法(Wilson定理与应用)
序言普通判断素数的方法：https://blog.csdn.net/fengqiyuka/article/details/99963246。但你以为判断一个素数只能用O(n)O(\sqrt n)O(n)的时间复杂度吗？错错错！在这一篇文章，我就要提到一个十分神奇的定理，Wilson定理。Wilson定理p为质数⇔(p−1)!≡−1(mod &Th...
2019-08-22 10:09:08
915
原创 判断素数的方法（普通篇）
不知名的东西：[1,n][1,n][1,n]中的素数大约有nlnn\frac{n}{\ln n}lnnn个。背景没有背景。素数是数学中一种十分重要的数字，它的重要性使得它在信息学领域中也有广泛的应用。其中有一种很常见的题目就是：“给你一个数iii，判断其是否是素数。”暴力方法一从素数的定义入手。一个数iii为素数当且仅当iii的因数只有111和iii。因此我们可以从...
2019-08-21 16:19:31
295
原创 3397. 【GDOI2014模拟】雨天的尾巴
题目描述深绘里一直很讨厌雨天。灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮食被弄得一片狼藉。无奈的深绘里和村民们只好等待救济粮来维生。不过救济粮的发放方式很特别。首先村落里的一共有n 座房屋，并形成一个树状结构。然后救济粮分m 次发放，每次选择两个房屋(x,y...
2019-07-12 21:02:53
173
原创 3362. 【NOI2013模拟】数数
题目描述神犇最近闲来无事，于是就思考哲学，研究数字之美。在神犇看来，如果一个数的各位能够被分成两个集合，而且这两个集合里的数的和相等，那么这个数就是优美的（具体原因就只有神犇才知道了）。现在神犇在思考另一个问题，在区间[A,B]中有多少个数是优美的？这个问题对于神犇来说很简单，相信对于你来说也不难。数据范围A,B≤109A,B \le 10^9A,B≤109题目分析这道题又是一个大...
2019-07-12 20:47:46
246
1
原创 3360. 【NOI2013模拟】苹果树
题目描述神犇家门口种了一棵苹果树。苹果树作为一棵树，当然是呈树状结构，每根树枝连接两个苹果，每个苹果都可以沿着一条由树枝构成的路径连到树根，而且这样的路径只存在一条。由于这棵苹果树是神犇种的，所以苹果都发生了变异，变成了各种各样的颜色。我们用一个1到N之间的正整数来表示一种颜色。树上一共有N个苹果。每个苹果都被编了号码，号码为一个1到N之间的正整数。我们用0代表树根。只会有一个苹果直接连到树...
2019-07-12 20:34:08
245
1
原创 JZOJ3224.阴阳
题目描述Farmer John 正在在计划自己的农场漫步。他的农场的结构就像一棵树：农场有N个谷仓（1<= N <=100,000），分别由N-1条路链接。这样，他便可以通过这些谷仓间的道路遍及各个谷仓。Farmer John想要选择一条路线：这条路线的起点和终点分别为农场中两个不同的谷仓，这条路线不能重复经过一条边两次。Farmer John担心这条路径可能会偏长，所以他想在路...
2019-07-12 20:15:40
152
1
原创 JZOJ3233.照片
题目描述Farmer John决定为他的N头排列好的奶牛（1 <= N<= 200,000）做一张全景合照。这N头奶牛分别以1…N进行编号。他一共拍了M（1<= M <=100,000）张相片，每张相片都只包含有一部分位置连续的奶牛：第i张照片涵盖着编号从a_i到b_i的所有奶牛。当然，这些照片合起来并不保证包含所有的牛。Farmer John拍摄完所有的相片后...
2019-07-12 20:06:06
181
原创 后缀数组（下——height与h）
背景没有背景我们发现，如果只有SA与rank，真是出了求排名什么也做不了。哈哈哈，其实SA与rank只是铺垫，后缀数组最厉害的地方就要展现——最长公共前缀先来一个最简单的问题：给定一个字符串，求出现最少2次的字符串长度。...
2019-07-10 21:08:59
474
4
原创 4613. 【NOIP2016模拟7.12】求和
题目描述n<=105n<=10^5n<=105题目分析我们惊喜地发现这竟然是一道数论题。第二类斯特林数定义S(n,m)S(n,m)S(n,m)：首先关于第二类斯特林数有一个特别重要的公式。S(i,j)=1j!∗∑k=1j(−1)k∗Cjk∗(j−k)iS(i,j)=\frac{1}{j!}*\sum_{k=1}^{j}(-1)^k*C_j^k*(j...
2019-07-03 20:21:37
111
49
原创 4769. graph
题目描述对于一个图， 如果它的点集能被分成两个部分， 使得在原图中每一部分之间的点没有任何边相连，则该图被称为二分图。现在给定一个无向图，每次增加一条边，或者删除一条边。要求您每次判断它是不是二分图。数据范围暴力对于前30分，我们显然可以直接暴力。如果是插入操作就直接把边加进去，然后判断一下它是否会组成奇环，如果是的话就直接输出“NO”，然后看其中的换最早删去的边，很显然至少要...
2019-03-18 21:11:36
155
1
原创 4240. 【五校联考5day2】游行
题目描述（简化）给定参数ai,li,ria_i,l_i,r_iai,li,ri。然后有一个有向图，对于两个点i,ji,ji,j，如果满足i&amp;amp;amp;amp;lt;j且l[i]≤a[j]≤r[i]i&amp;amp;amp;amp;lt;j且l[i] \le a[j] \le r[i]i&amp;amp;amp;lt;j且l[i]≤a[j]≤r[i]，那么就存在一条边(i,j)(i,j)(i,j)，否则不存在。对于每一个点i
2019-01-29 21:32:36
119
1
原创 PKUWC2019酱油记
PKUWC=Peking University Winter Camp（北京大学全国优秀中学生信息学冬季体验营）-71~-70dayCCF NOIP2018比赛开始了！刚进提高组的我，结果两天全挂，总分才374分。看来进冬令营是没辙的了。-60~-40day什么？初中分数线是470分？自闭了。-10~-1day突然间老师对我们说——这次北大冬令营在中山纪念中学举行！...
2019-01-23 21:48:37
318
原创 数学黑科技2——NTT
引入在你学NTT之前，你最好学一下FFT。https://blog.csdn.net/fengqiyuka/article/details/86553689看完此博客（如果我太蒟写得太烂可以看其它博客）再来看NTT。因为FFT与NTT的主要中心思想是一样的。NTT就当你们已经懂了FFT了。本来点值与插值需要O(n2)O(n^2)O(n2)才能解决，为什么能用O(nlog2n)O...
2019-01-22 20:52:48
700
原创 数学黑科技1——FFT
用途让我们看一下下面这一个问题：对于A(x)=a0+a1x+a2x2+...+an−1xn−1A(x)=a_0+a_1x+a_2x^2+...+a_{n-1}x^{n-1}A(x)=a0+a1x+a2x2+...+an−1xn−1,B(x)=b0+b1x+b2x2+...+bm−1xm−1B(x)=b_0+b_1x+b_2x^2+...+b_{m-1}x^{m-1}B(x)=b0+...
2019-01-19 20:35:17
547
原创 100048. 【NOIP2017提高A组模拟7.14】紧急撤离
题目描述某日， 敌军对某村落展开攻击，所幸我情报部门提前预知了消息，村民兵武装连夜组织村民快速转移，为此他们需要赶往地道入口。已知村庄形成了 N * M 的方格网络，周围被封锁，无法穿行。其中有些方格没有敌军占领，可以进入，有些方格已经被敌军渗透，不能进入。由于敌军的步步紧逼，民众只能向行或列增大的地方移动：即(x, y) → (x + 1, y)或(x, y) → (x, y + 1)。 机智...
2018-12-21 21:11:27
183
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人