4 L_0_Forever_LF

尚未进行身份认证

一个热爱OI的OIer

等级
TA的排名 5k+

NOIP2018游记

感觉今年noip题目顺序很神奇虽然麦老大觉得这样挺好的,能有一天打的特别爽…day0到了酒店时间还早,战斗战斗晚上beginend和金中的同学们跑过来和我们一起次饭,begin帅照++,金中的同学们还捎来了礼物(没有回礼十分惭愧)回到酒店后叫了个麦旋风,战斗战斗(放飞自我)晚上居然失眠了…在床上辗转反侧了将近2h就是睡不着,气得我…最后下床做了几个俯卧撑才睡着…(说不定是因为没有上晚...

2018-11-11 23:02:25

NOI2018退役记

感觉再不写以后也不想写了呢…算是一个退役报告吧NOI那段时间状态确实太差,可能退役也是必然结果吧虽然没想到最终会是这个成绩…Day0感觉整天都在看笔试…Day1上午笔试+试机,笔试顺利100,试机题竟然是九省联考下午开幕式,真的热…Day2进场先大概看了3道题,感觉T1一眼题,T2要推性质,T3似乎是道很可做的字符串题T1是道看完题就会的套路题,写题+对...

2018-07-25 11:39:47

最小树形图(朱刘算法)学习笔记&板子

最小树形图朱刘算法大概流程:初始化答案ans=01.每个点vvv选个最小入边(u,v,prec[v])(u,v,prec[v])(u,v,prec[v]),如果有点没有precprecprec就无解2.∑i,i≠rootans+=prec[i]∑i,i≠rootans+=prec[i]\sum_{i,i\neqroot}ans+=prec[i]2.若最小入边构成的是一棵树,那...

2018-07-08 19:56:14

6.28联考题解

这篇拖得有点久…A:模拟我们做kmp的过程,我们会得到两类关系,一类关系是第iii个位置和第jjj个位置相等,另一类是第iii个位置和第jjj个位置不等,相等的我们可以把他们合并在一起,于是变成一个图,相邻点不同色,共有ccc种颜色,求总染色个数这类图染色问题只有弦图是能做的否则做不了他这个kmp的过程似乎加的点就是完美消除序列证明的话可以考虑假设新加的点相连的两个点xxx,y...

2018-07-03 20:18:57

6.27联考题解

A:给定单位圆上n个点,求在其中挑选k个点,要求它们构成的凸包包含圆心,求凸包的最大面积考虑枚举凸包上弧度最小的点,做个dp,f[i][j]f[i][j]f[i][j]表示dp到第jjj个点,已经选了kkk个点且第jjj个点是第kkk个点的凸包最大面积转移就枚举上一个选的点,因为点是以弧度形式给出的,可以直接用弧度计算面积f[i][j]=f[i−1][k]+sin(radj−rad...

2018-06-29 17:12:25

6.26联考题解

A:首先答案的下界是l−1+lcl−1+lcl-1+l^c对长为lll,字符集为ccc的所有串建进一个图里,每个串连ccc条边分别连向添加这个字符后这个串长为lll的后缀的串的点,感受一下这个图显然有哈密顿回路且这个哈密顿回路就是我们要找的最优解然鹅找哈密顿回路是NP的,考虑把他转化成找欧拉回路,用边代表这个图中的点我们建一个新图,把这些串的所有长为l−1l−1l-1的前缀作为点,...

2018-06-26 20:29:24

6.25联考题解

A:维护一个集合,兹磁插入一个数xxx,询问集合里的数和xxx做and,or,xorand,or,xorand,or,xor运算的最大值权值ai<65536=216ai<65536=216a_if[a][b]f[a][b]f[a][b]表示集合中前8位的数是aaa的数里,和一个后8位是bbb的数做位运算,后8位结果的最大值设xxx的前8位是xxx,后8位是yyy插入xx...

2018-06-26 20:07:34

UOJ#123. 【NOI2013】小Q的修炼

第一次完整做完一道题答….这道题答似乎算是十分友好的前面几个点的代码没存,只有最后几个点的代码(不过后来看了一下感觉这个代码是能跑所有点的)case1,2写个暴力遍历所有情况,case2要跑一会case3我们看一下这个train3.in发现他分成了很多块,每个块的大小是170,在每个块内他会对变量2~12修改,在块的末尾,他会让1加上这些变量,然后把除了2的变量清空(变...

2018-06-23 15:25:11

NOI2015题解

D1T1:先用并查集把相等关系并起来再看有没有同一个联通块的不等关系D1T2:树剖D1T3:大概思想就是根据一个数>x−−√>x>\sqrtx的因子只有1个,对<n−−√<n>n−−√>n>\sqrtn的暴力枚举之前写过题解D2T1:K=2K=2K=2时可以直接用huffman树做K≠2K≠2K\neq2时,若nnn不满...

2018-06-23 14:57:47

6.22联考题解

A:和某题很像,这题是带修改版本的考虑把每条边(u,v,w)(u,v,w)(u,v,w)边权加到他连接的两点u,vu,vu,v上当A,B中某人同时取了u,vu,vu,v,他获得2w2w2w的价值,对差值贡献±2w±2w\pm2w当A,B一人取了uuu,一人取了vvv,各获得www,对差值贡献000发现将差值/2/2/2后和原来取边的情况等价问题变成了nnn个点,取每个点有...

2018-06-22 21:50:00

BZOJ5012[ioi2017]Train

下面定义的能走到/不能走到都是在A,B采取最优决策下的因为充一次电能跑n个点,所以A胜利的条件就是能走到一个有充电站的环,B反之如果一个充电车站不能走到任何一个充电车站(包括自己),那么我们可以把它视为不能充电的我们不断bfs求出哪些充电车站不能被其他充电走到,然后去掉他们,重复这个过程直到图中剩余所有充电车站都可以到达一个充电车站然后看起点是否能走到某个充电车站就知道是否A赢了...

2018-06-20 16:02:06

6.19联考题解

A:n个数,每次随机两个数合并,贡献是这两个数的和,求总贡献的期望乘∏ni=2i(i−1)2∏i=2ni(i−1)2\prod_{i=2}^n\frac{i(i-1)}{2}单独考虑每个数对答案的贡献,发现不管他是否合并,他都一直在这些数里面,因此剩余mmm个数的时候他被选中的概率就是2m2m\frac2m,因此n−1n−1n-1轮后他贡献的总概率就是∑ni=22i∑i=2n2i\sum...

2018-06-20 08:18:02

BZOJ4371: [IOI2015]sorting排序

我们假设E不操作,A把所有元素复位的最优解是枚举i,若他不在位置i上就和位置i交换,把他转化到图上正确性显然现在E操作,我们假设位置0~n-1上有碟子0~n-1,碟子i上有苹果i我们让E操作是交换碟子,A操作是交换苹果发现这和原问题是等价的,于是我们就可以把E的操作和A的操作分离开来二分答案,执行完E的前mid次操作后判A是否可以按照上面提到的最优解复原code:#in...

2018-06-18 21:59:51

BZOJ4369: [IOI2015]teams分组

将一个人(A,B)视作一个二维平面上的点,则一个小组k可以看作是[0,k]x[k,+∞]的一个矩形对于每个询问,我们从小到大处理k,每次将当前的可行区域内最低的那些点分配给k,对于不可行或之前取过的点的矩形区域,我们维护他们的拐点,这些拐点从左到右高度递减,用一个单调栈维护,查询矩形内点数可以用主席树总复杂度O((n+s)logn)O((n+s)logn)O((n+s)logn)cod...

2018-06-18 21:48:36

UOJ#211. 【UER #6】逃跑

谢谢栋栋教我这题qaq先画一下柿子ans=E×all=all∑(ai−ave)2=all∑(a2i−2ai×ave+ave2)ans=E×all=all∑(ai−ave)2=all∑(ai2−2ai×ave+ave2)ans=E×all=all\sum(a_i-ave)^2=all\sum(a_i^2-2a_i×ave+ave^2)ave=∑aiallave=∑aiallave=\df...

2018-06-18 16:41:33

NOI2016部分题解

D1T1优秀的拆分枚举AABB中AB的交界处,其实就是要计算每个位置AA的数量,算这个东西有个经典套路:枚举A的长度,每A个字符设置一个关键点,任意一个A一定覆盖且仅覆盖1个关键点,枚举相邻的两个关键点,后缀数组上st表O(1)lcp求他们往左往右匹配长度O(nlogn)O(nlogn)O(nlogn)code:#include<set>#include&l...

2018-06-16 09:37:44

6.15联考题解

A:我们尝试给每个点划分联通块定义一个联通块的位置是它里面深度最浅的点那么一个点要么属于他某个祖先的联通块,要么自己这里有一个联通块于是可以做个dp但是dp状态里要有个当前的最大值,状态数就n2n2n^2了我们可以先二分,就不用记录当前最大的联通块大小了然后记f[i][0/1]f[i][0/1]f[i][0/1]表示联通块位置在iii,iii这个位置的联通块中没有/有...

2018-06-15 21:55:18

LOJ#2461. 「2018 集训队互测 Day 1」完美的队列

可以先看一下这篇,写的比较详细了我们考虑对每个询问jjj求出一个ed[j]ed[j]ed[j],表示在执行完(j,ed[j]](j,ed[j]](j,ed[j]]的操作后,jjj在序列里加入的所有xxx全部被pop出去了,就可以对每个颜色xxx求出若干个存在的区间,将这些区间取并,即可差分贡献到答案现在考虑怎么求ed[j]ed[j]ed[j]我们将原序列分块,操作jjj覆盖了若干个整块...

2018-06-14 08:03:45

UOJ #141. 【UER #4】量子态的棋盘

先考虑假设知道了棋盘长什么样,怎么计算每个篮子会接到多少个球对于一个格子(i,j)(i,j)(i,j),若我们知道会有xxx个球滚到这个格子,那么一定会有⌊x2⌋+xmod2⌊x2⌋+xmod2\lfloor\dfracx2\rfloor+x\mod2个球走到这个格子指的方向,⌊x2⌋⌊x2⌋\lfloor\dfracx2\rfloor个球走到另一个方向换句话说,只有xmo...

2018-06-13 15:18:27

6.12联考题解

A:对于T=1T=1T=1的询问分块,对于<=n−−√<=nmod K=i mod K=i mod\K=i\的和,对于>n−−√>n>\sqrtn的K,每次询问直接暴力跳O(nn−−√)O(nn)O(n\sqrtn)对于T≠1T≠1T\neq1的询问首先肯定贪心的染颜色数最少的那种颜色,设有ccc个,将...

2018-06-13 15:03:13

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!