ACM

题目链接 题意：如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关—— 1、整数中某一位是7； 2、整数的每一位加起来的和是7的整数倍； 3、这个整数是7的整数倍；

题目链接 题意：给出n，问[1,n]中，满足包含“13”且这个数（不是各位的和）能被13整除的数的个数。 思路：依然是数位dp..不过有一个小tip。。 由于包含13的情况非常难考虑（包含一个“13”，两个“13”…..)

题目链接 题意：求一个区间内所有位数字之和能被10整除的数的个数。 思路：数位dp，dfs要一个参数记录从最高位到现在的pos位置的数字之和的结果。 代码实现 1 dp[i][j] 表示长度为i，和为j的方案数。 2 记得开long long ，然而我开了那么多long long 忘了dp 的long long 结果wa到死。。果然大早上不清醒吗== 3 4 5 6/* *********************************************** 7Author :111qqz 8Created Time :2016年03月16日 星期三 08时10分19秒 9File Name :code/hdu/4722.cpp 10************************************************ */ 11 12#include <cstdio> 13#include <cstring> 14#include <iostream> 15#include <algorithm> 16#include <vector> 17#include <queue> 18#include <set> 19#include <map> 20#include <string> 21#include <cmath> 22#include <cstdlib> 23#include <ctime> 24#define fst first 25#define sec second 26#define lson l,m,rt<<1 27#define rson m+1,r,rt<<1|1 28#define ms(a,x) memset(a,x,sizeof(a)) 29typedef long long LL; 30#define pi pair < int ,int > 31#define MP make_pair 32 33using namespace std; 34const double eps = 1E-8; 35const int dx4[4]={1,0,0,-1}; 36const int dy4[4]={0,-1,1,0}; 37const int inf = 0x3f3f3f3f; 38LL l,r; 39int digit[30]; 40LL dp[30][15]; //dp 数组忘记开long long ,wa到死。。。。。。。。。日了哈士奇。 41LL dfs ( int pos,int sum,bool limit) 42{ 43 if (pos==0) 44 { 45 if (sum==0) return 1; 46 else return 0; 47 } 48 if (!limit&&dp[pos][sum]!=-1) return dp[pos][sum]; 49 50 int mx = limit?digit[pos]:9; 51 52 LL res = 0 ; 53 for ( int i = 0 ; i <= mx; i ++) 54 { 55 res+=dfs(pos-1,(sum+i),limit&&i==mx); 56 } 57 58 if (!limit) dp[pos][sum] = res; 59 60 return res; 61 62} 63LL solve ( LL n) 64{ 65// if (n==0) return 1; 66 // if (n<=9) return 0; 67 if (n<0) return 0; 68 ms(digit,0); 69 int len = 0 ; 70 while (n) 71 { 72 digit[++len] = n % 10; 73 n /= 10; 74 } 75 76 return dfs(len,0,true); 77} 78int main() 79{ 80 #ifndef ONLINE_JUDGE 81 freopen("code/in.txt","r",stdin); 82 #endif 83// ios::sync_with_stdio(false); 84 int T; 85 cin>>T; 86 ms(dp,-1); 87 int cas = 0 ; 88 while (T--) 89 { 90 scanf("%lld %lld",&l,&r); 91 LL ans = solve (r)-solve(l-1); 92 93 printf("Case #%d: %lld\n",++cas,ans); 94 } 95 96 #ifndef ONLINE_JUDGE 97 fclose(stdin); 98 #endif 99 return 0; 100}

题目链接 题意：不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多少个windy数？ 思路：数位dp 这道题的特点是前面不允许前导0，也就是说，如果第i位前面全是0的话，这个数就变成了i位数，i就变成了最高位，而最高位没有前面的数（**如果这里不考虑不允许前导0这个因素而把前面的一个数认为成是0就错了） **最高位的数可以直接取。 还有记忆化调用以及存储的时候也要注意…只有当位数相同的时候转移才有意义。 具体的方法是dfs中多了一个prehasnonzero的bool变量，就是字面意思，判断当前位置前面的位置是够存在一个非0的值。

题目链接 题意：问从1到n的所有数中，有多少个数含有数字串“49” 思路：和上一道不要62很像，但是由于是要统计有49的，但是有49的情况实在太多了，正难则反，用减法定理反过来考虑，先统计出不含49的数的个数，这样就和不要62一样了，然后再用总数减。

题目链接 题意：问区间[n,m]中，不含数字4，也不含数字串“62”的所有数的个数。 思路：可以转化成求区间[0,x] 第一次接触数位dp，参考了这几篇博客。 不要62（数位dp）解题报告 解题报告2 解题报告3 比较重要的前提：

