時(shí)間：2017年2月3號(hào)

總結(jié)：題目偏簡(jiǎn)單。不過(guò)可能是最近囫圇吞棗般地學(xué)了太多算法，自己做題時(shí)的腦洞越來(lái)越少......有時(shí)明明很簡(jiǎn)單的題卻總想往學(xué)過(guò)的算法上面靠....浪費(fèi)了很多時(shí)間，雖然能AC，但效率低了很多。

改進(jìn)：補(bǔ)完以前剩下的hdoj11頁(yè)的水題，另外做題時(shí)學(xué)會(huì)從多個(gè)角度去思考以找到解題的思路。

題目：

1001:

PRoblem A Uppercase - SCUT 2013級(jí)新生選拔賽第二場(chǎng)

Time Limit : 3000/1000ms (java/Other)   Memory Limit : 65535/102400K (Java/Other)

Total Submission(s) : 43   Accepted Submission(s) : 41

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

Input

Output

Sample Input

abcdABCDabCD
Sample Output
042
簽到題
#include <bits/stdc++.h>using namespace std;typedef long long ll;char str[1010];int main(){	while(scanf("%s",str) != EOF){		int len = strlen(str);		int ans = 0;		for(int i=0 ;i<len ;i++){			if(str[i]>='A' && str[i]<='Z')				ans++;		}			printf("%d/n",ans);	}	return 0;}1002:
Problem B XRT in FSK
Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 65535/102400K (Java/Other)
Total Submission(s) : 100   Accepted Submission(s) : 36
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
由于學(xué)校的實(shí)習(xí)安排，XRT被安排去了煙臺(tái)FSK當(dāng)質(zhì)檢工(XRT:為什么是我...)。每次XRT都要檢查n個(gè)小球，已知這n個(gè)小球里面有一個(gè)是比較輕的，其余的n-1個(gè)小球重量都相同。XRT有一個(gè)天平，每次他可以把若干個(gè)球放在左邊，若干個(gè)球放在右邊，然后得到結(jié)果：左邊重，右邊重和平衡。由于XRT的數(shù)學(xué)很弱（XRT：泥垢了....），所以你可以告訴他,最少測(cè)量多少次能保證把比較輕的小球找出來(lái)嗎?
Input
輸入包含多組數(shù)據(jù)對(duì)于每組數(shù)據(jù)，輸入一個(gè)正整數(shù)n（1≤n≤108 ）
Output
每組樣例輸出一行,表示測(cè)量的最少次數(shù).
Sample Input
110
Sample Output
03
好像是初中的物理題....最優(yōu)策略是三分，因?yàn)?的余數(shù)只有0，1，2；所以當(dāng)余數(shù)為0，分為：m   m   m             用m與m比較當(dāng)余數(shù)為1，分為：       m   m   m+1         用m與m比較當(dāng)余數(shù)為2，分為：       m   m+1 m+1       用m+1與m+1比較因?yàn)榇纹肥禽^輕的（已知條件），所以每次比較都可以縮小問(wèn)題規(guī)模到原規(guī)模的1/3。（天平的結(jié)果相等取第三堆，不相等就直接取輕的那一堆）
#include <bits/stdc++.h>using namespace std;typedef long long ll;int main(){    int n;    while(scanf("%d",&n) != EOF){        double t = log(n)/log(3);        int ans = (int)t;        if(t - ans != 0)            ans++;        cout << ans <<endl;    }    return 0;}
1003:
Problem D The sad match I
Time Limit : 3000/3000ms (Java/Other)   Memory Limit : 65535/102400K (Java/Other)
Total Submission(s) : 83   Accepted Submission(s) : 22
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
集訓(xùn)隊(duì)又要選拔了，今年為了壯大集訓(xùn)隊(duì)規(guī)模，學(xué)校打算出很多很多場(chǎng)選拔賽，第i場(chǎng)的持續(xù)時(shí)間是[ai,bi)。每一場(chǎng)選拔賽都必須至少有一個(gè)老隊(duì)員在現(xiàn)場(chǎng)組織。很遺憾的是，選拔賽可能重疊，比如說(shuō)可能有一場(chǎng)比賽在[4,9)舉行，另一場(chǎng)在[6,10)舉行，那么同學(xué)們只能選擇參加其中一場(chǎng)了。當(dāng)然，我絕不會(huì)關(guān)心，你能不能參加的，我關(guān)心的是我到底要不要被迫去現(xiàn)場(chǎng)組織比賽。只要兩場(chǎng)比賽時(shí)間不沖突，他們就可以由同一個(gè)老隊(duì)員組織。現(xiàn)在給出所有的比賽時(shí)間，問(wèn)最少需要多少個(gè)老隊(duì)員作組織工作。例如在[0, 5), [2, 10), [8, 9)各有一場(chǎng)比賽，那么可以讓一個(gè)老隊(duì)員去第一、三場(chǎng)，另一個(gè)老隊(duì)員去第二場(chǎng)，這樣只需要兩個(gè)老隊(duì)員就夠了
Input
輸入的第一行包含一個(gè)整數(shù)T，表示T個(gè)測(cè)試樣例。每一個(gè)測(cè)試樣例的第一行包含一個(gè)正整數(shù)n(n≤105 )，表示有n場(chǎng)選拔賽。接下來(lái)的n行有每行有2個(gè)數(shù)，ai和bi, (0≤ai < bi ≤ 105)。
Output
對(duì)于每組數(shù)據(jù)，輸出至少需要的老隊(duì)員的人數(shù)
Sample Input
324 96 1014 941 32 34 96 10
Sample Output
212
套路題，區(qū)間打標(biāo)記。（雖然數(shù)組名是dp，這道題與dp并沒(méi)有關(guān)系....）
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e5 + 100;int dp[maxn];int main(){	int T;	scanf("%d",&T);	while(T--){		int n;		scanf("%d",&n);		memset(dp,0,sizeof(dp));		while(n--){			int a,b;			scanf("%d%d",&a,&b);			dp[a]++;			dp[b]--;		}			int Max = 0,sum=0;		for(int i=0 ;i<maxn ;i++){			sum += dp[i];			Max = max(sum,Max);		}		printf("%d/n",Max);	}	return 0;}1004：
Problem F Count the continent
Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 65535/102400K (Java/Other)
Total Submission(s) : 49   Accepted Submission(s) : 35
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
給出一個(gè)二維矩陣，表示一張地圖，0表示海洋,1表示陸地，若一塊陸地的坐標(biāo)為(r,c)，如果另一塊陸地為 (r-1,c) 或 (r+1,c) 或 (r,c-1) 或 (r,c+1)，則我們認(rèn)為這兩塊陸地相鄰，所有相鄰的陸地我們稱之為一個(gè)大陸，求大陸的數(shù)量。
Input
輸入包含多組數(shù)據(jù)對(duì)于每組數(shù)據(jù)，輸入第一行為一個(gè)正整數(shù)N (N≤10 )，然后給出一個(gè)N * N 的矩陣接下來(lái)的N行每行N個(gè)元素以空格分開，表示該格是陸地還是海洋。
Output
對(duì)于每組數(shù)據(jù)，輸出大陸的數(shù)量。
Sample Input
41 1 0 01 1 0 00 0 1 00 0 0 030 1 00 1 00 1 030 0 00 1 00 0 0
Sample Output
211
dfs入門題：
#include <bits/stdc++.h>using namespace std;typedef long long ll;int maze[15][15];int n;int dx[4] = {1,-1,0,0},dy[4] = {0,0,1,-1};bool check(int x,int y){	if(x<=0 || x>n || y<=0 || y>n || !maze[x][y]){		return false;	}	return true;}void dfs(int x,int y){	maze[x][y] = 0;	for(int i=0 ;i<4;i++){		int xx = x + dx[i];		int yy = y + dy[i];		if(check(xx,yy))			dfs(xx,yy);	}}int main(){	while(scanf("%d",&n) != EOF){		for(int i=1 ;i<=n ;i++){			for(int j=1 ;j<=n ;j++){				scanf("%d",&maze[i][j]);			}		}		int ans = 0;		for(int i=1 ;i<=n ;i++){			for(int j=1 ;j<=n ;j++){				if(maze[i][j]){					ans++;					dfs(i,j);				}			}		}		printf("%d/n",ans);	}	return 0;}1005：
Problem G Math Problem
Time Limit : 3000/3000ms (Java/Other)   Memory Limit : 65535/102400K (Java/Other)
Total Submission(s) : 60   Accepted Submission(s) : 21
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
已知a, n，求，求(Σni=1 an-i(a-1)i-1 ) mod 1000000007
Input
輸入第一行是一個(gè)正整數(shù)T(T≤1000)，表示有T組數(shù)據(jù)；每組數(shù)據(jù)包含兩個(gè)正整數(shù)a, n(a,n≤109 )。
Output
對(duì)于每組數(shù)據(jù)，輸出上式的結(jié)果。
Sample Input
31 12 25 10
Sample Output
138717049
第一次做這種數(shù)學(xué)公式變形題，我一開始的思路就是怎么合并式子，但化簡(jiǎn)時(shí)出現(xiàn)了（1/a），然后感覺(jué)會(huì)帶來(lái)誤差就直接放棄了先做的后面的題。回頭做時(shí)發(fā)現(xiàn)原來(lái)時(shí)等比數(shù)列求和：最后可以化簡(jiǎn)為： a^n - (a-1)^n然后快速冪即可，但注意負(fù)模的處理。
#include <bits/stdc++.h>using namespace std;typedef long long ll;const ll mod = 1000000007;ll fast_mod(ll x,ll n){	ll ans = 1;	while(n>0){		if(n&1)			ans = ans * x % mod;			x = x * x % mod;		n /= 2;	}	return ans%mod;}int main(){	int T;	scanf("%d",&T);	while(T--){		ll a,n;		scanf("%lld%lld",&a,&n);		if(n==1 || a==1){			printf("1/n");			continue;		}		if(a==0){			printf("0/n");			continue;		}				ll ans = (fast_mod(a,n) - fast_mod(a-1,n) + mod)%mod;		printf("%lld/n",ans);	}	return 0;}1006
Problem I Zeros
Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 65535/102400K (Java/Other)
Total Submission(s) : 54   Accepted Submission(s) : 36
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
給出n，計(jì)算n！末尾0的個(gè)數(shù)
Input
輸入包含多組數(shù)據(jù)每組數(shù)據(jù)包含一個(gè)正整數(shù)n (n≤109 )
Output
對(duì)于每組數(shù)據(jù)，輸出n！末尾0的個(gè)數(shù)
Sample Input
351001024
Sample Output
0124253
之前做過(guò)的題，印象很深刻.....
#include <bits/stdc++.h>using namespace std;typedef long long ll;int ans;void solve(int x){	while(x>=5){		x /= 5;		ans += x;	}}int main(){	int n;	while(scanf("%d",&n) != EOF){		ans = 0;		solve(n);			cout << ans << endl;	}	return 0;}1007：
Problem J It didn't hate
Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 65535/102400K (Java/Other)
Total Submission(s) : 42   Accepted Submission(s) : 29
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
東東特別討厭“11”，他將所有含有“11”子串的01串（只有0和1組成串）稱為光棍。長(zhǎng)度為2的光棍有1種：11；長(zhǎng)度為3的光棍有3種：011,110,111；長(zhǎng)度為4的光棍有8種：0011,0110,1100,1011,1101,1110,0111,1111；給出n，東東想知道長(zhǎng)度為n的光棍有多少？
Input
輸入包含大量數(shù)據(jù)，大約1000組左右每組數(shù)據(jù)包含一個(gè)1個(gè)正整數(shù)n(n≤106 )。
Output
對(duì)于每組數(shù)據(jù)，輸出長(zhǎng)度為n的光棍串的數(shù)量模1000000007的結(jié)果。
Sample Input
1469504
Sample Output
08632157493
DP:設(shè)dp[n][0]:長(zhǎng)度為n的合法數(shù)dp[n][1]:長(zhǎng)度為n，首位為1的非法數(shù)dp[n][2]:長(zhǎng)度為n，首位為0的非法數(shù) 所以狀態(tài)轉(zhuǎn)移方程：dp[n][0] = dp[n-1][0]*2 + dp[n-1][1];dp[n][1] =  dp[n-1][2];dp[n][2] = dp[n-1][1] + dp[n-1][2];
#include <bits/stdc++.h>using namespace std;typedef long long ll;const ll mod = 1000000007;const int maxn = 1e6 + 10;ll dp[maxn][3]; void init(void){	dp[0][0] = dp[0][1] = dp[0][2] = 0;	dp[1][0] = 0;	dp[1][1] = dp[1][2] = 1;	for(int i=2 ;i<maxn ;i++){		dp[i][0] = (dp[i-1][0] * 2 + dp[i-1][1])%mod;		dp[i][1] = dp[i-1][2] % mod;		dp[i][2] = (dp[i-1][1] + dp[i-1][2]) % mod;	}	}int main(){	init();	int n;	while(scanf("%d",&n) != EOF){		printf("%lld/n",dp[n][0]);	}	return 0;}1008:
Problem C Flip
Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 65535/102400K (Java/Other)
Total Submission(s) : 58   Accepted Submission(s) : 24
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
康哥哥和康妹妹經(jīng)常在一起玩游戲。其中一種就是硬幣翻轉(zhuǎn)。游戲的規(guī)則如下：1. N*M（N行，M列）的棋盤上，棋盤上每個(gè)位置都有個(gè)硬幣，不是朝上就是朝下；2. 兩人輪流進(jìn)行操作，不能進(jìn)行操作的人輸，當(dāng)棋盤上所有硬幣都朝下時(shí)游戲結(jié)束；3. 每次操作都在棋盤上選擇一個(gè)矩形，這個(gè)矩形的左上角和右下角位置分別是（x1，y1）和（N，M），然后翻轉(zhuǎn)這個(gè)矩形區(qū)域內(nèi)的所有硬幣，即把朝上的變成朝下的，把朝下的變成朝上的，（x1，y1）是操作者選定的，唯一限制是每次選定的左上角位置（x1，y1）必須從向上翻轉(zhuǎn)為向下；康哥哥曾經(jīng)給康妹妹一個(gè)問(wèn)題，假如給你最初棋盤的分布情況，你能確定最終誰(shuí)能贏嗎？假如兩人都采用最優(yōu)策略去玩游戲，游戲每次都是康哥哥先移動(dòng)。你能幫康妹妹解決這個(gè)問(wèn)題嗎？
Input
第一行輸入一個(gè)正整數(shù)T，接下來(lái)有T組數(shù)據(jù)(T≤50)。每組數(shù)據(jù)的首行輸入N和M（N，M如上所述），接下來(lái)輸入N行，每行有M個(gè)正整數(shù)，每個(gè)正整數(shù)不是0就是1，0表示硬幣向下，1表示硬幣向上。（1≤N,M≤20）
Output
對(duì)于每組數(shù)據(jù)，如果康哥哥能贏，輸出YES，否則輸出NO。康哥哥友情提示：這題真的不難，注意觀察條件。
Sample Input
22 21 11 13 30 0 00 0 00 0 0
Sample Output
YESNO博弈。首先明確一點(diǎn)：翻硬幣時(shí)無(wú)論玩家怎么選擇矩形左上角的點(diǎn)，點(diǎn)（n,m）都一定會(huì)被翻過(guò)來(lái)。然后簡(jiǎn)單模擬一下：假設(shè)點(diǎn)（n,m）的硬幣初始態(tài)為0首先哥哥操作： 0 -> 1然后妹妹操作： 1 -> 0哥哥：   0 -> 1妹妹：   1 -> 0哥哥：   0 -> 1妹妹：   1 -> 0.....我們發(fā)現(xiàn)，每次妹妹操作完，輪到哥哥翻硬幣時(shí)，點(diǎn)（n,m）硬幣的狀態(tài)都與初始態(tài)相同。而我們又知道結(jié)束狀態(tài)點(diǎn)（n,m）硬幣狀態(tài)一定是0。所以對(duì)于上面的例子，哥哥一定是輸，因?yàn)槊看胃绺绮僮鞫际窃诎腰c(diǎn)（n,m）的硬幣從0 -> 1，所以永遠(yuǎn)到達(dá)不了必?cái)↑c(diǎn)，即棋面全為0的狀態(tài)哥哥是永遠(yuǎn)到達(dá)不了的。所以：我們只需要判斷點(diǎn)（n,m）的初始態(tài)是0還是1，如果是1，則哥哥必贏，否則，妹妹必贏。代碼：
#include <bits/stdc++.h>using namespace std;typedef long long ll;int main(){	int T;	scanf("%d",&T);	while(T--){		int x,n,m;		int ans = 0;		scanf("%d%d",&n,&m);		for(int i=1 ;i<=n ;i++){			for(int j=1 ;j<=m ;j++){				scanf("%d",&x);			}		}		if(x)	puts("YES");		else	puts("NO");	}	return 0;}