- 博客(499)
- 收藏
- 关注
RSS订阅
原创 福建省2014ACM省赛H Big castle (树形dp)
题意：给出一棵树，然后每个节点有一个状态0或者1，当操作某个节点时，相邻的节点会反转。求能否通过操作使整个树的节点全部变成1.题解：开始的想法是dp[u][2] 1表示这个节点是亮的，0表示这个节点是暗的。发现很多状态无法确定，然后多加一维的状态，dp[u][2][2],第二维表示这个节点是否操作过。这个转移的思想就是保证儿子节点全部暗或者全部亮，然后判断这个节点原来亮暗状态然后进行状
2015-03-17 21:07:39
785
原创 SGU 390 Tickets (数位dp，k进制树的合并)
题意：给出一个区间，将这个区间连续的数的数位加起来，保证和要不小于k，求能分的最多区间。题解：详细可以看算法合集之《浅谈数位类统计问题》，这题我们将数变成一个k进制的树，然后在树上考虑问题，对于这样的区间和，相当于树上子树的合并问题，因为合并会出现上个子树还有剩余的数位和，于是我们要合理利用这些数位和，dp[pos][sum][rem]表示数位pos，和为sum，前一棵子树还剩余rem
2015-03-16 21:18:29
1135
原创 codeforce 271D Good Substrings (后缀自动机+dp)
题意：给出一个串，和一个01串，01串只有26个字符，每个字符对应26个英文字母表示这个字符是否是好的，1表示好的，0表示不好的。所给的串中多少个不同子串至多包含k个坏字母。题解：这题没想到用dp来做，一直去想性质，其实用dp做挺简单的。dp[i][j]表示在后缀动机上的i点，现在有j个坏字母对应子串的个数。明显:dp[i][k]+=dp[next[i][j]][k] if(alp
2015-03-15 17:13:13
768
原创 codeforces 424E Colored Jenga (状态压缩，概率dp用hash记忆优化搜索)
题意：给出以最多6层的积木，每层可以由三个木块拼成，总共有三种颜色的木块，开始时给出了积木的排列情况，我们每次可以从积木中抽一块木块，抽木块的规则是投骰子，骰子分别投到red,blue,green，的概率为1/6,1/3,1/3.每次投骰子都要花费一分钟，如果投到的颜色不存在就等一分钟不操作。注意的是要保证不能从顶部抽，并且抽木块时不能让整个积木倒了，要保证不倒中间的木块必须存在，每次抽出的木
2015-03-11 15:07:21
1034
原创 hdu 5185 Equation (完全背包变形)
题意：给出n个数字，数字满足 x[i]题解：类似于完全背包，dp[i][j]以j为结尾重量为i的方案数。我们通过分析会发现对于某个重量i，数字能取到的最大值是(sqrt(8*i+1)-1)/2，根据前n项和变形而来。这样就把复杂度从O(n^2)变为O(nsqrt(n))。转移方程 dp[i][j]=dp[i-j][j-1]+dp[i-j][j] 对于这样的重量i，以j数字为结尾任然
2015-03-09 13:26:33
637
原创 poj 3581 Sequence (后缀数组好题)
题意：给出一个字符串，求这个字符串分成三段并且反转着三段得到字典序最小的序列。题目保证第一个字符最大。题解：题目保证第一个字符最大是非常有用的条件，我们可以用贪心，将字符串倒叙，找到字典序最小的后缀作为第一段，注意最小要字典序是在不会导致有一段是空串的前提下，例如 4 3 2 1 明显倒序后最小后缀时1 2 3，但是这样不可取，因为如果去1 2 3，那么其他两段就是空串了！这是求出了第
2015-03-08 13:13:13
582
原创 hdu 5164 Matching on Array (奇葩版ac自动机)
题意：给出一个a序列，m个b序列，a能通过倍数关系能出现多少b串。例如a{ 2 4 8 } b{ 1 2 } 那么a中的{ 2 4 } 和{ 4 8 } 是可以通过b序列通过倍数变成的。题解：我们可以把串进行缩放，然后缩放后的串进行匹配。对于m==1的情况用kmp 其他情况用ac自动机。搞一个分数类进行处理。自动机的边用map，对奇葩的地方就是这里，用map做边，map>next
2015-03-03 23:07:13
512
原创 hdu 3962 Microgene (ac自动机+矩阵优化（好题）)
题意：给出n个串，现在要求长度为L的串至少包含着n个串中的两个串的个数。题解：一看这种计数类问题要么dp，要么矩阵乘法。dp明显内存时间都爆。那么可以考虑用矩阵乘法，首先如果直接用矩阵存不包含任意n个字符串，L次幂，将maze[0][i]相加得到长度为L的不包含任何n个串对应串的个数，然后在计算全部的情况，这样就缺包含一个字符串对应串的个数这个方案了，之前用枚举N个字符串哪个出现了进行
2015-03-03 19:38:38
582
原创 zoj 3535 Gao the String II (ac自动机+dp)
题意：给出A集合有m个穿，B集合有n个串，现在要求A集合中的串进行组合成长度不超过L的串S，是的包含最多B集合的串。题解：这题真心ｏｒｚ。dp[i][j][k]表示长度为i，在ac自动机上的状态j，并且是以k为结尾的A中的串。预处理出每个A集合中的串和其他A集合中的串拼接的长度，因为任何两个串拼接的长度可以有多个，所以暴力枚举拼接的长度然后判断是否可行。注意：空串可以拼接任何串在开
2015-03-03 16:13:48
687
原创 codeforces 294E Shaass the Great (树形dp，好题)
题意：给出一棵树，每条边有一个权值，现在要将树的某个边打断，然后重新建一条等长的边在某两点间，要求建完边的图形也要是树。求使得所有点两两距离和最短的方案。题解：我们分析如果某条边打断，那么就分成了两棵树，我们假设断掉的是u，v两点的边，那么两两距离和可以化成这个公式：S = { u的树中任意两点距离和 }+{ v的树中任意两点的距离和 } + { u树中任意点到u的距离和 * v的
2015-02-15 11:49:36
766
原创 codeforces 137D Palindromes (dp神题路基打印)
题意：求一个串分成k个回文串需要的最少操作数，这个操作是指将串的某个位置的值改变以使得分成的串能够成为回文。题解：感觉神题啊，路径打印十分困难。第一、我们要预处理下区间[i,j]上串变成回文的操作数！这步要用到区间dp来预处理，不断划分区间跟新。第二、dp计算出最小的操作数，dp[i][j]表示前j个点分成i份回文串需要的最小操作数。第三、获取，这就需要第二步中dp的值来倒
2015-02-09 15:31:35
894
原创 codeforces 453B Little Pony and Harmony Chest (离散化+dp状态压缩)
题解：给出n个数a[n]，然后要求一另外n个数b[n]满足 sum{|a[i]-b[i]|}最小。b[n]内的元素要满足任意两个都是互质的。题解：状态压缩，为什么？对于这样数据方位小的求最有解并且要某个状态要表示的东西很多那么普通dp绝对不行，那么久可以考虑状态压缩，dp[i][j]表示前i个数素数因子的选取状态为j时的最小差值和。说实话想不到这样状压，看了大犇的才懂，这样技巧性比
2015-02-03 16:52:08
705
原创 codeforces #247D Random Task (数位dp+二分搜索)
题意：给出m，k，找到这样的数n，满足n+1,n+2,n+3.....2*n区间内有m个数的二进制数中1的个数为k。题解：一开就想到枚举这样的数求在n+1,n+2,n+3.....2*n区间内有二进制有k个1的数的个数然后和m匹配如果相等就输出这个数，但是这样搜索O(n)很慢，会TL。看了大犇的，用二分，因为这样的m是随数增加而递增的。所以果断盗取了方法，二分下直接给过了1a。我用的是
2015-02-01 12:11:42
696
原创 poj1239(两次Dp)
两次dp求解，题目要求在整个是递增子序列的前提下最后一个元素的值要最小，并且在此前提下第一个的值要最大，不看题解根本想不到怎么做。做法：定义两个dp数组dp_min dp_max 第一个记录某个i点往后能延伸 的点序号即dp[i]-i就是末尾最小数的区间，dp_max则相反记录的是某个i之前的序列即i-dp[i]作为之前的最大数的区间。首先从前往后dp弄出租后一个数的最小值，然后从后往前
2014-11-28 17:27:41
1392
原创 poj3160(Tarjan+Spfa)
方法RT，但是一直wa不知道为何，感觉自己的代码写搓了今天起来研究了一下，发现错误好多，机智的找到错误，ac
2014-11-13 23:25:13
995
原创 hdu3401_分析降维_队列优化
这题很好，但是就是不会做，队列优化那块#include#include#include#includeusing namespace std;#define oo 0x3f3f3f3f#define maxn 2020#define maxm 2020int dp[maxn][maxm];//到第i天为止拥有的股票数为j时能赚的最大金额int ap[maxn
2014-11-13 11:28:16
729
原创 hdu3416(最短路+最大流)
最短路+最大流用Spfa算出 s到各个点的最短路 t到各个点的最短路if( dis1[i] + dis2[i] + map[i][j] ==dis1[t] )满足这种情况说明边在最短路上，所以根据这个方法建边然后最大流解决
2014-11-13 10:08:28
1195
原创 manacher算法模板
char s[maxn << 1];int p[maxn << 1];int Len[maxn];void manacher(){ int len = strlen(s), id = 0, maxlen=0; for(int i = len; i >= 0; --i){ s[i + i + 2] = s[i]; s[i + i + 1] = '#'; } s[0] = '*
2015-08-01 20:39:07
760
原创 zoj 3469 Food Delivery (区间dp)
没想到还会回来写博客，算是回忆下把，来一道区间dp基础题。题意：一个送外卖的从某个出发点送外卖，但是每个顾客地点都有一个不满意值，会随着时间每秒增加b[i]，每个顾客地点都有一个距离，可以人为是在x轴上的坐标。现在问如何送外卖使得不满意度最小。题解：好像做过，不过这次换了一个更优美的姿势过，记忆优化写起来会比较好写，而且姿势优美。dp[i][j][pos]表示[l,r]区间的顾客都
2015-07-23 10:28:49
979
原创 hihoCoder 1166 交换代数 (高斯消元，概率)
题意：给出区间[1,n]的状态，有0、1.现在每次可以选择任意区间取翻转，问全部翻转成0的次数期望。总共有n(n+1)/2个区间。题解：这个CLJ链接将的很清楚了。那么根据高斯消元列方程求解，因为有-2,+2，那么可以部除以2，这样就变成-1,+1.#include#include#include#include#include#include#include#i
2015-05-19 23:49:34
1053
原创 poj 1061 青蛙的约会 (解同余方程)
题意：两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐
2015-05-17 19:36:28
880
原创 hdu 5113 Black And White (dfs+强力剪枝)
题意：给出每种颜色的个数，现在要在n*m的各自上染色，问能否染成相邻颜色都不同的状态。题解：dfs肯定能想到，但是剪枝比较难想到，当染色到某个状态时，如果某个颜色的个数大于剩下各自的一半就剪枝，可以这样想：因为同种颜色不能相邻，那么极端情况，将这种颜色格一个格子放置，那么如果这种情况还有剩肯定无法满足条件。还有一个自己YY的优化方法，就是尽量让个数多的颜色先放置，那么就将颜色按个数排序
2015-05-17 13:36:15
693
原创 hdu 5148 City (树形dp)
题意：在树中取k个点，这些点中任意点的距离和要最小。题解：dp[i][j]，表示以i为跟的子树选择j个节点对应的距离对整体的贡献，就是一个树形背包。dp[u][j] = min { dp[u][j-t] + dp[v][t] + cost(t * (k-t) * w * 2) } cost是连接u和v的边对整体的贡献。 #include#include#include#i
2015-05-17 11:46:14
680
原创 hdu 5006 Resistance (高斯消元，0 0！)
题意：一些导线连接一些点，导线的电阻只有0和1.求S和T的等效电阻。题解：这题给re跪了，不过思路应该不会错，注意高斯消元的姿势。首先对于0电阻的这导线显然无法直接用高斯消元，先度这些点缩点，0电阻的缩成一个点，接着就可以根绝高斯消元列方程了。555#include#include#include#include#include#include#include#inc
2015-05-15 20:40:14
564
原创 hihoCoder 1159 扑克牌 (dp,难)
题意：一副不含王的扑克牌由52张牌组成，由红桃、黑桃、梅花、方块4组牌组成，每组13张不同的面值。现在给定52张牌中的若干张，请计算将它们排成一列，相邻的牌面值不同的方案数。牌的表示方法为XY，其中X为面值，为2、3、4、5、6、7、8、9、T、J、Q、K、A中的一个。Y为花色，为S、H、D、C中的一个。如2S、2H、TD等。题解：对应每个排有4中类型dp[a][b
2015-05-15 00:02:50
1155
3
原创 hihoCoder 1156 彩色的树 (贪心)
题意：给出一颗树，初始的颜色都是0，现在有两种操作。1、询问现在树有多少同种颜色组成的树；2、将x点的颜色改成y题解：这题乱搞题，思路是这样的，开始同颜色数的个数ans=1,每次给某个点改颜色直接影响的就是其父亲和孩子。那么只要考虑两点：1、对父亲的影响，对于如果现在的节点颜色等于父亲并且变换后的颜色不等于父亲，那么必然会增加一课同颜色子树。如果现在节点的颜色不等于父亲而变换后等于
2015-05-14 20:34:17
867
原创 hihoCoder 1169 猜数字 (线段树，离线处理)
题意：每次询问求出区间最接近k的数对应的差。题解：离线操作，两次排序，计算两次，第一次将询问和数字根据k从小到大排序，碰到询问只要查询区间的最大值跟定是最靠近k的，相反第二次是从大到小排序，求最小值是最靠近k的，两次计算的值取最小值即可。#include#include#include#include#include#include#include#include#
2015-05-14 17:43:41
675
原创 hihoCoder 1170 机器人 (状压dp)
题意：有16种颜色的球，现在有n个这样的球排成一列，要求将这些球变成所有相同颜色必须在一起的状态，每次只能交换相邻的球。题解：这题的做法并不知道如何解释，只是意会了而已。预处理出每种颜色的球变换到其他颜色的球前面对应的步数，事实上这个步数是相对某个状态来说的。然后就是状态压缩，每次添加一种颜色的球进去。注意：预处理也是有技巧的，暴力必然超时。#include#includ
2015-05-13 16:57:52
795
原创 hihoCoder 1149 回文字符序列 (区间dp)
题意：求一个串的回文子序列有多少个。题解：dp[i][j]表示[i,j]区间回文子序列的个数。dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1];if(str[i] == str[j]) dp[i][j] = dp[i+1][j-1] + 1;不断从内往外推，一旦存在str[i]==str[j]那么要加上dp[i+1][j-1
2015-05-13 10:33:24
937
原创 hdu 4046 Panda (线段树，单点更新，区间求和)
题意：两个操作，改变区间某个位置的值，询问区间好友wbw串的个数。题解：将线段树的每个点的值设为以这个点为结尾的串是否是wbw。接下来就是裸的线段树。注意一个位置改变会影响三个位置，所以要更新三个位置的点。区间更新是要这样做query(a+2,b,1)因为如果不这样会重复计算。#include#include#include#include#include#include
2015-05-10 23:27:07
614
原创 FJ三校联盟个人赛(师农工商)#1解题报告
A题—Eliminate Witches!：模拟这题用语法分析器来写思路就很清晰了！#include#include#include#include#include#include#include#include#include#include#include#define B(x) (1<<(x))using namespace std;typedef lo
2015-05-10 19:16:12
1177
原创 acdream 1116 Gao the string! (扩展kmp，dp思想，矩阵优化)
题意：题目要求每个后缀能包含多多少前缀，只不过这个数作为斐波那契的下标，求出对应斐波那契的和。题解：首先对于要计算出对应的后缀包含多少前缀，如果单单指考虑这样某个后缀能和多少前缀重合，可以通过扩展kmp求得。因为是求后缀对应的某个子串能包含多少前缀，因此要从后往前递推累加，然后同时计算对应的斐波那契数。开始的时候打斐波那契数的表，想找到循环节通过模处理，但是太大了，打不了，开始还因为这
2015-05-10 00:57:19
541
原创 hdu 5226 Tom and matrix (推公式，lucas)
直接求这个公式：∑bi=aCki=Ck+1b+1−Ck+1alucas :Cmn≡Cm/pn/p⋅Cm%pn%p(mod p)因为p可能是小质素，这样超过阶乘p的阶乘会爆0。#include#include#include#include#include#include#include#include#include#define B(x) (
2015-05-09 22:14:27
674
原创 第九届北京化工大学程序设计竞赛网络同步赛
A题：dfs，从打到搜索#include#include#include#include#include#include#include#include#include#define B(x) (1<<(x))using namespace std;typedef long long ll;typedef unsigned long long ull;const in
2015-05-09 18:33:48
1870
原创 acdream 1092 EOF女神的打地鼠游戏 (概率dp)
题意：ACdream的群主EOF女神（EndofFile）很喜欢玩打地鼠游戏，作为女神，肯定不能像正常人去玩这个看似普通的游戏。EOF女神站在直角坐标系的原点上，不移动。游戏开始后，某一时刻t[i]在坐标(x[i],y[i])处会出现一只地鼠，地鼠十分敏捷，只在这一个时刻出现，马上就消失，EOF作为女神，当然不屑于用锤子去打地鼠，她用念力组成的锤子去打地鼠(Orz…)，由于功力有限，女
2015-05-09 17:18:49
881
原创 hdu 2795 Billboard (线段树，单点更新)
题意：给出一个h*w的版面，现在要将每个海报（1*wi）贴到这上面，每次要选择最左边能够贴的地方！题解：其实n个点最多能用的高度就是n，那么可以根据搞当区间进行线段树，好吧我还是太水了。#include#include#include#include#include#include#include#include#include#define B(x) (1<<(
2015-05-08 21:06:36
441
原创 hdu 1754 I Hate It (单点更新，区间查询)
题意：给出n个学生的分数，每次可以选择两个操作，1是选择将区间某个点学生的分数更新，2是询问区间学生的最大值。题解：入门题，直接搞。#include#include#include#include#include#include#include#include#include#define B(x) (1<<(x))using namespace std;ty
2015-05-08 17:51:19
463
原创 hdu 1556 Color the ball (区间跟新，单点查询)
题意：n个操作，每次讲一个区间染色一次，问最后全部点被染色了多少次。题解：区间跟新完没必要一个点一个点的查询，直接在查询中输出对应值。#include#include#include#include#include#include#include#include#include#define B(x) (1<<(x))using namespace std;t
2015-05-08 12:38:12
507
原创 acdream 1086 晴天小猪爱61 (贪心+背包)
题意：给出一个数字，要把这个数字分成尽量少的含有61的数。题解：首先对于n>=6161的数，可以得出一个结论，肯定能分成***61 61**这样的形式。那么对于小于6161的数可以考虑用完全背包，中途记录状态就好了。#include#include#include#include#include#include#include#include#include#d
2015-05-08 08:59:38
551
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人