4 Clove_unique

尚未进行身份认证

All that you have lost can be won back bit by bit as long as you wish for it.

等级
TA的排名 770

写给NOIp2018前的你们

不知不觉中已经退役一年多了,现在的高二认不得几个,低三届的学弟学妹就更别说了,可能连照面都没打过。所幸圈子里还有各种因为博客认识的我也弄不清是高一还是高二的孩子们,还能让我得到一点点关于OI的消息。我不知道NOI P对于大家来说到底意味着什么。可能对于有些人来说,拿到一等之后就已经完成任务可以回教室学文化课了。对于有些人来说,它是WC的敲门砖,也是来年省选中说小也小说大也大的一部分,或者说,这更...

2018-10-14 11:13:56

康复计划

几天前还在想这辈子都不要再碰这个东西了可是既然已经入了计算机的坑哪有不写代码的道理到了大学之后之前的oi基础还是在很多方面给了我很大程度的帮助几个小时之前无意间翻到之前的游记cf和bc和bz上的记录还有某些能让人笑出腹肌的日常还是很怀念以前的日子但是现在真的是老了啊退役了之后就再也不可能再变回之前的那个我了吧以前烂熟于心的东西全部都离我远去那种崩溃谁又能理解的了呢选择不...

2018-09-27 21:17:30

往事依稀浑似梦 都随风雨到心头 ——OI回忆录

Noregrets.

2017-06-08 11:24:27

[BZOJ1266][AHOI2006]上学路线route(spfa+最小割)

题目描述传送门题目大意:给出一个n个点m条边的无向图,每一条边有长度和代价,先求1-n的长度最短路,在求去掉最小代价的边,使1-n的长度最短路变大题解首先建出来最短路径图,然后连边容量为代价,跑最小割就行了最短路径图也就是图上的每一条边都在至少一条最短路中,判断的时候只需要判断边(u,v,c)是否满足dis(u)+c=dis(v)就行了让这些最短路都不能1和n连通所以跑一下最小割就行了代码#in

2017-05-11 22:23:42

[BZOJ4128]Matrix(BSGS+矩乘)

题目描述传送门题目大意:给出矩阵AB和模数p,求最小的正整数x,满足Ax≡B(modp)A^x\equivB\pmodp题解裸的BSGS,直接换成矩阵乘法就好了注意map里放结构体的话要重载一下<和==代码#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#inc

2017-05-11 22:19:58

[BZOJ3613][Heoi2014]南园满地堆轻絮(贪心)

题目描述传送门题目大意:给出序列a,构造一个严格上升的序列b,使得max(|ai-bi|)最小题解考虑两个数,如果是上升的就不用管了,如果是下降的需要把这两个数都变成中间值才能保证答案最小所以答案就是最大的(逆序对差值+1)/2代码#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<

2017-05-11 22:16:31

[BZOJ1570][JSOI2008]Blue Mary的旅行(最大流)

题目描述传送门题目大意:有n个点m条边的图,每一条边一天只能通过一定数量的人,每个人一天只能走一条边,问T个人全部从1走到n所用的最短天数。题解首先二分答案k,然后判定k天能不能过去每个点拆k+1个点,分别表示k+1个时刻,然后对于从第i个时刻到第i+1个时刻连边,连对应的m条边,然后对于每一个时刻的1号点和n号点s->1,n->t,然后判断最大流是否>=T就行了但是我并没有写二分,而是枚举

2017-05-09 21:33:31

[BZOJ4336][BJOI2015]骑士的旅行(树链剖分+线段树+multiset+归并)

题目描述传送门题目大意:n个点的一棵树,有m个骑士,每个骑士居住在n个点中的一个,有一个武力值fi,有三种操作:1xy询问居住在树链x-y上前k大的骑士的武力值2xy编号为x的骑士居住地改为y3xy编号为x的骑士武力值改为y题解k比较小树链剖分,对线段树中的底层节点维护一个multiset,维护所有居住在这个点的骑士的武力值,然后线段树中的每一个点开一个结构体

2017-05-06 22:04:36

[BZOJ4152][AMPPZ2014]The Captain(堆优化dijkstra)

题目描述传送门题目大意:给定平面上的n个点,定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|),求从1号点走到n号点的最小费用。题解分别按照xy排序,然后相邻点连边,跑最短路就行了写了一发堆优化dijkstra,竟然把大小记反了!代码#include<algorithm>#include<iostream>#include<cstring>#include<

2017-05-05 23:11:47

[BZOJ1237][SCOI2008]配对(dp)

题目描述传送门题目大意:你有n个整数Ai和n个整数Bi。你需要把它们配对,即每个Ai恰好对应一个Bp[i]。要求所有配对的整数差的绝对值之和尽量小,但不允许两个相同的数配对。题解这题并没有想出来。。。首先排序,一个结论是一个数配对的数与其距离不会超过2,也就是最多一个3的置换这个证明的话,直观的理解是如果没有冲突的,直接对应位置配对就好了,然后有冲突的话应该尽量减少置换的大小,所以3

2017-05-05 17:40:33

[BZOJ3209]花神的数论题(数位dp)

题目描述传送门题目大意:sum(i)表示i的二进制中1的个数,求∏i=1nsum(i)\prod\limits_{i=1}^nsum(i)题解f(i,0/1,j)表示二进制为i位数,是否卡上界,有j个1的数的个数dp完了之后快速幂一下就行了代码#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#i

