時間：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
輸出實際輸入的字符串。每個從輸出樣例之間空一行。具體格式看樣例。最后一個例子后面不用空行?。?h3 style="font-family:"Times New Roman",Times,serif; font-size:17px; margin:8px auto">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
新的一年又要到了。濤哥哥竟然嫌銀杏路上的樹太難看，決定換一批新樹種下去。于是銀杏路上就又多了一排新樹（從左往右）?？墒欠N完后，濤哥哥還是不滿意。他認為這些樹的高度參差不齊，太影響校容了，必須從左往右改變樹高，使樹高為等差數列的才算是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;}