4 Facico

尚未进行身份认证

生命是闪耀的此刻,不是过程,就像芳香不需要道路一样。

等级
TA的排名 4k+

#164. 【清华集训2015】V

DescriptionPicks博士观察完金星凌日后,设计了一个复杂的电阻器。为了简化题目,题目中的常数与现实世界有所不同。这个电阻器内有编号为1∼n1∼n的nn个独立水箱,水箱呈圆柱形,底面积为1m21m2,每个水箱在顶部和底部各有一个阀门,可以让水以1m3/s1m3/s的流量通过,每个水箱的上阀门接水龙头,可以无限供应水,下阀门不接东西,可以让水流出。水箱顶部和底部都有一个

2017-12-07 15:52:35

【NOIP2017提高A组集训10.28】图

Description有一个n个点A+B条边的无向连通图,有一变量x,每条边的权值都是一个关于x的简单多项式,其中有A条边的权值是k+x,另外B条边的权值是k-x,如果只保留权值形如k+x的边,那么这个图仍是一个连通图,如果只保留权值形如k-x的边,这个图也依然是一个连通图。给出q组询问,每组询问给出x的值,问此时这个无向连通图的最小生成树权值是多少。Solution其实这是一道非常套路的题目。

2017-11-01 17:17:30

【NOIP2017提高A组集训10.28】三元组

Description有X+Y+Z个三元组(x[i],y[i],z[i]),请你从每个三元组中挑数,并满足以下条件:1、每个三元组中可以且仅可以选择一个数(即x[i],y[i],z[i]中的一个)2、选择x[i]的三元组个数恰好为X3、选择y[i]的三元组个数恰好为Y4、选择z[i]的三元组个数恰好为Z问选出的数的和最大是多少问选出的数的和最大是多少Solution在X=0的时候

2017-10-31 08:09:00

【NOIP2017提高A组集训10.28】序列操作

Description一开始有n个非负整数hi,接下来会进行m次操作,第i次操作给出一个数c[i],要求你选出c[i]个大于零的数并将它们减去1。问最多可以进行多少轮操作后无法操作(即没有c[i]个大于零的数)Solution这题数据范围出的很迷,log^2竟然都能过很显然我们只用给前k大的数减一,然后我们考虑一段数减完之后相对顺序会怎么变,我们可以发现只有序列末尾相等的那一段会移到那一段的

2017-10-31 08:02:28

【NOIP2017提高A组集训10.22】公交运输

Description城市中有一条长度为n的道路,每隔1的长度有一个公交车站,编号从0到n,学校在0号车站的位置。其中每个公交车站(除了n号车站)有两个属性ci和vi,代表从这个公交车站出发的公交车的性质。ci代表这个从i出发的公交车,相邻两个停靠站之间的距离。vi表示每坐1站的花费。注意,一辆公交车出发后会向n号车站的方向行进。同时,一名乘客只能从起点站上车,但可以从任意停靠站下车。校庆志愿者

2017-10-25 21:17:56

【NOIP2017提高A组集训10.22】友谊

DescriptionFlowey是一朵能够通过友谊颗粒传播LOVE的小花.它的友谊颗粒分为两种,圆粒的和皱粒的,它们依次排列组成了一个长度为2m的序列.对于一个友谊颗粒的序列,如果存在1<=iSolution这道题60分很好打,设f[i][j][k]为做到第i个,偶数的圆粒和皱粒的个数,然后转移,注意要看到只有前偶后奇才能转移就很简单了。我们发现,最麻烦的东西就是上面的限制。

2017-10-25 21:03:36

【ZJOI2016&&BZOJ4574】【NOIP模拟】作弊(DP&&随机数据)

DescriptionSolution一开始这道题就看错题了,我直接用一轮的期望作为下一轮的值,结果还以为很容易就能用n^3搞出来,结果搞了半天。因为最后序列的答案不会超过原序列的最大值,所以我们可以考虑对原序列离散化一下,然后考虑每个位置最后的值是原序列第k大的期望,那么我们可以设sum[i][j]表示第i个点值小于等于序列中第j大的方案是多少,然后用sum[i][j]-sum[i][j-1]

