- 博客(122)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 搭建 lamp环境【apache2.4.12 + php5.5.12 + mysql5.6.13】
centos 6.61. Apache/2.4.122. php 5.5.123. mysql 5.6.13# --------------------------------------------------------------------------------# prepare# 1. install g++yum list gcc-c++yum install
2015-08-04 15:05:46
1876
原创 HDU 4359 Easy tree DP? -- 我只能说是个dp
/* HDU 4359 Easy tree DP? 题意：求任意节点下左子树最大值小于右子树最大值的二叉树方案数 我只能说这是一个dp（rt） 状态：i个节点在满足不大于j深度有 dp[i][j] 种方案数 初始化： CLR(dp,0) dp[1][1~360] = 1 各种深度仅一个节点方案数为1 转移： （1）i个中挑一个为root 并
2013-10-12 09:57:48
908
原创 POJ 2443 Set Operation -- 位运算 + bitset
/* http://poj.org/problem?id=2443 POJ2443 Set Operation -- 位运算 + bitset 询问两个元素在不在同一个集合内 (在 ? yes : no)*/#include #include #include #include #include using namespace std;#def
2013-10-06 22:18:57
1274
原创 【解题报告】 HDU 4390 Number Sequence -- 容斥原理(不好理解)
/* HDU 4390 Number Sequence -- 容斥原理(不好理解) http://blog.csdn.net/acm_cxlove/article/details/8146102 n种球每种Ai个 {A1, A2, A3...An}放在m个盒子里，盒子不为空有多少种放法 先求出总的放法（允许为空），然后减去至少有一个盒子为空的放发 容斥原理可求出至少有一个盒子为空的
2013-09-23 14:18:48
870
原创 Poj 1845 Sumdiv -- A的所有约数和
/* Poj 1845 Sumdiv D(A)表示A的所有约数和,p表示A的素因数 A = pow(p1,n1)*pow(p2,n2)*...*pow(pn,nn) D(A) =( 1 + pow(p1,1) + pow(p1,2) + ... + pow(p1,n1))* ( 1 + pow(p2,1) + pow(p2,2) + ... + pow(p2,n2))
2013-09-18 11:23:12
812
原创 【解题报告】POJ 2449 Remmarguts' Date -- 有向图第k短路(有重边)
/* POJ 2449 Remmarguts' Date -- 有向图第k短路(有重边) 反向求单元点最短路(Dijkstra) 然后正向搜一遍 (用优先队列搞/A*)*/#include #include #include #include #include #include #include #include //#include using namespac
2013-09-18 10:08:51
1097
原创 【解题报告】NYOJ471 好多的树 -- 容斥原理
/* NYOJ471 好多的树 -- 容斥原理 求互质数对(0<i<n , 0<j<m)的个数 打表 f[i]表示有几个素因子,如果存在相同的则为-1(素因子一次不能多除) f[1]=0 f[2]=1 f[3]=1 f[4]=-1 f[5]=1 f[6]=2 f[7]=1 f[8]=-1 f[9]=-1 f[10]=2 然后就是解 if(f[i]>=0) ans
2013-09-12 21:06:27
1061
原创 【解题报告】HDU 4638 Group - 树状数组 + 求一段区间连续数字的段数
/* http://acm.hdu.edu.cn/showproblem.php?pid=4638 HDU 4638 Group - 树状数组 题意： 求一段区间连续数字的段数 [1 3 5 4 2] 询问(2,4)区间则3,5,4为连续序列输出 1 解法： 定义 线段 为 连续的数字段 定义 改变量deta 为 添加一个数字之后区间中线段增加或者减少了几个（其实就是-1
2013-08-19 15:31:40
1355
原创 【解题报告】HDU 4631 Sad Love Story 最短点距(动态)
/* http://acm.hdu.edu.cn/showproblem.php?pid=4631 Sad Love Story 最短点距 题意：点都是随机的 每加入一个点就求一个最短点距，然后将这些最短点距累加 最后输出 解法：用set维护坐标x的动态有序，然后插入一个点(x,y) 二分查一下它相邻的左边和右边， 然后逐个判断距离是否最小，直到 next_x * next_x >
2013-08-19 15:19:43
925
原创 【解题报告】fzu 1753 Another Easy Problem - 求150个组合数的最大公约数
/* http://acm.fzu.edu.cn/problem.php?pid=1753 fzu 1753 Another Easy Problem 求150个组合数（nCr(1 < n < 1e5 , 1 < r < 1e5)）的最大公约数 解法： 将一个组合数用大数表示法表示即 因子积的形式 然后求出每一个因子在每个组合数表示中最少个数即为最大公约数的大数表示*/#pra
2013-08-19 14:56:41
1306
原创 【解题报告】HDU 4679 Terrorist’s destroy -- 树形dp 删一边求两子树直径
/* HDU 4679 Terrorist’s destroy 给一棵树，任意删一条边，树分成了两个部分(a,b)，求min( max(a.直径,b.直径) * v.w ) 最大直径乘以边权 积的最小值 解法： 先找出整棵树的直径所在，即两个端点ds de 然后保存每个点到ds和de之间的距离 dds[] dde[] 然后从ds(de)开始搜 每个点保存子树中到de(ds)之
2013-08-19 14:36:21
1249
原创 【解题报告】POJ 1026 Cipher -- 置换群 轮换k次
/* POJ 1026 Cipher -- 置换群 轮换k次 给一个序列A{a1=4 a2=5 a3=3 a4=1 a5=2}和很多字符串 CDFET ... 按照A转换为 ETFCD (第一个到第四个，以此类推...) 再给一个k表示按照A序列规则转换k次 求最后的字符串 先求循环节 1 4 2 5 3 循环节长度的最小公倍数为 字符串转换的周期 这样在循环节内就知道哪
2013-08-05 21:34:18
1069
原创 【解题报告】POJ 3270 Cow 置换群基础 -- 轮换
/* POJ 3270 Cow 置换群基础 -- 轮换 题意： 给一个序列 A[1 8 9 7 6] 仅允许一次交换两个元素，交换代价为两个数字之和 求最小的代价和使得序列有序（递增） 元素不会重复 方法： 我们很容易算出 排序后的结果为A'[1 6 7 8 9] 也就是让A序列通过交换变为A'序列， 不过我们在这里尝试反过来考虑，将A'变为A A' [1 6 7 8 9] A
2013-08-03 21:44:51
1142
原创 【解题报告】HDU 4616 Game - 树形dp
/* dp[node][i][0]: node节点 在 消耗i陷阱时 并从该节点往下走（或者理解为还有能力往下走）的最大权值 dp[node][i][1]: node节点 在 消耗i陷阱时 并从子节点往上走（到该节点或者理解为没有能力接着走了）的最大权值*/#pragma comment(linker,"/STACK:102400000,102400000")#incl
2013-07-29 11:05:12
1717
原创 【解题报告】 ZOJ 3641 Information Sharing - 并查集+模拟
/* ZOJ 3641 Information Sharing 并查集+模拟 题意：给出了一些人对应了几个数字（information） 然后又有一些人会分享数字（share information）分享是双向的，取并集 最后会问某些人在此刻拥有哪些数字（information he has gotten） 做法：由于数字的个数才1000（at most 1000 distinct in
2013-07-23 23:35:57
953
原创 【解题报告】 ZOJ 3640 Help Me Escape - 期望dp
#include #include #include #include #include #include #include #include #include #define CLR(c,v) memset(c,v,sizeof(c))using namespace std;const int N = 2e4 + 5;const int INF = (1<<30);
2013-07-23 23:33:39
1772
原创 HDU 4565 -- So Easy! 数学 && 2013 ACM-ICPC 长沙赛区全国邀请赛 A题
题目要求这个得值但是取模前有更号，所以无法直接计算，我们发现015, (a-1)2< b 2, 0 31所以 0 | a+sqrt( b ) | 可得表达式：，由二项式展开可知等号右边一坨是整数并且加的数小于一，所以等式成立然后我们设 Kn 为为等号的左边，将表达式化为递推形式后，再利用矩阵连乘来解决 Kn 的问题转化过程就是移两次项，每次都将指数约去即可化简，
2013-06-03 13:59:50
3645
3
原创 HDU 3729 I'm Telling the Truth -- 二分图最大匹配 输出方案
/* http://acm.hdu.edu.cn/showproblem.php?pid=3729 I'm Telling the Truth 二分图最大匹配*/#include #include #include #include using namespace std;#define CLR(c,v) memset(c,v,sizeof(c))const int N =
2013-05-17 21:54:25
891
原创 2013河南省赛总结
省赛总结 第一次参加省赛，而且这一次省赛在我们学校体育馆里举办（PS：这次有120+个队伍参加比赛，而且比赛形式也完全依照icpc的标准）。作为东道主，自然要多操劳一些事情啦，我提供web打印代码的技术支持..... 周六下午来到体育馆参加热身赛，第一次看到这么多队伍比赛，有点激动啊，刚进赛场还被志愿者给挡外面了，因为没有穿粉红色的队服，好在有熟人给我招呼了一下，不然又给耽
2013-05-17 21:52:36
1083
2
原创 NYOJ 61 传纸条 && NYOJ 712 探寻宝藏 -- 双线dp
/* http://acm.nyist.net/JudgeOnline/problem.php?pid=61 传纸条 http://acm.nyist.net/JudgeOnline/problem.php?pid=712 探 寻 宝 藏 题意：给一个矩阵，求两条不相交的线从左上角到右下角经过的元素的最大和 双线dp - 即同时考虑两条不相交的线，使其线上的和最
2013-05-15 21:56:39
1432
原创 xjoj146 快速刷屏 -- 简单dp 居然没想到dp打表
主要是看到题目中说的字符串最多1w个，如果打表暴力的话应该是1w*5k的复杂度，就没继续下去了，结束之后发现的确是这个思路。。。。好囧啊，希望以后不要这样子了。/*http://202.117.21.117/xjoj/problem_html/146.html 快速刷屏dp[i] : 长度为i最短需要多少时间dp[i] = min(dp[i-1] + 1 , dp[j] + time*2
2013-05-09 23:23:52
1186
原创 CodeForce 280C Game on Tree -- 树形dp求期望
http://codeforces.com/problemset/problem/280/C/* codeforce game of tree 给你一棵树，你可以随机选择一个点，然后将这个点及其子树全部删去 问删去操作的期望数 将每个点的深度分之一 相加为结果*/#include #include #include #include #define CLR(c,v) (me
2013-05-06 23:50:56
858
原创 POJ 3311 Hie with the Pie -- TSP 状态压缩dp
/* http://poj.org/problem?id=3311 Hie with the Pie 旅行商问题，状态压缩的dp*/#include #include #include #include #include #include using namespace std;#define CLR(c,v) memset(c,v,sizeof(c))template
2013-05-06 23:08:42
768
原创 POJ 1080 Human Gene Functions -- dp最长公共子序列 (变体)
/* http://poj.org/problem?id=1080 Human Gene Functions 最长公共子序列 (变体) dp[i][j]: x串为i长度 y串为j长度 的最大匹配值*/#include #include #include #include #include #include #include #define CLR(c,v) (memse
2013-05-05 11:50:34
730
原创 NYOJ 304 节能 -- 区间dp
/* http://acm.nyist.net/JudgeOnline/problem.php?pid=304 节能 一个区间里面有很多不重复的灯，机器人从其中一个灯开始关灯。 给出灯和原点的距离 和 灯的功率，问机器人从开始关灯到关灯结束总共浪费的电能 机器人每秒移动一米。 因为各个灯消耗的电能不一样，所以机器人的关灯的选择有一定策略 思路 区间dp dp[i][j][0]
2013-05-05 11:37:50
1264
原创 NYOJ 674 善良的国王 -- 树形dp
/* http://acm.nyist.net/JudgeOnline/problem.php?pid=674 善良的国王 题意：有一棵树希望留下m个节点，问最少需要删除几条边 思路：树形dp 状态 dp[i][j] : 在以i节点为根的树（单独考虑这个树）下，留下 j 个点（包括i）最少需要删除几条边 初始化 dp[i][1] : 在 i 节点下，只留下1个点，则最少要删
2013-05-02 13:22:55
767
原创 POJ 1036 Gangsters -- 常规dp 题意好难懂啊
/* http://poj.org/problem?id=1036 Gangsters翻译： N 个盗贼去一个饭店，第i个盗贼在Ti时间来，他拥有Pi的财富。这个饭店的门有K+1种开放的状态，用[0,K]表示。这些状态能够被一个盗贼改变在一个时间单位内，要么把它打开，要么把它关闭，或者就是维持原状。在初始时刻这些门都是关闭着的。第i个盗贼进入了饭店仅当这个门是专门为他所开放的时
2013-04-29 23:24:09
938
转载 【转】经典动态规划题集
1014* Dividing 半个背包，注意中断1036 Gangsters1038* Bugs Integrated, Inc. 状态压缩1050 To the Max 最大子矩形1080 Human Gene Functions1088 滑雪1141* Brackets Sequence 括号序列1157 LITTLE SHOP OF F
2013-04-29 15:31:49
1011
原创 HDU 1251 统计难题 -- 字典树
1251 ( 统计难题 )#include #include #include #include #include #include using namespace std;const int MAX_26 = 26;const int MAX_TREE = 390010;#define FORi_26 for(int i=0;i<MAX_26;i++)struct Tr
2013-04-26 10:28:09
646
原创 第一届校赛总结NYIST（专业组）
校赛总结对于昨天校赛，我感觉准备的比较匆忙，在比赛的前一天晚上还在装系统，装打印机，修改一些关于比赛的程序（当然我也在帮忙，可见咱acm的人数还是少啊），甚至在比赛前半小时，有电脑里面还没有比赛必用的软件，不得已将比赛延时半小时了。我认为造成比赛延时的根本问题在于准备过程没有按照相关计划（或者压根没有指定相关计划）执行，导致了很多原本早应该完成的工作拖到后面去做，直到比赛前一个小时。在
2013-04-24 10:38:57
973
原创 【解题报告】NYOJ 679 贪婪的商店 -- 树形dp 裸的很
/* http://acm.nyist.net/JudgeOnline/problem.php?pid=679 贪婪的商店 最短路 或者 树形dp 很裸的树形dp，要买一件东西，需要再买某些物品，问最少需要花多少钱才能买到那件东西*/#include #include #include #include #include #include #include
2013-04-23 22:42:15
854
原创 148D Bag of mice - 简单概率dp
/* http://codeforces.com/contest/148/problem/D Bag of mice 题意：两个人抓老鼠，老鼠只有黑的或白色的。 骑士抓老鼠的时候会吓跑一只老鼠，公主抓老鼠的时候不会吓跑老鼠 谁先抓到白老鼠谁胜。 求公主胜的概率，如果没有白老鼠可抓，则定义为公主输 思路：定义两个数组 dp[w][b][0]表示在w白老鼠b黑老鼠情况中公主胜的概率，
2013-04-19 21:20:29
607
原创 HDU 2043 密码 -- 虽然是水题（取反的时候高位变1）
http://acm.hdu.edu.cn/showproblem.php?pid=2043 密码虽然是水题，但是因为位运算长度为32位，所以取反的时候高位 变1，调了我好久。。。#include #include #include #include #include #include #include using namespace std;#define CLR(c,v) me
2013-04-18 01:39:35
817
原创 HDU 1520 Anniversary party -- 树形dp 好题目
/* http://acm.hdu.edu.cn/showproblem.php?pid=1520 Anniversary party 比较典型的树形dp，好题目!!! 给一棵树，要求取某一个节点（每一个点有权值）时不能取对应的父节点和子节点，问满足条件的方案权值最大为多少。 定义状态dp[i][0]表示不取i节点时的最大权值，dp[i][1]表示取i节点时的最大权值。 所以 dp[f
2013-04-10 19:35:46
688
原创 HDU 1011 Starship Troopers - 01树形dp 有坑啊！！
/* http://acm.hdu.edu.cn/showproblem.php?pid=1011 Starship Troopers 01树形dp 题意：多个舰队，攻打bug的洞穴，每一个洞穴里面有很多bug和一些brain，我们需要派一个舰队去获得更多的brain 这个过程我们遵循：洞穴为一个树形结构（没有环），洞穴的入口为1(root节点)，如果洞穴i在洞穴j的前面， 则必须先进攻
2013-04-09 18:19:56
697
原创 HDU 3236 Gift Hunting - 分组背包 相当于两个01背包
/* http://acm.hdu.edu.cn/showproblem.php?pid=3236 Gift Hunting 题意：某人有两张卡，卡上的钱不能合并消费，买东西的时候物品有两个属性，一个是必须买的（即girlfriend need） 还有一个不是必须买的，同一样物品用不同的卡消费相同并且只能购买一次，我们需要最大的价值(即happy值). 思路: 分组背包，现将必买的东
2013-04-09 18:17:31
1159
原创 HDU 4501 小明系列故事——买年货 -- 分组背包变体
/* http://acm.hdu.edu.cn/showproblem.php?pid=4501 小明系列故事——买年货 题意：一个现金，一个优惠积分，都可以购买东西，并且只需要其中一个满足物品的消耗即可购买 另外可以免费挑选1-5个商品赠送 求最大的收益价值 每种物品给出三个消费（现金消耗，积分消耗，免费权消耗），但是这三个消费并不是同时需要满足， 所以我们可以将这个问题转化为一个
2013-04-09 08:25:37
1089
原创 pid=1009 FatMouse' Trade - 简单贪心
题意：用后面的换前面的，尽可能换取更多，物品可以拆分。/* http://acm.hdu.edu.cn/showproblem.php?pid=1009 FatMouse' Trade 简单贪心*/#pragma comment(linker, "/stack:64000000")#define _CRT_SECURE_NO_DEPRECATE#include #include
2013-04-08 09:16:03
672
原创 HDU 1561 The more, The Better - 依赖背包+树形dp基础
/* http://acm.hdu.edu.cn/showproblem.php?pid=1561 The more, The Better 依赖背包 -> 树形dp题意： 给一个树形结构，问最多拿max个城市 ，能获得的最大价值多少，拿下面的一定要先拿上面的。解题思路：定义状态dp[i][j] : 当前i节点及其子树下最多选择j个城市的最大值为dp[i][j];我们考虑到特殊状态：i
2013-04-08 08:03:27
3562
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人