前段时间牛客网举办了编程马拉松大赛，总共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)
            {
                //当前为仅仅能取0
                ans +=  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;
            else
                cout<<"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;
            }
            else
                temp=false;
        }
        if (s.length()>t.length()&&temp)
        {
            cout<<"Yes"<<endl;
        }
        else
            cout<<"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");
            else
                puts("No");
        }

    }
}