奇安信（2019笔试题）

40道选择（40分）
2道编程 （60分）

1. 队尾幸运编号

时间限制：C/C++语言 1000MS；其他语言 3000 MS
内存限制：C/C++ 语言65536KB；其他语言 589824KB

题目描述

N个人排成一队，从1到5轮流报数，报5的人是幸运者，出列。报到队尾后，从队首接着报。依此循环。
问：排在队尾的人是第几名幸运者？
注：N为小于100000的正整数。
例如：
1人排成一队，他就是第1名幸运者。
3人排成一队，队尾是第2名幸运者。
5人排成一队，队尾是第1名幸运者。
8人排成一队，队尾是第3名幸运者。
即求：N人排成一队，队尾是第多少名幸运者？

输入

队伍总人数

输出

队尾者的幸运编号

样例输入

20

样例输出

4

程序C++

此思路来源于 算法竞赛入门经典的 救济金发放(UVa133),只是注意输出的值不一样。
这里可以用num记录队尾的人是第几次才输出，也可以用一个数组记录每次弹出的幸运者编号，直到弹出队尾编号；
用数组的好处是可以看到弹出的幸运者编号；

#include <bits/stdc++.h>

const int maxn=100005;
int f[maxn];
int n;
using namespace std;

int go(int p,int d,int t)
{
    while(t--)
    {
        do{
            p=(p+d+n-1)%n+1;
        }while(f[p]==0);
    }
    return p;
}
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
        f[i]=i;

    vector<int> pep;//存储幸运者编号
    int left=n;//剩下的人数
    int p=0; //注意这里p的取值要为0 因为go函数中我们使用的是t-- 而不是--t 
    int num=0;
    while(left)
    {
        num++;
        p=go(p,1,5);
        pep.push_back(p);
        f[p]=0;
        left--;
        if(p==n)
           break;
    }
//    for(int i=0;i<pep.size();i++)
//    {
//        cout << pep[i] <<' ';
//    }
//    cout <<endl;
    cout << "num is :"<<num << endl;
    cout << "pep.size():" <<pep.size()<< endl;
    return 0;
}

2. 求最长不重复字符子串

时间限制：C/C++语言 1000MS；其他语言 3000 MS
内存限制：C/C++ 语言65536KB；其他语言 589824KB

题目描述

输入一行字符串，求里面不含有重复字符的最长子串。
比如输入字符串为aaabbacccc,可以从任意位置开始截取子字符串，
这些子字符串中，不含有重复字符的最长子字符串是abc,它的长度是3。

输入

字符串

输出

不含有重复字符的最长子串长度

样例输入

bcdbcdee

样例输出

4

程序C++

#include <iostream>
#include <string>
#include <cstring>

using namespace std;

int LengthofLongeststring(string s)
{
   int m[256]={0};
   int left=0,ans=0;
   for(int i=0;i<s.size();i++)
   {
       if(m[s[i]]==0 || m[s[i]]<left)
       {
           ans=max(ans,i-left+1);
       }
       else
       {
          left=m[s[i]];
       }
       m[s[i]]=i+1;
   }
   return ans;
}
int main()
{
    string s;
    getline(cin,s);

    int ans;
    ans=LengthofLongeststring(s);
    cout << ans <<endl;
    return 0;
}