- 博客(110)
- 收藏
- 关注
RSS订阅
原创 莫比乌斯函数/反演&&杜教筛 小结
1）莫比乌斯函数/反演 PPT https://wenku.baidu.com/view/fbec9c63ba1aa8114431d9ac.html bzoj 2440 https://www.lydsy.com/JudgeOnline/showsource.php?id=2721111 莫比乌斯函数基础应用（容斥） bzoj 2301 https://www.lyd...
2018-04-25 23:08:09
325
原创 血的教训
变量名尽量取好一点，不要与头文件里重合，比如 time。 NOIP2017 D1T2 CE -100 读题读5 遍！！！ NOIP2017 D2T1 WA -100（实际得分90……） 线性筛记得判爆掉！！！i*p[j]<=mx FFT 复数不要写错，定义减法时写错调了一晚上……树剖 单点修改是change（pos【x】，y） 记得加pos！！！ 看清过...
2017-11-16 11:18:48
275
原创 Atcoder 刷题（划水）记录
http://agc016.contest.atcoder.jp/tasks/agc016_b 题意：有N只猫，每只猫带着某种颜色的帽子，给出每只猫能看到（即其他N-1只猫）的颜色种数a【i】，问是否可以构造出合法序列。题解：本蒟蒻想了挺久的，显然a【i】的顺序没有什么卵用，排个序。会有一个显然的结论： 当max-min>1时直接输出No。max==min 则N==a[1]+1或N>=a
2017-10-23 21:12:01
1314
原创 清单
卷积FFT FWT http://picks.logdown.com/posts/179290-fast-walsh-hadamard-transform线性基 https://blog.sengxian.com/algorithms/linear-basis分块树链剖分
2017-09-24 12:19:44
286
原创 常用
求各种类型的最大值： 头文件：limits numericnumeric_limits<int>::()maxlimits<int>::()max=231−12^{31}-1英文 due to 因为 issue 问题 inclusion-exclusion principle 容斥原理 从歪果仁get到的神奇玩意： btw== By the way iff== if and
2017-08-29 21:22:49
294
原创 各类模板
头文件、define 线性筛 树链剖分 莫比乌斯函数/反演&&杜教筛 FFT 后缀数组 log2log2log^2版 后缀数组 logloglog版快速幂：LL qsm(LL a,LL b){ LL tmp=1; while (b) { if (b&1) tmp=tmp*a%mod; a=a*a%...
2017-07-19 21:21:53
483
原创 CF吐槽贴
连续三场unrated……分数稳如狗…… 常用： due to 因为 issue 问题 inclusion-exclusion principle 容斥原理 从歪果仁get到的神奇玩意： btw== By the way iff== if and only if
2017-06-29 10:05:47
413
原创 Samara Farewell Contest 2020 (XXI Open Cup, GP of Samara) 部分题解
B给出N 组 x1 y1 x2 y2，每组选一对x y使得∑x∑y\frac{ \sum x}{\sum y}∑y∑x最大二分答案然后选更大的即可C给定一幅 n × m 的地图，地图由“.”和“#”构成，“.”表示空地，“#”表示障碍。求这个地图沿垂直和水平方向分别 shift 多少，能使空地形成一个连通块。求出所有可能的 shift 方案。枚举上下shift的步数，左右只需维护一个前后缀的并查集即可详见https://blog.csdn.net/rzO_KQP_Orz/article/d
2021-02-19 23:37:26
1114
原创 Northern Eurasia Finals Online 2020 部分 题解
https://codeforces.com/group/wmhDiB5PTN/contest/313189A定义“Almost Balance Tree” 为一颗二叉树，满足左右儿子的重量差不超过1,给出A个1 B个2要求构造出合法的二叉树，无解输出-1显然有，在2的数量一定的前提下，1越多就越有可能可以得到合法的树。我们可以先算出在总和S=A+B*2的前提下，最少需要多少个1那么令f[S]表示S最少需要的1个数，考虑根为1、2进行转移1：1+f【up(s-1)】+f【down(s-1)
2021-02-15 15:55:57
947
原创 暑期划水小结
【7.14】【7.15】【7.16】 【7.14】T1 给出汉诺塔中间结果的某一步，求是否合法，如合法输出还有多少步完成。 T2 【7.15】T2 等价于求位置i左边位置k满足【k，i】是回文串的k之和，建出回文自动机后，每个节点计算出fail树内长度和，以及子树深度，直接算即可。T3 鬼畜的网络流，最大权闭合子图，S向正权点连边，...
2018-07-18 16:13:40
437
原创 CDQ分治&&整体二分
CDQ分治本质就是分两半，分别计算两边区间的贡献，然后再考虑跨区间的贡献。 具体教程网上一搜一大把…… 题单： 51nod 1376 ：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1376 考虑用 f【i】记录以i结尾的最长上升子序列的长度&&个数，然后每次切两半，先计算【l，mid】的答案，...
2018-07-01 18:34:46
205
原创 Wannafly挑战赛18 E-极差
题面：https://www.nowcoder.com/acm/contest/129/E 把要求的式子展开，转化为求三个序列对应区间内最大值乘积。 然后这显然可以分治~~~ 写的时候注意一边取开区间，后面判的时候就是闭区间了！！！ 代码：//include <bits/stdc++.h>#include <cstdio>#include <algor...
2018-07-01 17:22:58
315
原创 牛客练习赛21 D
将满足题意的（i,j）,(p,q)预处理出来，然后向质因子连边跑网络流即可。 被坑了一下午，这样写常数巨大。改成define就过了…… 题面：https://www.nowcoder.com/acm/contest/130/D 代码：//include <bits/stdc++.h>#pragma GCC optimize(2)#include <cstdio&...
2018-07-01 17:18:49
222
原创 笛卡尔树
具体介绍可以参见这篇Blog https://www.cnblogs.com/pushing-my-way/archive/2012/08/24/2653709.html相关题目： bzoj2616 题解：将图形从下至上划分为若干个矩形，呈现一个树形的结构。然后问题就转化为树上的DP了~ 详细参见：https://blog.csdn.net/qq_39972971/article/de...
2018-06-24 18:27:24
388
原创 BSGS&&扩展BSGS
BSGS算法用于解决已知 a，b，P的情况下，（a、P互质） 求最小的非负整数x满足ax≡b（mod P)ax≡b（mod P)a^x≡b（mod P) 具体操作百度一大把，这里简略说一下，就是令m=P−−√P\sqrt{P} 设x=i*m+j,枚举i然后左右同乘yi∗myi∗my^{i*m}的逆元，转化为求aj≡z′（mod P）aj≡z′（mod P）a^j≡z'（mod P）是否...
2018-06-03 12:17:43
491
原创 【GFOJ】2018省选训练12 & 多校联测
开始了刷题…… T1 题面：给出长度为 m的上升序列A, 请你求出有多少种1……n的排列, 满足A是它的一个LIS. (1<=m<=n<=15) 一开始想到过状压求LIS过程中的单调栈，然而没往下想，去手玩推式子了……然而没推出来…… 题解：【状压+3进制】 设F【S，S0】，S，S0为n位二进制，S表示当前已经加了哪些元素，S0表示当前单调栈中的元素，那么枚举最后一个加...
2018-05-19 16:45:27
286
原创 Prufer序列
详见M大神的Blog http://www.matrix67.com/blog/archives/682 主要记住这个公式： 每个点的度数为Di时树的个数 (n−2)![(D1−1)!(D2−1)!..(Dn−1)!]\frac{(n-2)!} { [ (D1-1)!(D2-1)!..(Dn-1)! ]} 如果一些点没有限制，...
2018-05-06 00:18:08
299
原创 GDOI2018酱油记
Day0 上午看了看板子，本来说的是一点半出发，结果司机两点半才来，打了一中午的sgs…… 下午到了后就是发考试大礼包（内含考生证、GDOI2018衣服、讲义等），然后吃饭，爽快战斗…… 12点前就睡了……Day1 T1 有点水啊，认真算了好几遍复杂度，发现没太大问题后就上了。期望：100 T2 这一定是贪心！！！然而想了很久都...
2018-05-04 22:47:51
198
原创 第二类斯特林数
这里有比较详细的总结 https://blog.csdn.net/OwenOwl/article/details/79442341 主要就是知道斯特林数的两种表达方法， 一个是组合递推，S(i, j) = j ∗ S(i − 1, j) + S(i − 1, j − 1) 一个是容斥通项, 。 还有这个重要结论 证明的话，左边相当于n个球随便放到x个盒的方案数，右边相当于枚举放了k个
2018-05-04 22:13:56
1353
原创 FWT
https://blog.csdn.net/CHHNZ/article/details/75529574 个人觉得这篇Blog讲的挺好的…… 相当于求位运算的卷积，也就是本来多项式乘法xi∗xjx^i*x^j应该向i+j贡献的，这里变成向iXjiXj贡献，X是某个位运算符，可以是&、|、^ bzoj 4589 把指数为质数的项赋为1，其他均为0，用FWT做一遍，求N次方再做一次逆操作即可。
2018-05-03 18:53:15
490
原创 线段树优化建图
由于GDOI2018day3T1考了这个知识点，然而我不会QAQ……所以补一下…… 主要思想就是假如有n个点向长度为M的区间连边，直接连的话边数是N*M的，然而可以开一个虚拟节点X，n个点向X连边，X再向区间连边，区间可以用线段树来优化~~~洛谷 https://www.luogu.org/problemnew/show/P3588 新开一个X，K个点向X连边，X再向K个点切成的K个区间连边。H
2018-05-03 12:46:31
1026
原创 后缀数组 炒鸡好写版
运用STL自带的sort排序，双关键字压成一个long long，常数很小的Nlog2NNlog^2N//#include <bits/stdc++.h>#include <cstdio>#include <algorithm>#include <iostream>#include <cstring>#include <limits>#include <map>#include <ve
2018-04-28 08:19:33
146
原创 FFT模板
用了个小优化，卷积时把实部虚部初值赋为两个要卷的多项式，最后得到答案虚部/2即为所求。//#include <bits/stdc++.h>#include <cmath>#include <cstdio>#include <algorithm>#include <iostream>#include <cstring>#include <limits>#include <map>#in
2018-04-28 08:10:35
158
原创 2018省选训练29 A
http://www.gdfzoj.com/oj/contest/375/problems/1 线段树妙题，题意是给定一个数列，操作有区间与/或一个值，和查询区间最大值。 维护一个same表示，区间内的数哪些位是全部相同的，以及bit，表示相同的是什么，修改操作本质是将一个区间某些位强制赋为1/0，如果修改的位是当前区间same的子集，直接用一些奇奇gaygay的位运算，最后发现，相当于区间加
2018-04-26 07:49:54
216
原创 【题解】【CF958】Helvetic Coding Contest 2018 online mirror (teams allowed, unrated)
比赛时由于手速太慢，水的一批…… 赛后改了一波题…… A1 给定两个10*10的矩阵，问是否可以通过上下、左右对称以及旋转的方式重合。 直接爆搜即可 A2 字符串HashB1 求叶子节点 B2 在树上选K个点，求对于K（1~N）个点之间的简单路径上的点数最大值。 1特判，2直径，其他考虑贪心，从直径的一端开始搜，剖一下重链，每次取最长即可。C1水题略 C2 N个数切成K段，定...
2018-04-20 23:14:00
399
原创 ARC095 题解
T1 ：对于N个数，求出除了第i个数（1<=i<=n）之外的所有数的平均数，直接排序分类讨论即可。T2 ：对于N个数，求任意两数的组合数的最大值，首先最大数肯定要取，然后扫一遍取最接近一半的即可，比赛时忘记考虑可以从小的一边接近一半，WA了3发才发现……T3 ：对于一个N*M（1<=N,M<=12）的字符矩阵，可以交换任意两行，任意两列，问能否最后得到一个矩阵关于两...
2018-04-15 11:45:14
265
原创 树链剖分模板 1036: [ZJOI2008]树的统计Count
#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#define inf 0x7fffffff#define N 30005 #define M 60005using namespace std;int n,q,cnt,sz;int v[N],de...
2018-03-31 08:43:41
181
原创 【ARC090 F】Strange Nim（SG函数）
题面： A 和 B 在玩取石子游戏，他们轮流操作，每次选择其中一堆石子，取走一部分 有 n 堆石子，每堆一开始有 Ai 个 每堆石子在不同时刻能取的石头个数是不一样的 具体来说，当第 i 堆石子有 x 个的时候，最多在这堆石子中取走 ⌊xKi⌋⌊xKi⌋⌊\frac{x}{Ki}⌋ 个， 最少取走一个 1<=n<=200 1 <= Ai, Ki <= 1e9...
2018-03-30 10:03:34
369
原创 Codeforces Round #472(Div 2)
这场打得十分之烂，赛场上只PP了AB，而且最后还FST了一题捂脸……愉快掉分QAQ。。。 A题一开始我码了个搜索，结果忘记特判QAQ…… B题码完后交了一发，然而由于比赛时提交太多CF挂掉，在很久之后我才知道WA了，于是又改了一下才过。 接着窝便去刚C题，由于没看清题目有个Ek−EI<=UE_k-E_I<=U的限制，给的式子窝看到j=i+1后就直接上了，求Ek−Ei+1Ek−Ei\frac{E
2018-03-27 19:41:09
151
原创 bzoj十一月份月赛 Problem A: 组题
题意：对于一个长度为n的数列，求一个长度>=k的子段，是的平均值最大。首先我想到的是对于i，相当于在1~i-k中找一个最大斜率。于是维护一个斜率的单调栈即可。然后查找时二分一下即可。不过这样写起来挺cd的，本蒟蒻码了1.8K，于是还跳了不少时间，最后WA了一发，全开longlong后A了…… 代码： http://paste.ubuntu.com/26139760/ 然而二分答案更好写(zzk
2017-12-08 22:39:21
321
原创 Problem 1049: Lost My Music【可持久化栈+倍增】
首先要求的式子是一个斜率的相反数，其实就是求斜率的最大值，那么我们只需维护一个下凸包即可， 考虑到直接用栈来存，如果是在一条链上的话可以保证每个数只会被插入弹出一次，直接做，暴力退栈就行了。 然而在树上暴力退的话会被卡成O（N2N^2）…… 所以对于每个点存一个倍增数组，记录其在凸壳里的祖先，然后乱搞即可…… 代码：//#include <bits/stdc++.h>#include <c
2017-11-30 11:25:37
439
原创 NOIP2017 酱油记
D0 到了酒店，看了会片&&肝sgs D1 T1看到题直接打表找规律。打完表从前几项找到了规律，然而发现后面的不符合规律，检查了一下，发现是打表写错了……背包时越界没有判，改了后结论就没问题了。 T2一看题，这不是zz模拟嘛……考虑各种奇奇gaygay的情况后，打了1h+，一测大样例，GG。又调了30min+。 然后看了看T3，想到DP状态。然而不会写Q
2017-11-16 10:59:30
335
原创 NOIP2017多校联测&提高组模拟26-A
T1 概率DP，随便做。 T2 比赛时看错题，以为起重机可以叠加来搬货物，然而并不可以QAQ。于是写了个30的zz状压，发现居然还有分…… 正解是贪心or网络流直接上。我还是太菜了QAQT3 首先发现对于叶子节点，它和相邻点形成一个团。找到一个叶子节点后，找到其父亲作为根，判断的方法是看该‘父亲’和孙子节点是否有交，没有则不合法。找到根后dfs即可。
2017-11-10 07:17:32
269
原创 NOIP2017多校联测&提高组模拟25-A
T1 写写画画可以发现其实原式相当于a*b……至于证明，相当于从原点向1~n，1~m的矩阵，画一堆直线，然后gcd==1的表示直线第一个点，min【ni,mj\frac{n}{i},\frac{m}{j}】则表示穿过的点数。所以相当于遍历了整个矩阵。T2 在dfs序上DP，相当于对于一个个区间，要么选左端点，要么选右边区间的值，搜一遍即可。T3貌似是DP加单调队列优化。
2017-11-10 07:06:10
249
原创 NOIP2017多校联测&提高组模拟24-A
T1 ：随便坐 T2：重点是求出三元环，O（N364\frac{N^3}{64}） T3：BFS，建图时注意一下，对于每个权值挂个链表，每次枚举子集后打标记。
2017-11-07 16:04:25
298
原创 NOIP2017多校联测&提高组模拟23--A组
T1 题意:题解：筛出1e6以内的质数，再用枚举每个质数i，把【l，r】间的i的倍数都除掉i， 时间为O（n2+n3+...\frac{n}{2}+\frac{n}{3}+...）~O(NlogN) (N为区间长度） 代码：http://paste.ubuntu.com/25906707/T2 、 题意：对于四个点组成的环，起点重点均为2，给定下限K，要求路径至少为K且最小 题解：对于
2017-11-07 15:47:21
339
原创 NOIP2017提高组模拟22-雅礼国庆10.5
T1 题意:有m（<=1e4）层边,每层有k(<=10)个点，第一层只有一个点S，最后一层只有一个点T。然后整个图是一个DAG，可以一次取反相邻两层的边，问有多少种方案使得最后的S到T的路径数为偶数，有模数。题解：用f【i】【j】表示做到第i层，路径数的奇偶性情况为j，如果是偶数为0，奇数为1。最后把状态中1 的个数为偶数的累加即可。 代码：http://paste.ubuntu.com/258
2017-11-03 20:39:11
436
原创 NOIP2017多校联测&提高组模拟21 11.3
T1 旋转坐标系就变成了一堆矩形，然后乱搞即可 然而比赛时我没有旋转直接上，刚了2h+，3K+的代码QAQ http://paste.ubuntu.com/25877178/ T2 相当于把坑反向移动，然后就只用维护四个方向的并查集即可。 http://paste.ubuntu.com/25877184/ T3 60分的做法有两种， 一种是 mask 表示已经报出哪些熟人的名字
2017-11-03 11:28:45
274
原创 NOIP2017提高组模拟19 /10.31
A 设编号从0开始，首先 有f【i】=（f【i-1】+m）%i 相当于 把第m%n-1个人踢掉，令K=m%n。等价于子问题在n-1个人最后活下来的人f【i-1】， 得到 f【i】=（f【i-1】+m）%i。 然后观察可以发现 i比较大时，f按照等差数列递增，因此可以一次直接跳过一大段。 O（能过）B 所求式子相当于 (xi∗yj−xj∗yi)2=∑rlx2i∗
2017-10-31 19:28:48
266
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人