CSDN周赛第十期总结

竞赛概述

CSDN编程竞赛第十期：比赛详情

本场竞赛由「电子工业出版社 & CSDN」联合主办
题目总体难度较高，前两题比较基础，第二题我在之前的博客中写过类似题题解。后两题是竞赛题，但做过的类似的应该可以很快a掉。

题解

由于比赛无法保存题目及代码，以下题解代码均为现在写的，题目是在网上找的回忆版，可能会有问题。

熊孩子摆拜访问

题目描述

已知存在一个长度为n的整数序列A，A中所有元素按照从小到大排序，现在执行倒置一段序列。请你找出A序列的倒置子序列。如果没有，输出“0 0”。

数据范围

1<=n<=1000

1<=num<=10000

样例输入

4

1 3 2 4

样例输出

2 3

代码

#include

void quicksort(int *a,int left,int right)
{
	if(left>right)
	{
		return ;
	}
	int i=left;
	int j=right;
	int key=a[left];
	while(i!=j)
	{
		while(a[j]>=a[left]&&i<j)
		{
			j--;
		}
		while(a[i]<=a[left]&&i<j)
		{
			i++;
		}
		int s;
		s=a[i];
		a[i]=a[j];
		a[j]=s;
	}
	a[left]=a[i];
	a[i]=key;
	quicksort(a,left,i-1);
	quicksort(a,i+1,right);
}

