6 My_ACM_Dream

尚未进行身份认证

我要认证

生活没有彩排每天都是现场直播

等级
TA的排名 8k+

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

zoj 3469 Food Delivery (区间dp)

没想到还会回来写博客,算是回忆下把,来一道区间dp基础题。题意:一个送外卖的从某个出发点送外卖,但是每个顾客地点都有一个不满意值,会随着时间每秒增加b[i],每个顾客地点都有一个距离,可以人为是在x轴上的坐标。现在问如何送外卖使得不满意度最小。题解:好像做过,不过这次换了一个更优美的姿势过,记忆优化写起来会比较好写,而且姿势优美。dp[i][j][pos]表示[l,r]区间的顾客都

2015-07-23 10:28:49

默默的换博客

www.linmeichen.com

2015-05-29 00:19:20

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

poj 1061 青蛙的约会 (解同余方程)

题意:两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐

2015-05-17 19:36:28

hdu 5113 Black And White (dfs+强力剪枝)

题意:给出每种颜色的个数,现在要在n*m的各自上染色,问能否染成相邻颜色都不同的状态。题解:dfs肯定能想到,但是剪枝比较难想到,当染色到某个状态时,如果某个颜色的个数大于剩下各自的一半就剪枝,可以这样想:因为同种颜色不能相邻,那么极端情况,将这种颜色格一个格子放置,那么如果这种情况还有剩肯定无法满足条件。还有一个自己YY的优化方法,就是尽量让个数多的颜色先放置,那么就将颜色按个数排序

2015-05-17 13:36:15

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

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

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

hihoCoder 1156 彩色的树 (贪心)

题意:给出一颗树,初始的颜色都是0,现在有两种操作。1、询问现在树有多少同种颜色组成的树;2、将x点的颜色改成y题解:这题乱搞题,思路是这样的,开始同颜色数的个数ans=1,每次给某个点改颜色直接影响的就是其父亲和孩子。那么只要考虑两点:1、对父亲的影响,对于如果现在的节点颜色等于父亲并且变换后的颜色不等于父亲,那么必然会增加一课同颜色子树。如果现在节点的颜色不等于父亲而变换后等于

2015-05-14 20:34:17

hihoCoder 1169 猜数字 (线段树,离线处理)

题意:每次询问求出区间最接近k的数对应的差。题解:离线操作,两次排序,计算两次,第一次将询问和数字根据k从小到大排序,碰到询问只要查询区间的最大值跟定是最靠近k的,相反第二次是从大到小排序,求最小值是最靠近k的,两次计算的值取最小值即可。#include#include#include#include#include#include#include#include#

2015-05-14 17:43:41

hihoCoder 1170 机器人 (状压dp)

题意:有16种颜色的球,现在有n个这样的球排成一列,要求将这些球变成所有相同颜色必须在一起的状态,每次只能交换相邻的球。题解:这题的做法并不知道如何解释,只是意会了而已。预处理出每种颜色的球变换到其他颜色的球前面对应的步数,事实上这个步数是相对某个状态来说的。然后就是状态压缩,每次添加一种颜色的球进去。注意:预处理也是有技巧的,暴力必然超时。#include#includ

2015-05-13 16:57:52

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

hdu 4046 Panda (线段树,单点更新,区间求和)

题意:两个操作,改变区间某个位置的值,询问区间好友wbw串的个数。题解:将线段树的每个点的值设为以这个点为结尾的串是否是wbw。接下来就是裸的线段树。注意一个位置改变会影响三个位置,所以要更新三个位置的点。区间更新是要这样做query(a+2,b,1)因为如果不这样会重复计算。#include#include#include#include#include#include

2015-05-10 23:27:07

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

acdream 1116 Gao the string! (扩展kmp,dp思想,矩阵优化)

题意:题目要求每个后缀能包含多多少前缀,只不过这个数作为斐波那契的下标,求出对应斐波那契的和。题解:首先对于要计算出对应的后缀包含多少前缀,如果单单指考虑这样某个后缀能和多少前缀重合,可以通过扩展kmp求得。因为是求后缀对应的某个子串能包含多少前缀,因此要从后往前递推累加,然后同时计算对应的斐波那契数。开始的时候打斐波那契数的表,想找到循环节通过模处理,但是太大了,打不了,开始还因为这

2015-05-10 00:57:19

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

第九届北京化工大学程序设计竞赛网络同步赛

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

acdream 1092 EOF女神的打地鼠游戏 (概率dp)

题意:ACdream的群主EOF女神(EndofFile)很喜欢玩打地鼠游戏,作为女神,肯定不能像正常人去玩这个看似普通的游戏。EOF女神站在直角坐标系的原点上,不移动。游戏开始后,某一时刻t[i]在坐标(x[i],y[i])处会出现一只地鼠,地鼠十分敏捷,只在这一个时刻出现,马上就消失,EOF作为女神,当然不屑于用锤子去打地鼠,她用念力组成的锤子去打地鼠(Orz…),由于功力有限,女

2015-05-09 17:18:49

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

查看更多

勋章 我的勋章
    暂无奖章