题目链接 题意：问区间[n,m]中，不含数字4，也不含数字串“62”的所有数的个数。 思路：可以转化成求区间[0,x] 第一次接触数位dp,参考了这几篇博客。 不要62（数位dp）解题报告 解题报告2 解题报告3 比较重要的前提： ¨对于一个小于n的数，肯定是从高位到低位出现某一位<n的那一位。 ¨如 n = 58 n为十进制数。 ¨ x = 49 此时x的十位<n ¨ x = 51 此时x的个位<n ¨有了上述性质，我们就可以从高到低枚举第一次<n对应位是哪一位。 这样之前的位确定了，之后的位就不受n的限制即从00...0~99...9，可以先预处理 以及写成递归形式代码会简洁很 …

题目链接 题意：求曼哈顿距离和平方根距离相等的点的对数？ 思路：化简发现是绝对值乘积等于0，容斥搞搞。 /* *********************************************** Author :111qqz Created Time :2016年03月07日 星期一 18时43分02秒 File Name :code/C.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include …

题目链接 题意：给出一个数列，按照最好的策略排序使得a[i+1]>a[i]的对数尽可能多，问最多的对数是多少。 思路：类似计数排序？ /* *********************************************** Author :111qqz Created Time :2016年03月07日 星期一 17时06分48秒 File Name :code/cf/#345/B.cpp ************************************************ */ #include <cstdio> #include <cstring> #include …

题目链接 题意：两个手柄？ 初始的电量给出，只有一个充电器，每经过一秒，充着电的手柄电量增加1，没有充电的手柄电量减少2，允许电量充到0以上，当有电量为0的时候，或者当某一分钟开始的时候有手柄电量为1，游戏立即结束。问最多能玩多少时间游戏。 思路：贪心。。每次给电量少的充电。 坑点在于当某一时刻有手柄电量为1，那么游戏在进行这一分钟之前就结束。 /* *********************************************** Author :111qqz Created Time :2016年03月07日 星期一 17时06分41秒 File Name :code/cf/#345/A.cpp …

一年过去了。 现在看到小可，内心却依然无法平静... 强装镇定得打个招呼已经是我的极限了orz 其实还是觉得很可惜...曾经的好朋友变得形同陌路总是令人伤感的... 可是没办法啊orz 果然是绕不过去的一个人啊.... 我赌五毛永远没办法做朋友了orz,虽然我挺希望我输掉的... 以及：感觉《熔炉》中的妍斗好像小可== 以及：好喜欢代码写得好的妹子

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. 对应的最优策略是。。翻偶数行和偶数列，都翻一遍，颜色就一样了。 /* *********************************************** Author :111qqz Created Time :2016年03月03日 星期四 20时47分47秒 File Name :code/hdu/5630.cpp …

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定理证明 以及这篇理解里有递归形式的容斥定理的一般写法。。递归形式的容斥定理 dfs(int beg,set S,int sym) { ans+=num(S)*sym; for(int i=beg;i<=n;i++) dfs(i,S∩A[i],sym*-1); } for(int i=1;i<=n;i++) dfs(i,A[i],1); 第一次接触递归形式的容斥定理...还不是特别理解，据说要比循环的写法少一层msk(应该是少一 …

指数型母函数网上的资料不是很多，推荐毛杰明的09年国家集训队论文《母函数的性质及应用》 以及Richard A.Brualdi 所著的《组合数学》的第七章来看...倒不用全看懂..但是这本上面干货比较多。 我来说下自己的理解： 指数型母函数和普通型母函数（不加普通二字也是指它）的区别是后者是用来求解组合问题（顺序无关行），而前者是求解排列问题（不同的顺序属于不同的方案）。 对于多重排列问题，由于某种元素可能有多个，需要去掉它的重复度（除以该种元素的个数的阶乘），而这个除以阶乘的形式和泰勒级数展开中的一些函数的展开形式一致（或者是一些变形）。 因此母函数可以用泰勒级数来化简。 这是求解这类问题最核心的内容。 也有直接算的。比如这 …