ACM

http://poj.org/problem?id=3734 题意+思路同******hdu2065红色病毒解题报告 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年02月27日 星期六 16时39分53秒 4File Name :code/poj/3734.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const LL MOD =1E4+7; 34LL n; 35LL res; 36LL ksm(LL a,LL b) 37{ 38 LL res = 1; 39 while (b) 40 { 41 if (b&1) res=(res*a)%MOD; 42 b = b>>1; 43 a = (a*a)%MOD; 44 } 45 return res; 46} 47int main() 48{ 49 #ifndef ONLINE_JUDGE 50 freopen("code/in.txt","r",stdin); 51 #endif 52 53 54 int T; 55 cin>>T; 56 while (T--) 57 { 58 scanf("%lld",&n); 59 60 LL ans = ksm(4,n-1)+ksm(2,n-1); 61 ans %=MOD; 62 printf("%lld\n",ans); 63 64 } 65 66 67 68 #ifndef ONLINE_JUDGE 69 fclose(stdin); 70 #endif 71 return 0; 72}

http://acm.hdu.edu.cn/showproblem.php?pid=2065 题意：a,b,c,d四种元素，a,c只能出现偶数次（包括0次），b,d没有限制，问n个（2^64）个元素有多少种不同的组合。 思路：指数型母函数。。。n大的没办法用之前的办法做。

http://www.lydsy.com/JudgeOnline/problem.php?id=1610 题意：给出n个点，问有多少条直线，这些之间之间都不平行。 思路：求斜率（注意考虑斜率不存在），看有多少种斜率。 妈蛋。。。。斜率不存在是横坐标相等啊，不是纵坐标啊。。。蠢哭了好么。。。。。。

http://www.lydsy.com/JudgeOnline/problem.php?id=1607 题意：n个数，求对于每个数来说，其他n-1个数中是它约数的数的个数。 思路：类似筛法，从小到大处理，数i对其所有倍数的数的答案有cnt[i]的贡献 。最后记得把自己是自己的约数的情况减掉。

http://acm.hdu.edu.cn/showproblem.php?pid=1521 题意：有n种物品，并且知道每种物品的数量。要求从中选出m件物品的排列数。例如有两种物品A,B，并且数量都是1，从中选2件物品，则排列有"AB",“BA"两种。

从这里母函数（Generating function）详解学习了普通型母函数 1#include <iostream> 2using namespace std; 3// Author: Tanky Woo 4// www.wutianqi.com 5const int _max = 10001; 6// c1是保存各项质量砝码可以组合的数目 7// c2是中间量，保存没一次的情况 8int c1[_max], c2[_max]; 9int main() 10{ //int n,i,j,k; 11 int nNum; // 12 int i, j, k; 13 14 while(cin >> nNum) 15 { 16 for(i=0; i<=nNum; ++i) // ---- ① 17 { 18 c1[i] = 1; 19 c2[i] = 0; 20 } 21 for(i=2; i<=nNum; ++i) // ----- ② 22 { 23 24 for(j=0; j<=nNum; ++j) // ----- ③ 25 for(k=0; k+j<=nNum; k+=i) // ---- ④ 26 { 27 c2[j+k] += c1[j]; 28 } 29 for(j=0; j<=nNum; ++j) // ---- ⑤ 30 { 31 c1[j] = c2[j]; 32 c2[j] = 0; 33 } 34 } 35 cout << c1[nNum] << endl; 36 } 37 return 0; 38} ① 、首先对c1初始化，由第一个表达式(1+x+x^2+..x^n)初始化，把质量从0到n的所有砝码都初始化为1.

http://acm.hdu.edu.cn/showproblem.php?pid=1284 题意：有1分，2分，3分的钱若干，问组成n（n<=32767）分钱的方案数。 思路：母函数. 需要注意的是多组数据。每次都搞会TLE，可以先预处理出来存到数组里，每次直接调用。如果预处理时间也还是慢的话，可以先跑出来，然后打表。这算一个小tip吧2333

