前段時間牛客網舉辦了編程馬拉松大賽，總共86道題，20天內完畢。

題目難度難中易都有。我發現這些題目，主要關注性能和思維。

非常多題目用常規方法是不能通過時間要求的。題目是來自于各大oj以及面試題。所以非常適合面試前的練手。
大賽地址：http://www.nowcoder.com/ta/hackathon不知道以后還可不能夠用。反正結束了。

這里我貼出一些試題和我做的代碼~

---

NowCoder猜想

題目描寫敘述

nowcoder在家極度無聊。于是找了張紙開始統計素數的個數。
設函數f(n)返回從1-n之間素數的個數。
nowcoder 發現:
f(1) = 0
f(10) = 4
f(100) = 25
…
滿足g(m) = 17 * m^2 / 3 - 22 * m / 3 + 5 / 3
當中m為n的位數。
他非常激動，是不是自己發現了素數分布的規律了！

請你設計一個程序，求出f(n)。來驗證nowcoder是不是正確的，或許還能夠得諾貝爾獎呢。^_^

輸入描寫敘述:
輸入包括多組數據。
每組數據僅有一個整數n (1≤n≤10000000)。

輸出描寫敘述:
對于每組數據輸入，輸出一行。為1->n(包括n)之間的素數的個數。

輸入樣例:
1
10
65
100
0

輸出樣例:
0
4
18
25

---

代碼

// write your code here cpp #include <string.h> #include <algorithm> #include <iostream> using namespace std;const int N = 10000000 + 10; bool prime[N]; int hs[664579 + 10]; void getPrimeTable() {for (int i = 3; i <= 3333; i += 2){if (prime[i]==0)for (int j = i*i; j < N; j += 2 * i)prime[j] = 1;}int total = 1;hs[1] = 2;for (int i = 3; i < N; ++i){if (i % 2 != 0 && prime[i]==0){hs[++total] = i;}} } int main() {getPrimeTable();int n, i;while (scanf("%d", &n), n){for ( i = 1; i <= 664579; ++i)if (hs[i] > n && hs[i - 1] <= n)break;printf("%d\n", i-1);}return 0; }

---

分遺產

時間限制：1秒空間限制：32768K
通過比例：13.93%
最佳記錄：0 ms|8460K （來自 僅僅想有創意）

題目描寫敘述

有一位阿拉伯老人，生前養有11匹馬。他去世前立下遺囑：大兒子、二兒子、小兒子分別繼承遺產的1/2、1/4、1/6。
兒子們想來想去沒法分：他們所得到的都不是整數，即分別為11/2、11/4、11/6，總不能把一匹馬割成幾塊來分吧？
聰明的鄰居牽來了自己的一匹馬，對他們說：“你們看，如今有12匹馬了，老大得12匹的1/2就是6匹，老二得12匹的1/4就是3匹， 老三得12匹的1/6就是2匹。還剩一匹我照舊牽回家去。”這樣把難分的問題攻克了。
如今又有一個老人要分遺產了，他有m匹馬(1≤m≤1000000)，而且有n個兒子(1≤n≤10)。每一個兒子分別得到1/a1、1/a2、…、1/an的遺產。
由于馬不能切割。而且遺產要所有分完，所以請你用上面那位聰明的鄰居的方法計算一下每一個兒子能分到幾匹馬。

輸入描寫敘述:
輸入包括多組測試數據。
每組測試數據包括兩行：
第一行為m、n。分別代表老人擁有的馬匹數和幾個兒子。
第二行有n個數據a1、a2、…、an。依次代表大兒子、二兒子…第n個兒子分到的遺產的份額。(0 < ai < 50)
程序以輸入0 0結束。該行不做處理。

輸出描寫敘述:
依照上面介紹的方法解決問題。

假設那種方法不能解決問題(即所有兒子不能得到整數匹馬)，則你的程序要輸出”Can’t Solve”；
否者依次輸出大兒子、二兒子…得到的馬的匹數。
每一個數之間有一個空格隔開(最后一個數據后面沒有空格)。

