SCPC 2019 招新赛题解

1. 为了追寻她而爬楼的达妹

Description

达妹为了追寻一个不喜欢她的女孩来到了一个有n阶的楼梯前，她喜欢的女孩就在楼顶，她喜欢的女孩定下了一个规则：只有走3的倍数步爬上楼梯才能见到她。（为啥是3的倍数步？谁知道呢）由于达妹太虚了…她一步只能爬一阶楼梯或者两阶楼梯。请你帮助达妹算算她有几种方法能爬上楼梯见到她喜欢的女孩。（如果只有两阶楼梯，那么达妹并不能用3的倍数步爬上楼梯，因为达妹不管是走两步一阶的情况，还是一步两阶的情况，走的步数都不是3的倍数）

Input

第1行输入一个整数t（1<=t<=520）。

接下来第2行到第t+1行，每行输入一个整数n（1<=n<=520）。

Output

对于输入的第2行到第t+1行，每行输出一个数m，代表达妹有几种走法可以见到她。如果没有方法见到她请输出0。（因为m会很大，所以请让m对233取模）

Sample Input 1

Sample Output 1

0
0
1

Hint

orz本来题目很简单!他们让我改了！你们A不了都是他们的锅！！

Source

达妹

题目要求的是仅由1和2为加数，且加数的个数为3的倍数，令他们的和为n的方案数。

用一个二维数组表示走到第i阶台阶时对3取模为j的方案数

那么可知

dp[i][0] = dp[i-1][2] + dp[i-2][2]

dp[i][1] = dp[i-1][0] + dp[i-2][0]

dp[i][2] = dp[i-1][1] + dp[i-2][1]

然后输出答案dp[n][0]就可以了

#include <stdio.h>
int main() {
    int dp[600][3]={0},n,x;
    dp[1][1]=1;dp[2][1]=1;dp[2][2]=1;
    for(int i=3;i<=520;i++){
        dp[i][0]=(dp[i][0]+dp[i-1][2] + dp[i-2][2])%233;
        dp[i][1]=(dp[i][1]+dp[i-1][0] + dp[i-2][0])%233;
        dp[i][2]=(dp[i][2]+dp[i-1][1] + dp[i-2][1])%233;
    }
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&x);
        printf("%d\n",dp[x][0]);
    }
    return 0;
}

#include <stdio.h>

int main() {

int dp[600][3]={0},n,x;

dp[1][1]=1;dp[2][1]=1;dp[2][2]=1;

for(int i=3;i<=520;i++){

dp[i][0]=(dp[i][0]+dp[i-1][2] + dp[i-2][2])%233;

dp[i][1]=(dp[i][1]+dp[i-1][0] + dp[i-2][0])%233;

dp[i][2]=(dp[i][2]+dp[i-1][1] + dp[i-2][1])%233;

}

scanf("%d",&n);

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

scanf("%d",&x);

printf("%d\n",dp[x][0]);

}

return 0;

}

2. 神犇的数学题

Description

题意十分的简单，有一个数字A，我们把A除去最后一位数字后得到B，现在我们给你A-B，需要你计算满足条件的A。

Input

第一行输入一个T(<=500)代表测试组数

后面2到T+1行每行输入一个正整数表示A-B，10<=A-B<=10^12。

Output

输出正整数A，如果没有符合的数则输出一个空行（若存在多个答案请从小到大输出）。

Sample Input

Sample Output

Case 1: 34
Case 2: 19 20
Case 3: 13
Case 4: 18

Case 1: 34

Case 2: 19 20

Case 3: 13

Case 4: 18

Hint

对于样例的第一个数据：

A-B = 31，我们可以得到A = 34的时候，B = 3，这时候A-B = 31。

Source

肖翱

这个题我们很容易推出一个式子A-A/10=C
但是这样只能得到一个答案，但是现在我们要的到所有的答案；
我们可以设A的最后一位为x，那么式子就变成了A-(A-x)/10=C
因为x的范围只有0~9所以我们直接枚举x就行了，因为我们要从小到大输出答案，所以我们就直接从9到0枚举。

