NBUT Summer Contest-2 题解报告

78 阅读 0 评论 52 点赞

我是靠谱客的博主大气外套，最近开发中收集的这篇文章主要介绍NBUT Summer Contest-2 题解报告，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

[A] 想减肥的字符串
- 问题描述
- 从前，有一串很长很长的字符串，它由n个小写字母组成。有一天它在照镜子的时候，觉得自己太肥了，于是它想减肥。减肥的时候，可以不断地去掉第一个或者最后一个字符。它希望自己减肥之后，对于小写字母a、b、c，自己身上都至少保留有一个。它想知道自己减肥后的最小长度，你能帮帮它吗？
- 输入
- 每行有一串由小写字母组成的字符串，字符串的长度n < 1000。保证字符串中包含有小写字母a、b、c
- 输出
- 每行输出一个数字，表示该组数据求得的最小长度。
- 样例输入
- ```
ccbaa
abbbbbbbbbc
```
- 样例输出
- ```
3
11
```
- 提示
- ```
无
```
- 来源
- ```
CSL
```
思路：

由于只有abc三个字符，当输入字符串后，从头开始遍历整个字符串，每次遇到字符假设为’a’，都判断之前是否出现过’b’, ‘c’，如果有，计算出包含’a’’b’’c’的该串的长度并与之前保存的结果进行比较即可，然后再记录下当前字符’a’出现的下标，以供进行下次的判断。只进行一次遍历操作，因此时间复杂度是o(strlen(str)

扩展：

当必须包含的字符为多个时，可以用map建立下标与相应字符的映射，set来储存出现过的字符，顺便加一个计数器计算当前出现过的字符个数，再进行与上面类似的操作即可。


#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char c[1010];
int main()
{
	while(~scanf("%s", c))
	{

int ans = 9999999;

int pos_a = -1, pos_b = -1, pos_c = -1;

int n = strlen(c);

for(int i = 0; i < n; i++)

{

if(c[i] == 'a')

{

pos_a = i;

if(pos_c != -1 && pos_b != -1)

{

int l;

l = min(pos_b, pos_c);

ans = min(ans, i-l);

}

}

else if(c[i] == 'b')

{

pos_b = i;

if(pos_c != -1 && pos_a != -1)

{

int l;

l = min(pos_c, pos_a);

ans = min(ans, i-l);

}

}

else if(c[i] == 'c')

{

pos_c = i;

if(pos_a != -1 && pos_b != -1)

{

int l;

l = min(pos_b, pos_a);

ans = min(ans, i-l);

}

}

}

//printf("%d %d %dn", q, w, e);

printf("%dn", ans + 1);
	}
	return 0;
}

[B] I love math

问题描述
给定一个正整数N,求1/X+1/Y= 1/N的所有正整数解,N最大为999999999，求方程解的个数.
输入
第一行有一个T，表示数据组数。T <= 100
接下来有T行，每行有一个正整数N，N <= 999999999
输出
对于每个N，输出对应解的个数。
样例输入
```
2
1
2
```
样例输出
```
1
3
```
提示

当N为2时，（4,4），（3,6），（6,3）都是满足的。

来源
```
本站或者转载
```

数论题，对于1/X + 1/Y =1/N,将X看成N+R，Y看成N+S，因为X,Y显然都大于N。最后化简可以得到N^2=R*S

那么我们将N进行质因数分解。得到P1^K1 * P2^K2 * P3^K3 *.........分成两部分显然有（k1+1)*(k2+1)*.......

N^2也一样。

那么答案就是这个组合方案数了

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>

int main()
{
int n,t;
while(~scanf("%d",&t))
{
while(t--)
{
scanf("%d",&n);
int ans=1;
double temp=(double)(sqrt(n)+1);
for(int i=2; i<=temp; i++)
{

if(n%i==0)
{
int b=0;
while(n%i==0)
{
b++;
n/=i;
}
ans*=2*b+1;
}
}
if(n!=1)
ans*=3;
printf("%dn",ans);
}
}
return 0;
}

C题暂时无题解。

[D] 字符串大配对

