2 zhouyuheng2003

尚未进行身份认证

不要害怕落日的黑暗,因为明天的太阳还会照常升起

等级
TA的排名 4w+

cometoj contest 6(记录型博客)

前言由于时间过少,这里仅仅记录我自己的思路(给自己看的),如果你有兴趣可以看看原题,再看看我写的,但是一般情况下不会很友好,此类文章在以后都会标记“(记录型博客)”A我们发现,所有的剩余量一定是a+2ba+\sqrt2ba+2​b或者是C−(a+2b)C-(a+\sqrt2b)C−(a+2​b)的形式把所有这些形式的全部抽出来分析一下种类好像不是很多,然后建图跑最短路即可...

2019-09-10 19:39:29

[51nod1847][算法马拉松23(飞越愚人节)F]奇怪的数学题

前言万年不写公开博客了,这次填个坑题目相关链接题目大意求∑i=1N∑j=1Nsgcd(i,j)k\sum_{i=1}^N\sum_{j=1}^Nsgcd(i,j)^ki=1∑N​j=1∑N​sgcd(i,j)k数据范围

2019-08-13 16:02:33

克鲁斯卡尔重构树

前言水的时候看到的算法正文对于一些问题,比如什么在一幅图从一个点开始经过的边小于等于某个值所能达到的点集中求balabala首先搞出最小生成树(显然只有最小生成树上的边有用)然后从小到大枚举边,把边所连的两个点合并成一个新的点(新的点的权值等于边的权值),新的点继承原来两个点相连的边将所有点合并完后,我们开始建克鲁斯卡尔重构树,这棵树的点就是原图中的点加上新建的点,这棵树的边是每个新建...

2019-07-12 10:20:51

主定理(master theorem)学习小记

前言这是分析复杂度的一个玩意儿,东西不多,原本只要死记一下就好了,但是考虑到我不太好的记忆力,所以还是解析一遍比较好正文主定理是用来分析T(n)=aT(nb)+f(n)T(n)=aT(\fracnb)+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

[loj2087][NOI2016]国王饮水记

前言回归OI,随便找一道清真dp题写写吧做完发现一点都不清真题目相关链接题目大意现在有nnn个数,每次可以取若干个数,将每个数赋成平均值,限制kkk次,问第一个数最大能变成多少数据范围n≤1000,k≤109n\le1000,k\le10^9n≤1000,k≤109另外,精度要求ppp位,3≤p≤30003\lep\le30003≤p≤3000题解设nnn个数为h1,h2,...

2019-07-05 15:57:37

vb学习记录

前言OI暂时停了,投入到文化课马上就要期末考了,为了技术的期末考试,所以就花一点时间学习一下vb吧介绍vb,是一门语言,与C++同为面向对象的的语言,在实际的界面方面却略有不同,他可以设置类似于按钮、文本输入框之类的东西(即对象),并且为这些单独编写代码,感觉还是挺有趣的语法因为只是看了一会儿,所以就大致说一下算了还是贴个进制转化的代码吧,自行理解PrivateSubComma...

2019-06-14 14:34:15

APIO2019游记&题解

前言在繁忙的文化课生活后,我得以havearest,来到北京参加APIO,然而,这APIO似乎并没有使我感到轻松比赛历程其它不说了,讲课听起来挺奇怪的,就直接从比赛写起吧好久不写博客了,总结一下十分必要,确实应从每一次的比赛中吸取教训这次比赛,开场写读优,大概好久不写OI题了,所一读输优写挂调了20min然后感觉linux的编辑器太丑、不好用,又调了10分钟准备工作做完后,感觉...

2019-05-19 01:08:49

ZJOI2019赛季回顾

前言ZJOI2019落下了帷幕尽管成绩不尽如人意但是明天还会继续正如一句话所说:不要害怕落日的黑暗,因为明天的太阳还会照常升起总排rank35,仅以此文章回顾整个赛季NOIP2018DAY1不算很难的题,大家都ak了,也没什么好说的NOIP2018DAY2day2T1很傻的一个地方判错了,丢分,然后剩下两个暴力,总分194day2T3确实菜了,动态dp考前原本可以把板子打...

2019-04-29 19:14:11

codeforces contest 1140(D~G)

前言A~C不想写博客了,就不写了,后面的题还是要推一推的,所以写一下CF1140D题目大意:给出一个正多边形,顶点按顺序标号为111~nnn,一个三角划分的权值是每个三角形三个顶点的编号乘积之和求出一个三角划分使得这个三角划分的权值是所有的中最小的n≤500n\le500n≤500题解:区间dp即可,挺方便的,复杂度O(n3)\mathcalO(n^3)O(n3)但是事实上...