http://acm.hdu.edu.cn/showproblem.php?pid=2082 题意：26个字母，第i个字母有x[i]个，价值为i.问能组成多少个价值不超过50的单词（注意这里的单词只考虑字母的组成，不考虑字母之间的顺序） 思路：母函数。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年02月27日 星期六 15时56分31秒 4File Name :code/hdu/2082.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E4; 34LL a[N],tmp[N]; 35int x[N]; 36int n; 37int main() 38{ 39 #ifndef ONLINE_JUDGE 40 freopen("code/in.txt","r",stdin); 41 #endif 42 43 44 ios::sync_with_stdio(false); 45 int T; 46 cin>>T; 47 while (T--) 48 { 49 for ( int i = 1; i <= 26 ; i ++) cin>>x[i]; 50 51 ms(tmp,0); 52 ms(a,0); 53 for ( int i = 0 ; i <= x[1]; i++) 54 { 55 a[i] = 1; 56 } 57 // cout<<"aaa"<<endl; 58 int cur = x[1]*1; 59 for ( int i = 2 ; i <= 26 ; i++) 60 { 61 for ( int j = 0 ; j<= cur ; j++) 62 { 63 for ( int k = 0 ; k <= x[i] ; k++) 64 { 65 tmp[j+i*k]+=a[j]; 66 } 67 } 68 69 cur += x[i]*i; 70 71 // cout<<"bbb:"<<endl; 72 73 for ( int j = 0 ; j <= cur ; j++) 74 { 75 a[j] = tmp[j]; 76 tmp[j] = 0 ; 77 } 78 } 79 // cout<<"asdsad"<<endl; 80 LL ans = 0LL ; 81 for ( int j = 1 ; j <= 50 ; j++) 82 { 83 ans += a[j]; 84 } 85 cout<<ans<<endl; 86 } 87 88 #ifndef ONLINE_JUDGE 89 fclose(stdin); 90 #endif 91 return 0; 92}

http://acm.hdu.edu.cn/showproblem.php?pid=5616 题意：有n个（n<=20）砝码，第i个重量为w[i]，给出m个查询，每个查询一个重量，问这个重量能否被称量出。 思路：暴力（没美感），01背包（不会），母函数（瞬间成了傻逼题）和这题很像 hdu1709 balance hdu1709解题报告

http://acm.hdu.edu.cn/showproblem.php?pid=2152 题意：中文题目，大概是说有n（<=100）种水果，第i种至少拿l[i]个，最多拿r[i]个，现在挑选m种水果组成一个果盘，问方案数。 思路：母函数，之前的题目都是只对上界有限制，其实对下界有限制是一样的。以及。。。一开始以为是拿100元买。。。后来发现是“一打百元大钞”23333 其实再出难点可以对个数以及钱数都有限制。。。。

http://acm.hdu.edu.cn/showproblem.php?pid=2069 题意：有1,5,10,25,50面值的硬币若干，问组成n元钱有多少种不同的方案。一个额外的要求是硬币的总是不能超过100.（那句 your program should be able to handle up to 100 coins.真的是这个意思。。。？感觉好坑。。。）

http://acm.hdu.edu.cn/showproblem.php?pid=1709 题意：有n个砝码，第i个的重量为w[i]，问从1到sum(所有砝码的重量之和)那些重量无法称量。（所有质量都是整数） 思路：母函数。 一个砝码可以看做有三种状态，放，放左边（+），放右边（-）

http://acm.hdu.edu.cn/showproblem.php?pid=2189 题意：n个人可以分成若干组，每组人数都为素数，问有多少种分法。 思路：母函数。先预处理素数，记得多处理一点… 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年02月26日 星期五 16时24分17秒 4File Name :code/hdu/2189.cpp 5************************************************ */ 6 7#include <cstdio>muhanshu 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=155; 34int pri[N]; 35int a[N],tmp[N]; 36int cnt; 37int n; 38 39bool judge ( int n) 40{ 41 if (n<=3) return true; 42 for ( int i = 2 ; i*i <= n ; i++) 43 { 44 if (n%i==0) return false; 45 } 46 47 return true; 48} 49 50 51void pre() 52{ 53 cnt = 0; 54 for ( int i = 2 ; i <= 200 ; i++) 55 { 56 if (judge(i)) 57 pri[++cnt] = i; 58 } 59} 60int main() 61{ 62 #ifndef ONLINE_JUDGE 63 freopen("code/in.txt","r",stdin); 64 #endif 65 66 67 int T; 68 pre(); 69 scanf("%d",&T); 70 while (T--) 71 { 72 scanf("%d",&n); 73 74 ms(a,0); 75 for ( int i = 0 ; i <= n ; i+=2 ) 76 { 77 a[i] = 1; 78 tmp[i] = 0; 79 } 80 81 82 for ( int i = 2 ; pri[i] <= n ; i++) 83 { 84 for ( int j = 0 ; j <= n ; j++) 85 { 86 for ( int k = 0 ; k + j <= n ; k +=pri[i]) 87 { 88 tmp[j+k] +=a[j]; 89 } 90 } 91 for ( int j = 0 ; j <= n ; j ++) 92 { 93 a[j] = tmp[j]; 94 tmp[j] = 0; 95 } 96 } 97 98 printf("%d\n",a[n]); 99 } 100 101 #ifndef ONLINE_JUDGE 102 fclose(stdin); 103 #endif 104 return 0; 105}