輸入樣例:
11 3
2 4 6
2 2
3 3
0 0

輸出樣例:
6 3 2
1 1

---

代碼

// write your code here cpp #include<iostream> using namespace std; int LCM(int num1,int num2){int x,y;if(num1<num2){num1^=num2;num2^=num1;num1^=num2;}x=num1;y=num2;while(y!=0){int temp=x%y;x=y;y=temp;}return (num1*num2)/x; } int main(){int n,m;while (cin>>m>>n&&n!=0&&m!=0){int temp=1;int sum=0;int Multiply=1;int heritage[10];for (int i = 0; i <n; i++){cin>>heritage[i];}for (int i = 0; i <n; i++){temp=LCM(temp,heritage[i]);Multiply*=heritage[i];}for (int i = 0; i <n; i++){sum+=temp/heritage[i];}if (m%sum==0){ int k=m/sum;for (int i = 0; i <n-1; i++){cout<<k*temp/heritage[i]<<" ";}cout<<k*temp/heritage[n-1]<<endl;}else{cout<<"Can't Solve"<<endl;}}return 0; }

---

素數和

參與人數：36時間限制：1秒空間限制：32768K
通過比例：10.10%
最佳記錄：80 ms|8888K （來自 夕陽古道）
題目描寫敘述

NowCoder發現某些整數能夠拆分成兩個不同的素數的和。比如7=2+5、20=3+17=7+13等。

他想知道每一個正整數都有幾種拆分的方法。你能幫他解決嗎？
輸入描寫敘述:
輸入包括多組數據。

每組數據僅有一個整數n (1≤n≤100000)。

輸出描寫敘述:
相應每一個整數，輸出其拆成不同素數和的個數。每一個結果占一行。

輸入樣例:
30
26
20

輸出樣例:
3
2
2

---

代碼：

// write your code here cpp #include <stdio.h> #include <string.h> #include <algorithm> #include <iostream>#include <math.h> using namespace std; const int N = 100000 + 10; bool vis[N]; int prime[N]; int cnt; int hs[N]; void makePrimeTable() {for (int i = 3; i < 320; ++i){if (!vis[i])for (int j = i*i; j < N; j += 2 * i)vis[j] = true;}prime[cnt++] = 2;for (int i = 3; i < N; ++i)if ((i & 1) == 1 && !vis[i])prime[cnt++] = i; } int main() {int n;makePrimeTable();for (int i = 0; i < cnt; ++i)for (int j = i + 1; prime[i] + prime[j]<=100000 && j < cnt; ++j){hs[prime[i] + prime[j]]++;}while (scanf("%d", &n) != EOF){printf("%d\n", hs[n]);}return 0; }

---

包括一

參與人數：21時間限制：1秒空間限制：32768K
通過比例：21.59%
最佳記錄：0 ms|8460K （來自 僅僅想有創意）
題目描寫敘述

NowCoder總是力爭上游，凡事都要拿第一，所以他對“1”這個數情有獨鐘。愛屋及烏，他也非常喜歡包括1的數，比如10、11、12……。你能幫他統計一下有多少個包括1的正整數嗎？
輸入描寫敘述:
輸入有多組數據。每組數據包括一個正整數n。(1≤n≤2147483647)。

輸出描寫敘述:
相應每組輸入。輸出從1到n（包括1和n）之間包括數字1的正整數的個數。

輸入樣例:
1
9
10
20

輸出樣例:
1
1
2
11

---

代碼：

// write your code here cpp #include <string.h> #include <iostream> #include <algorithm> using namespace std; const int INF = 1 << 30; #pragma warning(disable:4996)/* dp[i][0] 表示長度為i。不含1的數 dp[i][1] 表示長度為i，含1的數字 dp[i][1] = dp[i-1][1] * 10 + dp[i-1][0] */ int dp[11][2]; int num[11]; int main() {dp[0][0] = 1;for (int i = 1; i <= 10; ++i){dp[i][0] = dp[i - 1][0] * 9;dp[i][1] = dp[i - 1][1] * 10 + dp[i - 1][0];}long long n;while (scanf("%lld", &n) != EOF){n++;int len = 0;while (n){num[++len] = n % 10;n /= 10;}int ans = 0;bool flag = false;for (int i = len; i >= 1; --i){if (flag)//當前為有num[i]種取法ans += num[i] * (dp[i - 1][0]+dp[i-1][1]);else if (num[i] == 1){//當前為僅僅能取0ans += dp[i - 1][1];flag = true;}else{//當前為有num[i]種取法ans += num[i] * dp[i - 1][1];if (num[i] > 1)ans += dp[i - 1][0];}}printf("%d\n", ans);} }