#include <stdio.h>
int main(void){
	int t;
	scanf("%d",&t);
	for(int cas = 1;cas <= t;cas++){
		long long n;
		scanf("%lld",&n);
		printf("Case %d:",cas);
		for(int x = 9;x >= 0;x--){
			long long k = 10*n-x;
			if(k%9==0)
				printf(" %lld",k/9);
		}
		printf("\n");
	}
	return 0;
}

#include <stdio.h>

int main(void){

int t;

scanf("%d",&t);

for(int cas = 1;cas <= t;cas++){

long long n;

scanf("%lld",&n);

printf("Case %d:",cas);

for(int x = 9;x >= 0;x--){

long long k = 10*n-x;

if(k%9==0)

printf(" %lld",k/9);

}

printf("\n");

}

return 0;

}

3. 肖姐姐的计算器

Description

肖姐姐曾经在达妹的手上工作过，有一次达妹想让肖姐姐帮她写一个能计算一元多项式的计算器，但肖姐姐觉得这种事情太简单了，于是她决定让你们来完成。（在计算器上键入的一个一元一次方程中，只包含整数、小写字母及+、-、=这三个数学符号（当然，符号“-”既可作减号，也可作负号）。方程中并没有括号，也没有除号，方程中的字母表示未知数。你可假设对键入的方程的正确性的判断是由另一个程序员在做，或者说可认为键入的一元一次方程均为合法的，且有唯一实数解。）

Input

一个一元一次方程。

Output

解方程的结果(精确至小数点后三位)。

Sample Input 1

3a+4a=7

3a+4a=7

Sample Output 1

a=1.000

a=1.000

Source

彭志强

这是一道简单的模拟题
一元一次方程的解法：移项、合并同类项
用l，r分别记录系数和与常数和，最后输出r/l即可（注意保留小数，0的话不能有符号，每个数的符号要注意）

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<sstream>
#include<vector>
#include<random>
#include<ctime>
#define ll long long
using namespace std;
int Read(){
	int out=0,flag=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();}
	while(c>='0'&&c<='9'){out=out*10+c-'0';c=getchar();}
	return flag*out;
}
int l,r;
char x;
void solve()
{
	char c;
	int f1=1,f2=1,tmp=0;
	while(~scanf("%c",&c))
	{
		if(c>='0'&&c<='9')
		{
			tmp*=10;
			tmp+=c-'0';
		}
		else
		{
			if(c>='a'&&c<='z')
			{
				if(tmp==0)l+=f2*f1;
				else l+=tmp*f2*f1;
				x=c;
			}
			else r+=tmp*(-f2)*f1;
			tmp=0;
		}
		if(c=='+')
		{
			f1=1;
			continue;
		}
		else if(c=='-')
		{
			f1=-1;
			continue;
		}
		else if(c=='=')
		{
			f1=1;f2=-1;
			continue;
		}
	}
	if(tmp!=0)r+=tmp*(-f2)*f1;
}
int main()
{
	solve();
	printf("%c=%.3lf",x,1.0*r/l==0?abs(1.0*r/l):1.0*r/l);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<queue>

#include<stack>

#include<sstream>

#include<vector>

#include<random>

#include<ctime>

#define ll long long

using namespace std;

int Read(){

int out=0,flag=1;char c=getchar();

while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();}

while(c>='0'&&c<='9'){out=out*10+c-'0';c=getchar();}

return flag*out;

}

int l,r;

char x;

void solve()