http://acm.hdu.edu.cn/showproblem.php?pid=1085 题意；一元的钱有num_1张，2元的钱有num_2张，5元的钱有num_5张，问最小的不能组成的钱是多少。 思路：有限个个数的母函数，并且不知道最好要多少，所以限制条件变成了不同种类钱的个数。统计0到num_1+2num_2+5num_5的方案数，第一个为0的就是答案。

http://acm.hdu.edu.cn/showproblem.php?pid=1398 题意：所有的货币都是平方数，比如1,4,9…问凑出n块钱有多少种办法。 思路：母函数。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年02月25日 星期四 22时15分31秒 4File Name :code/hdu/1398.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=305; 34int a[N],tmp[N]; 35int n; 36int main() 37{ 38 #ifndef ONLINE_JUDGE 39 freopen("code/in.txt","r",stdin); 40 #endif 41 42 while (scanf("%d",&n)!=EOF&&n) 43 { 44 for (int i = 0 ; i <= n ;i++) 45 { 46 a[i] = 1; 47 tmp[i] = 0 ; 48 } 49 50 for ( int i = 2 ; i*i <= n ; i ++) 51 { 52 for ( int j = 0 ; j <= n ; j++) 53 { 54 for ( int k = 0 ; k+j <= n ; k+=i*i) 55 { 56 tmp[j+k] += a[j]; 57 } 58 } 59 60 for ( int j = 0 ; j <= n ;j++) 61 { 62 a[j] = tmp[j]; 63 tmp[j] = 0 ; 64 } 65 } 66 67 printf("%d\n",a[n]); 68 } 69 70 #ifndef ONLINE_JUDGE 71 fclose(stdin); 72 #endif 73 return 0; 74}

http://acm.hdu.edu.cn/showproblem.php?pid=1028 题意：求整数拆分数。 思路：母函数模板题。关于母函数的学习：http://www.cnblogs.com/syxchina/archive/2011/07/07/2197205.html http://www.cppblog.com/tanky-woo/archive/2010/08/02/121969.html

http://poj.org/problem?id=2926 题意：给出n(1E5)个五维空间内的坐标…问最远的两个点距离多少。 思路：拆点即可。去绝对值。可以由二维空间推广到k维空间。一个点可以拆成2^(k-1)个点。 具体见代码。

http://acm.split.hdu.edu.cn/showproblem.php?pid=5626 题意：给出n（1E6）个点的二维坐标，问距离最远的两个点的距离是多少。 思路：对曼哈顿距离进行变换。 先看曼哈顿距离的定义 |x1−x2|+|y1−y2| 拆绝对值 x1−x2+y1−y2或x1−x2+y2−y1

http://www.lydsy.com/JudgeOnline/problem.php?id=1604 题意：了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的N(1≤N≤100000)只奶牛，你会发现她们已经结成了几个“群”．每只奶牛在吃草的时候有一个独一无二的位置坐标Xi，Yi(l≤Xi，Yi≤[1．.10^9]；Xi，Yi∈整数．当满足下列两个条件之一，两只奶牛i和j是属于同一个群的： 1．两只奶牛的曼哈顿距离不超过C(1≤C≤10^9)，即lXi - xil+IYi - Yil≤C. 2．两只奶牛有共同的邻居．即，存在一只奶牛k，使i与k，j与k均同属一个群． 给出奶牛们的位置，请计算草原上有多少个牛群，以及最大的牛群里有多少奶牛

http://140.114.86.238/problem/10925/ Description 有兩個序列S1和S2，各有N個元素。當我們在S1,S2各取一個數字時，總共會有NN這麼多可能的”和”(sum)。請找出這NN這麼多和裡最小的N個值，並將它們加總後輸出。