時間：2017年2月3號
總結：題目偏簡單。不過可能是最近囫圇吞棗般地學了太多算法，自己做題時的腦洞越來越少......有時明明很簡單的題卻總想往學過的算法上面靠....浪費了很多時間，雖然能AC，但效率低了很多。
改進：補完以前剩下的hdoj11頁的水題，另外做題時學會從多個角度去思考以找到解題的思路。
題目：
1001:
abcdABCDabCDSample 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
由于學校的實習安排，XRT被安排去了煙臺FSK當質檢工(XRT:為什么是我...)。每次XRT都要檢查n個小球，已知這n個小球里面有一個是比較輕的，其余的n-1個小球重量都相同。XRT有一個天平，每次他可以把若干個球放在左邊，若干個球放在右邊，然后得到結果：左邊重，右邊重和平衡。由于XRT的數學很弱（XRT：泥垢了....），所以你可以告訴他,最少測量多少次能保證把比較輕的小球找出來嗎?Input
輸入包含多組數據對于每組數據，輸入一個正整數n（1≤n≤108 ）Output
每組樣例輸出一行,表示測量的最少次數.Sample Input
110Sample Output
03好像是初中的物理題....最優策略是三分，因為3的余數只有0，1，2；所以當余數為0，分為：m m m 用m與m比較當余數為1，分為： m m m+1 用m與m比較當余數為2，分為： m m+1 m+1 用m+1與m+1比較因為次品是較輕的（已知條件），所以每次比較都可以縮小問題規模到原規模的1/3。（天平的結果相等取第三堆，不相等就直接取輕的那一堆）#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
集訓隊又要選拔了，今年為了壯大集訓隊規模，學校打算出很多很多場選拔賽，第i場的持續時間是[ai,bi)。每一場選拔賽都必須至少有一個老隊員在現場組織。很遺憾的是，選拔賽可能重疊，比如說可能有一場比賽在[4,9)舉行，另一場在[6,10)舉行，那么同學們只能選擇參加其中一場了。當然，我絕不會關心，你能不能參加的，我關心的是我到底要不要被迫去現場組織比賽。只要兩場比賽時間不沖突，他們就可以由同一個老隊員組織。現在給出所有的比賽時間，問最少需要多少個老隊員作組織工作。例如在[0, 5), [2, 10), [8, 9)各有一場比賽，那么可以讓一個老隊員去第一、三場，另一個老隊員去第二場，這樣只需要兩個老隊員就夠了Input
輸入的第一行包含一個整數T，表示T個測試樣例。每一個測試樣例的第一行包含一個正整數n(n≤105 )，表示有n場選拔賽。接下來的n行有每行有2個數，ai和bi, (0≤ai < bi ≤ 105)。Output
對于每組數據，輸出至少需要的老隊員的人數Sample Input
324 96 1014 941 32 34 96 10Sample Output
212套路題，區間打標記。（雖然數組名是dp，這道題與dp并沒有關系....）#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
給出一個二維矩陣，表示一張地圖，0表示海洋,1表示陸地，若一塊陸地的坐標為(r,c)，如果另一塊陸地為 (r-1,c) 或 (r+1,c) 或 (r,c-1) 或 (r,c+1)，則我們認為這兩塊陸地相鄰，所有相鄰的陸地我們稱之為一個大陸，求大陸的數量。Input
輸入包含多組數據對于每組數據，輸入第一行為一個正整數N (N≤10 )，然后給出一個N * N 的矩陣接下來的N行每行N個元素以空格分開，表示該格是陸地還是海洋。Output
對于每組數據，輸出大陸的數量。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 0Sample Output
211dfs入門題：#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 1000000007Input
輸入第一行是一個正整數T(T≤1000)，表示有T組數據；每組數據包含兩個正整數a, n(a,n≤109 )。Output
對于每組數據，輸出上式的結果。Sample Input
31 12 25 10Sample Output
138717049第一次做這種數學公式變形題，我一開始的思路就是怎么合并式子，但化簡時出現了（1/a），然后感覺會帶來誤差就直接放棄了先做的后面的題。回頭做時發現原來時等比數列求和：最后可以化簡為： a^n - (a-1)^n然后快速冪即可，但注意負模的處理。#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;}1006Problem 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，計算n！末尾0的個數Input
輸入包含多組數據每組數據包含一個正整數n (n≤109 )Output
對于每組數據，輸出n！末尾0的個數Sample Input
351001024Sample Output
0124253之前做過的題，印象很深刻.....#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組成串）稱為光棍。長度為2的光棍有1種：11；長度為3的光棍有3種：011,110,111；長度為4的光棍有8種：0011,0110,1100,1011,1101,1110,0111,1111；給出n，東東想知道長度為n的光棍有多少？Input
輸入包含大量數據，大約1000組左右每組數據包含一個1個正整數n(n≤106 )。Output
對于每組數據，輸出長度為n的光棍串的數量模1000000007的結果。Sample Input
1469504Sample Output
08632157493DP:設dp[n][0]:長度為n的合法數dp[n][1]:長度為n，首位為1的非法數dp[n][2]:長度為n，首位為0的非法數 所以狀態轉移方程：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
康哥哥和康妹妹經常在一起玩游戲。其中一種就是硬幣翻轉。游戲的規則如下：1. N*M（N行，M列）的棋盤上，棋盤上每個位置都有個硬幣，不是朝上就是朝下；2. 兩人輪流進行操作，不能進行操作的人輸，當棋盤上所有硬幣都朝下時游戲結束；3. 每次操作都在棋盤上選擇一個矩形，這個矩形的左上角和右下角位置分別是（x1，y1）和（N，M），然后翻轉這個矩形區域內的所有硬幣，即把朝上的變成朝下的，把朝下的變成朝上的，（x1，y1）是操作者選定的，唯一限制是每次選定的左上角位置（x1，y1）必須從向上翻轉為向下；康哥哥曾經給康妹妹一個問題，假如給你最初棋盤的分布情況，你能確定最終誰能贏嗎？假如兩人都采用最優策略去玩游戲，游戲每次都是康哥哥先移動。你能幫康妹妹解決這個問題嗎？Input
第一行輸入一個正整數T，接下來有T組數據(T≤50)。每組數據的首行輸入N和M（N，M如上所述），接下來輸入N行，每行有M個正整數，每個正整數不是0就是1，0表示硬幣向下，1表示硬幣向上。（1≤N,M≤20）Output
對于每組數據，如果康哥哥能贏，輸出YES，否則輸出NO。康哥哥友情提示：這題真的不難，注意觀察條件。Sample Input
22 21 11 13 30 0 00 0 00 0 0Sample Output
YESNO博弈。首先明確一點：翻硬幣時無論玩家怎么選擇矩形左上角的點，點（n,m）都一定會被翻過來。然后簡單模擬一下：假設點（n,m）的硬幣初始態為0首先哥哥操作： 0 -> 1然后妹妹操作： 1 -> 0哥哥： 0 -> 1妹妹： 1 -> 0哥哥： 0 -> 1妹妹： 1 -> 0.....我們發現，每次妹妹操作完，輪到哥哥翻硬幣時，點（n,m）硬幣的狀態都與初始態相同。而我們又知道結束狀態點（n,m）硬幣狀態一定是0。所以對于上面的例子，哥哥一定是輸，因為每次哥哥操作都是在把點（n,m）的硬幣從0 -> 1，所以永遠到達不了必敗點，即棋面全為0的狀態哥哥是永遠到達不了的。所以：我們只需要判斷點（n,m）的初始態是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;}
新聞熱點
疑難解答