{

char c;

int f1=1,f2=1,tmp=0;

while(~scanf("%c",&c))

{

if(c>='0'&&c<='9')

{

tmp*=10;

tmp+=c-'0';

}

else

{

if(c>='a'&&c<='z')

{

if(tmp==0)l+=f2*f1;

else l+=tmp*f2*f1;

x=c;

}

else r+=tmp*(-f2)*f1;

tmp=0;

}

if(c=='+')

{

f1=1;

continue;

}

else if(c=='-')

{

f1=-1;

continue;

}

else if(c=='=')

{

f1=1;f2=-1;

continue;

}

if(tmp!=0)r+=tmp*(-f2)*f1;

}

int main()

{

solve();

printf("%c=%.3lf",x,1.0*r/l==0?abs(1.0*r/l):1.0*r/l);

return 0;

}

4. traitor

Description

经过雨烟绕指柔的判断，他发现雨烟小分队里面出现了一些叛徒，可是叛徒隐藏的非常深，但又不能打草惊蛇，所以想请聪明的你帮雨烟绕指柔找到叛徒。

目前知道一个数列为0 1 1 2 2 4 5 8 11 17 24(从第五项开始每一项等于前四项中固定三项的和)，并且知道叛徒的编号不属于这个数列。

但是雨烟绕指柔有看不出来不在这个数列的数字有哪些，所以请你帮忙找出这些不在数列里面的数字并且按要求输出

Input

给你一个数字n $(1 \leq n \leq 1 e 6)$

n代表测试数据的组数

紧接着n行每行输入1个数字m $(0 \leq m \leq 1 e 18)$

m指的是代表这个人的数字

Output

如果是叛徒请输出m!

不是就不输出

答案需要对1e6+3取模

如果一个叛徒都没有叛徒请输出”The rain squad has never been a traitor“

Sample Input 1

1
1

Sample Output 1

The rain squad has never been a traitor

1	The rain squad has never been a traitor

Sample Input 2

1
21241258018612289

1 2	1 21241258018612289

Sample Output 2

The rain squad has never been a traitor

1	The rain squad has never been a traitor

Source

onebelieve

首先，数列递推式为a[i]=a[i-2]+a[i-3]+a[i-4]
首先打表把该数列存到数组里面，然后输入m的时候就找数组里面有没有存过这个数字，存过就继续，没存过就输出该数字的阶乘模1e6+3
要是都存在就输出“The rain squad has never been a traitor”

#include<iostream>
using namespace std;
long long a[1000000];
const int mod=1e6+3;
int s[1000000];

void init()
{
	a[0]=0;
	a[1]=1;
	a[2]=1;
	a[3]=2;
	for(int i=4;i<=100;i++)
	{
		a[i]=(a[i-2]+a[i-3]+a[i-4]);
	}
}

bool judge(long long s)
{
	for(int i=0;i<=100;i++)
	{
		if(a[i]==s)
		{
			return false;
		 } 
	}
	return true;
}

void cheng(long long n)
{
	if(n>=mod)
	{
		printf("0\n");
		return ;
	}
	long long sum=1;
	for(int i=2;i<=n;i++)
	{
		sum=sum*i%mod;
	}
	printf("%lld\n",sum);
}

int main()
{
	init();
	int n;
	scanf("%d",&n);
	long long s;
	int nofind=1;
	for(int i=0;i<n;i++)
	{
		scanf("%lld",&s);
		if(judge(s)) cheng(s),nofind=0;
	}
	if(nofind)
	printf("The rain squad has never been a traitor\n");
	return 0;
}

#include<iostream>

using namespace std;

long long a[1000000];

const int mod=1e6+3;

int s[1000000];

void init()

{

a[0]=0;

a[1]=1;

a[2]=1;

a[3]=2;

for(int i=4;i<=100;i++)

{

a[i]=(a[i-2]+a[i-3]+a[i-4]);

}

bool judge(long long s)

{

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

{

if(a[i]==s)

{

return false;

}

return true;

}

void cheng(long long n)

{

if(n>=mod)

{

printf("0\n");

return ;

}

long long sum=1;

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

{

sum=sum*i%mod;

}

printf("%lld\n",sum);

}

int main()

{

init();

int n;

scanf("%d",&n);

long long s;

int nofind=1;

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

{

scanf("%lld",&s);

if(judge(s)) cheng(s),nofind=0;

}

if(nofind)

printf("The rain squad has never been a traitor\n");

return 0;

}

5. 杀死神牛

Description

我们都知道神犇和神牛不是同一种生物，而有一天你发现一头神牛在外面打着神犇的名声装神弄鬼，于是你准备杀死他。现在给你一把武器他的攻击力是a，这头神牛的恢复能力是b，并且告诉你他的初始生命值是c，如果你不能将它的生命值减为0那么他会继续恢复血量（就算是负数也会恢复血量，不会因为回血会死）。注意数据保证神牛一定会被杀死！

Input

N,a,b,c的范围都保证在100以内。给你N组数据

Output

每组数据有a,b,c三个量。杀死这头神牛输出需要攻击多少次

Sample Input 1

4 1 7

4 2 8

4 2 6

Sample Output 1

2
3
2

Source

蔡洪浩

因为题目已经保证答案存在
那么就直接分为两种情况讨论就可以了
设需要攻击x次
假设神牛死亡是在一次攻击之后
那么可得： a*x-b*(x-1)=c
即(a-b)x=c-b x的正整数解
特判一下a=b的情况，因为题目数据保证了有解，所以此时a=b=c,x=1.

#include<stdio.h>
int main(){
	int n,a,b,c;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d %d %d",&a,&b,&c);
		int m=c-a,res=0;
	    if(m==0) printf("1");
	    else if(m!=0){
	        while(m!=0){
	        	m=m+b;
	        	m=m-a;
	        	res++;
			}
			printf("%d\n",res+1);
		}
	}
	return 0;
}

#include<stdio.h>

int main(){

int n,a,b,c;

scanf("%d",&n);

for(int i=1;i<=n;i++){

scanf("%d %d %d",&a,&b,&c);

int m=c-a,res=0;

if(m==0) printf("1");

else if(m!=0){

while(m!=0){

m=m+b;

m=m-a;

res++;

}

printf("%d\n",res+1);

}

return 0;

}

6. 拯救神犇

Description

魔王抓住了神犇，而你在得知这件事后，决定拿着全村最好的剑去挑战魔王。经过了漫长的打斗（斗马苍穹的特效），你终于打败了魔王。而当你正准备去解救神犇时，却发现聪明的魔王留下了一把锁将神犇困住了。锁上面清晰可见一串很长的数字，它的长度为n且没有前导0。就在你正在研究怎么破解该锁的情况下，神犇告诉你一条信息：改变最多k次使得该数S最小，神犇将所有的希望都放在了你的身上。如果在24小时内没有解救出神犇，它就会被饿死。5555555…

Input

第一行：两个整数n，k，1<=n<=200,000，0 <= k <= n

接下来一行输入数字S表示困住神犇的锁上的数字

数字的长度不是n！！！

此处输入的n没有作用！！！！

Output

输出一行：表示经过改变后的S的最小值。改变后的S应不含前导0

Sample Input 1

5 3
51528

5 3

51528

Sample Output 1

10028

10028

Sample Input 2

3 2
102

3 2

102

Sample Output 2

100

100

Sample Input 3

1 1
1

1 1

Sample Output 3

Hint

一个数不包含前导0 ：如果一个数由至少两位组成并且第一位为0，则包含前导0.

Source

张荣鑫

首先题目给我们一个长度为n的数字，我们肯定考虑用字符串形式存储。然后要让这个数字尽可能小，我们可以贪心，优先将高位变为最小值即可。

注意：“0”不算含有前导0。

#include <stdio.h>
#include <string.h>
int n, k;
char s[200005], ch;
int main(){
	scanf("%d%d%s", &n, &k, s + 1);
	n = strlen(s+1);
	for (int i = 1; i <= n && k; ++i)
		k -= (ch = (i == 1 && n > 1) ^ '0') != s[i], s[i] = ch;
	printf("%s", s + 1);
}

#include <stdio.h>

#include <string.h>

int n, k;

char s[200005], ch;

int main(){

scanf("%d%d%s", &n, &k, s + 1);

n = strlen(s+1);

for (int i = 1; i <= n && k; ++i)

k -= (ch = (i == 1 && n > 1) ^ '0') != s[i], s[i] = ch;

printf("%s", s + 1);

}

7. 神犇的偶数

Description

神犇最喜欢偶数了！！！

现在有个人给了神犇一个数字N，问神犇这个数字能否由两个非负偶数相加得到。

神犇太难了，每天挨敖睿学长的打，还有许许多多的问题要解决，你能帮助他吗 (QAQ) ？

百度百科：偶数是能够被2所整除的整数。

Input

输入一个数字N。

$1 \leq N \leq 1 e 6 (1000000)$

Output

如果可以则输出 “YES” （不包括引号）

否则输出 “NO” （不包括引号）

Sample Input 1

4

Sample Output 1

YES

YES

Hint

真的签到题！！！！

Source

敖睿

真正的签到题。

我们考虑数字是否是偶数即可，同时我们要特判数字为2的情况。因为0不是偶数。

#include<stdio.h>
int main(){
  int n;
  scanf("%d",&n);
  printf(n>2&&n%2==0?"YES":"NO");
  return 0;
}

#include<stdio.h>

int main(){

int n;

scanf("%d",&n);

printf(n>2&&n%2==0?"YES":"NO");

return 0;

}

8. 神犇的终极防AK题

Description

相信各位都会求一个数组里面的最大值了

姚涵学姐现在不想知道最大值

但是她想知道n个数字里面第二大的值是多少，你能帮她找出来吗？？

Input

第一行输入一个数字n $(2 \leq n \leq 1000)$

第二行一共n个数字 $a_{1}, a_{2} . . . a_{n}$ ，用空格隔开 $(0 \leq a_{i} \leq 1e^{6})$

输入数据保证n个数字没有重复的。

Output

输出这n个数字中第二大的值

Sample Input 1

2
1 2

1 2

Sample Output 1

1

Sample Input 2

3
3 2 1

3 2 1

Sample Output 2

2

Hint

这真的是水题呀，嘤嘤嘤

Source

俞昊

签到题

题意：求数组内第二大的值

冒泡然后从大到小排序直接取a[2]就是第二大的了

#include<stdio.h>
int a[1010];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(a[i]<a[j]){
				int t=a[i];
				a[i]=a[j];
				a[j]=t;
			}
		}
	}
	printf("%d\n",a[2]);
	return 0;
}

