上机编程题（2016校招）

1、兔子藏洞（CVTE）

一只兔子藏身于20个圆形排列的洞中（洞从1开始编号），一只狼从x号洞开始找,下次隔一个洞找(及在x＋2号洞找)，在下次个两个洞找(及在x＋5号洞找)，它找了n次仍然没有找到。问兔子可能在那些洞中。

输入描述:

输入有多组数据，每组数据一行两个整数分别为x和n(x <= 20,n <= 100000)。

输出描述:

每组数据一行按从小到大的顺序输出兔子可能在的洞，数字之间用空格隔开。若每个洞都不可能藏着兔子，输出-1。

#include<iostream>
using namespace std;
#define num 20             //洞数
int main(){
    int x,n;
    bool flag[num];        //记录狼找过的洞
    while(cin>>x&&cin>>n){
        if(x>20||x<=0) continue;
        memset(flag,0,num*sizeof(bool));
        x=x-1;
        int count=0;
        for(int i=1;i<=n;i++){
            if(flag[x]==0){
                count++;
                flag[x]=1;
            }
            x=(x+i+1)%20;
        }
        if(count==n)
            cout<<-1;
        else{
            for(int i=0;i<num;i++){
                if(flag[i]==0)
                    cout<<i+1<<" ";
            }
        }
        cout<<endl;
    }
    return 0;
}

2、最长公共子串

对于两个字符串，请设计一个时间复杂度为O(m*n)的算法(这里的m和n为两串的长度)，求出两串的最长公共子串的长度。这里的最长公共子串的定义为两个序列U1,U2,..Un和V1,V2,...Vn，其中所求的最长公共子串为原串中的连续字符。

给定两个字符串A和B，同时给定两串的长度n和m。

测试样例：

"1AB2345CD",9,"12345EF",7

返回：4

int findLongest(string A, int n, string B, int m) {
        int **count=new int *[n+1];
        int max=0;
        for(int i=0;i<=n;i++){
            count[i]=new int[m+1];
        }
        for(int i=0;i<=n;i++)
            for(int j=0;j<=m;j++)
                count[i][j]=0;
        for(int i=0;i<n;i++){
           for(int j=0;j<m;j++) {
               if(A[i]==B[j]){
                   count[i+1][j+1]=count[i][j]+1;
                   max=max>=count[i+1][j+1] ? max:count[i+1][j+1];
               }
           }
        }
        return max;
    }

3扎金花（搜狐）

两个搜狐的程序员加了一个月班，终于放假了，于是他们决定扎金花渡过愉快的假期 。

游戏规则：
共52张普通牌，牌面为2,3,4,5,6,7,8,9,10,J,Q,K,A之一，大小递增，各四张； 每人抓三张牌。两人比较手中三张牌大小，大的人获胜。 

对于牌型的规则如下： 
1.三张牌一样即为豹子 
2.三张牌相连为顺子（A23不算顺子） 
3.有且仅有两张牌一样为对子 豹子>顺子>对子>普通牌型 在牌型一样时，比较牌型数值大小（如AAA>KKK,QAK>534，QQ2>10104） 在二人均无特殊牌型时，依次比较三张牌中最大的。大的人获胜，如果最大的牌一样，则比较第二大，以此类推（如37K>89Q） 如二人牌面相同，则为平局。 

输入描述:

输入两个字符串代表两个玩家的牌（如"10KQ" "354"），先输入的作为玩家1，后输入的作为玩家2

输出描述:

1 代表 玩家1赢 0 代表 平局 -1 代表 玩家2赢 -2 代表不合法的输入

输入例子:

KQ3 3Q9
10QA 6102
5810 7KK
632 74J
10102 K77
JKJ 926
68K 27A

输出例子:

1
1
-1
-1
1
1
-1