题目链接 题意：求曼哈顿距离和平方根距离相等的点的对数？ 思路：化简发现是绝对值乘积等于0，容斥搞搞。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年03月07日 星期一 18时43分02秒 4File Name :code/C.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=2E6+7; 34 35struct node 36{ 37 int x,y; 38 39 bool operator < (node b)const 40 { 41 if (x==b.x) return y<b.y; 42 return x<b.x; 43 } 44}p[N]; 45 46 47 48bool cmp( node a,node b) 49{ 50 return a.y<b.y; 51} 52LL cal( LL x) 53{ 54 LL res = x*(x+1)/2; 55 return res; 56} 57int n; 58LL a,b,c; 59LL cnta,cntb,cntc; 60int main() 61{ 62 #ifndef ONLINE_JUDGE 63 freopen("code/in.txt","r",stdin); 64 #endif 65 66 ios::sync_with_stdio(false); 67 cin>>n; 68 for ( int i = 1 ;i <= n ; i++) cin>>p[i].x>>p[i].y; 69 70 sort(p+1,p+n+1); 71 72 a=b=c=0LL; 73 cnta=cntb=cntc=0LL; 74 75 76 for ( int i = 1 ; i <= n-1 ; i++) 77 { 78 if (p[i].x==p[i+1].x) 79 { 80 cnta++; 81 } 82 else 83 { 84 a+=cal(cnta); 85 cnta = 0 ; 86 } 87 } 88 a +=cal(cnta); 89 90 91 for ( int i = 1 ; i <= n-1 ; i++) 92 { 93 if (p[i].x==p[i+1].x&&p[i].y==p[i+1].y) 94 { 95 cntc++; 96 } 97 else 98 { 99 c +=cal(cntc); 100 cntc = 0 ; 101 } 102 } 103 104 c+=cal(cntc); 105 106 107 108 sort(p+1,p+n+1,cmp); 109 for ( int i = 1 ; i <= n-1 ; i ++) 110 { 111 if (p[i].y==p[i+1].y) 112 { 113 cntb++; 114 } 115 else 116 { 117 b +=cal(cntb); 118 cntb = 0 ; 119 } 120 } 121 b +=cal(cntb); 122 123 LL ans=0LL; 124 ans = a+b-c; 125 cout<<ans<<endl; 126 127 #ifndef ONLINE_JUDGE 128 fclose(stdin); 129 #endif 130 return 0; 131}

题目链接 题意：给出一个数列，按照最好的策略排序使得a[i+1]>a[i]的对数尽可能多，问最多的对数是多少。 思路：类似计数排序？ 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年03月07日 星期一 17时06分48秒 4File Name :code/cf/#345/B.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=1E3+7; 34int n ; 35int a[N]; 36int cnt[N]; 37int num[N]; 38int sum[N]; 39int main() 40{ 41 #ifndef ONLINE_JUDGE 42 freopen("code/in.txt","r",stdin); 43 #endif 44 45 cin>>n; 46 ms(cnt,0); 47 ms(num,0); 48 ms(sum,0); 49 for ( int i = 1 ; i <= n ; i++) 50 { 51 cin>>a[i]; 52 cnt[a[i]]++; 53 } 54 if (n==1) 55 { 56 puts("0"); 57 return 0 ; 58 } 59 if (n==2) 60 { 61 if (a[1]==a[2]) 62 { 63 puts("0"); 64 } 65 else 66 { 67 puts("1"); 68 } 69 return 0; 70 } 71 72 int mx = -1; 73 for ( int i = 1 ; i <= 1000 ; i++) 74 { 75 num[cnt[i]]++; 76 mx = max(mx,cnt[i]); 77 } 78 79 for ( int i = mx ; i >= 1 ; i --) 80 { 81 sum[i] = sum[i+1]+num[i]; 82 } 83 84 int ans = 0 ; 85 for ( int i = 1 ; i <= mx ; i++) 86 { 87 ans +=sum[i]-1; 88// cout<<"sum[i]:"<<sum[i]<<endl; 89 } 90 cout<<ans<<endl; 91 92 93 94 #ifndef ONLINE_JUDGE 95 fclose(stdin); 96 #endif 97 return 0; 98}

题目链接 题意：两个手柄？ 初始的电量给出，只有一个充电器，每经过一秒，充着电的手柄电量增加1，没有充电的手柄电量减少2，允许电量充到0以上，当有电量为0的时候，或者当某一分钟开始的时候有手柄电量为1，游戏立即结束。问最多能玩多少时间游戏。

http://acm.hdu.edu.cn/showproblem.php?pid=5631 题意；给出一张n个点n+1（n<=100）条边的无向图，现在删除若干条边（至少一条边），问删完之后图依然联通的方案数。 思路：分析可知，由于只删边，不删点，n个点，最少需要n-1条边才能联通，所以最多删两条边。我们可以暴力枚举删除的两条边（或者一条边） O(n^2)的复杂度完全可以接受。剩下的问题就变成了每次删边之后判断图的连通性。 题解给出的是bfs。。。大概是bfs一遍，然后入队的点数是n就联通？ 或者dfs一遍也可以？ 也是标记过的点数是n就说明联通？ 但是看到排名考前的人都是用到了并查集来判断…比较巧妙。

http://acm.hdu.edu.cn/showproblem.php?pid=5630 题意：nm的棋盘，相邻格子的颜色相反，每次可以翻转一个任意大小矩形的格子，问最少需要翻转多少次使得棋盘的nm个格子颜色相同。（翻转的意思是颜色反色） 思路：手写了下。。发现。。答案就是n/2+m/2. 对应的最优策略是。。翻偶数行和偶数列，都翻一遍，颜色就一样了。

http://acm.hdu.edu.cn/showproblem.php?pid=4451 题意：N clothes, M pants and K shoes，然后给出p个不合法的搭配，形式是“clothes x pants y” or “pants y shoes z”.” 问有多少种合法的方案。 思路：一开始觉得是容斥。。当然可以。。但是实际上，不合法的搭配的形式比较简单，每种不合法的发配都是两个两个的不合法，以及每种不合法的形式都有pants，那么我们就可以通过先确定pants，对于每种pants，方案数就是能和当前pants搭配的clothes数，乘以能和当前pants搭配的shoes数，然后累加每种pants的答案即可。

题意：F(x) = (1+x)^a1 + (1+x)^a2 + … + (1+x)^am，求系数是奇数的项的个数。 思路：解题报告 涉及到的由lucas定理得到的推论的证明lucas定理证明 以及这篇理解里有递归形式的容斥定理的一般写法。。递归形式的容斥定理

指数型母函数网上的资料不是很多，推荐毛杰明的09年国家集训队论文《母函数的性质及应用》 以及Richard A.Brualdi 所著的《组合数学》的第七章来看…倒不用全看懂..但是这本上面干货比较多。

http://codeforces.com/problemset/problem/451/E 题意：有n个花坛，要选s支花，每个花坛有f[i]支花，同一个花坛的花颜色相同，不同花坛的花颜色不同，问说可以有多少种组合。 思路：典型的母函数…然而s有点大，根据泰勒展开什么的…先转一下官方题解。

http://poj.org/problem?id=1322 题意： 思路：别看n,m很大，但是想一下，m显然不可能大于c（如果大于c，那么根据抽屉原理，至少存在一种巧克力大于一个，然而大于一个就会被取走…矛盾），这样概率为0。m也不可能大于n，因为最好的情况就是取出的巧克力都放在了桌子上，如果总共取的还不到n个，又怎么可能剩下m（m>n）个呢。此外，还需要n,m奇偶性相同，否则设n-m=2K+1，说明如果要剩余m个，那么就要减少2k+1个，但是巧克力是两个两个减少的，减少的个数一定是偶数，因此矛盾。所以n,m奇偶性相同。

http://poj.org/problem?id=2356 题意：有 n 个数，从中选取若干个（1..n），和能被 n 整除。问是否有解，无解输出 0，有解的话，输出个数以及选择的 a[i]（不是 i）。 由抽屉原理可知一定有解： 做一个带模的前缀和 sum[i]=(sum[i-1]+a[i])%n n个数，sum[i]最多有n种。 如果某个sum[i]为0，那么表示从1到i的和能被n整除。 如果所有的 sum[i] 不为 0，那么一共有 n 个 sum[i]、n-1 个值（1..n-1），一定有 sum[i] == sum[j]（i <= j）。 那么a[i]到a[j]的和一定能被n整除。

http://acm.hdu.edu.cn/showproblem.php?pid=1205 题意：有n种糖果，第i种糖果有a[i]个，相邻两次不能吃一样的糖果，问能否有办法吃完所有糖果… 思路：如果第i种糖果有k个的话，那么其他所有种类的糖果之和至少有k-1个，才可能吃完。复杂度O(n) 看到有人说是抽屉原理…..大概。。。？不过不太明显。。直接想就好吧

hdu1796 题意：给出n（<=2^31）以及m(<=10)个元素组成的无重复元素集合，集合元素0<=a[i]<=20，问有多少个小于n的数能至少被集合中的一个元素整除。

http://acm.hdu.edu.cn/showproblem.php?pid=4336 题意：有n种卡片，买一包干脆面得到第i种卡片的概率是p[i]，每包干脆面最多有一张卡片，问收集齐所有卡片要买的干脆面的包数的数学期望。 思路：容斥模板题。1.0/p[i]就是拿到某张卡片需要买的包数的数学期望