- 博客(72)
- 收藏
- 关注
RSS订阅
原创 傻杯1.0
傻杯是装傻子的地方。1.求最短路/生成树时没注意数据范围——它是个累加和，小心爆int。2.认真看数据规模，邻接表存图的时候一定要考虑仔细最多会有多少边。无向边双倍。往往开头定义的常数maxm为最大点数，不小心直接开e[maxm*2]就GG了。3.静态差错不仅要查语法，也一定要注意思路的细节。4.变量名好好取。再敲错就收拾收拾去天台吧。5.深入理解时间换空间&空间换...
2017-12-11 20:33:05
10662
1
原创 NOIP2018游记
好久没写博客啦，本来还想考完之后把刷题记录传个档，结果一天假期都在补番，只能写一写游记了。D0又回到XJ了，每次来都是考试啊。回酒店先颓废了一会儿，然后写了写扫描线excrt还有一些零零碎碎的板子，最后着重看了看欧拉回路和kmp……睡前例行看知乎，十一点睡下居然又醒到午夜。早上五点醒了，以为在做梦，又睡过去。D1解压密码很应景啊。吐槽一下XJ真的好冷。T1是一眼题吧，分治的思想之前在一道区...
2018-11-13 12:53:49
318
原创 0825模拟赛总结
题解：再说。T1数据范围那么小，又是第一题，状压不可能那就搜索了，然而题目统计答案又对一个大质数取模，优化到死都没什么用（事实上模数只是吓吓人的）。但是我们可以打表啊……我自以为写的搜索比std的剪枝要优，但是我有两组没打出来，可恶的出题人还把最大的那个用了两组数据。T2继续爆搜……搜不过去的写了波随机。标算和计算几何搭边，但是随机+贪心能卡过，贪心原则是尽可能靠近圆心。机房有位神仙证明了...
2018-08-25 17:47:05
172
原创 0824模拟赛总结
题解：再说。我看什么题都像图论。T1想了挺久的，一直想不出怎么在环上操作。画了个图玩了一会儿，突然想到MST了。仔细一想觉得正确性没问题，kruscal写得还算熟练，没什么大问题。调了几个小错误就过了样例，顺便手玩了几组小数据没发现错误，内心非常快乐，转头去看T2。这种决策之类的题很容易想到dp，推了推方程发现不太有思路……T3一眼题，动态维护树的直径。然而没有想到怎么动态维护，只好敲了个...
2018-08-24 13:40:12
263
原创 Codeforces 855G Harry Vs Voldemort（边双+缩点+并查集）
题意： 众所周知，小y好奇心极强。 这次，他看到了一个n个节点的树，他突然想知道有多少个三元组(u, v, w)满足其两两不同且存在一条u到w路径和一条v到w路径满足两条路径之间没有公共边。 单单知道这个小y还不满足，他决定增加一些边，每加一条边他就想知道答案。数据规模： 20%: n <= 10, q <= 10 50%: n <= 500, q <= 50...
2018-08-23 15:52:44
406
原创 20180726の模拟赛总结……
为什么26的比赛今天写呢，因为昨天基本是乱敲，效率极低…… T1无脑乱做就行，估计我以前还做过……一个排列，每次可以拎一个数丢最前面，求使其升序的最小次数。随便手玩了几个样例找到规律，从最大的往前扫，如果存在一个xxx在x+1x+1x+1的后面，那么[1,x][1,x][1,x]都要拎最前面……但是我就是变量写错了orz……居然还过了那么多样例。 T2更显然，给了一堆字符串，求一个字典满足它们...
2018-07-27 22:24:53
150
原创 假期计划DAY1的模拟赛总结
我敲啊，lemon配错了，没忽略行末空格，直接挂了100+……乍一眼看完题目很水啊，而且很似曾相识……T1是很久之前写过的简单二分，原题好像叫跳石头还是啥的。10min+才切掉，感觉手有点慢了……用lrd老师的话说，10min是要能轻松敲完一棵Treap的……我还是太弱了。 T2想了有一会儿。其实是很简单的。题意是求单源到各点的最短路条数，我跑了遍SPFA，有些细节的累加还是推敲了一下……其...
2018-07-24 18:38:17
210
2
原创 NOI2014 动物园（kmp）
题目描述 近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的园长决定开设算法班，让动物们学习算法。 某天，园长给动物们讲解KMP算法。园长：“对于一个字符串SS它的长度为LL。我们可以在O(L)的时间内求出一个名为next的数组。有谁预习了next数组的含义吗？”熊猫：“对于字符串S的前ii个字...
2018-07-14 21:19:35
562
原创 20180714
随便立个flag吧，我要去北大。 还有两三个月，集训是最能感受到自己和别人差距的时候啊。说不上很丧，只是有点担心了。从不负责任的角度说，我为我过去没有意识到这种紧迫性而追悔。 仍然是我上次所想的，努力是最不值得称道的。我需要更多的技巧、灵感，必须要建立起自己的体系。 几乎想不出来竞赛结束之后全是文化课的日子。前段时间复习学考，虽然很尽力，但是还是觉得非常无趣。…………非常无趣。我要去北大...
2018-07-14 18:29:07
207
原创 DAY5测试T2 Tree（LCA+线段树/树上差分）
【问题描述】 小s是A星球的霸主。A星球上有n个城市，城市之间有一些道路。小s发现城市和道路刚好组成了一棵树。并且他发现如果有任意一条道路损坏，城市和城市之间就不连通了。A星球上还有m对工作站(A, B)。每对工作站在工作的时候，需要人员从A城市走到B城市。 现在A星球有Q个任务，每个任务可以由第L对工作站到第R对工作站任意一个来完成。小s想知道对于每个任务，损坏了哪些边会导致...
2018-07-10 07:33:57
446
原创 POJ1236 Network of Schools（强连通分量）
题面。有向图。显然同一个SCC中的任意两个学校都可以共享到软件。那么Tarjan求强连通分量后缩点，统计所有入度为 0 的SCC，它们是必须被我们提供软件的。这是第一问。第二问，题意即为最少添加几条有向边使整张图成为一个强连通图。统计零出度点。容易发现所有零入度和零出度都必须成为边的一端才能实现上述要求。则 max ( cnt 零入，cnt 零出 ) 即为答案。很显然啦。要注意如果缩点...
2018-07-09 07:34:31
132
原创 BZOJ2246 SDOI2011 迷宫探险（状压+概率dp）
题面太长了，贴起来好麻烦，走链接吧： P2489 [SDOI2011]迷宫探险题目指向状压。自然地考虑用二进制表示状态，0为无害，1为有害。紧接着会发现，当我们走到某个点 ( x, y ) 时，我们并不一定能确定地图上其它点是否无害。（比如说，在我们走到陷阱A的第一个位置之前，我们不能确定A是否有害，而我们完全有可能在走到 ( x, y）之前没有去过A）。所以，应该用三进制表示状态：0为...
2018-07-07 20:32:48
360
原创 hnoi2010 合唱队 （区间dp）
题目描述 为了在即将到来的晚会上有更好的演出效果，作为 AAA 合唱队负责人的小 A 需要将合唱队的人根据他们的身高排出一个队形。假定合唱队一共有 N 个人，第 i 个人的身高为 Hi 毫米(1000≤Hi≤2000)，并且已知任何两个人的身高都不同。假定最终排出的队形是 N 个人站成一 排。为了简化问题，小 A 想出了如下排队的方式：他让所有的人先按任意顺序站成一个初始队形，然后从左到右按...
2018-05-13 20:50:00
289
原创 关灯/节能（区间dp）
题目描述 宁智贤得到了一份有趣而高薪的工作。每天早晨她必须关掉她所在村庄的街灯。所有的街灯都被设置在一条直路的同一侧。 宁智贤每晚到早晨5点钟都在晚会上，然后她开始关灯。开始时，她站在某一盏路灯的旁边。 每盏灯都有一个给定功率的电灯泡，因为宁智贤有着自觉的节能意识，她希望在耗能总数最少的情况下将所有的灯关掉。 宁智贤因为太累了，所以只能以1m/s的速度行走。关灯不需要花费额外的时间，因为当她通过...
2018-05-13 19:49:19
515
原创 八皇后 （搜索-位运算）
题目描述检查一个如下的6 x 6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。上面的布局可以用序列2 4 6 1 3 5来描述，第i个数字表示在第i行的相应位置有一个棋子，如下：行号 1 2 3 4 5 6列号 2 4 6 1 3 5这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把...
2018-04-27 21:53:38
602
原创 luogu 1594 护卫队（线性dp）
题目描述 护卫车队在一条单行的街道前排成一队，前面河上是一座单行的桥。因为街道是一条单行道，所以任何车辆都不能超车。桥能承受一个给定的最大承载量。为了控制桥上的交通，桥两边各站一个指挥员。护卫车队被分成几个组，每组中的车辆都能同时通过该桥。当一组车队到达了桥的另一端，该端的指挥员就用电话通知另一端的指挥员，这样下一组车队才能开始通过该桥。每辆车的重量是已知的。任何一组车队的重量之和不能超...
2018-04-25 21:36:26
220
原创 luogu1280 尼克的任务 （线性dp）
题目描述 尼克每天上班之前都连接上英特网，接受他的上司发来的邮件，这些邮件包含了尼克主管的部门当天要完成的全部任务，每个任务由一个开始时刻与一个持续时间构成。尼克的一个工作日为N分钟，从第一分钟开始到第N分钟结束。当尼克到达单位后他就开始干活。如果在同一时刻有多个任务需要完成，尼克可以任选其中的一个来做，而其余的则由他的同事完成，反之如果只有一个任务，则该任务必须由尼克去完成，假如某些任务开...
2018-04-23 21:28:00
163
原创 ZHX’s Contest
题目描述 作为史上最贪玩的宏志狗，chty已经数月没交数学作业了，而他在月考中数学考了146分，完爆了全班同学，保平认为自己遭到了光速打脸，于是他给chty出了n道题，教他做人。 chty认为第i道题的难度就是i，他想让这些题目排列起来很漂亮。 chty认为一个漂亮的序列{an}下列两个条件均需满足。1：a1..ai是单调递减或者单调递增的。2：ai..an是单调递减或者单调递增的。...
2018-04-15 16:08:08
274
原创 反素数
背景 如果一个自然数比所有比它小的自然数的约数个数都要多，那么我们就称这个数为一个反素数。例如，1、2、4、6、12和24都是反素数。任务 请写一个程序： 读入一个自然数n； 找出不大于n的最大的反素数； 将结果输出。输入格式 只包含一行，为一个自然数n。输出格式 输出唯一的一个整数——不大于n的最大反素数。不那么暴力的暴力枚举还是很好搞的，看时间复杂度也不需要怎...
2018-04-15 15:52:54
536
原创 GDOI2007 天才的约数和
题目描述这天周航遇到了靳泽旭。 周航：“我是天才！” 靳泽旭：“你为什么是天才？” 周航：“你随便告诉我一个数字，我立即可以算出它所有约数之和，以及所有约数的倒数和！” 靳泽旭：“换过来，我告诉你一个数的所有约数（包括1和该数本身）的和以及约数的倒数之和，你是天才你应该立即能推出这个数是什么！”周航被难倒了！ 现在，这个难倒了天才的题目就交到你手上了。输入格...
2018-04-13 21:22:26
360
原创 lzy的数论挑战
故事背景 lzy最近迷恋数论！刚刚学完了最大公约数gcd，然后lzy就和hh进行了世纪数论决斗。题目描述 现在轮到hh进攻了，hh出题如下：任意给一个整数n， 那么整数 n 和 a^1999+b^1999+c^1999（满足a+b+c=0，且a，b，c都是整数）的固定最大公约数是多少？（也就是说，无论abc取什么，都存在这样一个最大公约数）。输入输出格式 输入：一行，一个整数...
2018-04-13 20:49:49
371
1
原创 分数分解
题目描述 给定n（2≤n≤10^9）值，要求x、y均为正整数，且 x < y，并且满足1/x+1/y=1/n. 编程统计有多少对这样的x和y。输入格式 一个整数n。输出格式 一个整数，表示相应的方法数是多少。第一步化简式子嘛， n( x+y ) = xy，反正看到这里我是什么冲动都没有，但是题解很巧妙：两边同时加上 n^2再移项，得 n^2 = n^2 - n( x+y...
2018-04-13 20:31:04
1510
原创 noip2009普及 细胞问题
简单数论。真的很简单啦！非常显而易见： 这个细胞 i 在 t s后要均分，则必须是 m1^m2的倍数。怎么判断呢？ m1^m2 的质因子种类和 m1 是一样的，指数则都是 m2 倍。细胞分裂只能增加 si 自身原有质因子的指数而不能得到新的质因子，在这个约束下，我们发现： si 必须包括 m1 的每种质因子——至少一个。一旦有不包含，即不合法。那么怎么求 t 呢？设对于 m1 的某个质因子 p...
2018-04-13 20:00:57
268
原创 东莞市选 格斗俱乐部（区间dp）
【问题描述】 格斗俱乐部是格斗爱好者的一个组织，在这里，格斗者们能通过与别的成员进行格斗来释放自己的压力与轻松自己的情绪。最近俱乐部举行了一场比赛，该比赛有N位选手参加，他们将围成一个圆圈，每一场比赛圈内任意的两位相邻的选手均可进行相互的格斗，胜利者将留在圈内进入下轮比赛而失败者则直接被送往医院（没有平局）。比赛是残酷的，最后圈内将只剩下一位选手，他将是总冠军。 我们做个奇怪的假设，两...
2018-04-12 16:31:13
680
2
原创 USACO 蛋糕塔（dp-分组背包）
【问题描述】 Hl高中要举行一场蛋糕塔比赛。注意，不是蛋糕比赛，而是蛋糕塔比赛。 学校会提供N种不同类型的蛋糕，第i种蛋糕的高度为Hi(5 <= H_i <= T)，营养价值为Vi(1 <= Vi<= 1,000,000)，并且保证所有蛋糕的高度为5的整数倍，每种类型的蛋糕没有数量限制。 蛋糕塔比赛的规则就是要求按照提供的蛋糕，垒成一个高度不超过T(1...
2018-04-12 16:10:12
240
原创 音量调节 changingsounds（dp-分组背包）
时间限制：1秒问题描述 一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都要改变一次音量。在演出开始之前，他已经做好了一个列表，里面写着在每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。 音量用一个整数描述。输入文件中给定整数beginLevel，代表吉他刚开始的音量，以及整数maxLevel，代表吉他的最大音量。音量...
2018-04-12 14:39:31
432
原创 20180407 dp测试赛 总结
先是题解： A：hdu 1176 免费馅饼 （dp） B：Codeforces 474D 蛋糕（dp-递推） C：Codeforces 366C 水果（dp-01背包） D：Codeforces 149D 括号染色（区间dp） E：Codeforces 245H 回文串（区间dp） F：Codeforces 432D 完美子串 + 51nod 1129 字符串最大值（dp-kmp） ...
2018-04-09 07:36:50
190
原创 Codeforces 432D 完美子串 + 51nod 1129 字符串最大值（dp-kmp）
我觉得我能A这题完全是因为前一天晚上做了很类似的。字符串，前缀后缀，出现次数，关键词一拼就是kmp。 首先我们考虑第二问的第二个数，怎么求得一段前缀子串在 s 中出现的次数。这里需要我们深入地了解next数组的含义。呃，我的意思是，如果 s[ 1~i ]出现过x次，那么 s[ 1~next[ i ] ]也必然至少出现过x次。 由此，我们设 d[ i ]表示 s[ 1~i ]出...
2018-04-08 21:38:39
503
原创 Codeforces 700B 友好城市（树形dp）
感觉现在的我还比较难想到这个思路啊。距离累加和，是由边决定的，所以我们计算每条边的贡献。 可以知道，对于一条边e，如果起点端有 x 个友好城市，终点端有 y 个友好城市，那么这条边的最大贡献就是 min( x,y )，因为少的那端怎么样也只有x个，再没法提供城市给另一端匹配了。至于如何求一端的友好城市数，实际上就是求子集（当然子节点应该是友好城市才能计数）大小，因为这端是 x ，那另...
2018-04-08 21:04:45
239
原创 Codeforces 245H 回文串（区间dp）
仍然是区间dp。这题相对好推一点。设f[ i ][ j ]表示 [ i,j ] 的回文串个数。 so，一般地，f[ i ][ j ]=f[ i ][ j-1 ]+ f[ i+1 ][ j ] - f[ i+1 ][ j-1 ]，很简单的容斥原理…… 而对于 s[ i ]==s[ j ]，还需要特殊处理。由于我做这题的时候全程带着做最长回文子序列的脑子做，所以以为可以直接 ++f[ i ...
2018-04-08 20:48:22
299
原创 Codeforces 149D 括号染色（区间dp）
看到括号就不想做…………所以真的没做。考完看了题解，发现还是很好推的。首先，预处理出括号匹配。这一步用栈可以很简单地完成，即：扫描字符串，遇到 ‘(’ 压入栈，遇到 ‘)’ 就弹出栈顶与之匹配，其正确性肉眼可见。下面我们用match_[i]表示与第i个位置匹配的括号的位置（好绕）。设f[ i ][ j ]表示[ i,j ]的染色方法数。然后，我们一眼就能发现这是区间dp。那么对...
2018-04-08 20:29:56
1266
原创 Codeforces 366C 水果（dp-01背包）
我是真心觉得它难的。 第一反应暴搜，2^100，算了。想了很久很久的各种设置状态的方法，都没法顺利进行状态转移。正解是这样的： 可得：∑aj=k*∑aj ( j:[ 1,m ] );那么，我们创造一个数组 g[ i ]=a[ i ]-k*b[ i ]; 于是乎，这个问题就转化成了，挑选一种或多种水果，使得 ∑g[ i ]=0，并且使对应的 ∑ai 最大。 是不是熟悉起来...
2018-04-08 19:53:50
321
原创 Codeforces 474D 蛋糕（dp-递推）
无敌水题，实际上样例解释就暴露了它递推的本质。f[ i ]表示吃 i 个蛋糕的方案数。 那么，f[ i ]=f[ i-1 ]+f[ i-k ]; ( i >k ) 这个递推和走楼梯很像。即当前i个蛋糕，可以分为两种情况：吃掉一个蛋糕，剩下蛋糕的方案数即为f[ i-1 ]；或者选择吃掉k个蛋糕，剩下蛋糕的方案数为f[ i-k ]。初始化：i < k: f[ i ]=1; ...
2018-04-08 07:58:00
170
原创 hdu 1176 免费馅饼 （dp）
免费的陷阱。第一眼嘛，FJ摘苹果，但是n<=1e5，O( n^2 )，稳定TLE。 那么寻找别的思路，通过观察发现x的范围很小，[0.10]，遂采取暴力措施，设 f[ i ][ j ] 表示第 i 秒，以（必须）站在 j 为条件时，其最多能接到的馅饼。我起初是产生了歧义，关于这句话：因此在第一秒，他只能接到4,5,6这三个位置中其中一个位置上的馅饼。我理解成了一般性地，在 i ...
2018-04-07 21:41:28
143
原创 #454 最大利润（树形dp）
贯彻树形dp第一维通常是节点编号的思想，f[i]表示以i点为根的子树的最大利润。根据题意，相连的两点不能同时取，故可想到增加一维表示i点取或不取：f[ i ][ 0 ]表示不取，f[ i ][ 1 ]表示取。那么我们就可以列出状态转移方程了：f[ i ][ 1 ] = ∑ f[ x ][ 0 ] + value[ i ] ; f[ i ][ 0 ] = ∑ max( f[ x ][...
2018-03-21 21:21:42
218
原创 noi2011 道路修建（树形dp）
无根树，揪出结点1当根。dfs求f[i]子树大小。对于点i以及与之相连的点j，可知i一侧的点数为f[i]，j一侧为n-f[i]，故修路费用即为e[i].v*abs(n-2*f[e[i].y])。e[i].v是道路长度。注意，由于是递归求法，从下往上计算，故j必然是i的上层。为了避免双向边的重复统计和错误统计（方向反了），code里用了一个玄学操作。即更新时标记那条边。inlin...
2018-03-18 19:15:42
219
原创 矩阵连乘（区间dp）
f[i][j]表示第i~j个矩形相乘所得的最少乘法次数。 设a[i][j].x/y分别为第i~j个矩形连乘（最优方案）所得的x/y。则可得状态转移方程：f[i][j]=max(f[i][l]+f[l+1][j]+a[i][l].x*a[l+1][j].x*a[l+1][j].y); (i<=l<=j)值得注意的是，在状态更新之后，a[i][j]也应该被更新： a[...
2018-03-18 18:57:53
296
原创 背包的第k优解（dp-背包-状态记录）
一句话题意已经在题名里了。显然，这里必须要决策的过程当中不断地记录下前k优解。我们在0-1背包的基础上增加一维f[k][j]表示背包装的物品体积为j时的第k优解。对于每次决策f[j]=max(f[j],f[j-w[i]]+v[i]) 我们都让f[1~k][j]宇f[1~k][j-w[i]+v[i]合并取前k优解。显然，如果f[1~k]是乱序的，每次搜索一遍的 时间复杂度为O(k^2) ...
2018-03-13 21:17:16
368
原创 构建双塔（dp-双进程）
f[i][j] 表示取前i块水晶、两塔差为j时较高塔的最大高度。注意，这里的f[i][j]都是从上一阶段推得的。我们在面对第i块水晶时，它可能是从以下四种决策得来的：f[i][j]=max(f[i-1][j]) ; 这块水晶被丢掉了。f[i][j]=max(f[i-1][j+h[i]]) ; 这块水晶被给了上一个状态中较低的那座塔，且它未超过较高的塔，由图可知较高塔的最大高度是不变...
2018-03-13 21:06:47
445
原创 配置魔药（dp-双进程）
根据求什么设什么原则，f[k][i][j]表示放第k种魔药、第一个坩埚时间为i、第二个坩埚时间为j时的最大药效。设第k种药的起始时间为a[k].st，结束时间为a[k].sw。那么可得状态转移方程： f[k][i][j]=max(f[k-1][a[k].st-1][j]); (i>=a[k].st) f[k][i][j]=max(f[k-1][i][a[k].st-1]);...
2018-03-13 20:38:58
424
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人