湖南警察学院新生训练赛第1场题解

目录

A、段的多项式

B、爱情上上签

C、CTRL

D、《怪奇物语》的名字真难记！

E、奖励Games(shabi problem)

F、小罗不想当渣男┭┮﹏┭┮

---

A、段的多项式

题目链接：登录—专业IT笔试面试备考平台_牛客网

这题是本场比赛最难的题了，但是仔细想还是不难的。

先展示一下错误代码，这应该是大部分人的思路了吧，最后是运行超时，这是按照题目去写的代码，时间复杂度是o(n方)，而k1和k2的大小在1000000之内，因此用两层循环是不行的。

错误示范：

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   #define LL long long//用LL表示long long
4.  
   int k1,k2,p;
5.  
    
6.  
   const int N=1e6 10;
7.  
   LL arr[N],brr[N];//题目给出的数据范围会爆int，所以要用 long long
8.  
   int main()
9.  
   {
10.  
    cin>>k1>>k2>>p;
11.  
    for(int i=0;i<=k1;i )cin>>arr[i];
12.  
    for(int i=0;i<=k2;i )cin>>brr[i];
13.  
    int sum=0;
14.  
    for(int i=0;i<=k1 k2;i )//这个下面是双层循环，复杂度高，会超时
15.  
    {
16.  
    int c=0;
17.  
    for(int j=0;j<=i;j )
18.  
    {
19.  
    c =arr[j]*brr[i-j]%p;
20.  
    }
21.  
    sum=(sum c)%p;
22.  
    }
23.  
    cout<<sum%p<<endl;
24.  
    }

这题最巧妙的地方就是令x=1，这样就发现我们所要求的答案就是arr数组的和与brr数组的和的乘积，这样我们就可以在o(n)的时间复杂度求出正确答案，正确代码如下。

正确示范：

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   #define LL long long//用LL表示long long
4.  
   int k1,k2,p;
5.  
    
6.  
   const int N=1e6 10;
7.  
   int main()
8.  
   {
9.  
   cin>>k1>>k2>>p;
10.  
    LL sum1=0,sum2=0;
11.  
    for(int i=0;i<=k1;i )
12.  
    {
13.  
    LL a;//这里开long long因为数据范围在1000000000000007以内，大于int范围。
14.  
    cin>>a;
15.  
    sum1=(sum1 a)%p;//这里一定要在中间过程取模，否则sum1会爆long long
16.  
    }
17.  
    for(int i=0;i<=k2;i )
18.  
    {
19.  
    LL a;//这里开long long因为数据范围在1000000000000007以内，大于int范围。
20.  
    cin>>a;
21.  
    sum2=(sum2 a)%p;//这里也一定要在中间过程取模，否则sum1会爆long long
22.  
    }
23.  
    cout<<sum1*sum2%p<<endl;
24.  
    }

B、爱情上上签

题目链接：登录—专业IT笔试面试备考平台_牛客网

注意这一题的数据不能用n方复杂度的，，所以大家还是要思考如何用一个循环的方法去解决这个问题。
题意：给出两个相同长度的字符串和长度n

题目要求：使得修改第一个字符串后与第二个字符串完全一样可执行的操作：将第一个字符串中的任何一个字符修改为该字符前的任一字符

例：abcdef 和abcaef 可以修改前一个字符串中d为前面的abc中的c ,此时 两个字符串可以相等, 即促成了完美姻缘

暴力想法：每次出现两个字符串中相同位置字符不同时 去for循环遍历第一个字符串该位置前的所有字符，判断这些字符中是否有一个与第二个字符串的那个原本不同的字符相同，可以找到就继续两个字符串进行比较， 找不到就是促不成完美姻缘，一直比较完都可以的话就是可以促成完美姻缘。

eg:上述想法需要双层循环 而n最大是1e6 双层循环会运行1e12左右 ，一般题目只支持运行次数1e8以内 所以单纯暴力肯定不行

思考：字符串只有小写字母组成 也就是说对于出现了字符不同时 
          我们是不是只要找第一个字符串前面有没有出现过第二个字符串这个时候的这个字符
          出现不同时的第二个串的字符是不是只有26种情况即（‘a’-‘z’）
          我就只需要把第一个字符串之前出现过的字符标记一下 
          当我需要用这个字符时 去直接判断是不是之前标记过就能解决问题了
          标记可以用数组来 很显然数组下标不能是字符 就需要进行转换 具体如下

1.  
   #include <bits/stdc .h>
2.  
   using namespace std;
3.  
   int main()
4.  
   {
5.  
       int n;
6.  
       cin>>n;
7.  
       string s,ss;
8.  
       cin>>s>>ss;
9.  
       int mp[30];
10.  
        memset(mp,0,sizeof mp);//一个经常用的赋值函数，将mp数组所有元素赋值为0，但是仅限于0和-1.
11.  
        int flag=0;
12.  
        for(int i=0;i<n;i )
13.  
        {
14.  
            mp[int(s[i]-'a')]=1;
15.  
            if(s[i]!=ss[i]&&(mp[int(ss[i]-'a')]==0))
16.  
            {
17.  
            flag=1;
18.  
            break;
19.  
            }
20.  
        }
21.  
        if(flag)cout<<"love is a trick"<<endl;
22.  
        else cout<<"love is forever"<<endl;
23.  
        return 0;
24.  
    }

C、CTRL

题目链接：登录—专业IT笔试面试备考平台_牛客网

这题如果能自己手写一个check函数来判断某个数的数位和是不是2的倍数要方便很多。因为不是很难，所以我们直接展示代码。。

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   #define LL long long//这里用LL表示long long
4.  
   int n;