#include<stdio.h>

int a[1010];

int main(){

int n;

scanf("%d",&n);

for(int i=1;i<=n;i++){

scanf("%d",&a[i]);

}

for(int i=1;i<=n;i++){

for(int j=i+1;j<=n;j++){

if(a[i]<a[j]){

int t=a[i];

a[i]=a[j];

a[j]=t;

}

printf("%d\n",a[2]);

return 0;

}

9. 神犇的博弈

Description

自从大家都喜欢上了博弈（下棋）蔡蔡为了跟上大家的脚步也拉着神犇（张荣鑫）和他一起博弈来锻炼技术，不过他们之间的博弈有一些区别，具体如下：

它是这样定义的：

1、本游戏是一个二人游戏;

2、有一堆五星英雄一共有N个；

3、两人轮流进行;

4、每走一步可以取走1…M个五星英雄；

5、最先取光五星英雄的一方为胜；

并且保证蔡蔡先手，神犇后手，保证他们绝对理智聪明的情况下。

(数据N，M都保证在1000000以内）

Input

输入一个T代表T组数据，接下来有T行每行一个a和一个b。（T的大小小于100000）

输入N,M

Output

如果蔡蔡赢得了比赛则输出”caicainiubi!”

如果神犇赢得了比赛则输出”zhangrongxinniubi!”

Sample Input 1

2
100 4
56 12

100 4

56 12

Sample Output 1

zhangrongxinniubi!
caicainiubi!

1 2	zhangrongxinniubi! caicainiubi!

Source

蔡洪浩

因为每个人都可以拿1到m个五星英雄，所以可以保证每次蔡蔡和神犇两个人拿的五星英雄的和为m+1个，如果n为(m+1)的倍数，那么此时后手（神犇）胜利，因为可以保证后手拿到没回合的第m+1个五星英雄

同理，如果n不为(m+1)的倍数，那么此时先手（蔡蔡）胜利，因为蔡蔡可以使得拿完之后剩余的五星英雄为(m+1)的倍数。那么此时蔡蔡就成为第一种情况中的后手。

#include<stdio.h>
int main() {
	int n;
	scanf("%d",&n);
	while(n--) {
		int a,b;
		scanf("%d%d",&a,&b);
		printf(a%(b+1)?"caicainiubi!\n":"zhangrongxinniubi!\n");
	}
}

#include<stdio.h>

int main() {

int n;

scanf("%d",&n);

while(n--) {

int a,b;

scanf("%d%d",&a,&b);

printf(a%(b+1)?"caicainiubi!\n":"zhangrongxinniubi!\n");

}

10. 神犇的硬币

Description

神犇特别喜欢收集硬币，他收集了好多好多的硬币，现在他把这些硬币全部拿出来了。

神犇把他的很多个硬币摆在一行，有正面朝上的，也有背面朝上的。正面朝上的用1表示，背面朝上的用0表示。

现在要求从这行的第一个硬币开始，将前若干个硬币一起翻面，问如果要将所有硬币翻到正面朝上，最少要进行这样的操作多少次？

Input

一行，一个字符串，由0和1组成，表示硬币状态

硬币个数<=10000

Output

一个数，表示要翻转的最少次数

Sample Input 1

10

Sample Output 1

2

Hint

第1次翻转：把第一个硬币翻到反面，字符串为00

第2次翻转：把第一、二个硬币一起翻到正面，字符串为11，翻转完成，输出2

Source

俞昊

首先，翻硬币的顺序对结果没有影响

然后从后往前面暴力翻硬币即可！！

#include<stdio.h>
#include<string.h>
char a[10001]={0};
int main()
{
	int n,i,sum=0,j;
	scanf("%s",a);
	n=strlen(a);
	for(i=n-1;i>=0;i--)
		if(a[i]=='0')
		{
			for(j=i;j>=0;j--)
				if(a[j]=='1')
					a[j]='0';
				else
					a[j]='1';
			sum++;
		}
	printf("%d\n",sum);
	return 0;
}

#include<stdio.h>

#include<string.h>

char a[10001]={0};

int main()

{

int n,i,sum=0,j;

scanf("%s",a);

n=strlen(a);

for(i=n-1;i>=0;i--)

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

{

for(j=i;j>=0;j--)

if(a[j]=='1')

a[j]='0';

else

a[j]='1';

sum++;

}

printf("%d\n",sum);

return 0;

}

2019-10-08　　19:37:53　　Author: WindCry1

SCPC 2019 招新赛题解

于10月 7, 201910月 7, 2019由WindCry1发布

1. 为了追寻她而爬楼的达妹

2. 神犇的数学题

3. 肖姐姐的计算器

4. traitor

5. 杀死神牛

6. 拯救神犇

7. 神犇的偶数

8. 神犇的终极防AK题

9. 神犇的博弈

10. 神犇的硬币

0 条评论

发表评论取消回复

SCPC 2019 招新赛题解

于10月 7, 201910月 7, 2019由WindCry1发布

1. 为了追寻她而爬楼的达妹

2. 神犇的数学题

3. 肖姐姐的计算器

4. traitor

5. 杀死神牛

6. 拯救神犇

7. 神犇的偶数

8. 神犇的终极防AK题

9. 神犇的博弈

10. 神犇的硬币

0 条评论

发表评论 取消回复

发表评论取消回复