2017-09-04 22:44:28

【JZOJ5343】【NOIP模拟】健美猫(模拟)

DescriptionSolution由于比较的蠢,比赛的时候没有想出来。一开始的方向就搞错了,搞了个自以为是对的贪心,然后就一直往这个地方想,用的时间太多就弃疗了。其实思想还是比较的简单的,首先把原序列的答案求一次,我们可以逆向考虑一下,不用把序列移动,把下标移动。比如把每个下标向左移动一格,那么原本a[i]>i的值会减1,a[i]<=i的值会+1,还有下标从n到1的数会改变一下。

2017-09-04 22:26:03

【NOIP模拟】赤壁情(DP)

DescriptionSolution这是一个计数的问题,一个关于排列的方案数的问题。但是用一般的排列求是不行的,对于插入排列因为要去绝对值,所以很麻烦。对于绝对值来说,我们可以把贡献给拆开,|i-j|把它拆开,那么就从小到大插入,先放入的j放入值-j,后放入的值i放入值i,因为不知道最后的位置是什么,所以一开始只存储相对的位置,那么到最后个数成为n个的时候就是一个排列了。然后每次插入的

2017-09-02 19:28:54

【JZOJ5335】【NOIP2017提高组模拟】早苗(DP、矩阵乘法)

DescriptionSolution这题的DP其实很显然。首先显然有一个状态是f[i][j]表示做到第i个,向前最多连续j个不同的方案数。我们既然不能有m个不同的,那么我们只要不向m转移就好了。转移也是比较的显然首先可以新加一个颜色f[i][j]–>f[i+1][j+1]*(m-j)或者可以把前面的连续j个颜色断开f[i][j]–>f[i+1][1~j-1]然后用矩阵乘法。Co

2017-08-24 20:06:07

【JZOJ5336】【NOIP2017提高模拟】提米树(DP、前缀和)

DescriptionSolution首先剪枝是对于一个点的,就是要把这个点下面的所有边给删掉。然后有些点是两两不能做相邻的叶子的,只有dfs序相邻的叶子到他们lca上的点之间可以做相邻的叶子对,这样可以做到dfs序相邻。然后我们可以设f[i]表示以i节点作为dfs序结尾的最大决心数量,那么枚举相邻的叶子,然后把上面的点两两配对来更新,这样是n^2log(带lca)的。但是要注意当一个点被更

2017-08-24 19:59:00

【JZOJ5328】【NOIP2017提高组模拟】世界线(STL)

DescriptionSolution这题刚看的时候就知道是用bitset来做,但是比赛的时候并不知道要怎么打,所以就只用了set来打。比赛之后学了一下bitset发现bitset其实就是帮你把二进制状压了一下。时间和空间都是除以32的。然后拓扑排序一下,倒着把点的集合合并到前面去。但是直接这样做bitset会爆空间,所以我们可以考虑每次只存[l,r]的点,这样就可以用时间来换空间。Co

2017-08-23 22:54:03

【JZOJ5317】【清华集训模拟】func(辗转相除法、找规律)

DescriptionSolution这是一个可以找规律的题目,但是性质也是比较的好推。我们可以观察相邻的两项i,i+1,f(i)、f(i+1)的值分别是对应着x、y,然后f(2*i)=x,f(2*i+1)=x+y,f(2*i+2)=y。然后我们可以发现相邻的两个每次都*2,他们的值也是较小的加上较大的。那么我们可以倒着推回来,每次值是较大的减较小的,然后判断是左边的较小还是右边的较小,

2017-08-23 22:48:00

【JZOJ5316】【清华集训模拟】merge(DP、括号序)

