2 zhouyuheng2003

尚未进行身份认证

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

等级
博文 96
排名 5w+

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

ZJOI2019一试翻车记

前言退役了day1day1上午是lyx的讲课标题是《具体数学》从上升幂、下降幂到斯特林数的求一行、一列、单个之类的然后还有熟悉的猪叫day1下午是kcz的杂题选讲不知为何,声音很催眠day2day2上午fzy的数据结构选讲好难day2下午cqz的随机算法????day3考试的一天差点迟到,慌得一匹开场身份证落在包里了T1打麻将我写了一个爆搜,单次判定O(n∗...

2019-03-28 07:27:49

动态dp

前言这是今年NOIP前的坑了,当时由于感觉不太会考所以没先学然而NOIP考到了打出GG现在回来补一波题目先拖出模板题,从模板题认识动态dp的一种典型形式洛谷P4719【模板】动态dp题意:给定一棵n个点的树,点带点权有m次操作,每次操作给定x,y,表示修改点x的权值为y你需要在每次操作之后求出这棵树的最大权独立集的权值大小数据范围:1≤n,m≤1051\len,m\l...

2019-03-22 21:18:59

[zjoi2017]仙人掌

前言谨以此题纪念我第一次参加省选时刚了5h这一题得到0分的经历题目相关链接题目大意给出仙人掌定义:如果一个无自环无重边无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌给出一个图,求有多少种加边方式使得图成为一个仙人掌数据范围多组数据∑n≤5∗105,∑m≤106\sumn\le5*10^5,\summ\le10^6∑n≤5∗105,∑m≤106题解首先,如果这...

2019-03-21 21:28:34

[luogu4128][shoi2006]有色图

前言毒瘤计数题题目相关题目链接题目大意nnn个点的完全图,对边染色(颜色有mmm种),求本质不同的染色方案数,答案对ppp取模数据范围1≤n≤53,1≤m≤1000,1≤p≤1091\len\le53,1\lem\le1000,1\lep\le10^91≤n≤53,1≤m≤1000,1≤p≤109题解我们乍一看是染色问题,我们就想到了Poyla定理l=1∣G∣∑ai∈Gk...

2019-03-20 12:58:54

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