3 WWWengine

尚未进行身份认证

推广:http://bytew.net/OIer/ 数据库

等级
TA的排名 6w+

【NIOIP2016提高】天天爱跑步(LCA+树上差分)

近几年复赛最难的树上问题了。几个月前做是参照题解的方法,用了可持久化线段树在树上无脑维护和统计。当时的做法早已忘记,于是回过来自己做了做,其实远没有那么难做,只要发现一些奇妙的性质。 对于一个玩家s->t,如图。对于图中a点的观察员存在这样一个式子:w(a)=dep(a)-dep(lca)+dep(s)-dep(lca)。对于图中b点的观察员存在这样一个式子:w(...

2018-10-29 19:01:49

[USACO5.5]矩形周长Picture(线段树扫描线)

我没法写出这么详尽的题解,传送门:矩形周长很经典的一个题目,将线段之间的关系处理得很好。算是学到了一种黑科技。其实还可以离散化。(主要是题解写得好)#include<cmath>#include<cstring>#include<iostream>#include<algorithm>using namespace std;#de...

2018-09-29 23:54:34

Naptime(环形dp)

题目大意:每天有N个小时,每个小时进入熟睡状态可以获得体力值Ui,每N个小时必须休息B个小时,这B个小时可以随意分成几段,但是每段的第一个小时体力值是不计算的。现在叫你求解N个小时睡B个小时能得到的最大体力值。 分析:先假设前后两天不相连,以第一个小时作为起点。设f(i,j,0/1)表示前i个小时里,睡了j个小时,其中第i个小时正在睡(1),或者没有睡(0)。可以得到状态转移方程:...

2018-09-25 15:16:36

【IOI1998】Polygon(区间dp)

设f(l,r,0)表示区间[l,r]操作后的最大值,f(l,r,1)表示区间[l,r]操作后的最小值,简单的区间合并即可。可以把第一条边断掉,然后把这后面的N个点复制一遍,直接做N*2长度的区间dp。答案是max:f(i,i+N-1,0)。#include<cstdio>#include<iostream>#include<algorithm>...

2018-09-25 10:59:24

【HNOI2004】L语言(Trie树+搜索)

思路:Tire树存单词,然后每段话在Trie树上搜索。vis[i]=1表示这段话1到i能被识别,搜完后vis[i]=1最大的i就是答案,可以确保i之前的能被识别,否则dfs无法到达i。#include<cstdio>#include<cstring>using namespace std;const int MAXLEN=1000005;int ch[20*...

2018-09-04 21:36:02

【USACO08DEC】秘密消息Secret Message(二进制Trie树)

Trie树模板题,唯一的不同在与统计答案,设val[i]表示Trie树上经过i节点的单词数,end[i]表示在i节点结束的单词数。统计时,每走到一个节点就加上end[i];如果Trie树先走到尽头就直接返回答案;如果输入的先走完,那么最后一个节点不加end[i]而是val[i]。特别注意:Trie树先走到尽头时一定要把剩下的输入读完再退出。#include<cstdio>u...

2018-09-04 17:37:29

字符串与二进制Trie树的简单模板

字符串的Trie树:Description  给出n个单词组成的字典(可能由相同的单词),请你完成下列任务:  任务1、把n个单词去重后按字典序由小到大后输出。  任务2、给出m个询问,每次询问一个单词是否在字典中存在,如果存在,输出该单词在字典中出现的次数。Input  第一行为n和m。接下来的n行,每行一个单词。中间空一行。在接下来的m行,每行一个单词,表示一个询问。...

2018-09-04 16:47:19

【SDOI2010】古代猪文(数论杂烩)

难题,这题要用到很多数论知识但都不深,有专门的知识点我就用红色标出。(PS.洛谷上SDOI2010跟Pig有关的好多黑题,深表同情...)首先搬出问题:                                               由扩展欧拉定理,                                              而根据欧拉函数的定义,...

2018-09-04 10:52:49

【SHOI2015】超能粒子炮·改(Lucas定理)

我觉得这题挺难的,题解看来看去都是一步出结论,没什么过程,只有自己搞了。既然过了就尽量写清楚点。这题的模数是个质数且比较小,需应用卢卡斯定理:                                        现在用这个定理对题目所求一步一步地展开: 设答案(暂且不加上最外面的取模): 取模,用上Lucas定理:   把p=2333代入:...

2018-09-03 22:13:15

【NOI2002荒岛野人】(扩展欧几里得算法)

题意:给你N组Ci,Pi,Li,求一个最小的M,满足对于任意的一对i,j,都有:无解或者最小正整数解x满足。(也就是有一个先老掉了)。该方程可以转化为:  于是转化为枚举M,每次用扩展欧几里得一一检查是否合法。#include<cstdio>#include<algorithm>using namespace std;typedef long...

2018-09-03 14:32:16

【JLOI2014】聪明的燕姿(数论)

首先有个结论:如果一个数N可以分解为:,其中p为素数,c表示次数。那么N的所有正因数之和为:。对于此题用深搜,枚举p是无法避免的,且p可能为S-1,甚至无法打素数表。但我们可以枚举较小的素数,然后特判另一部分是否是一个质数,可以证明这样不会重复统计答案,因为即使S的分解一样,但分到N的因数上就不一样了。于是我们搜索,可以只枚举那些小于等于根号S的质数,直到能够整除当前值,然...

2018-09-03 09:42:08

樱花(素数筛+整数唯一分解)

原题见洛谷。首先可以化成这样的形式:然后对于N!的质因子分解应该不是难事,可以很快得到每个质因子的次数。由于有个平方,右边的次数还要乘2。左边可以完全不管内容,只是把它当作两个数a,b相乘。于是a,b相乘后,每个质因子次数之和,分别等于N!每个质因子的次数乘2,直接扫一遍乘完就行。#include<cstdio>using namespace std;typede...

2018-09-02 22:10:57

Prime Distance(素数筛)

原题见洛谷。首先一次预处理出根号R内的所有质数。虽然L,R很大但是它们相差不大,对于每个筛出来的质数,把[L,R]内所有能被它整除的数标记,然后剩下的数从L到R扫一遍就可以统计答案了。注意标记时的细节。#include<cstdio>#include<cmath>#include<iostream>#include<cstring>...

2018-09-02 14:35:10

【HNOI2008】越狱(快速幂)

这题容易多想。其实就是一个简单且直观的想法。所有的情况:每个房间都有m种选择,所以n个房间就是m^n种情况。无人越狱的情况:相邻房间不同即可,第一个房间有m种选择,后面的由于不能与相邻的相同,只有m-1种选择,所以方案是m*(m-1)^(n-1)。只需用总方案减去不可行的方案即可。#include<cstdio>#include<cmath>#incl...

2018-09-01 20:25:29

【USACO09NOV】灯Lights(DFS+二分)

这题N实在太小了,暴搜都可以得到很可观的分数,为了巩固搜索,就用DFS做了一下。BFS貌似也可做。在搜索前需要把每个点的异或值求出来,这样就不用建边枚举边了。首先每个灯最多被按一次;其次猜测需要按下的次数在10次以下。于是方案1:迭代加深搜索。#include<cstdio>#include<cstring>#include<iostream&gt...

2018-09-01 18:23:26

【CEOI2004】锯木厂选址(斜率优化dp)

此题类似于ZJOI2007仓库建设。设f[i][j]表示前i个锯木厂解决完前j棵树时的最小运输费用。算上山脚的,总共有3处锯木厂。方便起见,把山脚处也算一棵树,重量为0,那么总共有N+1棵树。所以答案是f[3][N+1]。设sumw[i]表示前i棵(从山顶开始)树的重量之和,sumx[i]表示第i棵树距山顶树的距离。假设第1~k棵树已由1~i-1号锯木厂解决,那么现在第k+1~j棵树交给第i...

2018-09-01 11:44:47

【APIO2010】特别行动队(斜率优化dp)

假设现在枚举到i,设前i个人的战斗力之和为sumx[i]。令第k+1~i个人分在一组,那么有:展开,移项,可以得到:此时可以发现2*a*sumx[i],由于sumx[i]递增,a<0,所以整个是小于零且单调递减的,同时f[i]又要取到最大值。画图可知我们需要维护一个上凸包,如图。#include<cstdio>#include<cstring>#i...

2018-09-01 09:48:48

【ZJOI2007】仓库建设(斜率优化dp)

设f[i]表示前i个仓库的货物处理完所需的最小花费。假设第k+1~i个仓库的货物集中在一起,那么只能是都搬到i仓库。那么此时:用给的x转化一下:设sump[i]表示前i个仓库的p之和,可以得到:设,那么整个式子就变成了:移项,可以得到:由于x[i]满足大于0且单调递增,而f[i]要求最小值,所以这里只要单调队列维护一个下凸包即可。#include<...

2018-08-31 23:00:21

【HNOI2008】玩具装箱(斜率优化dp)

设f[i]表示前i件玩具装好所花的最小花费。设sumc[i]表示前i件玩具的c之和。假如第k+1~i件玩具放在一起,那么间隔有i-k-1,所需的c为sumc[i]-sumc[k],所以花费为(sumc[i]+i-sumc[k]-k-1-L)^2。所以有状态转移方程:。现在来对这个方程简化:设a[i]=sumc[i]+i,b[i]=sumc[i]+i+L+1。那么方程可化简为:。展开,去...

2018-08-31 20:57:03

Cats Transport(斜率优化dp)

原题见洛谷。设f[i][j]表示前i个cs官接走前j只猫,前j只猫等待的最少时间。设cat[i]表示刚好接到接第i只猫的出发时间,那么cat[i]等于t[i]减去h[i]之前所有路的长度。把猫按cat排序,设sumt[i]表示前i只猫的cat[i]的和。现在来分析状态转移方程。假如第i个cs官接走了第k+1~j只猫,那么f[i][j]=f[i-1][k]+(cat[j]-cat...

2018-08-31 17:21:25

查看更多

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