- 博客(111)
- 问答 (1)
- 收藏
- 关注
RSS订阅
原创 [luogu4027] [NOI2007]货币兑换
前言回光返照题目相关link题解考虑从最后一天倒推可以计算出某一天的钱的得利率，A券价值（最终相当于多少钱），B券价值（同上）
2020-01-18 14:48:39
277
原创 [uoj24]缩紧优化
前言写写题题目相关link题目大意给你nnn个正整数aia_iaif(x)=∑i=1n(ai%x+ai/x)f(x)=\sum_{i=1}^{n}(a_i\%x+a_i/x)f(x)=i=1∑n(ai%x+ai/x)xxx为正整数，求最小的f(x)f(x)f(x)数据范围n≤106,ai≤106n\le10^6,a_i\le10^6n≤106,ai≤106题解开个桶...
2019-12-06 21:24:12
271
原创 CSP-2019总结
前言CSP（不是NOIP）在一周前结束了，对于这次CSP，感慨万分，也写下这篇总结意义这次CSP既是我第一次参加CSP也是最后一次能从CSP中获得实际效益（明年还有一次娱乐场），对于CSP一试就感受到题型的不同（侧重真正的OI了很多），不过还好一试考了90+，过考试还是没有问题的，然后二试于我而言如果发挥失误很大也就意味着与4年多来学的OI告别，所以在考试中还是挺小心的正文day1da...
2019-11-22 21:16:36
856
原创 [luogu2042] [NOI2005]维护数列
前言写写比较麻烦的这题题目相关题目大意写一个大数据结构数据范围20000题目链接题解首先要过模板题，比如会个非旋treap，写一下，通过[luogu3369][模板]普通平衡树...
2019-11-14 15:59:33
196
原创 [luogu3290][SCOI2016]围棋
前言一道dp题题目相关题目链接题目大意一个n∗mn*mn∗m的棋盘（0,1,2）并给出一个2∗c2*c2∗c的模板，求多少种棋盘包含模板qqq次询问答案模1e9+71e9+71e9+7数据范围n≤100,m≤12,c≤6,q≤5n\le 100,m\le12,c\le6,q\le5n≤100,m≤12,c≤6,q≤5题解首先我们发现包含模板的数量不好算，但是我们发现可以求出...
2019-11-04 20:08:48
193
原创 排序算法总结
前言初赛到了，理一下排序算法冒泡排序扫n遍，每一遍比较相邻大小复杂度O(n2)\mathcal O(n^2)O(n2)插入排序每次插入一个数到相应位置复杂度O(n2)\mathcal O(n^2)O(n2)选择排序每次选一个最小的加入复杂度O(n2)\mathcal O(n^2)O(n2)堆排序全放堆里，每次取出最小的复杂度O(nlogn)\mathcal O(nlogn...
2019-10-14 20:13:49
193
原创 斯特林反演&[bzoj4671]异或图
前言继续学习容斥的技巧！题意简介题面链接题目大意定义两个无重边无自环图G1,G2G_1,G_2G1,G2的异或为G3G_3G3(G1,G2,G3G_1,G_2,G_3G1,G2,G3点数都为nnn)满足当边(u,v)(u,v)(u,v)在G1,G2G_1,G_2G1,G2中共出现111次时G3G_3G3中有边(u,v)(u,v)(u,v)，否则没有现在给出sss个图...
2019-10-09 15:25:50
578
原创 扩展欧几里得
前言划水选手来把以前学的算法写博客上，防止以后忘了然后先定义gcd(a,0)=agcd(a,0)=agcd(a,0)=a欧几里得算法求gcd(a,b)gcd(a,b)gcd(a,b)即最大公约数，有什么用，能求lcm(a,b)=a∗b/gcd(a,b)lcm(a,b)=a*b/gcd(a,b)lcm(a,b)=a∗b/gcd(a,b)，）大雾方法：gcd(a,b)=gcd(b,a%b)g...
2019-10-01 19:42:57
132
原创 cometoj contest 6（记录型博客）
前言由于时间过少，这里仅仅记录我自己的思路（给自己看的），如果你有兴趣可以看看原题，再看看我写的，但是一般情况下不会很友好，此类文章在以后都会标记“（记录型博客）”A我们发现，所有的剩余量一定是a+2ba+\sqrt 2 ba+2b或者是C−(a+2b)C-(a+\sqrt 2 b)C−(a+2b)的形式把所有这些形式的全部抽出来分析一下种类好像不是很多，然后建图跑最短路即可...
2019-09-10 19:39:29
270
1
原创 [51nod1847][算法马拉松23（飞越愚人节）F]奇怪的数学题
前言万年不写公开博客了，这次填个坑题目相关链接题目大意求∑i=1N∑j=1Nsgcd(i,j)k\sum_{i=1}^N\sum_{j=1}^Nsgcd(i,j)^ki=1∑Nj=1∑Nsgcd(i,j)k数据范围
2019-08-13 16:02:33
178
原创 克鲁斯卡尔重构树
前言水的时候看到的算法正文对于一些问题，比如什么在一幅图从一个点开始经过的边小于等于某个值所能达到的点集中求balabala首先搞出最小生成树（显然只有最小生成树上的边有用）然后从小到大枚举边，把边所连的两个点合并成一个新的点（新的点的权值等于边的权值），新的点继承原来两个点相连的边将所有点合并完后，我们开始建克鲁斯卡尔重构树，这棵树的点就是原图中的点加上新建的点，这棵树的边是每个新建...
2019-07-12 10:20:51
464
原创 主定理(master theorem)学习小记
前言这是分析复杂度的一个玩意儿，东西不多，原本只要死记一下就好了，但是考虑到我不太好的记忆力，所以还是解析一遍比较好正文主定理是用来分析T(n)=aT(nb)+f(n)T(n)=aT(\frac nb)+f(n)T(n)=aT(bn)+f(n)满足a,b≥1a,b\ge1a,b≥1的复杂度的其实感觉也挺好分析的考虑T(n)T(n)T(n)的瓶颈问题假设aT(nb)>&a...
2019-07-10 13:53:10
1033
1
原创 [loj2087][NOI2016]国王饮水记
前言回归OI，随便找一道清真dp题写写吧做完发现一点都不清真题目相关链接题目大意现在有nnn个数，每次可以取若干个数，将每个数赋成平均值，限制kkk次，问第一个数最大能变成多少数据范围n≤1000,k≤109n\le1000,k\le10^9n≤1000,k≤109另外，精度要求ppp位，3≤p≤30003\le p\le30003≤p≤3000题解设nnn个数为h1,h2,...
2019-07-05 15:57:37
438
原创 vb学习记录
前言OI暂时停了，投入到文化课马上就要期末考了，为了技术的期末考试，所以就花一点时间学习一下vb吧介绍vb，是一门语言，与C++同为面向对象的的语言，在实际的界面方面却略有不同，他可以设置类似于按钮、文本输入框之类的东西（即对象），并且为这些单独编写代码，感觉还是挺有趣的语法因为只是看了一会儿，所以就大致说一下算了还是贴个进制转化的代码吧，自行理解Private Sub Comma...
2019-06-14 14:34:15
551
原创 APIO2019游记&题解
前言在繁忙的文化课生活后，我得以have a rest，来到北京参加APIO，然而，这APIO似乎并没有使我感到轻松比赛历程其它不说了，讲课听起来挺奇怪的，就直接从比赛写起吧好久不写博客了，总结一下十分必要，确实应从每一次的比赛中吸取教训这次比赛，开场写读优，大概好久不写OI题了，所一读输优写挂调了20min然后感觉linux的编辑器太丑、不好用，又调了10分钟准备工作做完后，感觉...
2019-05-19 01:08:49
2470
原创 ZJOI2019赛季回顾
前言ZJOI2019落下了帷幕尽管成绩不尽如人意但是明天还会继续正如一句话所说：不要害怕落日的黑暗，因为明天的太阳还会照常升起总排rank35，仅以此文章回顾整个赛季NOIP2018 DAY1不算很难的题，大家都ak了，也没什么好说的NOIP2018 DAY2day2T1很傻的一个地方判错了，丢分，然后剩下两个暴力，总分194day2T3确实菜了，动态dp考前原本可以把板子打...
2019-04-29 19:14:11
509
1
原创 codeforces contest 1140（D~G）
前言A~C不想写博客了，就不写了，后面的题还是要推一推的，所以写一下CF 1140 D题目大意：给出一个正多边形，顶点按顺序标号为111~nnn，一个三角划分的权值是每个三角形三个顶点的编号乘积之和求出一个三角划分使得这个三角划分的权值是所有的中最小的n≤500n\le500n≤500题解：区间dp即可，挺方便的，复杂度O(n3)\mathcal O(n^3)O(n3)但是事实上...
2019-04-19 20:58:21
636
原创 codeforces contest 1142
前言这个contest是div1的，div2的题其实也做了一下，但这里就不贴出了CF 1142 A题目大意：有nnn个城市排成一圈，相邻两个城市距离为kkk，一个人从起点SSS（SSS未给出）开始，每次走xxx（xxx未给出）的距离，当其第二次到达SSS时就不再走了现在给出离起始位置最近的城市的距离aaa和离走一步后的位置最近的城市的距离bbb，求可能的走的步数的最大值和最小值n,k≤1...
2019-04-16 21:18:51
146
原创 Two Merged Sequences（CF 1144 G）
前言在做其它题的时候脑补到过这个题意，没想到还真有这样的题题目相关链接题目大意给一个序列，问是否能将这个序列完全划分成一个上升子序列和下降子序列数据范围n≤2⋅105n\le2·10^5n≤2⋅105题解有个不错的思路：找到最大值，讨论他是上升序列的最后一个元素还是下降序列的第一个元素如果是上升序列的最后一个元素，那么需要满足两个条件：1.其后面的元素都是在下降序列中的2...
2019-04-11 20:22:41
450
原创 [loj3056][hnoi2019]多边形
前言模数打错导致在模拟赛时变成40分题目相关链接题目大意给定一个多边形的三角划分定义一个旋转操作为对于四个有边相连的点a<b<c<da<b<c<da<b<c<d，原本a↔ca\leftrightarrow ca↔c连边，旋转后b↔db\leftrightarrow db↔d连边给定一...
2019-04-10 11:16:43
400
原创 codeforces contest 1119
CF 1119 A题目大意：给一个数组aia_iai，求最大的i−ji-ji−j使得ai≠aja_i\neq a_jai̸=aj，输出这个i−ji-ji−j的值题解： 这题可以做到O(n)\mathcal O(n)O(n)，有一个很好的性质，就是一定满足i=ni=ni=n或j=1j=1j=1。我们发现这很好证明，如果a1≠ana_1\neq a_na1̸=an，那么答案就是n−1...
2019-04-08 21:19:08
343
原创 Dominant Indices(CF 1009 F)
前言记录一下长链剖分的小技巧题目相关链接题目大意一棵nnn个节点的树，定义fi,jf_{i,j}fi,j为与iii号点距离为jjj的节点数量，对于每个iii求出一个最小的jjj满足fi,jf_{i,j}fi,j是所有jjj的取值中最大的数据范围n≤106n\le10^6n≤106题解直接长链剖分即可，我们发现“重”儿子继承的时候是直接最前面加个1，所以可O(1)\mathca...
2019-04-02 17:53:39
205
原创 [luogu3676]小清新数据结构题
前言此题貌似有不少做法题目相关链接题目大意给出一棵树，支持两个操作1.修改一个点的权值2.指定一个点，计算以其为根时每个子树权值平方和数据范围n,q≤200000n,q\le200000n,q≤200000题解对于这题，我们发现直接维护好像不太方便考虑转化一下问题设S=∑i=1nsiS=\sum_{i=1}^ns_iS=∑i=1n...
2019-04-01 14:23:09
191
原创 [luogu5142]区间方差
前言略题目相关链接题目大意单点修改，区间方差数据范围n,q≤100000n,q\le 100000n,q≤100000题解区间方差的定义1r−l+1∑i=lr(ai−a)2\frac{1}{r-l+1}\sum_{i=l}^r(a_i-a)^2r−l+11i=l∑r(ai−a)2其中a=1r−l+1∑i=lraia=\frac{1}{r-l+1}\sum_{i=l}^r...
2019-04-01 10:09:49
1177
原创 长链剖分：O(nlogn)预处理O(1)求kth祖先
前言一个长链剖分的小trick问题如题，数据范围大概10510^5105思路我们知道重链剖分是什么，即选择自己儿子中子树节点树最大的作为重儿子，其它儿子为轻儿子而长链剖分则是选择儿子中子树深度最大的儿子为长儿子，其它为短儿子这样进行树剖后就有一些很奇妙的性质，即：一个节点的kth祖先所在的链的链长大于k我们考虑：对于每一条长度为xxx的链，我们记录链头的每个kth祖先（k∈[1,x...
2019-04-01 08:41:30
342
原创 [zjoi2015]幻想乡战略游戏
前言略略略题目相关链接题目大意给出一棵树，每次修改一个点的权值，维护一个带权重心啥是带权重心？设点iii的值为ViV_iVi我们要选一个点uuu，每个点对应一个值：∑v=1nVv∗dis(u,v)\sum_{v=1}^n V_v*dis(u,v)v=1∑nVv∗dis(u,v)我们要选一个uuu使得这个值最小输出最小的值数据范围n,q≤105n,q\le10^5n,q...
2019-03-31 09:13:51
532
原创 数列分块入门（套题）（loj6277,loj6278,loj6279,loj6280,loj6281,loj6282,loj6283,loj6284,loj6285）
前言zjoi考差了，码一些分块题缓解一下心情壹数列分块入门 1[loj6277]题目大意：区间加，单点查直接分块，区间加时完全覆盖的块打tag，边界块暴力重构块大小设为n\sqrt nn，复杂度O(nn)\mathcal O(n\sqrt n)O(nn)code#include<cstdio>#include<cctype>#include<c...
2019-03-29 16:00:25
229
原创 [luogu2664]树上游戏
前言点分治题目相关链接题目大意给出一棵树，每个节点有一个颜色设s(u,v)s(u,v)s(u,v)为树上点uuu到点vvv的路径上的颜色数对于每个iii，求Si=∑j=1ns(i,j)S_i=\sum_{j=1}^ns(i,j)Si=j=1∑ns(i,j)数据范围n≤100000n\le100000n≤100000题解点分治大法好（但是我们这里不考虑）考虑每种颜色的贡献...
2019-03-28 19:44:54
441
原创 ZJOI2019一试翻车记
前言退役了day1day1上午是lyx的讲课标题是《具体数学》从上升幂、下降幂到斯特林数的求一行、一列、单个之类的然后还有熟悉的猪叫day1下午是kcz的杂题选讲不知为何，声音很催眠day2day2上午fzy的数据结构选讲好难day2下午cqz的随机算法？？？？day3考试的一天差点迟到，慌得一匹开场身份证落在包里了T1打麻将我写了一个爆搜，单次判定O(n∗...
2019-03-28 07:27:49
394
原创 动态dp
前言这是今年NOIP前的坑了，当时由于感觉不太会考所以没先学然而NOIP考到了打出GG现在回来补一波题目先拖出模板题，从模板题认识动态dp的一种典型形式洛谷P4719 【模板】动态dp题意：给定一棵n个点的树，点带点权有m次操作，每次操作给定x,y，表示修改点x的权值为y你需要在每次操作之后求出这棵树的最大权独立集的权值大小数据范围：1≤n,m≤1051\le n,m\l...
2019-03-22 21:18:59
1379
原创 [zjoi2017]仙人掌
前言谨以此题纪念我第一次参加省选时刚了5h这一题得到0分的经历题目相关链接题目大意给出仙人掌定义：如果一个无自环无重边无向连通图的任意一条边最多属于一个简单环，我们就称之为仙人掌给出一个图，求有多少种加边方式使得图成为一个仙人掌数据范围多组数据∑n≤5∗105,∑m≤106\sum n\le5*10^5,\sum m\le10^6∑n≤5∗105,∑m≤106题解首先，如果这...
2019-03-21 21:28:34
380
原创 [luogu4128][shoi2006]有色图
前言毒瘤计数题题目相关题目链接题目大意nnn个点的完全图，对边染色（颜色有mmm种），求本质不同的染色方案数，答案对ppp取模数据范围1≤n≤53,1≤m≤1000,1≤p≤1091\le n\le53,1\le m\le1000,1\le p\le10^91≤n≤53,1≤m≤1000,1≤p≤109题解我们乍一看是染色问题，我们就想到了Poyla定理l=1∣G∣∑ai∈Gk...
2019-03-20 12:58:54
5150
原创 [bzoj1547]周末晚会
前言这是一道Burnside引理的应用题题目相关链接题目大意一个长度为nnn的010101圈，没有超过kkk个的连续的111，求方案数数据范围T≤50,n≤2000,k≤2000T\le50,n\le2000,k\le2000T≤50,n≤2000,k≤2000题解我们设fif_ifi表示不含超过kkk个连续111的长度为iii的链的数量我们考虑求fif_ifi，用所有方案...
2019-03-14 08:19:32
271
原创 Burnside引理和Polya定理学习笔记
前言求·······的方案数循环同构算一种一脸懵逼（于是我觉得系统的学一遍Burnside引理和Polya定理）正文置换置换的概念对于一个排列aia_iai我们想成iii输进去会出来一个aia_iai那么我们如果输入一个排列，将能得到一个排列就比如我们输入的排列是111到nnn有序的，那么这个置换就是(123⋅⋅⋅na1a2a3⋅⋅⋅an)\begin{pmatrix}...
2019-03-13 18:47:14
373
原创 单位根反演&[loj6485]LJJ 学二项式定理
前言之前写反演的博客对于单位根反演只提了FFT这里补一下一个应用单位根反演fi=∑j=0n−1ωni∗jgj⇔gi=∑j=0n−1ωn−i∗jnfjf_i=\sum_{j=0}^{n-1}\omega_n^{i*j}g_j\Leftrightarrow g_i=\sum_{j=0}^{n-1}\frac{\omega_n^{-i*j}}nf_jfi=j=0∑n−1ωni∗jgj⇔g...
2019-03-08 08:15:31
405
原创 模拟赛-20190228-随机数（random）
### 前言~~一道暴力就要用积分的题~~整理一下思路### 题目相关##### 题目大意有$n$个实数$x_1,x_2···x_n$，其中$x_i$在$[l_i,r_i]$中均匀随机求$max((\sum x_i)^m,0)$的期望##### 数据范围$1\le n\le10,1\le m\le100,-10^6\le l_i\le r_i\le 10^6$
2019-03-06 07:27:21
327
空空如也
devc++编译运行的程序出现Error216该如何解决？
2019-08-13
TA创建的收藏夹 TA关注的收藏夹
TA关注的人