---

循環數

參與人數：18時間限制：1秒空間限制：32768K
通過比例：28.57%
最佳記錄：0 ms|8460K （來自 西山雨）
題目描寫敘述

142857是一個六位數，我們發現：
142857 * 1 = 142857
142857 * 2 = 285714
142857 * 3 = 428571
142857 * 4 = 571428
142857 * 5 = 714285
142857 * 6 = 857142
即用1到6的整數去乘142857，會得到一個將原來的數首尾相接循環移動若干數字再在某處斷開而得到的數字。
也就是說，假設把原來的數字和新的數字都首尾相接，他們得到的環是同樣的。僅僅是兩個數的起始數字不一定同樣。
請寫一個程序，推斷給定的數不是循環數。

輸入描寫敘述:
輸入包括多組數據。

每組數據包括一個正整數n，n是2到60位的正整數，而且同意前綴0。即001也是合法的輸入數據。

輸出描寫敘述:
相應每一組數據。假設是循環數。則輸出“Yes”；否則，輸出“No”。

輸入樣例:
142857
012345

輸出樣例:
Yes
No

---

代碼：

// write your code here cpp #include <iostream> #include <string> using namespace std;string sum(string s1,string s2){if(s1.length()<s2.length()){string temp=s1;s1=s2;s2=temp;}int i,j;for(i=s1.length()-1,j=s2.length()-1;i>=0;i--,j--){s1[i]=char(s1[i]+(j>=0?s2[j]-'0':0)); //注意細節if(s1[i]-'0'>=10){s1[i]=char((s1[i]-'0')%10+'0');if(i) s1[i-1]++;else s1='1'+s1;}}return s1;}int main(){string str;string::size_type i,j,size_str;while(cin>>str){string str1(str);size_str= str.size();while(--size_str){str1 = sum(str1,str);if(str1.size() != str.size()) break;for(i = 0; i < str.size(); i++){for(j = 0; j < str1.size(); j++){if(str1[j] != str[(i + j) % str.size()]) break;}if(j >= str1.size()) break;}if(i >= str.size()) break;}if(size_str)cout<<"No"<<endl;elsecout<<"Yes"<<endl;}return 0;}

---

強勢糖果

參與人數：15時間限制：1秒空間限制：32768K
通過比例：48.48%
最佳記錄：0 ms|8460K （來自 靜夜漫思2008）
題目描寫敘述

NowCoder是一個好勝心特別強的人。小時候他和他弟弟分糖果時，他要求自己糖果的總數量必須比弟弟多，也不同意弟弟獨自擁有某種類型的糖果。如今請你幫忙推斷一下媽媽分好的兩堆糖果是否能讓他愜意。
輸入描寫敘述:
輸入有多組數據。

每組數據包括兩個字符串A、B，代表NowCoder與弟弟分到的糖果，每種糖果用一個大寫字母表示，即同樣類型的糖果為同樣的大寫字母。

字符串長度不大于10000。

輸出描寫敘述:
每一組輸入相應一行輸出：假設NowCoder擁有的糖果數量比弟弟多，而且弟弟擁有的糖果類型NowCoder同樣都有，則輸出“Yes”；否則輸出“No”。

輸入樣例:
ABCDFYE CDE
ABCDGEAS CDECDE
ABC AAAA

輸出樣例:
Yes
Yes
No

---

代碼：

