時(shí)間：2017年2月8日

總結(jié)：

1）. 上一場(chǎng)因?yàn)樵谕饷媛糜螞]有參加，這一場(chǎng)訓(xùn)練賽又因?yàn)榭伎颇恳粫r(shí)人太多排了很久的隊(duì)而耽誤了一小時(shí)（還好考試成績(jī)不錯(cuò)），兩點(diǎn)鐘到家后邊吃飯邊讀題想題別有一番樂趣 = =。

2) .   我發(fā)現(xiàn)我現(xiàn)在遇到第一次沒有思路的題越來(lái)越喜歡在AC后寫博客，因?yàn)槊看螌懖┛偷倪^(guò)程就是將解題思路從無(wú)到有用自己的話進(jìn)行復(fù)述的過(guò)程，不僅加深了印象，而且能更深入地理解這道題，有時(shí)還會(huì)有一些意想不到的收獲，例如寫博客時(shí)忽然發(fā)現(xiàn)這道題的一些細(xì)節(jié)自己并不理解為什么可以這樣做（手動(dòng)滑稽= =

3）.回歸正題，題目整體感覺不難，主要一些小細(xì)節(jié)不注意會(huì)很坑，總之，專心讀題！認(rèn)真讀題！仔細(xì)讀題！

題目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!
題意和解題思路都很簡(jiǎn)單直接，但因?yàn)槲议_始做題時(shí)這道題已經(jīng)WA了二十多份代碼，一個(gè)AC的也沒有，就果斷放棄了嘗試，后來(lái)問學(xué)長(zhǎng)才知道需要用輸入掛，賽后百度了一圈，原理大致是因?yàn)椋簊canf需要對(duì)占位符進(jìn)行解引，而getchar則不需要，所以用getchar來(lái)讀入數(shù)據(jù)然后處理，當(dāng)數(shù)據(jù)規(guī)模很大時(shí)，能夠減少輸入所花的時(shí)間。賽后補(bǔ)題時(shí)就套用了學(xué)長(zhǎng)的輸入掛模板:
#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
武警哥哥是炙手可熱的碼農(nóng)，他一天之內(nèi)要打上萬(wàn)行的代碼。當(dāng)然天天被折磨的他，也想來(lái)考考聰明的你們了。在輸代碼的時(shí)候經(jīng)常會(huì)用到鍵盤上的’←’ , ‘→’這兩個(gè)鍵移動(dòng)光標(biāo)來(lái)方便地進(jìn)行輸入操作。在輸一串字符的時(shí)候中間摻插輸入’←’ , ’→’（此處我們用’-‘ , ‘+’來(lái)替換,在輸入的字符串中忽略’- ‘ , ’+’字符，當(dāng)作左移右移鍵）操作，那么我們最終會(huì)得到怎么樣一個(gè)字符串呢？字符串由包含空格！
Input
輸入數(shù)據(jù)包含多組測(cè)試實(shí)例，每個(gè)測(cè)試實(shí)例為一個(gè)字符串（除了字符’-‘,’+’），長(zhǎng)度不超過(guò)1000。
Output
輸出實(shí)際輸入的字符串。每個(gè)從輸出樣例之間空一行。具體格式看樣例。最后一個(gè)例子后面不用空行??！
Sample Input
ab-cd--+eab1++2---------------3
Sample Output
Case 1:acedbCase 2:3ab12
做這題時(shí)先看了一下提交情況，沒有一個(gè)超時(shí)的，然后果斷暴力，一次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
哦！天?。?！《奔跑吧兄弟》的導(dǎo)演竟然邀請(qǐng)我去參加節(jié)目，而且為了不讓我在節(jié)目里面拉低整個(gè)隊(duì)伍的智商，提前給我透露了任務(wù)。任務(wù)如下：現(xiàn)在有n個(gè)地點(diǎn)，而且給定了具體路線（比如有3個(gè)地點(diǎn)a,b,c,給定了a-b-c-a的路線,那么只有3種順序abc,bca,cab），在每個(gè)地點(diǎn)你會(huì)收到一筆錢Li，但也必須花費(fèi)一筆錢Wi，在某個(gè)地點(diǎn)多出來(lái)的錢可以存到下一個(gè)地點(diǎn)使用。但是如果你在某個(gè)地點(diǎn)沒能花夠Wi，對(duì)不起，你就會(huì)out。到達(dá)最多的地方的隊(duì)伍獲勝。相信自己！這就是夢(mèng)！！好吧，夢(mèng)醒了，問題來(lái)了，在夢(mèng)里我最多可以到達(dá)幾個(gè)地點(diǎn)？
Input
有多組樣例，每個(gè)樣例第一行是一個(gè)正整數(shù)n(1<=n<=100000)，表示有n個(gè)地點(diǎn)，接下來(lái)一行按照路線順序有n組數(shù)據(jù)（Li，Wi），表示每個(gè)地點(diǎn)的收入和花費(fèi)（正整數(shù)）。
Output
輸出最多可以到達(dá)幾個(gè)地點(diǎn)。
Sample Input
33 2 3 4 2 233 2 3 4 2 3
Sample Output
32開始還以為是DP，跪了半個(gè)小時(shí)連樣例都過(guò)不了，然后果斷放棄。賽后經(jīng)過(guò)孟神講解才發(fā)現(xiàn)其實(shí)很簡(jiǎn)單，本質(zhì)就是一個(gè)求最大連續(xù)和，只不過(guò)求的不是和，而是求最長(zhǎng)的連續(xù)個(gè)數(shù)。然后定義：presum : 當(dāng)前和prenum:當(dāng)前的連續(xù)個(gè)數(shù)ans       :最終結(jié)果然后當(dāng)presum小于0時(shí)（說(shuō)明不能再往前走了），就更新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
今天，給大家一個(gè)簡(jiǎn)單題??！相信大家在寫代碼的時(shí)候，總是在不斷的切換大小寫.....當(dāng)在大寫沒有鎖定的時(shí)候 shift + 字母 打印出大寫字母，而在大寫鎖定的時(shí)候 shift + 字母 打印出小寫字母?。〉强偸且催@么多鍵好累的??！要高效的工作?。∫虼?，給一個(gè)字符串，有大小寫字母組成，求最少的按鍵次數(shù).....鍵有（26個(gè)字母和shift和caps lock），起始狀態(tài)在小寫??！hint:shift鍵不能一直按著??！，最后鍵的狀態(tài)若在大寫狀態(tài)不必改為小寫。
Input
多個(gè)測(cè)試?yán)?，每個(gè)例子輸入一個(gè)字符串，長(zhǎng)度小于10000
Output
輸出最少的按鍵次數(shù)
Sample Input
aaaaAaaaaaaaAAAaAAA
Sample Output
9104
暴力模擬即可，AC的第一道題，感覺思路很直接。定義一個(gè)變量flag。flag = 0:當(dāng)前是小寫輸入狀態(tài)。flag = 1:當(dāng)前是大寫輸入狀態(tài)。
#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完后，濤哥哥還是不滿意。他認(rèn)為這些樹的高度參差不齊，太影響校容了，必須從左往右改變樹高，使樹高為等差數(shù)列的才算是beautiful！那么問題來(lái)了，沒吃藥的濤哥哥對(duì)著任何一棵樹念一分鐘咒語(yǔ)，就可以把樹的高度改變。機(jī)智的你能幫他算出他最少需要幾分鐘能將這排樹變成他心中beautiful樣子呢？雖然濤哥哥沒有吃藥，但是他不能把一棵樹的高度成負(fù)數(shù)。
Input
輸入一個(gè)T，表示有T組樣例。（1<=T<=100）再輸入一個(gè)n，d，表示種下了n棵樹和想要的公差（改變后右邊的樹高減左邊的樹高），接下的n行里，每行輸入k，high，分別表示樹種下的位置以及樹原有的高度，當(dāng)然同一位置不會(huì)種多棵樹。（1<=k<=n<=100，0<=d，0<=high<=1000，且數(shù)據(jù)皆為整數(shù)）
Output
輸出一個(gè)num，代表最少需要的時(shí)間。
Sample Input
14 11 12 23 1 4 5
Sample Output
2DP：我的思路是用：總數(shù)  減去  已經(jīng)相應(yīng)排列成等差數(shù)列的樹的數(shù)量最大值假設(shè)第k棵樹的高度不變，設(shè)在其前面的k-1棵樹中與其對(duì)應(yīng)成等差數(shù)列關(guān)系的樹的數(shù)量（包括自己）是dp[k]。當(dāng)我們已知前n棵樹的dp[i]（i= 1....n）的值，則求 dp[n+1]時(shí)，可以從n遍歷到1，如果有其中某一棵樹m的高度與第n+1棵樹的高度對(duì)應(yīng)成等差數(shù)列，則dp[n+1] = dp[m] + 1。然后從dp[i] （i= 1.....n）找出一個(gè)最大值，然后用總數(shù)減去最大值就是答案。
#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
某某某今天很開心，媽媽昨天對(duì)他說(shuō)：“你老大不小了，還找不到女朋友，個(gè)頭是個(gè)大問題。聽說(shuō)最近市場(chǎng)上出了幾種藥，能長(zhǎng)個(gè)頭，明天給你去買幾種吃，吃哪種，你說(shuō)了算，只要不超過(guò)N元錢就行”。今天一早他就開始做預(yù)算，但是他很愛嘗試各種藥，想買的品種太多了，肯定會(huì)超過(guò)媽媽限定的N元。于是，他把每件物品規(guī)定了一個(gè)重要度，分為5等：用整數(shù)1~5表示，第5等最重要。他還從因特網(wǎng)上查到了每種藥的價(jià)格（都是整數(shù)元）。他希望在不超過(guò)N元（可以等于N元）的前提下，使每種藥的價(jià)格與重要度的乘積的總和最大。設(shè)第j件藥的價(jià)格為v[j]，重要度為w[j]，共選中了k件物品，編號(hào)依次為j1，j2，……，jk，則所求的總和為：v[j1] * w[j1] + v[j2] * w[j2] +…+ v[jk] * w[jk]。（其中*為乘號(hào)）請(qǐng)你幫助他設(shè)計(jì)一個(gè)滿足要求的購(gòu)物單。
Input
輸入包含多個(gè)測(cè)試數(shù)據(jù)。每個(gè)測(cè)試數(shù)據(jù)的第1行，為兩個(gè)正整數(shù)，用一個(gè)空格隔開：N,m其中N（<30000）表示總錢數(shù)，m（<25）為希望購(gòu)買藥品的種數(shù)。從第2行到第m+1行，每行有2個(gè)非負(fù)整數(shù)v,w（其中v表示該藥品的價(jià)格(v<=10000)，w表示該藥品的重要度(1~5)）
Output
對(duì)于每個(gè)測(cè)試數(shù)據(jù)輸出一行，其中只含有一個(gè)正整數(shù)，為不超過(guò)總錢數(shù)的藥品的價(jià)格與重要度乘積的總和的最大值（<100000000）。
Sample Input
1000 5800 2400 5300 5400 3200 2
Sample Output
3900
01背包，只不過(guò)狀態(tài)轉(zhuǎn)移時(shí)要多一層條件。
#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
小邊為了尋找夢(mèng)寐以求的骨頭誤入一個(gè)迷宮,它靈敏的嗅覺告訴它,在迷宮中的某一處有一塊完美的骨頭.由于迷宮會(huì)在一段時(shí)間后關(guān)閉,所以小邊必須在一定時(shí)間找到那塊骨頭,這樣才能有充足的時(shí)間來(lái)帶著骨頭離開.小邊在迷宮中可以從當(dāng)前位置走到相鄰的位置,每次移動(dòng)消耗單位時(shí)間,當(dāng)然,因?yàn)樾∵厡?duì)骨頭的無(wú)比執(zhí)著,它偶爾會(huì)使出絕技”狗急跳墻”(一次移動(dòng)兩個(gè)單位位置,同樣消耗單位時(shí)間).使用這個(gè)技能的時(shí)候,可以翻過(guò)一面單位厚度的墻(即第一步移動(dòng)可以踩在墻上,當(dāng)然也可以不踩).hint：使用技能的時(shí)候，不用管中間那一步是否可走。那么小邊能夠如愿以償?shù)恼业焦穷^并離開迷宮么?
Input
多組輸入每組輸入第一行是四個(gè)數(shù)m,n(0<m,n<=30),k(0<=k<=30),t(0<=t<=100),分別代表迷宮的長(zhǎng),寬,小邊使用”狗急跳墻”的最大次數(shù)以及找到骨頭的時(shí)間限制.m=n=k=t=0代表輸入結(jié)束接下的m行每行有n個(gè)字符,‘.’代表地面,’#’代表墻,’@’代表目前小邊所處的位置,’X’代表骨頭所在的位置
Output
若小邊能在規(guī)定時(shí)間內(nèi)找到骨頭,則輸出Yes,否則輸出No.每個(gè)輸出占一行.
Sample Input
3 3 1 2@###.##X#4 4 1 3@.#.#.########X.0 0 0 0
Sample Output
YesNo
迷宮題，讀題不仔細(xì)，還以為狗急跳墻真的只能用于跳墻= =思路：多加一維狀態(tài)，表示此時(shí)還可以使用的技能次數(shù)，然后套路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;}