DescriptionSolution我们可以想到一个很显然的错误的DP,f[i][j]+=f[i-1][j]+f[i][j-1]这样明显是会算重的,所以我们要考虑怎样去重。你可以找一下规律。我们知道如果在(i,j)前面有一段连续的相同的数的话是会算重的,那么在这之中的转移我们可以强制要求i>=j,那么这个就相当于一个括号序(()()),但是要保证括号影响的连续性,我们需要保证括号外面(

2017-08-23 22:37:52

【JZOJ5330】【NOIP提高组模拟】密码(库默尔定理、数位DP)

DescriptionSolution这题和[51Nod1569二项式系数的个数]是用一道题。就是要求Cmn|pkC_{n}^m|p^k根据库默尔定理,CmnC_{n}^m中p的次幂数就是n+m(加法)在p进制下的进位次数。那么题意就变成了选小于等于n的两个数,在p进制下的进位次数为k。知道这个之后我们就可以数位DP。我们设f[i][j][k][l]表示做到第i为,进位次数为j

2017-08-23 22:24:42

【JZOJ5296】【清华集训模拟】Sequence(整体二分)

DescriptionSolution这是第一次打整体二分。是一道十分裸的整体二分。整体二分大致思想就是,对于一坨询问,我们二分一个值,然后对所有的询问都进行判断,然后分别放到[l,mid]和[mid+1,r],这要每次枚举的区间都是[l,r]的话,时间复杂度就是log的。首先排名[x,y]的可以用主席树来搞出它的值域范围。我们对于b的答案二分一个值mid。然后找到所有b的值小于mid(

2017-08-23 22:10:44

【JZOJ5295】【清华集训模拟】Create(主席树)

DescriptionSolution这题的40分非常的好打,直接倒着主席树一下就好了。其实100分也差不多,只是要发现一些东西。因为估价函数们是不会变化的,所以我们可以考虑用一个数据结构。我们对于每个数a,只有大于估价函数的x才是有贡献的,我们可以考虑排序一下x,然后对于每个a找到最大的x小于等于a,然后统计这些区间有多少个覆盖a这个位置,这个可以用主席树来搞。但是我们对于一段相同

2017-08-23 21:57:50

【JZOJ5287】【NOIP2017提高组模拟】最短路

DescriptionSolution这题就是要求一个仙人掌图上面的两点间最短路径。那么我们一开始可以从1号节点开始跑一次spfa,然后加入两个点的在dfs树上的lca不是环上的点的话,那么直接用d[x]+d[y]-2*d[lca]就可以了。但是如果是环上的点要怎么办?我们环上的点可以有两条路径相互到达,那么我们可以把两个点同时跳到同一个环上然后在计算环上的距离。那么我们可以把环上的点的

2017-08-23 21:43:49

【JZOJ5272】【GDOI2018模拟】神奇的重复序列(DP,性质题)

DescriptionSolution如果两个串重叠的话,那么很明显这个串会是一个周期串(画个图就知道了)。枚举两个串的左端点的间距k,那么根据周期串的性质,在%k相同的地方都是相同的,那么我们枚举k,然后在枚举第一个串的左端点,然后用一个指针j向右扫过去。如果要把%k相同的修改为相同的话,那么就是保留其中出现次数最多的字符。那么我们对于%k的位置要存储每个字符出现多少次还有出现最多的是什么,和

2017-08-23 08:00:18

【JZOJ5270】【GDOI2018模拟】神奇的矩阵(二维线段树)

DescriptionSolution这题直接三方log只有70分,想要打的更好只能打平方log方的,那么很显然就是用一个二维的数据结构来维护。这还是我第一次打二维线段树(不是线段树套线段树)首先我们对于绝对值可以考虑小的数被贡献多少次,那么就是找大的数的和-小的数的出现次数,那么我们就可以考虑把所有的数从小到大排序然后依次插入。然后每个点上统计一个以它为左上角的矩阵可以被贡献多少次,那

2017-08-23 07:49:12

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!