// write your code here cpp #include <iostream> #include <string> using namespace std;void judge(string &nowcoder,string &brother) {if(nowcoder.length() <= brother.length()){cout<<"No"<<endl;return;}int hashTable[26] = {0};for ( int i = 0; i < nowcoder.length(); ++i )hashTable[nowcoder[i]-'A']++;for ( int i = 0; i < brother.length(); ++i ){if(hashTable[brother[i]-'A']==0){cout<<"No"<<endl;return;}}cout<<"Yes"<<endl; }int main() {string s,t;while (cin>>s>>t){int hash[26]={0};bool temp=false;for (int i=0;i<s.length();i++){hash[s[i]-'A']++;}for (int i=0;i<t.length();i++){if (hash[t[i]-'A']!=0){temp=true;}elsetemp=false;}if (s.length()>t.length()&&temp){cout<<"Yes"<<endl;}elsecout<<"No"<<endl;}return 0; }

---

Homework

參與人數：12時間限制：1秒空間限制：32768K
通過比例：15.71%
最佳記錄：0 ms|8460K （來自 僅僅想有創意）
題目描寫敘述

臨近開學了，大家都忙著收拾行李準備返校，但nowcoder卻不為此操心!
由于他的心思全在暑假作業上：眼下為止還未開動(-_-!!還以為他有多冷靜呢)。
暑假作業是非常多張試卷，我們這些從試卷里爬出來的人都知道。卷子上的題目有選擇題、填空題、簡答題、證明題等。
而做選擇題的優點就在于工作量非常少。但又由于選擇題題目都普遍非常長。

假設有5張試卷，當中4張是選擇題，最后一張是填空題。非常明顯做最后一張所花的時間要比前4張長非常多。

但假設你僅僅做了選擇題，盡管工作量非常少，但表明上看起來也已經做了4/5的作業了。 nowcoder決定就用這個方案來蒙混過關。
他統計出了做完每一張試卷所需的時間以及它做完后能得到的價值（按上面的原理，選擇題越多價值當然就越高咯）。
如今就請你幫他安排一下，用他僅剩的一點時間來做最有價值的作業。

輸入描寫敘述:
測試數據包括多組。
每組測試數據以兩個整數M。N(1≤M≤20, 1≤N≤10000)開頭，分別表示試卷的數目和redraiment剩下的時間。