5.  
   bool check(LL x)
6.  
   {
7.  
   int sum=0;
8.  
   while(x!=0)
9.  
   {
10.  
    sum =(x%10);
11.  
    x/=10;
12.  
    }
13.  
    if(sum%2==0)return true;//这里sum表示的就是数位和，如果数位和是2的倍数那么返回真，
14.  
    else return false;//否则返回假
15.  
    }
16.  
    int main()
17.  
    {
18.  
    cin>>n;
19.  
    LL c=0,t=0,r=0,l=0;//这里要注意这一题给出的数据范围会爆int
20.  
    for(int i=1;i<=n;i )
21.  
    {
22.  
    LL a;//这里要注意这一题给出的数据范围会爆int
23.  
    cin>>a;
24.  
    bool ans=check(a);
25.  
    if(a%3==0&&ans==true)c =a;
26.  
    else if(a%3==0&&ans==false)t =a;
27.  
    else if(a%3!=0&&ans==true)r =a;
28.  
    else l =a;
29.  
    }
30.  
    cout<<c<<" "<<t<<" "<<r<<" "<<l<<endl;
31.  
    }

D、《怪奇物语》的名字真难记！

题目链接：登录—专业IT笔试面试备考平台_牛客网

这题要用到getline函数来输入字符串，因为普通的输入无法输入带有空格的字符串。 

纯暴力题，来两次循环将字符串进行遍历，第一次循环看看各种缩写出现的次数，WB出现次数用a[0]表示，MB出现次数用a[1]表示，DH出现次数用a[2]表示，LS出现次数用a[3]表示，E出现次数用a[4]表示。第二次循环就是将字符串输出，但是特判这几个缩写名字，并且将缩写次数多的进行特判。时间复杂度为o(n)，代码如下。

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   int a[5]={0};
4.  
   int main()
5.  
   {
6.  
   string s;
7.  
   getline(cin,s);
8.  
   for(int i=0;i<s.size();i )
9.  
   {
10.  
    if(s[i]=='W'&&s[i 1]=='B')a[0] ;
11.  
    else if(s[i]=='M'&&s[i 1]=='B')a[1] ;
12.  
    else if(s[i]=='D'&&s[i 1]=='H')a[2] ;
13.  
    else if(s[i]=='L'&&s[i 1]=='S')a[3] ;
14.  
    else if(s[i]=='E')a[4] ;
15.  
    }
16.  
    for(int i=0;i<s.size();i )
17.  
    {
18.  
    if(s[i]=='W'&&s[i 1]=='B')
19.  
    {
20.  
    if(a[0]==1)cout<<"Will Byers";
21.  
    else cout<<"Will";
22.  
    i ;
23.  
    }
24.  
    else if(s[i]=='M'&&s[i 1]=='B')
25.  
    {
26.  
    if(a[1]==1)cout<<"Mike Wheeler";
27.  
    else cout<<"Mike";
28.  
    i ;
29.  
    }
30.  
    else if(s[i]=='D'&&s[i 1]=='H')
31.  
    {
32.  
    if(a[2]==1)cout<<"Dustin Henderson";
33.  
    else cout<<"Dustin";
34.  
    i ;
35.  
    }
36.  
    else if(s[i]=='L'&&s[i 1]=='S')
37.  
    {
38.  
    if(a[3]==1)cout<<"Lucas Sinclair";
39.  
    else cout<<"Lucas";
40.  
    i ;
41.  
    }
42.  
    else if(s[i]=='E')cout<<"Eleven";
43.  
    else cout<<s[i];
44.  
    }
45.  
    }

E、奖励Games(shabi problem)

题目链接：登录—专业IT笔试面试备考平台_牛客网

签到题，不难发现，在回合进行的过程当中，先手奖励的次数肯定要大于等于后手的奖励次数，而又题目要求当奖励次数相同时候，判定先手赢，所以无论如何先手都是赢的那一方，因此只需要输出"Fuck it is a so shabi problem"就可以啦。

代码如下

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   int main()
4.  
   {
5.  
   int n;
6.  
   cin>>n;
7.  
   cout<<"Fuck it is a so shabi problem"<<endl;
8.  
   }

F、小罗不想当渣男┭┮﹏┭┮

题目链接:链接：登录—专业IT笔试面试备考平台_牛客网

我们先来解释一下这个样例：(1,1)能否刚好两步走到(1,2)。草稿纸上模拟一下发现肯定不行，要么直接一步走到，要么三步（(1,1)-->(2,1)-->(2,2)-->(1,2))，要么五步((1,1)-->(2,1)-->(2,2)-->(2,3)-->(1,3)-->(1,2))，七步，九步......。因此当n大于最小的曼哈顿距离时候也不能判定n一定是合理的，还要判断n减去最短距离的奇偶性。当然如果n小于这个最短的距离，那么这个n肯定是不合理的

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   int t;
4.  
   int main()
5.  
   {
6.  
   cin>>t;
7.  
   while(t--)
8.  
   {
9.  
   int a,b,c,d,n;
10.  
    cin>>a>>b>>c>>d>>n;
11.  
    int mi=max(a,c)-min(a,c) max(b,d)-min(b,d);//mi表示的是两点之间的最短距离。
12.  
    if(n<mi)cout<<"YES"<<endl;//因为最短步数就是mi，所以这个n肯定不合理，小罗是大渣男。
13.  
    else //n大于或者等于mi的情况
14.  
    {
15.  
    if((n-mi)%2==0)cout<<"NO"<<endl;
16.  
    else cout<<"YES"<<endl;
17.  
    }
18.  
    }
19.  
    }

这篇好文章是转载于：学新通技术网