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 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 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 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个数进去依然满足，任意两个数的和不会和另外的两数和相等。 前面比赛的时候一直以…
UESTC 1264 人民币的构造 数论
人民币的构造 数论 Source 第七届ACM趣味程序设计竞赛第三场（正式赛）C My Solution tem+sum是当前的最大可以构出的值。 否则tem=sum;tem=2*(tem+sum)+1;新的最大值是tem+sum 1,3,9开始找规律1只能1，1、…
UESTC 1265 宝贵资源
宝贵资源 新手题 Source 第七届ACM趣味程序设计竞赛第三场（正式赛）A My Solution 看清楚是正方形好了，第一没注意就交了，浪费了20min的罚时，o(︶︿︶)o 唉新手嘛。 #include #include using namesp…
UESTC 1255 斓少摘苹果 贪心
斓少摘苹果 贪心 Source 第七届ACM趣味程序设计竞赛第二场（正式赛） C My Solution 第一想法是模拟，应该超时 只有最后一次可能是不到m个苹果 其它时候都是每次m个 所以总数sum，次数可能为(sum-1)/m+1…
UESTC 1253 阿里巴巴和n个大盗 博弈、策略
阿里巴巴和n个大盗 博弈、策略 Source 第七届ACM趣味程序设计竞赛第二场（正式赛） D My Solution 首先总人数是n+1人。 由于必须半数以上人同意才能通过方案，所以当剩余两个人时2号必死，因为1号…
