时间：2017年2月8日

总结：

1）. 上一场因为在外面旅游没有参加，这一场训练赛又因为考科目一时人太多排了很久的队而耽误了一小时（还好考试成绩不错），两点钟到家后边吃饭边读题想题别有一番乐趣 = =。

2) .   我发现我现在遇到第一次没有思路的题越来越喜欢在AC后写博客，因为每次写博客的过程就是将解题思路从无到有用自己的话进行复述的过程，不仅加深了印象，而且能更深入地理解这道题，有时还会有一些意想不到的收获，例如写博客时忽然发现这道题的一些细节自己并不理解为什么可以这样做（手动滑稽= =

3）.回归正题，题目整体感觉不难，主要一些小细节不注意会很坑，总之，专心读题！认真读题！仔细读题！

题目1001：

PRoblem A

Time Limit : 2000/500ms (java/Other)   Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 95   Accepted Submission(s) : 7

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

Input

Output

Sample Input

49 8 17 644 10 5 8
Sample Output
8silly linlihao159!
题意和解题思路都很简单直接，但因为我开始做题时这道题已经WA了二十多份代码，一个AC的也没有，就果断放弃了尝试，后来问学长才知道需要用输入挂，赛后百度了一圈，原理大致是因为：scanf需要对占位符进行解引，而getchar则不需要，所以用getchar来读入数据然后处理，当数据规模很大时，能够减少输入所花的时间。赛后补题时就套用了学长的输入挂模板:
#include <bits/stdc++.h>using namespace std;const int BUF = 20000000;const int maxn = 105;int a[maxn];char Buf[BUF],*buf = Buf;inline void read(int& a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}int main(){	int now = fread(Buf,1,BUF,stdin);	int n;	while(1){		read(n);		if (buf - Buf > now) break;		int sum = 0;		for (int i = 1; i <= n; i++){			read(a[i]);		}		for (int i = 1; i <= n; i++){			sum += a[i];		}		if(sum % n != 0){			printf("silly linlihao159!/n");			continue;		}		int avg = sum/n;		int ans = 0;		for(int i=1 ;i<n ;i++){			if(a[i] != avg){				a[i+1] -= avg - a[i];				ans += abs(avg - a[i]);			}		}		printf("%d/n",ans);	}	return 0;}1002:
Problem B
Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 76   Accepted Submission(s) : 23
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
武警哥哥是炙手可热的码农，他一天之内要打上万行的代码。当然天天被折磨的他，也想来考考聪明的你们了。在输代码的时候经常会用到键盘上的’←’ , ‘→’这两个键移动光标来方便地进行输入操作。在输一串字符的时候中间掺插输入’←’ , ’→’（此处我们用’-‘ , ‘+’来替换,在输入的字符串中忽略’- ‘ , ’+’字符，当作左移右移键）操作，那么我们最终会得到怎么样一个字符串呢？字符串由包含空格！
Input
输入数据包含多组测试实例，每个测试实例为一个字符串（除了字符’-‘,’+’），长度不超过1000。
Output
输出实际输入的字符串。每个从输出样例之间空一行。具体格式看样例。最后一个例子后面不用空行！！
Sample Input
ab-cd--+eab1++2---------------3
Sample Output
Case 1:acedbCase 2:3ab12
做这题时先看了一下提交情况，没有一个超时的，然后果断暴力，一次AC。
#include <bits/stdc++.h>using namespace std;typedef long long ll;char str[1010];int main(){	int _ = 0;	while(gets(str)){		if(_++)	printf("/n");		char s[1010] = "";		int l = 0;		int len = strlen(str);		int p = 0;		for(int i=0 ;i<len ;i++){			if(p<0)	p = 0;			if(p>l)	p = l;			if(str[i] == '+')		p++;			else if(str[i] == '-')		p--;			else{				for(int j=l ;j>=p ;j--){					s[j+1] = s[j];				}				l++;				s[p] = str[i];				p++;			}		}		printf("Case %d:",_);		cout <<	s << endl;	}	return 0;}1003:
Problem C
Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 44   Accepted Submission(s) : 15
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
哦！天啊！！《奔跑吧兄弟》的导演竟然邀请我去参加节目，而且为了不让我在节目里面拉低整个队伍的智商，提前给我透露了任务。任务如下：现在有n个地点，而且给定了具体路线（比如有3个地点a,b,c,给定了a-b-c-a的路线,那么只有3种顺序abc,bca,cab），在每个地点你会收到一笔钱Li，但也必须花费一笔钱Wi，在某个地点多出来的钱可以存到下一个地点使用。但是如果你在某个地点没能花够Wi，对不起，你就会out。到达最多的地方的队伍获胜。相信自己！这就是梦！！好吧，梦醒了，问题来了，在梦里我最多可以到达几个地点？
Input
有多组样例，每个样例第一行是一个正整数n(1<=n<=100000)，表示有n个地点，接下来一行按照路线顺序有n组数据（Li，Wi），表示每个地点的收入和花费（正整数）。
Output
输出最多可以到达几个地点。
Sample Input
33 2 3 4 2 233 2 3 4 2 3
Sample Output
32开始还以为是DP，跪了半个小时连样例都过不了，然后果断放弃。赛后经过孟神讲解才发现其实很简单，本质就是一个求最大连续和，只不过求的不是和，而是求最长的连续个数。然后定义：presum : 当前和prenum:当前的连续个数ans       :最终结果然后当presum小于0时（说明不能再往前走了），就更新prenum=presum = 0。在线处理即可。
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 100005;int a[maxn*2];int n;int main(){	while(scanf("%d",&n) != EOF){		for(int i=0 ;i<n ;i++){			int x,y;			scanf("%d%d",&x,&y);			a[i] = a[i+n] = x - y;		}		int ans = 0;		int prenum = 0;		ll presum = 0;		for(int i=0 ;i<2*n && ans <= n; i++){			presum += a[i];			if(presum >= 0 && prenum < n){				prenum++;			}			else{				ans = max(ans,prenum);				prenum = 0;				presum = 0;			}		}		printf("%d/n",ans);	}	return 0;}1004：
Problem D
Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 73   Accepted Submission(s) : 22
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
今天，给大家一个简单题！！相信大家在写代码的时候，总是在不断的切换大小写.....当在大写没有锁定的时候 shift + 字母 打印出大写字母，而在大写锁定的时候 shift + 字母 打印出小写字母！！但是总是要按这么多键好累的！！要高效的工作！！因此，给一个字符串，有大小写字母组成，求最少的按键次数.....键有（26个字母和shift和caps lock），起始状态在小写！！hint:shift键不能一直按着！！，最后键的状态若在大写状态不必改为小写。
Input
多个测试例子，每个例子输入一个字符串，长度小于10000
Output
输出最少的按键次数
Sample Input
aaaaAaaaaaaaAAAaAAA
Sample Output
9104
暴力模拟即可，AC的第一道题，感觉思路很直接。定义一个变量flag。flag = 0:当前是小写输入状态。flag = 1:当前是大写输入状态。
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 10010;char str[maxn];int main(){	while(scanf("%s",str) != EOF){		int len = strlen(str);		int ans = 0;		bool flag = 0;		for(int i=0 ;i<len ;){			if(str[i]>='a' && str[i]<='z'){				int cnt = 1;				i++;				while(str[i]>='a' && str[i]<='z'){					cnt++;					i++;				}				if(flag == 0)					ans += cnt;				else{					if(cnt==1)						ans += 2;					else{						flag = 0;						ans += cnt + 1;					}					}			}				if(str[i]>='A' && str[i]<='Z'){				int cnt = 1;				i++;				while(str[i]>='A' && str[i]<='Z'){					cnt++;					i++;				}				if(flag == 1){					ans += cnt;				}				else{					if(cnt == 1)						ans += 2;					else{						flag = 1;						ans += cnt + 1;					}				}			}		}		printf("%d/n",ans);	}	return 0;}1005：
Problem E
Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 91   Accepted Submission(s) : 24
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
新的一年又要到了。涛哥哥竟然嫌银杏路上的树太难看，决定换一批新树种下去。于是银杏路上就又多了一排新树（从左往右）。可是种完后，涛哥哥还是不满意。他认为这些树的高度参差不齐，太影响校容了，必须从左往右改变树高，使树高为等差数列的才算是beautiful！那么问题来了，没吃药的涛哥哥对着任何一棵树念一分钟咒语，就可以把树的高度改变。机智的你能帮他算出他最少需要几分钟能将这排树变成他心中beautiful样子呢？虽然涛哥哥没有吃药，但是他不能把一棵树的高度成负数。
Input
输入一个T，表示有T组样例。（1<=T<=100）再输入一个n，d，表示种下了n棵树和想要的公差（改变后右边的树高减左边的树高），接下的n行里，每行输入k，high，分别表示树种下的位置以及树原有的高度，当然同一位置不会种多棵树。（1<=k<=n<=100，0<=d，0<=high<=1000，且数据皆为整数）
Output
输出一个num，代表最少需要的时间。
Sample Input
14 11 12 23 1 4 5
Sample Output
2DP：我的思路是用：总数  减去  已经相应排列成等差数列的树的数量最大值假设第k棵树的高度不变，设在其前面的k-1棵树中与其对应成等差数列关系的树的数量（包括自己）是dp[k]。当我们已知前n棵树的dp[i]（i= 1....n）的值，则求 dp[n+1]时，可以从n遍历到1，如果有其中某一棵树m的高度与第n+1棵树的高度对应成等差数列，则dp[n+1] = dp[m] + 1。然后从dp[i] （i= 1.....n）找出一个最大值，然后用总数减去最大值就是答案。
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 110;struct Tree{	int id,h;}a[maxn];int dp[maxn]; bool comp(Tree& a,Tree& b){	return a.id < b.id;}int main(){	int T;	scanf("%d",&T);	while(T--){		int n,d;		scanf("%d%d",&n,&d);		for(int i=0 ;i<n ;i++){			scanf("%d%d",&a[i].id,&a[i].h);		}			sort(a,a+n,comp);		dp[0] = 1;		int Max = 1;		for(int i=1 ;i<n ;i++){			if(i*d > a[i].h){				dp[i] = 0;				continue;			}			dp[i] = 1;			for(int j=i-1 ;j>=0 ;j--){				int tem = a[i].h - a[j].h;				if(tem == d*(i-j)){					dp[i] = max(dp[i],dp[j]+1);                                         break;				}			}			Max = max(Max,dp[i]);		}		printf("%d/n",n-Max);		}	return 0;}1006：
Problem F
Time Limit : 3000/2000ms (Java/Other)   Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 61   Accepted Submission(s) : 30
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
某某某今天很开心，妈妈昨天对他说：“你老大不小了，还找不到女朋友，个头是个大问题。听说最近市场上出了几种药，能长个头，明天给你去买几种吃，吃哪种，你说了算，只要不超过N元钱就行”。今天一早他就开始做预算，但是他很爱尝试各种药，想买的品种太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每种药的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每种药的价格与重要度的乘积的总和最大。设第j件药的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：v[j1] * w[j1] + v[j2] * w[j2] +…+ v[jk] * w[jk]。（其中*为乘号）请你帮助他设计一个满足要求的购物单。
Input
输入包含多个测试数据。每个测试数据的第1行，为两个正整数，用一个空格隔开：N,m其中N（<30000）表示总钱数，m（<25）为希望购买药品的种数。从第2行到第m+1行，每行有2个非负整数v,w（其中v表示该药品的价格(v<=10000)，w表示该药品的重要度(1~5)）
Output
对于每个测试数据输出一行，其中只含有一个正整数，为不超过总钱数的药品的价格与重要度乘积的总和的最大值（<100000000）。
Sample Input
1000 5800 2400 5300 5400 3200 2
Sample Output
3900
01背包，只不过状态转移时要多一层条件。
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 30005;ll dp[maxn],sum[maxn],v[55],w[55];int n,m;int main(){	while(scanf("%d%d",&n,&m) != EOF){		for(int i=1 ;i<=m ;i++){			int x,y;			scanf("%d%d",&x,&y);			v[i] = x;			w[i] = x*y;		}		memset(dp,0,sizeof(dp));		memset(sum,0,sizeof(sum));		for(int i=1 ;i<=m ;i++){			for(int j=n ;j>=v[i] ;j--){				if(dp[j-v[i]] + w[i] > dp[j] && sum[j-v[i]] + v[i] <= n){					dp[j] = dp[j-v[i]] + w[i];					sum[j] = sum[j-v[i]] + v[i];				} 			}		}			ll ans = 0;		for(int i=0 ;i<=n ;i++){			ans = max(ans,dp[i]);		}		printf("%lld/n",ans);	}	return 0;}1008：
Problem H
Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 62   Accepted Submission(s) : 7
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
小边为了寻找梦寐以求的骨头误入一个迷宫,它灵敏的嗅觉告诉它,在迷宫中的某一处有一块完美的骨头.由于迷宫会在一段时间后关闭,所以小边必须在一定时间找到那块骨头,这样才能有充足的时间来带着骨头离开.小边在迷宫中可以从当前位置走到相邻的位置,每次移动消耗单位时间,当然,因为小边对骨头的无比执着,它偶尔会使出绝技”狗急跳墙”(一次移动两个单位位置,同样消耗单位时间).使用这个技能的时候,可以翻过一面单位厚度的墙(即第一步移动可以踩在墙上,当然也可以不踩).hint：使用技能的时候，不用管中间那一步是否可走。那么小边能够如愿以偿的找到骨头并离开迷宫么?
Input
多组输入每组输入第一行是四个数m,n(0<m,n<=30),k(0<=k<=30),t(0<=t<=100),分别代表迷宫的长,宽,小边使用”狗急跳墙”的最大次数以及找到骨头的时间限制.m=n=k=t=0代表输入结束接下的m行每行有n个字符,‘.’代表地面,’#’代表墙,’@’代表目前小边所处的位置,’X’代表骨头所在的位置
Output
若小边能在规定时间内找到骨头,则输出Yes,否则输出No.每个输出占一行.
Sample Input
3 3 1 2@###.##X#4 4 1 3@.#.#.########X.0 0 0 0
Sample Output
YesNo
迷宫题，读题不仔细，还以为狗急跳墙真的只能用于跳墙= =思路：多加一维状态，表示此时还可以使用的技能次数，然后套路BFS即可。注意平地也可以使用技能。
#include <bits/stdc++.h>using namespace std;int maze[35][35],vis[35][35][35];int dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};int sx,sy,gx,gy,m,n,k,T;struct P{      int x,y;      int t,num;      friend bool Operator<(P a,P b){          return a.t > b.t;      }  };bool check(int xx,int yy,int num){	if(xx>=1 && xx<=n && yy>=1 && yy<=m && !vis[xx][yy][num])		return true;	return false;}int bfs(){    priority_queue<P> que;      P a,b,c;    a.x = sx;    a.y = sy;    a.t = 0;    a.num = k;    vis[sx][sy][k] = 1;    que.push(a);    while(que.size()){    	a = que.top();    	que.pop();    	if(a.x == gx && a.y == gy){    		return a.t;		}			for(int i=0 ;i<4 ;i++){			b.x = a.x + dx[i];			b.y = a.y + dy[i];			b.t = a.t + 1;			b.num = a.num;			if(check(b.x,b.y,b.num)){				if(maze[b.x][b.y]){					vis[b.x][b.y][b.num] = 1;					que.push(b);				}				if(b.num > 0){					for(int j=0 ;j<4 ;j++){						if(abs(i-j) == 2) continue;						c.x = b.x + dx[j];						c.y = b.y + dy[j];						c.num = b.num - 1;						c.t = b.t;						if(check(c.x,c.y,c.num) && maze[c.x][c.y]){							vis[c.x][c.y][c.num] = 1;							que.push(c);						}					}					}			}		}	}    return -1;}int main(){	char ch;   	while(scanf("%d%d%d%d",&n,&m,&k,&T) != EOF && (n||m||k||T)){   		memset(vis,0,sizeof(vis));   		for(int i=1 ;i<=n ;i++){   			for(int j=1 ;j<=m ;j++){   				cin >> ch;   				if(ch == '.'){   					maze[i][j] = 1;					}				else if(ch == '#'){					maze[i][j] = 0;				}				else if(ch == '@'){					maze[i][j] = 1;					sx = i,sy = j;				}				else{					maze[i][j] = 1;					gx = i,gy = j;				}   					}		}		int t = bfs();		if(t == -1 || t>T){			printf("No/n");		}		else{			printf("Yes/n");		}	}    return 0;}