2019-04-19 20:58:21

codeforces contest 1142

前言这个contest是div1的,div2的题其实也做了一下,但这里就不贴出了CF1142A题目大意:有nnn个城市排成一圈,相邻两个城市距离为kkk,一个人从起点SSS(SSS未给出)开始,每次走xxx(xxx未给出)的距离,当其第二次到达SSS时就不再走了现在给出离起始位置最近的城市的距离aaa和离走一步后的位置最近的城市的距离bbb,求可能的走的步数的最大值和最小值n,k≤1...

2019-04-16 21:18:51

Two Merged Sequences(CF 1144 G)

前言在做其它题的时候脑补到过这个题意,没想到还真有这样的题题目相关链接题目大意给一个序列,问是否能将这个序列完全划分成一个上升子序列和下降子序列数据范围n≤2⋅105n\le2·10^5n≤2⋅105题解有个不错的思路:找到最大值,讨论他是上升序列的最后一个元素还是下降序列的第一个元素如果是上升序列的最后一个元素,那么需要满足两个条件:1.其后面的元素都是在下降序列中的2...

2019-04-11 20:22:41

[loj3056][hnoi2019]多边形

前言模数打错导致在模拟赛时变成40分题目相关链接题目大意给定一个多边形的三角划分定义一个旋转操作为对于四个有边相连的点a<b<c<da<b<c<da<b<c<d,原本a↔ca\leftrightarrowca↔c连边,旋转后b↔db\leftrightarrowdb↔d连边给定一...

2019-04-10 11:16:43

codeforces contest 1119

CF1119A题目大意:给一个数组aia_iai​,求最大的i−ji-ji−j使得ai≠aja_i\neqa_jai​̸​=aj​,输出这个i−ji-ji−j的值题解:这题可以做到O(n)\mathcalO(n)O(n),有一个很好的性质,就是一定满足i=ni=ni=n或j=1j=1j=1。我们发现这很好证明,如果a1≠ana_1\neqa_na1​̸​=an​,那么答案就是n−1...

2019-04-08 21:19:08

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

[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

[luogu5142]区间方差

前言略题目相关链接题目大意单点修改,区间方差数据范围n,q≤100000n,q\le100000n,q≤100000题解区间方差的定义1r−l+1∑i=lr(ai−a)2\frac{1}{r-l+1}\sum_{i=l}^r(a_i-a)^2r−l+11​i=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

长链剖分:O(nlogn)预处理O(1)求kth祖先

前言一个长链剖分的小trick问题如题,数据范围大概10510^5105思路我们知道重链剖分是什么,即选择自己儿子中子树节点树最大的作为重儿子,其它儿子为轻儿子而长链剖分则是选择儿子中子树深度最大的儿子为长儿子,其它为短儿子这样进行树剖后就有一些很奇妙的性质,即:一个节点的kth祖先所在的链的链长大于k我们考虑:对于每一条长度为xxx的链,我们记录链头的每个kth祖先(k∈[1,x...

2019-04-01 08:41:30

[zjoi2015]幻想乡战略游戏

前言略略略题目相关链接题目大意给出一棵树,每次修改一个点的权值,维护一个带权重心啥是带权重心?设点iii的值为ViV_iVi​我们要选一个点uuu,每个点对应一个值:∑v=1nVv∗dis(u,v)\sum_{v=1}^nV_v*dis(u,v)v=1∑n​Vv​∗dis(u,v)我们要选一个uuu使得这个值最小输出最小的值数据范围n,q≤105n,q\le10^5n,q...

2019-03-31 09:13:51

数列分块入门(套题)(loj6277,loj6278,loj6279,loj6280,loj6281,loj6282,loj6283,loj6284,loj6285)

前言zjoi考差了,码一些分块题缓解一下心情壹数列分块入门1[loj6277]题目大意:区间加,单点查直接分块,区间加时完全覆盖的块打tag,边界块暴力重构块大小设为n\sqrtnn​,复杂度O(nn)\mathcalO(n\sqrtn)O(nn​)code#include<cstdio>#include<cctype>#include<c...

2019-03-29 16:00:25

[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∑n​s(i,j)数据范围n≤100000n\le100000n≤100000题解点分治大法好(但是我们这里不考虑)考虑每种颜色的贡献...

2019-03-28 19:44:54

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。