接下來有M行。每行包括兩個整數T，V(1≤T≤N,0輸入以0 0結束。

輸出描寫敘述:
相應每組測試數據輸出redraiment能獲得的最大價值。

保留小數點2位

輸入樣例:
4 20
4 10
5 22
10 3
1 2
0 0

輸出樣例:
37.00

---

代碼：

// write your code here cpp #include <iostream> #include <vector> #include <algorithm> #include <iomanip> using namespace std;struct Homework {int num;int value;double average;bool operator < ( const Homework & h ) const{return (average < h.average);} };int main() {int M, N;vector<Homework> hwork;while (cin >> M >> N && (M || N ) ){double totalValue = 0.0;hwork.resize( M );for ( int i = 0; i < M; i++ ){cin >> hwork[i].num >> hwork[i].value;hwork[i].average = (double)(hwork[i].value) / hwork[i].num;}sort( hwork.begin(), hwork.end() );for ( int i = M-1; N > 0 && i >= 0; ){if ( N >= hwork[i].num ){N -= hwork[i].num;totalValue += hwork[i].value;--i;}else{totalValue += (double)(N) / hwork[i].num * hwork[i].value;break;}}cout << setiosflags( ios::fixed ) << setprecision( 2 ) << totalValue << endl;hwork.clear();}return 0; }

發工資

參與人數：17時間限制：1秒空間限制：32768K
通過比例：70.83%
最佳記錄：0 ms|8460K （來自 僅僅想有創意）
題目描寫敘述

對于財務處的工作人員來說，發工資那天是最忙碌的。

財務處的NowCoder近期在考慮一個問題：假設每一個員工的工資額都知道，最少須要準備多少張人民幣，才干在給每位同事發工資的時候都不用找零呢？
這里假設員工的工資都是正整數，單位元，人民幣一共同擁有100元、50元、20元、10元、5元、2元和1元七種。

輸入描寫敘述:
輸入數據包括多個測試實例，每一個測試實例的第一行是一個整數n (n≤100)。表示人數，然后是n個員工的工資。

輸出描寫敘述:
對于每一個測試實例輸出一個整數x,表示至少須要準備的人民幣張數。每一個輸出占一行。

輸入樣例:
3
1 2 3
3
100 200 300

輸出樣例:
4
6

---

代碼：

// write your code here cpp #include<iostream> #include<vector> #include<algorithm>using namespace std;const int MAX= 110; vector<int> dp(MAX);int main() {int n;int count = 0;int index;int w[] = {0,1,2,5,10,20,50,100};vector<int> weight(w,w + 8);while(cin >> n){count = 0;while(n--){cin >> index;if(index > 100) {count += index / 100;index = index % 100;}for(int i = 1;i <= index;++i){dp[i] = i;}dp[0] = 0;for(int i = 2;i <= 7;++i){for(int j = weight[i];j <= index;++j){dp[j] = min(dp[j],dp[j - weight[i]] + 1);}}count += dp[index];}cout << count << endl;}return 0; }

---

單詞迷陣

參與人數：12時間限制：1秒空間限制：32768K
通過比例：18.97%
最佳記錄：0 ms|8460K （來自 僅僅想有創意）
題目描寫敘述

單詞迷陣游戲就是從一個10x10的字母矩陣中找出目標單詞。查找方向能夠從左往右、從右往左、從上往下或者從下往上。

比如以下的迷陣中包括quot等單詞。
rmhlzxceuq
bxmichelle
mnnejluapv
caellehcim
xdydanagbz
xinairbprr
vctzevbkiz
jgfavqwjan
quotjenhna
iumxddbxnd
現給出一個迷陣，請你推斷某個單詞是否存在當中。

輸入描寫敘述:
輸入有多組數據。

每組數據包括兩部分。

第一部分有10行，是一個10x10的字母矩陣。

第二部分第一行包括一個整數n (1≤n≤100)，緊接著n行，每行包括一個單詞。單詞的長度不會超過10。

輸出描寫敘述:
相應每一個單詞，假設它存在于迷陣之中。則輸出“Yes”；否則輸出“No”。

每一組數據之后輸出一個空行作為分隔。

輸入樣例:
rmhlzxceuq
bxmichelle
mnnejluapv
caellehcim
xdydanagbz
xinairbprr
vctzevbkiz
jgfavqwjan
quotjenhna
iumxddbxnd
7
dan
danz
brian
michelle
jen
jqi
paul
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
2
aaa
bbb

輸出樣例:
Yes
Yes
Yes
Yes
Yes
Yes
Yes

Yes
No

---

代碼：

// write your code here cpp #include<stdio.h> #include <string.h> using namespace std;char a[10][10]; char str[100]; bool flag; int dx[] = { 1, -1, 0, 0 }; int dy[] = { 0, 0, -1, 1 }; bool f(int x, int y, int n) {int t;int tmpx = x, tmpy = y;for (int i = 0; i < 4; ++i){t = 1;x = tmpx;y = tmpy;while ((dx[i] + x) >= 0 && (dx[i] + x)<10 && (dy[i] + y) >= 0 && (dy[i] + y) < 10 && a[dx[i]+x][dy[i]+y]==str[t]&&t<n){t++;x += dx[i];y += dy[i];}if (t >= n)return true;}return false; } int main() {int n, len;while (scanf("%s", a[0]) != EOF){for (int i = 1; i < 10; ++i)scanf("%s", a[i]);scanf("%d", &n);for (int i = 0; i < n; ++i){scanf("%s", str);len = strlen(str);flag = false;for (int j = 0; j < 10; ++j){for (int k = 0; k < 10; ++k){if (a[j][k] == str[0]){flag = f(j, k, len);}if (flag)break;}if (flag)break;}if (flag)puts("Yes");elseputs("No");}} }

總結

以上是生活随笔為你收集整理的编程马拉松大赛试题及代码（C++实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。