问题描述
字符最近骚动起来了，大热天的，空调都不给力，还要每天被你们敲敲敲，次奥，不能忍，他们决定找个对象就私！！！奔！！！
字符'['只喜欢']'站在他右边，当然']'也只喜欢'['站他左边,'('和')'同样如此.
所以如果他们站成这样"]["，他们的缘分只能等下辈子啦.
每行有一串字符串只包含'(',')','[',']'.长度不会超过100000.
任意一对匹配后，就私奔到月球了！！！
输入
每行输入一串字符串str. len <= 100000
输出
请问有多少个私奔了！！！告诉他们麻麻去.
样例输入
```
((()))
([]])
([)]
[]()
)[)(
```
样例输出
```
6
4
4
4
0
```
提示
```
无
```
来源
```
zyvas
```

水题。从样例那边可以看得出，输入的时候当分别记录下‘（’和‘[’的数量，当输入‘（’或‘]’的时候，进行判断有没有对应的括号就行了。




#include<stdio.h>
#include<string.h>

int main()
{
       char a;
       while(~scanf("%c",&a))
       {
              int ans = 0;
              int c[4];
              memset(c, 0, sizeof(c));
              //mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman";"
>输入预处理下就好
              if(a == '[')
              {
                    c[0]++;
              }
              else if(a == '(')
              {
                     c[2]++;
              }
              while((a = getchar()) != 'n')
              {
                    if(a== '[')
                     {
                            c[0]++;
                     }
                     else if(a == ']')
                     {
                            if(c[0] > 0)
                            {
                                   ans+= 2;
                                   c[0]--;
                            }
                     }
                     if(a== '(')
                     {
                            c[2]++;
                     }
                     else if(a == ')')
                     {
                           if(c[2] > 0)
                            {
                                   ans+= 2;
                                   c[2]--;
                            }
                     }
              }
              printf("%dn", ans);
       }
       return 0;
}

[E] 让我们一起来黑静爷吧

问题描述
cjl经常被hxj和zy黑。。已经是家常便饭了。这次，cjl有一个逆袭的机会！他们要玩一个游戏，
如果cjl赢了就能够让hxj和zy称他为j爷。2333 这个游戏是这样的，给定N个正整数，双方轮流操作，
每次可以让其中一个值y变成x.1 <= x < y,且在[x+1,y]至少有一个素数.最后谁无法操作即为输.我们让cjl先手.
（静爷不哭，站起来（哔））
输入
第一行有一个整数T,表示组数。T <= 1000
接下来有N组数据，每组数据有一个值N，表示接下来有N个值。 N <= 1000
下一行是N个正整数A[i]. A[i] <= 5000000
输出
对于每组数据，cjl赢的话，输出"Win",否则输出"Lost"
样例输入
```
2
1
5
2
3 4
```
样例输出
```
Win
Lost
```
提示
```
无
```
来源
```
zyvas
```

先把范围内的素数筛选出来，然后，这就是个n堆石子的组合博弈了。这里要按每个数a[i] ，1--a[i] 里素数的个数来当石子的个数，因为每次取都要至少取掉一个素数。

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<iostream>

using namespace std;

bool vis[5000010];

int ans[5000010];

int num[5000010];

void get_prime()
{
int t=5000000;
memset(vis,true,sizeof(vis));
int tot=0;
for(int i=2;i<=t;i++)
{
if(vis[i])
{
tot++;
ans[tot]=i;
}
for(int j=1;(j<=tot) && (i*ans[j] <= t);j++)
{
vis[i*ans[j]]=false;
if(i%ans[j]==0)
break;
}
}
num[0]=0;
vis[1]=0;
for(int i=1;i<=t;i++)
{
num[i]=num[i-1]+vis[i];
}
}

int main()
{
get_prime();
int t;
while(~scanf("%d",&t))
{
while(t--)
{
int n,_xor=0,pos=0,temp,i,a;
bool flag=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a);
_xor^=num[a];
if(num[a] > 1)
flag=1;
}
if(!_xor)
printf("Lostn");
else
{
if(_xor && flag)
printf("Winn");
else
printf("Lostn");
}
}
}
return 0;
}