Posts

题目链接 题意：有n天的旅行，但是只剩下了m天的旅行记录，记录格式为d[i],h[d[i]]，表示第i个记录是第d[i]天的，高度为h[d[i]]，相邻两天的高度之差的绝对值不超过1.问满足以上条件的最大的h是多少。无解输出impossible. 思路：为了练习二分。 二分高度，然后check是否合法。注意边界，所以可以添加两个点。

题目链接 题意：没图不好描述，有中文题面中文题面，直接看吧。 思路：据说这道题有三种做法。当时比赛一种都不会。

题目链接 題意：已知一个包含 nn 个元素的正整数集合 SS，设 f(S)f(S) 为集合 SS 中所有元素的异或(XOR)的结果。 如：S={1,2,3}, 则 f(S) = 0f(S)=0。

题目链接 题意；给出一个字符串，只由小写字母组成，可以任意排列，但是不能减少字符，问最多能得到多少个回文串，答案9+7

比赛链接 两题QAQ A：7分钟1A 有n个大人m个小孩乘公交车，票价每人一元，一个大人最多免费带一个小孩，没有大人陪同的小孩不能乘车。 问是否有解，如果有解输出所有乘客付的钱的可能的最小值和可能的最大值。

题目链接 题意：将正整数n(n<=1E9)，拆分成k个（k<=1E9）个**互不相等的正整数，**并且使得k个正整数的乘积最大。如果可以拆分，输出最大乘积，否则输出-1.

题目链接 题意：n（n<=300）个球，每个球上标有一个标号(a[i]<=300)，从中拿一个，不放回，再拿一个，问第一个球上的数字严格大于第二个球上的数字的概率。 思路：古典概型。总数为n*(n-1)/2…然后标号最大300，不妨用cnt[i]统计标号为i的球的个数。从小往大扫一遍cnt,cnt[i]对分子的贡献就是cnt[i]*cur。。cur 为 sum{cnt[1]..cnt[i-1]}; 最后注意将分子除以2，因为有一半是第一个球比第二个球小的情况。

题目链接 题意：给出n个点，m条边，定义一条路径的价值为【路径长度*(路径终点的度)】，求最大价值。 思路：一月份的时候写过一个回溯。。。TLE22了。。。其实也能猜到是dp..但是无奈不会写。然而其实真的不难== 我们枚举路径的终点，dp[i]表示以点i为终点能得到的最长路径长度。

题目链接 题意：n个点，m（m<n/2）条不能走的边，问最少连多少条边，使得任何两个点之间的距离最多为2. 输出最少的边数和连接的哪些边。 思路： **数据范围很关键。**数据范围很关键。数据范围很关键。

题目链接 题意：给出n和k，给出一个长度为n的字符串表示房间的占用情况（0表示没占用，1表示已占用），从n个房间中找出k+1个，使得k+1中的k个距离k+1个中的1个的距离和最小。

题目链接 题意：长度为n的初始为1，2,3…n的序列，最多进行k次两个数交换，变换后的序列中最懂能有多少逆序对。 思路：贪心得想。。每次变最外层的对答案贡献最多。 以及，最能能变化n/2次。

题目链接 题意：2×2的格子，有三个位置分别放”A“ “B” “C” ，一个位置为空。只有和空位相邻位置上的字母能移动到空位。没有其他移动规则。现在给出两个状态。问能否互相转化。 思路： 貌似可以dfs…？但是一共才2*2，可以直接暴力枚举。 手写一种变换最多能有12种。

题目链接 题意：设条件A为一个数恰好是k个互不相同的b的整数次幂的和，问某一个区间内满足条件A的数的个数是有多少个。

题目链接 题意：将一个10进制数x按照2进制展开后得到的值设为f(x)…现在给出a,b（10^9）问【0，b】中满足f[x]<=f[a]的数的个数。 思路：先算出f[a]，然后我们发现f(x)最大也就10*2^10=10240，数组可以存下，搞之。和上一道题类似，我们不关心两个f函数的值具体是多少，只关心它们的相对大小情况，所以还是可以合并成一个变量。然而我用两个变量为什么错了，不懂==

hdu5642题目链接 题意：问长度为n的仅由26个小写字母组成的合法字符串有多少个。如果某个字符连续出现四次或以上，则这个字符串为非法。否则为合法。

题目链接 题意：找到某区间中平衡数的个数。所谓平衡数是指，存在某个位置，使得两边的力矩相等。举个例子，比如14326，如果把4作为中间，那么左边=11=1，右边=31+22+62=19。 思路：枚举中间的pivot，注意个位数也是平衡数（就是认为两边的力矩都是0了），所以每一个位置都可能是平衡位置，枚举的时候从1到len… 一开始我是分别记录两边的值，非常浪费空间，然而发现其实没必要。我们只关心左右是否相等，而不关心左右的值到底是多少，所以可以把两边的值带符号合并成一个值（pivot左边为+，pivot右边为负）。如果最后为0，说明左右相等。

题目链接 题意：问某区间中，round number 的个数是多少。所谓round number，当且仅当一个数的二进制表示中，‘0’的个数大于等于‘1’的个数。 思路：简单数位dp..和windy数那道题类似，都是不允许前导0.。。所以在dfs中要加一维判断前面是否有非0的数。。。

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

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

题目链接 题意：求一个区间内所有位数字之和能被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}