#include<iostream>
#include<string>
using namespace std;
bool string2value(string A,char *a){
    int len=A.size();
    for(int i=0;i<len;i++){
        if(A[i]>'1'&&A[i]<='9')
           a[i]=A[i]-'0';
        else if(A[i]=='1'){
            if(A[i+1]=='0'){
                a[i]=10;
                i++;
            }
            else{
                cout<<-2<<endl;
                return 0;
            }
        }
        else if(A[i]=='J'){
            a[i]=11;
        }
        else if(A[i]=='Q'){
            a[i]=12;
        }
        else if(A[i]=='K'){
            a[i]=13;
        }
        else if(A[i]=='A'){
            a[i]=14;
        }
        else{
            cout<<-2<<endl;
            return 0;
        }
    }
    for(int i=0;i<len;i++){
        for(int j=len-1;j>i;j--){
            if(a[j]>a[j-1]){
                char temp=a[j];
                a[j]=a[j-1];
                a[j-1]=temp;
            }
        }
    }
    return 1;
}
char gettype(char *a){
    if(a[0]==a[2])
        return 1;
    if(a[2]-a[1]==1&&a[1]-a[0]==1)
        return 2;
    if(a[0]==a[1]||a[1]==a[2])
        return 3;
    else
        return 4;
}
int compare(char a,char b){
    if(a>b)  return 1;
    if(a==b)  return 0;
    return -1;
}
int main(){
    string A,B;
    bool flag=1;
    while(cin>>A>>B){
        int len1=A.size();
        int len2=B.size();
        char a[3],b[3];
        if(string2value(A,a)){
            if(string2value(B,b)){
                char t1=gettype(a);
                char t2=gettype(b);
                if(t1==t2){
                    if(t1==1||t1==2){
                      cout<<compare(a[0],b[0])<<endl;
                    }
                    else if(t1==3){
                        int t=compare(a[1],b[1]);
                        if(t!=0)  cout<<t<<endl;
                        else{
                            char a0,b0;
                            if(a[1]!=a[0]) a0=a[0];
                            else a0=a[2];
                            if(b[1]!=b[0]) b0=b[0];
                            else b0=a[2];
                            cout<<compare(a0,b0)<<endl;
                        }
                    }
                    else{
                        int t=compare(a[0],b[0]);
                        if(t!=0)  cout<<t<<endl;
                        else{
                            int t=compare(a[1],b[1]);
                            if(t!=0)  cout<<t<<endl;
                            else{
                            cout<<compare(a[2],b[2])<<endl;
                            }
                        }
                    }
                }
                else{
                    if(t1<t2)
                        cout<<1<<endl;
                    else
                    cout<<-1<<endl;
                }
                
            }
            else
                continue;
        }
        else
            continue;

    }

    return 0;
}

    程序条件太多，提交程序时，出现如下问题：

段错误:您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起

 4发奖金（搜狐）

搜狐进行了一次黑客马拉松大赛，全公司一共分为了N个组，每组一个房间排成一排开始比赛，比赛结束后没有公布成绩，但是每个组能够看到自己相邻的两个组里比自己成绩低的组的成绩，比赛结束之后要发奖金，以1w为单位，每个组都至少会发1w的奖金，另外，如果一个组发现自己的奖金没有高于比自己成绩低的组发的奖金，就会不满意，作为比赛的组织方，根据成绩计算出至少需要发多少奖金才能让所有的组满意。 

输入描述:

每组数据先输入N，然后N行输入N个正整数，每个数表示每个组的比赛成绩。

输出描述:

输出至少需要多少w的奖金。

#include<iostream>
using namespace std;
int main(){
    int N,*score,*reward;
    while(cin>>N){
        score=new int[N];
        reward=new int[N];
        for(int i=0;i<N;i++){
            cin>>score[i];
            reward[i]=1;
        }
        for(int i=0;i<N-1;i++){
            if(score[i+1]>score[i])
                reward[i+1]=reward[i]+1;
        }
        for(int i=N-1;i>0;i--){
            if(score[i-1]>score[i])
                reward[i-1]=reward[i]+1>reward[i-1] ? reward[i]+1:reward[i-1];
        }
        int sum=0;
        for(int i=0;i<N;i++)
            sum+=reward[i];
        cout<<sum<<endl;
    }
}