前段時(shí)間牛客網(wǎng)舉辦了編程馬拉松大賽，總共86道題，20天內(nèi)完畢。

題目難度難中易都有。我發(fā)現(xiàn)這些題目，主要關(guān)注性能和思維。

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

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

---

NowCoder猜想

題目描寫敘述

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

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

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

輸出描寫敘述:
對于每組數(shù)據(jù)輸入，輸出一行。為1->n(包括n)之間的素?cái)?shù)的個(gè)數(shù)。

輸入樣例:
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; }

---

分遺產(chǎn)

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

題目描寫敘述

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

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

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

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

輸入樣例:
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; }

---

素?cái)?shù)和

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

NowCoder發(fā)現(xiàn)某些整數(shù)能夠拆分成兩個(gè)不同的素?cái)?shù)的和。比如7=2+5、20=3+17=7+13等。

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

每組數(shù)據(jù)僅有一個(gè)整數(shù)n (1≤n≤100000)。

輸出描寫敘述:
相應(yīng)每一個(gè)整數(shù)，輸出其拆成不同素?cái)?shù)和的個(gè)數(shù)。每一個(gè)結(jié)果占一行。

輸入樣例:
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; }

---

包括一

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

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

輸出描寫敘述:
相應(yīng)每組輸入。輸出從1到n（包括1和n）之間包括數(shù)字1的正整數(shù)的個(gè)數(shù)。

輸入樣例:
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的數(shù) dp[i][1] 表示長度為i，含1的數(shù)字 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)//當(dāng)前為有num[i]種取法ans += num[i] * (dp[i - 1][0]+dp[i-1][1]);else if (num[i] == 1){//當(dāng)前為僅僅能取0ans += dp[i - 1][1];flag = true;}else{//當(dāng)前為有num[i]種取法ans += num[i] * dp[i - 1][1];if (num[i] > 1)ans += dp[i - 1][0];}}printf("%d\n", ans);} }

---

循環(huán)數(shù)

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

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

輸入描寫敘述:
輸入包括多組數(shù)據(jù)。

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

輸出描寫敘述:
相應(yīng)每一組數(shù)據(jù)。假設(shè)是循環(huán)數(shù)。則輸出“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)); //注意細(xì)節(jié)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;}

---

強(qiáng)勢糖果

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

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

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

字符串長度不大于10000。

輸出描寫敘述:
每一組輸入相應(yīng)一行輸出：假設(shè)NowCoder擁有的糖果數(shù)量比弟弟多，而且弟弟擁有的糖果類型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

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

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

假設(shè)有5張?jiān)嚲?#xff0c;當(dāng)中4張是選擇題，最后一張是填空題。非常明顯做最后一張所花的時(shí)間要比前4張長非常多。

但假設(shè)你僅僅做了選擇題，盡管工作量非常少，但表明上看起來也已經(jīng)做了4/5的作業(yè)了。 nowcoder決定就用這個(gè)方案來蒙混過關(guān)。
他統(tǒng)計(jì)出了做完每一張?jiān)嚲硭璧臅r(shí)間以及它做完后能得到的價(jià)值（按上面的原理，選擇題越多價(jià)值當(dāng)然就越高咯）。
如今就請你幫他安排一下，用他僅剩的一點(diǎn)時(shí)間來做最有價(jià)值的作業(yè)。

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

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

輸出描寫敘述:
相應(yīng)每組測試數(shù)據(jù)輸出redraiment能獲得的最大價(jià)值。

保留小數(shù)點(diǎn)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; }

發(fā)工資

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

對于財(cái)務(wù)處的工作人員來說，發(fā)工資那天是最忙碌的。

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

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

輸出描寫敘述:
對于每一個(gè)測試實(shí)例輸出一個(gè)整數(shù)x,表示至少須要準(zhǔn)備的人民幣張數(shù)。每一個(gè)輸出占一行。

輸入樣例:
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; }

---

單詞迷陣

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

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

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

輸入描寫敘述:
輸入有多組數(shù)據(jù)。

每組數(shù)據(jù)包括兩部分。

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

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

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

每一組數(shù)據(jù)之后輸出一個(gè)空行作為分隔。

輸入樣例:
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");}} }

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。