ACM

2016HUAS_ACM暑假周测4 - A - 度熊哈希值问题

2016HUAS_ACM暑假周测4 - A - 度熊哈希值问题
哈希值问题。一看就应该知道用线段树可以AC。但是一开始想着用long long存应该没问题,就用一个数组存下了从1到这个数的乘积。用的时候用后面的位置除以前面位置-1的值就好了。但是竟然。。。Runtime Error(INTEGER_DIVIDE_BY_ZERO),怎么可能会有0作被除数的情况,这不科学啊?难道溢出了?诶。算了。还是线段树吧,然后就AC了。。。只不过这线段树不够优啊,happy_... 继续阅读 »
ACM

2016HUAS_ACM暑假集训4 - H - 组合

2016HUAS_ACM暑假集训4 - H - 组合
经典的尼姆博弈。有三堆各若干个物品,两个人轮流从某一堆取任意多的物品,规定每次至少取一个,多者不限,最后取光者得胜。关于博弈的问题,AleiChen的博客写的不错,可以去看看。题目:飞机票直达(H - 组合)代码:Memory: 1728 KBTime: 0 MSLanguage: C++Result: Accepted#include <i... 继续阅读 »
ACM

2016HUAS_ACM暑假集训4 - J - 组合

2016HUAS_ACM暑假集训4 - J - 组合
经典威佐夫博弈问题。有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。公式: p =[(b-a)(1+√5)/2] (b>a)题目:飞机票直达(J - 组合)代码:Memory: 176 KBTime: 16 MSLanguage: C++Result: Accepted#include&... 继续阅读 »
ACM

2016HUAS_ACM暑假集训4 - M - 基础DP

2016HUAS_ACM暑假集训4 - M - 基础DP
经典的0/1背包问题,使用递推公式。从最后一个物件拿还是不拿开始往前推。一开始看0/1背包的知识点是说用二维数组。这样是直观一点,初学好理解。但是后面看还可以空间优化,使用一维数组更好。递推公式:dp[i][j]=j<w[i]?dp[i-1][j]:max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);dp[i][j]代表拿(这里用拿还不妥当,用“考虑”比较好... 继续阅读 »
ACM

2016HUAS_ACM暑假集训4 - F - 数论

2016HUAS_ACM暑假集训4 - F - 数论
这个题的题目意思是找有没有安全的洞窟。题目每行包括一个m , 一个n。意味着有n个洞,狼会每m个洞查看一次。可以发现:1、当m或者n为1的时候是没有安全的洞窟的。2、当m和n都为偶数的时候,偶数洞窟会出现安全洞窟(因为标号是从0开始的)。3、当m或者n能互相被整除的时候也会出现安全洞窟,因为狼只是在不断循环找重复的洞而已。4、其他情况皆为没有安全洞窟。题目:飞机票直达(F - 数论)代码:Memo... 继续阅读 »
ACM

2016HUAS_ACM暑假集训4 - D - 计数,排列(错排公式)

2016HUAS_ACM暑假集训4 - D - 计数,排列(错排公式)
这个题是错排公式啊,一直不知道在那里推推推,怎么推都是错的。然后看错排公式,还不是一眼就懂什么意思。D(n) = (n-1) [D(n-2) + D(n-1)]特殊地,D(1) = 0, D(2) = 1.我们可以设定n个信封进行排列。1 2 3 4 5 6 7 8 9 10 ... n拿一个出来,因为要排错,自己正确的位置不能选,所以有n-1种位置可以选。选完之后又分两种情况。第一种(这种情况好... 继续阅读 »
ACM

2016HUAS_ACM暑假集训4 - C - 递推

2016HUAS_ACM暑假集训4 - C - 递推
计算网格,我们可以先考虑只有一行的情况。1、只有1方格个的时候是12、2个的时候是2个小方格,大方格包含在1的小方格里面,已经计算过了,所以是2+13、3个的时候是3个小方格,大方格包含在1和2的小方格里面,已经计算过了,所以是3+2+14、4个的时候是4个小方格,大方格包含在1和2和3的小方格里面,已经计算过了,所以是4+3+2+1......依次类推是一个等差数列求和的公式,可得ans=(1+... 继续阅读 »
ACM

2016HUAS_ACM暑假集训4 - B - 递推

2016HUAS_ACM暑假集训4 - B - 递推
这个题目多画几个三角形就得出规律了,废话不多说上图:因为要面最多,所以我们在画这个三角形的时候要尽可能和每个三角形的(两条相交的)边都相交。这样每次都会在前一次的基础上加上前一次加6的[个数加一]。得出规律后知道除了2外,这是一个等比数列,求和就行。题目:飞机票直达(B - 递推)代码:Memory: 1728 KBTime: 15 MSLanguage: C++Re... 继续阅读 »
ACM

2016HUAS_ACM暑假集训4 - A - 递推

2016HUAS_ACM暑假集训4 - A - 递推
这个题目其实就是一个求组合公式的问题,《算法竞赛入门经典(第二版)》320页有介绍。还有就是要取模,这个在存的时候一边取模一遍存比较好,防止溢出。题目:飞机票直达(A - 递推)代码:Memory: 17224 KBTime: 46 MSLanguage: C++Result: Accepted#include <iostream>... 继续阅读 »
ACM

2016HUAS_ACM暑假周测3 - G - A + B Problem II

2016HUAS_ACM暑假周测3 - G - A + B Problem II
G - A + B Problem II像这种大数问题不能直接把它看成是数的,要用字符来处理,这题用三个数组会是0MS,但是我用了stack,所以花了15MS,但是这个题被格式弄PE好几次。。。题目:飞机票直达(G - A + B Problem II)Memory: 1748 KBTime: 15 MSLanguage: C++Result: A... 继续阅读 »