April Fools Day Contest 2014 H. A + B Strikes Back
H. A + B Strikes Back My Solution I am glad to come over the interesting problem.^_^ After 5 times of WA, I get a real test and Accepted. #include #include using namespace std…
UESTC 1034 AC Milan VS Juventus 分情况讨论
AC Milan VS Juventus 分情况讨论 Source The 13th UESTC Programming Contest Preliminary The question is from here. My Solution 分情况讨论清楚就好，然后注意 a == b 的时候也是 No 把分类出来的区间理…
BestCoder Round #75 King’s Order dp：数位dp
King's Order 数位dp Source The question is from BC and hduoj 5642. My Solution 数位dp 状态： d[i][j][k] 为处理完i 个字符 , 结尾字符为′a′+j , 结尾部分已重复出现了 k 次的方案数; 边界：d[1][j][…
UESTC 1144 Big Brother 二分图、最大匹配
Big Brother 二分图、最大匹配 Source 2015 UESTC Training for Graph Theory The question is from here. My Solution 最大匹配问题 匈牙利算法， (似乎也可以用它的改进版，Hopcroft-Karp算法) #includ…
BestCoder Round #75 King’s Cake 模拟&&优化 || gcd
King's Cake 模拟 优化 gcd source The question is from BC and hduoj 5640. My Solution //A really easy problem, I get a Runtime Error(STACK_OVERFLOW) first, then Time Limit Exceeded //next Runtime E…
UESTC 1282 被兵暴的沈宝宝 Catalan数、逆元
被兵暴的沈宝宝 Catalan数、逆元 Source UESTC 1282 （CDOJ 1282） MySolution 卡特兰数经典模型 化简版的递推式是白书上看来的，f2 = f3 = 1 ,卡特兰数从 f3 开始 然后 f(i+1) = (4*i-6)*f(i)/i; 结合拓展欧几里得…
UESTC 1063 秋实大哥与妹纸 二叉堆(小根堆)
秋实大哥与妹纸 二叉堆(小根堆) Source 2015 UESTC Training for Data Structures The question is from here. My Solution Memory Limit: 1500/1500KB (Java/Others) 卡内存的题目，第一次遇到 (┬＿┬) 维…
UVa 11400 Lighting System Design dp : 线性结构上dp LIS
Lighting System Design dp : 线性结构上dp LIS The question is from here. My Solution 首先这个题目是要保持总灯泡数不变的，一定是换一个上去才可以，是在这个情况下money-saving，而不管energy-saving。所以把…
UVa 11997 K Smallest Sums 优先队列 打有序表 归并
UVa 11997 K Smallest Sums 优先队列 打有序表 归并 The question is from here. My Solution 把每个数组排序以后打个 有序表 表1: A1 + B1 <= A1+B2 <= A1+B3 <= `````````` 表2: A2 + B1 <= `````` …
UVa 1218 Perfect Service dp：树上dp 状态转移方程的优化
UVa 1218 Perfect Service 树上dp 状态转移方程的优化 The question is from here. 与这个题目 UVa 1220 Party at Hali-Bula dp：树的最大独立集写法很像，虽然各有不同； My Solution 状态定义：d[u][0] 表示u是服…
UVa 1220 Party at Hali-Bula dp：树的最大独立集
UVa 1220 Party at Hali-Bula dp：树的最大独立集 The question is from here. My Solution 注意点：这个题目有些测试数据是先出现father再出现son的，如 5 jack jill black black jack kar pur pur black …
UVa 12186 Another Crisis dp：树上dp
UVa 12186 Another Crisis 树上dp The question is from here. My Solution d(i)表示给上级发信至少需要多少工人。把所有子结点的d值排序然后取前c个， 对除非的处理 ★★ c = (k*T - 1) /100 +1; 用前向星储存树 每…
UESTC 1137 邱老师选妹子 dp：？这个难道不是暴力法
邱老师选妹子 dp：这个难道不是暴力法 Source 2015 UESTC Training for Dynamic Programming The question is from here. My Solution 暴力法分分钟过，只是不知道为什么，这个是在dp专题，☺☺ 暴力的话 10^6*6…
UVa 10003 Cutting Sticks dp : 线性dp triangulation三角剖分
UVa 10003 Cutting Sticks 线性dp triangulation三角剖分 The question is from here. My Solution 线性dp 三角剖分类题目的经典吧， 状态：d[ i ][ j ] 表示切割 i - j 这一段的最小费用 ，0 <= i < j <=…
UESTC 1131 男神的礼物 dp：最优矩阵链乘 triangulation 双dp
男神的礼物 最优矩阵链乘 triangulation 双dp Source 2015 UESTC Training for Dynamic Programming My Solution 这是一个经典的最优矩阵链乘问题，只不过单个费用会改变，像是2个dp搞在一起，是把单个的min…
UVa 11584 Partitioning by Palindromes 线性结构上dp LIS
UVa 11584 Partitioning by Palindromes 线性结构上dp LIS The question is from here. My Solution d[ i ] = min{ d[ j ]+1 | is[j+1][i]是回文串 }; d[ i ] 表示0~i 内回文串的最小个数; 然后对于is[ j+1 ][ i ]…
UVa 12563 Jin Ge Jin Qu hao 0-1背包问题
UVa 12563 Jin Ge Jin Qu hao 0-1背包问题 The question is from here My Solution： 刘老师给了我们那么多的数据是为了告诉我们: 歌曲的总时间不会超过 n*180-1+678 及 50*180-1+678 = 9677 并不像题中的t <= 1…
UESTC 766 乐乐和球球 博弈 暴力(也可以不用暴力法)
乐乐和球球 博弈 暴力(也可以不用暴力法) My Solution 首先 N>=K 的情况应该是 拿空N-K 然后加上 C 当 N=C 则，为C 如果 (K/N)*N=C 则 i+C 如果t…
UESTC 1251 谕神的密码 贪心
谕神的密码 贪心 Source 第七届ACM趣味程序设计竞赛第二场（正式赛）B My Solution w9=s/9; y9=s-w9*9; 贪心， 最大的前面999....y9...最小的前面为1.......y9 99999 主要是上面这样，然后有几个地方y9=…
UESTC 1262 Memory 暴力法
Memory 暴力法 Source 第七届ACM趣味程序设计竞赛第三场（正式赛）E My Solution 思路是已经有i-1个满足条件的数，再加第i个数进去依然满足，任意两个数的和不会和另外的两数和相等。 前面比赛的时候一直以…