2017-05-05 14:08:46

[BZOJ3566][SHOI2014]概率充电器(概率期望+树形dp)

题目描述传送门题目大意:一棵树,每一个点初始有一个概率为1,然后每个点可以沿着边向四周扩展,每条边有一个概率可以经过,问最终为1的点的个数的期望。题解f(i)表示点i从父亲扩展不到的概率,g(i)表示点i从儿子扩展不到的概率最终的答案是sigma1-f(i)*g(i)*(1-p(i))转移的时候,先计算出来某一个点扩展不到的概率,应该为f(i)org(i)*点不为1的

2017-05-05 11:12:24

[BZOJ4545]DQS的trie(广义后缀自动机+lct)

题目描述传送门题目大意:先给出一棵trie,然后支持几种操作若opt=1,则是一组询问,询问当前trie的本质不同的子串数目是多少。若opt=2,则后面跟两个整数rt,si,表示以点rt为根向下长出一个子树,大小为si。即加入一个子trie若opt=3,则是一组询问,后面输入一个字符串S,询问字符串S在当前trie中的出现次数。题解这题其实是substring和生成魔咒的结合版

2017-05-04 21:08:23

[BZOJ4319]cerc2008 Suffix reconstruction(贪心+构造+后缀数组)

题目描述传送门题目大意:给出一个sa,求一个合法的字符串的方案,或无解-1。题解无解就是a..z都填完了但是还不够所以肯定是按照rank填,填的过程中相邻两个rank的地方尽量是一样的,实在不行再不一样按照rank从小到大填数,对于相邻两个rank,比较两个的后面那个位置,如果后面的那个位置前面的rank小于后面的rank,说明这两个位置是可以填一样的,否则不行代码#include<algo

2017-05-04 17:24:23

[BZOJ3513][MUTC2013]idiots(FFT+组合数学)

题目描述传送门题目大意:给定n个长度分别为ai的木棒,问随机选择3个木棒能够拼成三角形的概率。题解这道题要根据三角形的两边之和大于第三边来做,其实判定的条件就是随机选出来的三条边中较小的两条之和大于第三条边首先容斥一下,用总的方案数减去不合法的方案数令F(i)表示两条边和为i的方案数,a(i)表示长为i的木棒有多少个,那么可以写成一个卷积的形式F(i)=∑a(i−j)a(j)F(i)=\su

2017-05-04 15:35:10

[BZOJ4445][Scoi2015]小凸想跑步(半平面交)

题目描述传送门题目大意:一个凸n边形,N个顶点按照逆时针从0~n-l编号。现在小凸随机选择多边形中的某个位置,标记为P点。将P点与n个顶点各连一条边,形成N个三角形。如果这时P点,0号点,1号点形成的三角形的面积是N个三角形中最小的一个,小凸则认为这是一次正确站位。现在小凸想知道他一次站位正确的概率是多少。题解设选的位置坐标为(x,y),用叉积化一下式子(x1−x)(y2−y)−(y1−y)

2017-05-04 14:02:10

[BZOJ2756][JLOI2010]铁人双项比赛(半平面交+三分法)

题目描述传送门题目大意:n个人参加比赛,先跑步和自行车的总路程为s,其中跑步为k,走路为r,每个人跑步和自行车都有一个速度。求出对第n个人最有利的k和r,使其获得冠军,并且领先第二名的时间最多。题解首先将每个人的k-时间方程写出来y=x/v1+(s-x)/v2=(1/v1-1/v2)x+s/v2这样得到了n个方程,用半平面交求凸壳(其它比半平面交高明到不知道哪里去了的办法都资瓷求出凸壳之后

2017-05-04 09:03:36

[BZOJ4864][BeiJing 2017 Wc]神秘物质(splay)

题目描述传送门题目大意:有一列数列,支持以下操作对于一列数,相邻一段中最大和最小的两个数的差值称为区间极差。mergexe当前第x个数和第x+1个数合并,得到值为e的新数;insertxe在当前第x个数和第x+1个数之间插入一个能量为e的新数。maxxy当前第x到第y个原子之间的任意子区间中区间极差的最大值;minxy当

2017-05-04 08:55:52

[BZOJ1088][SCOI2005]扫雷Mine(dp)

题目描述传送门题目大意:第一行有雷,第二行没有雷,但是有数字。问满足这个数字的第一行的方案数。题解f(i,s)表示满足前i个格子的限制,并且第一行最后三个格子的状态是s的方案数直接dp就可以了代码#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>usingnames

2017-05-03 18:51:55

[BZOJ1029][JSOI2007]建筑抢修(贪心+堆)

题目描述传送门题目大意:修复每一个建筑都需要一定的时间,如果某一个建筑不能在某一个时刻前被修复就永不能被修复了,问最多能修复多少个建筑题解按照最晚的时刻排序,然后对于一个建筑,如果能修就修,否则让其替换前面一个耗时最长的建筑和工作安排那道题有点像代码#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>

2017-05-03 18:49:47

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024超级勋章
    1024超级勋章
    授予原创文章总数达到1024篇的博主,感谢你对CSDN社区的贡献,CSDN与你一起成长。