复试上机真题历年回顾-2018

最长回文子串

输入一个只含有英文字母的字符串,
输出最大回文子串的长度以及此长度回文子串的个数(回文子串不区分大小写)

暴力即可

//2018
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
typedef pair<int,int>pii;
#define x first
#define y second
pii res;
signed main(){
    string s;
    cin>>s;
    for(int i=0;s[i];i++) s[i]=tolower(s[i]);
    int len=s.length();
    res.x=1;
    res.y=len;
    for(int i=2;i<=len;i++){
        bool flag=0;
        int cnt=0;
        for(int j=0;j+i<=len;j++){
            string t1=s.substr(j,i);
            string t2=t1;
            reverse(t2.begin(),t2.end());
            if(t1==t2) { //判断是否为回文串
                flag=1;
                ++cnt;                
            }
        }  
        if(flag) res.x=i,res.y=cnt;//存在回文串,更新答案
    }
    cout<<res.x<<" "<<res.y<<endl;
    return 0;
}

哥德巴赫猜想

任何-一个大于2的偶数均可表示为两个素数之和。输入m, n (6<=m<=n<=50) ,则把[m, n]
内的所有偶数表示成两个素数之和的形式。输出这些素数及其出线的次数，输出次
序按照素数出现的次数从多到少输出;若出线次数相同，按照素数从大到小输出;
若偶数有多种素数相加形式，则把所有的情况都输出，每种情况占一行。

样例

输入: 8 9
输出:5 1 3 1
输入: 9 10
输出:
5 2
7 1 3 1
输入: 14 15
输出:
7 2
11 1 3 1
输入: 8 10
输出:
5 3 3 1
3 2 7 1 5 1

首先用线性筛一下素数
将每个偶数分解两个素数的所有情况存储到vector里
递归遍历每一个偶数,存储所有素数并按题目要求输出

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define x first
#define y second
typedef pair<int,int>pii;
const int N = 1000010;

int n, cnt;
int primes[N];
bool st[N];
struct node{
    int num;
    int cnt;
};
bool cmp(node a,node b){//定义比较函数
    if(a.cnt!=b.cnt) return a.cnt>b.cnt;
    return a.num>b.num;
}
void get_primes(int x)
{
    for (int i = 2; i <= x; i ++ )
    {
        if(!st[i]) primes[cnt ++] = i;
        for (int j = 0; primes[j] <= x / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }

}
node a[200000];
map<int,int>mp;
vector<vector<pii>>v;
int len,c;
void dfs(int idx){
    if(idx==len) { //递归完所有偶数 退出递归
        for(auto t:mp){
            if(t.y==0) continue;
            a[c].num=t.x;
            a[c].cnt=t.y;
            ++c;
        }
        sort(a,a+c,cmp);//按题目要求排序
        for(int i=0;i<c;i++)
            cout<<a[i].num<<" "<<a[i].cnt<<" ";
        cout<<endl;
        c=0;
        return;
    }
    vector<pii>vv =v[idx];
    for(auto t: vv){
        mp[t.x]++;//标记素数
        mp[t.y]++;
        dfs(idx+1);
        mp[t.x]--;//删除标记,注意下减为0
        mp[t.y]--;
    }
}
signed main(){
    int l,r;;
    cin>>l>>r;
    get_primes(r);//线性筛
    for(int i=l;i<=r;i++){
        if(i%2) continue;
        vector<pii>vv;
        for(int j=2;j<=i/2;j++){
            if(!st[j]&&!st[i-j]) {
                vv.push_back(make_pair(j,i-j));//存储一个偶数的所有划分素数之和的所有情况
            }
        }
        v.push_back(vv);//存储所有偶数的所有情况

    }
    len =v.size();//偶数个数
    dfs(0);//递归遍历所有偶数

    return 0;
}

重复数字

给定任意个整数，以逗号隔开，输出最后一个重复数字，没有重复数字输出-1

样例

输入:
1,2,3,4,4,3,2,1
1,2,3,4,5,6,7,8
输出:
1
-1

记录每个数的个数及其最后一次出现的位置
只要出现次数大于1加上位置最靠后即可
注意getline

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define int long long 
#define endl '\n'
signed main(){
    string str;
    while(getline(cin,str)){
        int tmp=0,cnt=0;
        map<int,pii>mp;//一个数对应一个pair<int,int>
        //其中pair第一个first表示这个数出现的次数 
        //pair第二个second表示这个数最后一次出现的位置
        for(int i=0;str[i];i++){
            if(str[i]!=','){
                tmp=tmp*10+str[i]-'0';
            }else{
                ++cnt;
                mp[tmp].fi++;
                mp[tmp].se=cnt;
                tmp =0;
            }
        }
        //添加最后一个数
        ++cnt;
        mp[tmp].fi++;
        mp[tmp].se=cnt;
        int maxn=1;//更新最后一个重复数字的位置
        int ans=-1;//记录答案
        for(auto t:mp){
            if(t.se.fi==1) continue;//未重复淘汰
            if(maxn<t.se.se){
                maxn=t.se.se;//更新maxn
                ans=t.fi;//记录答案
            }
        }
        cout<<ans<<endl;
    }

}

移位操作

定义移位操作, shift (str, x)代表将str中的前x位移到后面,例如shift ("ABCD”)得到CDAB。
输入一个长度为n的字符串最多进行n次移位操作后，输出有几次得到的字符串与原字符串相同。

输入:
byebye
hello
输出:
2
1

暴力即可 用substr

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define x first
#define y second

signed main(){
    string s;
    while(cin>>s){
        int len=s.length();
        int cnt=0;
        for(int i=1;i<=len;i++){
            string t=s.substr(i)+s.substr(0,i);//拼接
            if(t==s) ++cnt;
        }
        cout<<cnt<<endl;
    }

    return 0;
}