- 博客(100)
- 问答 (3)
- 收藏
- 关注
RSS订阅
原创 【游记】HNOI-2018 铭记惨痛历史 共创美好未来
看过许多dalao的游记，如果dalao们是爆炸记的话，那么蒟蒻的退役记不就相当于核爆记了？作为联赛四道题不同程度翻车的中老年选手，有幸参加这次HNOI，为各位dalao垫一下排名，先Orz众dalao攒攒RpDay-3dalao们开始分享对这次省选的解析预测 蒟蒻在台下：蒟蒻开始刷模板题Day-2上午模拟Day1，日常爆炸，打个暴力还没开longlong，我...
2020-06-04 21:19:35
728
1
原创 【总结】noip数学汇总
noip临近，有点怕需要数学知识定理才能做的题快速幂用途O(logt)O(\log t)O(logt)时间内求解xtx^txt证明&过程由于xa⋅xb=xa+bx^a\cdot x^b=x^{a+b}xa⋅xb=xa+b，而且每个自然数ttt都可以拆分为不超过log2t\log_2tlog2t个二次幂的和，即t=∑i=0ki2it=\sum_{i=0} k_i2^it=∑i...
2018-11-06 11:09:42
1371
原创 【题解】 AtCoder-agc006C Rabbit Exercise
ProblemAtCoder & bzoj题意：数轴上有nnn个点（初始坐标均为整数），编号为111~nnn。给出mmm个操作。每个操作会选定点aaa，然后随机在点a−1a-1a−1和点a+1a+1a+1中选一个，将点aaa以选中的点为中心做对称，将这mmm个操作按顺序执行kkk遍（111~mmm完整执行一次算111遍），求最终每个点的位置的期望值Solution不难发现根据期望...
2018-10-31 21:35:04
191
原创 【题解】HNOI-2018寻宝游戏
Problem洛谷 & bzoj连题面都不贴 & 题面题目概述：给定nnn个长为mmm的01串，qqq次询问，每次给定一个长为mmm的目标串，求有多少种在nnn个串间填“位与”和“位或”符的方法使得最终计算结果为目标串Thought考试时忘记拼接程序了/(ㄒoㄒ)/~~对于10%10%10\%的部分分可以O(q⋅2n)O(q⋅2n)O(q\cdot 2^n)暴力...
2018-06-23 11:03:51
379
原创 【题解】NOIP-2017宝藏
Problem洛谷题目概要： 给定一张无向连通图，求一棵权值最小的有向生成树 权值定义为：从根开始，不断选择联通已选点uuu与未选点vvv的一条边，连边花费为从根到uuu的节点数乘以边的权值，公式表达为∑u∑v≠dad(u)dis(root,u)∗wuv∑u∑v≠dad(u)dis(root,u)∗wuv\sum_u \sum_{v\not = dad(u)}dis(root,u)*w...
2018-06-21 18:34:25
616
原创 【模板】快速读入/读入优化
蒟蒻输入成长史放个板子在这测试了几个输入方法，发现几种输入方法的速度大致为：cin<<scanf<cin(关闭流同步)<read<<freadcin<<scanf&am
2018-06-19 13:38:08
7774
4
原创 【题解】BJOI-2017机动训练
Problembzoj & 洛谷题目大意（题面又臭又长）：给定一个地形图nnn行mmm列，移动类似于国际象棋中的王，但只能往终点移动，求从任意点到任意点的路径中的权值和，路径的权值即为所有路径中相同路径的数量（即求不同路径的数量的平方和）Solution一开始想了一个期望50的暴力加20的找规律，思想始终停在直接统计……正解应该是将平方和转换为两个人走的路径一样的方...
2018-06-16 17:40:13
321
原创 【题解】HNOI-2018毒瘤
Problem洛谷 & pdf题面题目概述：给定一张nnn个点mmm条边的无向图，求独立集数量n≤100000,m−n≤10n≤100000,m−n≤10n\leq 100000,m-n\leq 10Thoughts话说在考场上居然没开long longlong longlong~long，直挂252525分一开始看题面，观察特殊数据，发...
2018-06-13 14:25:41
404
原创 【题解】CodeForces-613D Kingdom and its Cities
话说之前自己都不相信自己能一遍打对，交都没交就傻傻地对拍了，所以文末附赠数据生成器ProblemCodeForces未经润色的题目概要： 给定一棵有nnn个节点的树，qqq次询问，每次询问给kkk个点，求至少删除多少点，使得这kkk个点两两不属于同一联通块（n,q,∑k≤100000n,q,∑k≤100000n,q,\sum k\leq 100000）Solution根据这类...
2018-06-11 22:05:31
272
原创 【题解】HNOI-2014 世界树
Problem洛谷 & bzoj & loj题目概要：给定一棵nnn个节点的树，qqq次询问：给定mmm个关键点，每个原树上的点被最近且序号最小的关键点控制，问每个关键点（n,q,∑m≤300000n,q,∑m≤300000n,q,\sum m\leq 300000）Solution观察数据限制：∑m≤300000∑m≤300000\sum m\leq 3000...
2018-06-11 15:08:13
302
原创 【题解】UOJ207 共价大爷游长沙
Problemuoj题目概要： 给定一棵树，维护四种操作： 1：断开一条边，加入一条边，保证操作后仍是树 2：往集合S中加入一个点对(x,y)(x,y)(x,y) 3：删除集合中一个点对 4：询问一条边，是否集合中所有点对之间的路径都要经过这条边Solution不是很难的一题……想到某校自主招生题：给定序列，其中有一个数字出现一次，其余数字均出现两次，找出这个数（...
2018-06-05 16:33:20
264
原创 【题解】LNOI-2014 LCA 好题
Problem洛谷 & bzoj题目概要（题目不完整，细节看链接）： 给出有根树，设dep[i]dep[i]dep[i]表示点iii的深度，有q次询问，每次询问给出l,r,zl,r,zl,r,z，求∑ri=ldep[lca(i,z)]∑i=lrdep[lca(i,z)]\sum_{i=l}^rdep[lca(i,z)]Thoughts感觉可以从下网上动态加边，并预处理...
2018-06-04 22:30:03
287
原创 【笔记】生成函数/母函数在通项公式上的应用
在看了好多篇博客，翻阅了几本书后，终于对生成函数有了一点点理解，还请各位和我一样刚入门的同学一起静下心来仔细思考，最好在草稿纸上演算一下对于序列{ai}{ai}\{a_i\}，它对应的生成函数为 G(x)=∑i=0+∞aixi=a0+a1x+a2x2+a3x3+…G(x)=∑i=0+∞aixi=a0+a1x+a2x2+a3x3+…G(x)=\sum_{i=0}^{+\infty}a_ix...
2018-05-31 21:12:20
2542
5
原创 【笔记】多项式求逆
Problem对于一个多项式a(x)a(x)a(x)，求其逆元b(x)b(x)b(x)，即a(x)∗b(x)≡1(modxn)a(x)∗b(x)≡1(modxn)a(x)*b(x)\equiv 1\pmod {x^n}Solution对于单个元素的逆元我们是会求的，比如说一个数ttt的逆元在膜质数意义下为tp−2tp−2t^{p-2}但现在要求求一个多项式的逆元，联想到在模数为...
2018-05-29 22:40:06
901
原创 【题解】WC-2011最大XOR和路径
Problembzoj & 洛谷Thought本想像游走那题一样如spfa暴力更新每一个点的线性基，但那样的复杂度十分玄学，个人认为用来骗分还是有点用的Solution考虑到对于一条从1到n的路径一定是由一条从1到n的简单路径加上若干个环组成，所以可以预处理处图中的环（不一定要将所有环处理，因为两个相交的小环异或起来可以替代这两个环合起来的大环），可以用O(n+m)...
2018-05-26 16:42:22
410
原创 【笔记】从递推式得到通项公式的几种方法
数列这玩意在竞赛中考的不少，可以变形一些式子，所以做一个小总结1 ：an+1=an+f(n)an+1=an+f(n)a_{n+1}=a_n+f(n)an=a1+∑n−1i=1f(i)an=a1+∑i=1n−1f(i)a_n=a_1+\sum_{i=1}^{n-1}f(i)2 ：an+1=f(n)·anan+1=f(n)·ana_{n+1}=f(n)·a_nan=a1∏n...
2018-05-23 20:19:24
15545
原创 【题解】HNOI-2011XOR和路径
Problem洛谷 & bzojSolution可能是第一次两分钟想出HNOI的题考虑到直接求解异或和很麻烦（如果dalao能直接做当我没说），套路拆分二进制位，对于每一个二进制位单独考虑，则ans=∑t=2kE(n)∗tans=∑t=2kE(n)∗tans=\sum_{t=2^k}E(n)*t则如果权值只有0和1，则可以使用最基本的高斯消元求解（和HNOI那道游走...
2018-05-20 22:25:26
175
原创 【题解】SDOI-2014重建
Problembzoj & luogu题意：给定图GGG与每条边eieie_i的存在概率pipip_i，求图是一棵生成树TTT的概率PPPSolution看到这道题首先想到了O(n22nlogn)O(n22nlogn)O(n^22^n\log n)的Map+Dp接着想到了MatrixTreeMatrixTreeMatrixTree定理可以套用在这个上面，试了几次后就不...
2018-05-19 11:02:40
179
原创 【题解】HAOI-2012高速公路
Problembzoj & Luogu题意：给定链，每次修改区间上的权值或查询在一段区间上任取两端点的链长期望值Solution根据期望的性质明显得到式子ans=2∑r−1i=l(i−l+1)(r−i)wi(r−l+1)(r−l)ans=2∑i=lr−1(i−l+1)(r−i)wi(r−l+1)(r−l)ans=\frac{2\sum_{i=l}^{r-1}(i-l+1)(...
2018-05-18 22:49:48
252
原创 【题解】bzoj-1415 NOI-2005 聪聪与可可
ProblemLuogu&bzojSolution这题一看就联想起了HNOI游走那道题，仔细一看发现不对发现这题的转移是有终点的，所以可以用Dp，加上题目是一张图，推荐用记忆化搜索显然想到f[i][j]f[i][j]f[i][j]表示当聪聪在点iii可可在点jjj时聪聪抓可可步数的期望，先预处理聪聪在iii可可在jjj时聪聪的选择路径t[i][j]t[i][j]t[...
2018-05-17 22:11:34
185
原创 【游记】CTSC&APIO-2018游记
Day0参加了学校的合唱比赛，唱了《送别》+《毕业歌》+《我相信》。总体的创意还是不错的，感情应该也比较到位。结果在唱《毕业歌》时强调气势，导致越唱越快，合唱比伴奏快了几拍，虽然唱了几句大家发觉后调整回来了，但评委应该是注意到了的，最后只拿了一等奖。从客观角度看，我们时间少，一起仅排练了两次，而且没有音乐课，没有音乐老师指导；但从主观角度看，21班没拿第一就是失败、是耻辱，这次抢调应该是我们的...
2018-05-05 17:48:11
638
原创 【题解】poj-1905 Glass Beads
Problem话说这是一道5倍经验题？(poj,zoj,uva,uvalive,spoj)题意：给定一个环形字符串(len≤104)(len≤104)(len\leq 10^4)，求从哪一位作为起始字符整个字符串的字典序最小Solution这题有多种解法，蒻为了学习便用了后缀自动机这题要求字符串的一种形态下字典序最小，明显可以贪心：提取出字典序最小的字符，再从这些字符的后面...
2018-04-30 16:37:17
185
原创 【题解】bzoj-2653 Middle
Problembzoj&洛谷题意：给定长为n的序列，共q次询问子序列(l,r),l∈[a,b],r∈[c,d](l,r),l∈[a,b],r∈[c,d](l,r),l\in [a,b],r\in [c,d]的中位数最大值，强制在线Solution对于一个序列，定有比中位数大的元素和比中位数小的元素一样多转化成+1与-1，比中位数大的设为+1，小的设为-1，则只要有一...
2018-04-28 18:23:28
217
原创 【实用】同届dalao传送门
同机房的各位，个个都Orz (:зゝ∠) Orz (:зゝ∠) Orz (:зゝ∠) Orz (:зゝ∠) Orz (:зゝ∠) 蒟蒻实况： 在各位面前蒟蒻无地自容高一进队dalao一只–> litble一言不合就AK的dalao一只–>yasar虐人细无声-同桌dalao一只–>Rayment算法全会，正在刷cf的dalao一只–&
2018-04-14 19:21:29
562
原创 【题解】Code+ Apr_18 最短路
Problem良心洛谷想要数据的也可以去Code+上下载题意： 给定nnn个点，求从sss到ttt的最短路径，其中有两种走法（可以混搭）：一种是走给定的mmm有向边(ui,vi,wi)(ui,vi,wi)(u_i,v_i,w_i)；另一种可以由任意点xxx到任意点yyy，其费用是c∗(xc∗(xc*(x xorxorxor y)y)y)数据范围：n≤105,m≤5×105n≤10...
2018-04-13 16:59:34
201
原创 【模板】二维线段树or树状数组(poj-1195)
ProblemPoj题意：给定二维平面，维护单点加与区间求和操作Solution蒟蒻最近开始学数据结构了，发现了二维结构这种神奇的东东这题不过就是二维树状数组或线段树的裸题，发这篇博客不过是为了贴个板子Code二维树状数组#include<cstdio>#include<cstring>using namespace std;#de...
2018-04-12 22:09:30
180
原创 【题解】Codeforces-940F Machine Learning
Problemcf太麻烦就用洛谷题意：给定一个数组，维护两种操作： 1、查询一段区间内的所有数字出现次数的mex 2、修改某点的值Solution像这种有关出现次数的多组区间询问的题目，当然蒟蒻只会用莫队啦很明显带修改莫队，用一个桶t1[x]t1[x]t1[x]维护xxx的出现次数，用另一个桶t2[x]t2[x]t2[x]维护所有数字中∑t1[i]==x∑t1[i]==...
2018-04-11 21:08:48
182
原创 【题解】HNOI-2010 Planar
Problembzoj 洛谷题意：给定一张完全图和图中的一条哈密顿回路，问是否为平面图Solution看到这题中有一条哈密顿回路，如果这个图是平面图，那么这条哈密顿回路在平面上就是一个切割平面的圈明显想到每一条非哈密顿回路上的边不会和这个圈相交，则一定在这个圈的外部或内部发现如果将两条边放在圈的同一侧必定相交，那么就必须把它俩分开（一条在里面一条在外面），那么对每两条...
2018-04-08 22:23:31
188
原创 【题解】code+ Apr_18 白金元首与七彩魔法
Problem洛谷简要题意：给定一个极坐标平面，和两个用极坐标表示的点，还有一个根据极坐标得值的函数，求以这两个点为端点的线段上的函数最大值想要题面和数据可以上code+下载Solution一看到题就感觉是数学题，求函数极值，然而那个函数好像很复杂官方题解是暴力扫描，然而蒟蒻比赛时WA4个点死活改不出来，可能是过程中间出现了nan？然而这题好像可以用爬山，看看这...
2018-04-07 19:07:02
208
原创 【题解】HNOI-2017 礼物
Problembzoj & 洛谷题意： 给定两序列，可以将其中任意一个序列的值同时增加任意值，同时也可以将任意序列旋转（向左右平移），最小化∑ni=1(xi−yi)2∑i=1n(xi−yi)2\sum_{i=1}^n(x_i-y_i)^2Solution这题应该是HNOI-2017最水的一道题了……考虑一个式子增减为CCC，平移jjj格，式子套路拆分（式子中不特别...
2018-04-02 22:36:19
243
原创 【题解】ZJOI-2014 力
Problem点准啦 猜下哪个是bzoj(～￣▽￣)～题意： 给定数列{qi}{qi}\{q_i\}，求数列{Ei}{Ei}\{E_i\}，其中满足关系式： Fj=∑i<jqiqj(i−j)2−∑i>jqiqj(i−j)2Fj=∑i<jqiqj(i−j)2−∑i>jqiqj(i−j)2F_j=\sum_{ij}\frac{q_iq_j}{(i-j)^2} E...
2018-04-01 10:07:10
203
原创 【题解】POI-2014 RAJ-Rally
Problem屠龙宝刀注册即送，只需三fan钟，你就会和我一样爱上介款游戏题意：给定一个DAG，求删掉哪个点后图上最长链最短Solution这道题的脑洞还是有点大的，Orz_Poles想到不能枚举删除每个点后跑拓扑想到可以跑拓扑时枚举删除每个点发现对于每个点，删掉后都等价于把连接这个点的所有边删掉，于是乎枚举删除一个点等价于枚举删除一个点所连的边那这时如何快速求得删...
2018-03-29 20:25:33
290
原创 【题解】POI-2006 MET-Subway
Problem你从没玩过的chuan新版本，黄金屠龙注册即送，一击999级题意：给定一棵树，求II条可相交路径覆盖最多的点有多少Thought题目分析（直接看解法的请往下翻）：这题一眼有点像最小路径覆盖（二分图or网络流），但实际上并不一样，因为全局最优与局部最优可能会有冲突实际上观察这题的数据，推测复杂度O(n)O(n)不难想到选取的II条路径都是从叶子到叶子存在...
2018-03-28 20:47:38
258
原创 【题解】HNOI-2016大数
Problemabandon_bzojSolution不知道为啥，我看到这题就觉得是莫队，所以就没怎多想，就那么做了考虑一个大数p|Ap|Ap|A，那么显然p|A∗10x,x∈Np|A∗10x,x∈Np|A*10^x,x\in N所以可以预处理f[i]f[i]f[i]表示从第iii开始直到末尾所组成的大数modpmodp\bmod p的值，那么对于一个大数a[l…r]a[l...
2018-03-25 21:35:02
152
原创 【题解】HNOI-2016序列
Problemcollapse_bzojSolution这道题在HNOI2016中还算是好的了……这题中如若去掉多组询问的话可以在O(nlogn)O(nlogn)O(n\log n)的时间内得解（并查集），但多组询问必定要优化，发现这种其他结构基本上无法涉足的题目就只能上莫队了（我也不知道为啥想到莫队，可能这就是题感吧）减去O(nn‾√)O(nn)O(n\sqrt n)只剩下...
2018-03-25 21:05:45
298
原创 【题解】HNOI-2016网络
ProblemLet’s_boycott_bzojSolution算是HNOI中比较简单的了……这题一眼就是链剖，发现不能简单地线段树上标记覆盖修改，于是在线段树上的每一个节点上建一个堆，修改时如果修改区间，则直接在代表那个区间的线段树节点上插入即可，在修改时直接修改路径的补集，查询时要收集线段树上从根到那个节点一路上的堆顶值，这题唯一的难度就在代码要在短时间内打对吧（好像20...
2018-03-25 20:44:28
173
空空如也
Linux下CGAL编译不通过
2020-05-08
WSL里安装g++时遇到问题
2019-11-17
Ubuntu16.04下可以ping通baidu，但Firefox打不开任何网页
2019-08-07
TA创建的收藏夹 TA关注的收藏夹
TA关注的人