Posts

http://www.lydsy.com/JudgeOnline/problem.php?id=1607 题意：n个数，求对于每个数来说，其他n-1个数中是它约数的数的个数。

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）分钱的方案数。 思路：母函数.

http://acm.hdu.edu.cn/showproblem.php?pid=2082 题意：26个字母，第i个字母有x[i]个，价值为i.问能组成多少个价值不超过50的单词（注意这里的单词只考虑字母的组成，不考虑字母之间的顺序） 思路：母函数。

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种水果组成一个果盘，问方案数。

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个人可以分成若干组，每组人数都为素数，问有多少种分法。 思路：母函数。先预处理素数，记得多处理一点…

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块钱有多少种办法。 思路：母函数。

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）个点的二维坐标，问距离最远的两个点的距离是多少。

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個值，並將它們加總後輸出。

http://acm.hdu.edu.cn/showproblem.php?pid=1575 题意：A为一方阵，求(A^k)73得到的矩阵的主对角线的和。

http://www.lydsy.com/JudgeOnline/problem.php?id=2002 题意+思路： 同codeforces 13 E holes. 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年02月21日 星期日 02时29分39秒 4File Name :code/bzoj/2002.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=2E5+7; 34int n,m; 35int siz = 450; //sqrt(2E5) 36int a[N]; 37int pos[N]; 38int cnt[N]; 39int nxt[N]; 40int end[N]; 41 42 43void go( int x) 44{ 45 int ans = 0 ; 46 while (1) 47 { 48 if (x>=n) 49 { 50 printf("%d\n",ans); 51 break; 52 } 53 ans +=cnt[x]; 54 x = nxt[x]; 55// cout<<"nxt[x]:"<<nxt[x]<<endl; 56 } 57} 58void update ( int i,int j) 59{ 60 if (j>=n) 61 { 62 cnt[i]=1; 63 nxt[i]=n; 64 end[i]=i; 65 } 66 else 67 { 68 if (pos[i]==pos[j]) 69 { 70 cnt[i] = cnt[j] + 1; 71 nxt[i] = nxt[j]; 72 end[i]=end[j]; 73 } 74 else 75 { 76 cnt[i] = 1; 77 nxt[i] = j; 78 end[i] = end[j]; 79 } 80 } 81} 82int main() 83{ 84 #ifndef ONLINE_JUDGE 85 freopen("code/in.txt","r",stdin); 86 #endif 87 88 scanf("%d",&n); 89 for ( int i = 0 ; i < n ;i++) 90 { 91 scanf("%d",&a[i]); 92 pos[i] = i/siz; 93 } 94 95 for ( int i = n - 1 ; i >= 0 ; i--) update(i,i+a[i]); 96 97 scanf("%d",&m); 98 while (m--) 99 { 100 int opt; 101 scanf("%d",&opt); 102 if (opt==1) 103 { 104 int x; 105 scanf("%d",&x); 106 go(x); 107 } 108 else 109 { 110 int x,y; 111 scanf("%d %d",&x,&y); 112 a[x]=y; 113 update(x,x+a[x]); 114 int p = pos[x]*siz; 115 for ( int i = x-1 ; i >= p ; i--) update(i,i+a[i]); 116 } 117 } 118 119 #ifndef ONLINE_JUDGE 120 fclose(stdin); 121 #endif 122 return 0; 123}

http://codeforces.com/problemset/problem/13/E 题意：给你n个洞，进入某个洞后会跑到另一个洞，到了另一个洞之后又可能会继续到下一个洞，问你从一个洞进去，钻了几个洞才会出来，在哪个洞出来