int main(){
	int a[100000],b[100000];
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
		b[i] = a[i];
	}
	quicksort(b,0,n-1);
	int left = 0,right = 0;
	for(int i=0;i<n;i++){
		if(b[i]!=a[i]&&!left){
			left = i+1;
		}
		if(b[i]!=a[i]&&left!=0){
			right = i+1;
		}
	}
	printf("%d %d",left,right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

走楼梯

题目描述

楼梯有 N 阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。

输入描述

一个数字，楼梯数。

输出描述

输出走的方式总数。

样例输入 1

4

样例输出 1

5

代码

递归

#include

int step(int n){
	if(n == 1 || n == 2){
		return n;
	}else{
		return step(n-1) + step(n-2);
	}
}

int main(){
	int n;
	scanf("%d",&n);
	printf("%d",step(n));
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这题没多少印象，但是印象里递归好像有测试点过不去，会超时，再补一个动态规划的题解。

动态规划

#include


int main(){
	int n;
	scanf("%d",&n);
	int res[n+1];
	res[0] = 0;
	res[1] = 1;
	res[2] = 2;
	if(n<=3)
	{
		printf("%d",n);
		return 0;
	}
	for(int i=3;i<=n;i++)
	{
		res[i]=res[i-1]+res[i-2];
	}
	printf("%d",res[n]);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

括号上色

小艺酱又得到了一堆括号。
括号是严格匹配的。
现在给括号进行上色。
上色有三个要求：
1、只有三种上色方案，不上色，上红色，上蓝色。
2、每对括号只有一个上色。
3、相邻的两个括号不能上相同的颜色，但是可以都不上色。
问括号上色有多少种方案？答案对1000000007取模。

输入描述：

输入括号序列s。(2<=|s|<=700)

输出描述：

输出方案数。

输入样例：

(())

输出样例：

12

代码

#include
#include
#include

#define LL long long
const int mod=1000000007;

char s[1000];
int q[1000];
int mp[1000]={0};
int tot=1;
LL dp[1000][1000][3][3]={0};
int vis[1000][1000]={0};

int dfs(int L, int R)
{
	if(vis[L][R])
	{
		return 0;
	}
	vis[L][R]=1;
	if(R-L==1)
	{
		dp[L][R][1][0]=1, dp[L][R][2][0]=1;
		dp[L][R][0][1]=1, dp[L][R][0][2]=1;
		return 0;
	}
	if(mp[L]==R)
	{
		dfs(L+1, R-1);
		for(int u=0;u<3;u++)
		{
			for(int v=0;v<3;v++)
			{
				for(int x=0;x<3;x++)
				{
					for(int y=0;y<3;y++)
					{
						if((u==0||v==0)&&(u!=0||v!=0)&&(u!=x||u+x==0)&&(v!=y||v+y==0))
						{
							dp[L][R][u][v]+=dp[L+1][R-1][x][y], dp[L][R][u][v]%=mod;
						}
					}
				}
			}
		}
	}
	else
	{
		dfs(L, mp[L]); dfs(mp[L]+1, R);
		for(int u=0;u<3;u++)
		{
			for(int v=0;v<3;v++)
			{
				for(int x=0;x<3;x++)
				{
					for(int y=0;y<3;y++)
					{
						if((u==0||v==0)&&(u!=0||v!=0)&&(v!=x||v==0&&x==0))
						{
							dp[L][R][u][y]+=dp[L][mp[L]][u][v]*dp[mp[L]+1][R][x][y], dp[L][R][u][y]%=mod;
						}
					}
				}
			}
		}
	}
	
}

int main()
{
	int len,ans = 0;
	scanf("%s",s+1);
	len = strlen(s+1);
	for(int i=1;i<=len;i++)
	{
		if(s[i]=='(')
		{
			q[tot++]=i;
		}
		else
		{
			mp[q[--tot]]=i;
		}
	}
	dfs(1, len);
	for(int u=0;u<3;u++)
	{
		for(int v=0;v<3;v++)
		{
			ans+=dp[1][len][u][v], ans%=1000000007;
		}
	}
	printf("%d",ans);
	return 0;
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

喜水青蛙

题目描述

总是喜欢在水里嬉戏的青蛙，某天要过河拜访一位朋友。
已知河道中长满了带刺的不知名生物，能通过的路只有一条直线，长度为L。
直线上随机分布着m块石头。青蛙的最小跳跃距离是s，最大跳跃距离是t。
青蛙想要尽可能的少踩石头，那么它通过河道最少会踩到多少石头？

输入描述：

多组数据输入，其中每组数据：
第一行输入1个整数L(1<=L<=1e9)。
第二行输入3个整数：s、t、m(1<=s<=t<=10，1<=m<=100)。
第三行输入m个不同的整数，表示m个石子在数轴上的分布位置。
每行所有相邻整数用空格隔开。

输出描述：

输出青蛙过河最少会踩到的石子数量，
每组输入数据对应的输出结果单独成行。

输入样例：

10
2 3 5
2 3 5 6 7

输出样例：

2

代码

#include

int min(int x, int y)
{
	return x<y?x:y;
}

int gcd(int x,int y){
	if(y==0)return x;
	return gcd(y,x%y);
}

int lcm(int x, int y){
	return x*y/gcd(x,y);
}

void quicksort(int *a,int left,int right)
{
	if(left>right)
	{
		return ;
	}
	int i=left;
	int j=right;
	int key=a[left];
	while(i!=j)
	{
		while(a[j]>=a[left]&&i<j)
		{
			j--;
		}
		while(a[i]<=a[left]&&i<j)
		{
			i++;
		}
		int s;
		s=a[i];
		a[i]=a[j];
		a[j]=s;
	}
	a[left]=a[i];
	a[i]=key;
	quicksort(a,left,i-1);
	quicksort(a,i+1,right);
}

int main(){
	int l,s,t,m;
	int a[101],b[101],f[20000],flag[20000];
	scanf("%d %d %d %d",&l,&s,&t,&m);
	int k=lcm(s,t);
	for(int i=1;i<=m;i++)scanf("%d",&a[i]);
	if(s==t){
		int sum=0;
		for(int i=1;i<=m;i++)if(a[i]%s==0)sum++;
		printf("%d",sum);
		return 0;
	}
	a[m+1]=l;
	quicksort(a,0,m+1);
	for(int i=1;i<=m+1;i++){
		if(a[i]-a[i-1]>=2*k)b[i]=(a[i]-a[i-1])%k+k;
		else b[i]=a[i]-a[i-1];
	}
	for(int i=1;i<=m+1;i++){
		a[i]=a[i-1]+b[i];
		flag[a[i]]=1;
	}
	flag[a[m+1]]=0;
	for(int i=1;i<=a[m+1]+t+1;i++){
		f[i]=0x3fffffff;
		for(int j=s;j<=min(i,t);j++){
			f[i]=min(f[i],f[i-j]+flag[i]);
		}
	}
	printf("%d",f[a[m+1]+t+1]);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

总结

这次周赛有点属于拼手速的，看完就得开始写，最后能取得第二名的好成绩还是很不错的，希望下次继续进步吧，也希望csdn越办越好。