2016年下学期《程序设计实践》重修考试

发表于 | 分类于 ， |
程序设计实践课程，2016年下学期，重修考试题解。
题目 类型 难度
Color 统计，容斥 ★
Set 数学 ★★
Robot 数学 ★★
Matrix 数学 ★★★
Exam Schedule 模拟 ★★★★

本来是6个题，因为当时时间太赶了，最难的那个没时间出数据，又觉得重考也觉得没必要，就这样了。
实际考试的时候，拿了一个之前的题目凑成了6个题，所以题解还是只给5道题。

Color

题意

题目是CF的原题。一个$m\times n$的格子，中间有$k$个黑格子，一次可以让不含黑格子的某一行或者某一列变成红色。问最多可以让多少格变红。

思路

统计不含黑格的行数$row$和列数$col$，答案就是$row\times n + col \times m - row \times col$

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <cstring>

int main(){
	int T,m,n,k,x,y,cx[100],cy[100],i,sx,sy;
	scanf("%d",&T);
	while(T--){
		memset(cx,0,sizeof(cx));
		memset(cy,0,sizeof(cy));

		scanf("%d %d %d",&m,&n,&k);
		for(i=0;i<k;i++){
			scanf("%d %d",&x,&y);
			cx[x-1] = 1;
			cy[y-1] = 1; 
		}
		sx = sy = 0;
		for(i=0;i<m;i++) if(!cx[i]) sx++;
		for(i=0;i<n;i++) if(!cy[i]) sy++;		
		printf("%d\n",sx*n+sy*m-sx*sy);
	}
	return 0;
}

Set

题意

题目来源于是CF，但是有加强。
给一个整数的集合，执行两步操作：先对某些数加上x，再在对某些数减去y，使得集合内的数都是一样的。
问你给定的集合是否可以做到。

思路

一个数$n$，经过操作可能得到的数为$\{n,n+x,n+x-y,n-y\}$。
如果集合内数的种类为$k$，显然$k<4$时，一定可以做到；$k>4$时，一定做不到。
当$k=4$时，不妨设四种数从小到大依次为$a,b,c,d$，显然，只能全部变成$b$或者$c$。
不妨设全部变成$b$,那么

$(1)-(2)+(3)$，化简一下可以得到等式$a+d=b+c$。

标程

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
#include <cstdio>
#include <algorithm>

using namespace std;

int main(){
	int K,n,m,a[4],i,t;

	scanf("%d",&K);
	while(K--){
		scanf("%d",&n);
		m = 0;
		while(n--){
			scanf("%d",&t);
			if(m > 4) continue;
			for(i=0; i<m && a[i]!=t; i++);
			if(i == m)	a[m++] = t;
		}
		if(m < 4) puts("Yes");
		else if(m>4) puts("No");
		else {
			sort(a,a+4);
			if(a[0]+a[3] == a[1]+a[2]) puts("Yes");
			else puts("No");
		}
	}

	return 0;
}

Robot

题意

一个机器人的指令集，包含上下左右四种指令，每个指令表示往对应方向移动一步。
机器人一开始站在原点，如果将其中一种指令全部替换成另外一种，请问机器人是否在执行完指令序列后，回到原点。

思路

显然替换完之后的指令序列如果要使得机器人回到原点，那么必然$L=R，U=D$。
由于替换的关系，那么必然是一种指令的数量为$0$，而其他的指令满足$x+y=z$的形式。

标程

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
#include <cstdio>

int main(){
	int L,R,U,D;
	char s[222],*p;
	while(gets(s)){
		L = R = U = D = 0;
		for(p=s;*p;p++){
			switch(*p){
				case 'L': L++; break;
				case 'R': R++; break;
				case 'U': U++; break;
				case 'D': D++; break;
			}
		}
		if(L+U == D && R == 0 ||
		   L+D == U && R == 0 ||
		   R+U == D && L == 0 ||
		   R+D == U && L == 0 ||
		   U+L == R && D == 0 ||
		   U+R == L && D == 0 ||
		   D+L == R && U == 0 ||
		   D+R == L && U == 0 ) puts("Yes");
		else puts("No");
	}

}

Matrix

题意

求按

规律安排矩阵的第1列的累加和。

思路

典型的找规律的题目。很容易发现奇数元素是$\lceil n / 2 \rceil ^ 2 + 1 $，偶数元素是 $n^2$。因为$n$最大有$10^9$，所以暴力和打表都是不可做的。
如果$n=2k+1$，那么$S(n) = \sum_{i=0}^k{\big((2i)^2+1+(2i)^2\big)} = 8 \sum_{i=0}^k{i^2} + k + 1 = \frac{4}{3}k(k+1)(2k+1)+k+1$。
如果$n=2k$，那么$S(n) = S(n+1) - n^2 - 1$。
因为要取模，所以要么就根据$k$的值先把$3$除掉，或者乘以$3$对于$10^9+7$的逆元(这个很容易计算得到为$333333336$)。

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>

int main(){
	long long n,m,s;
	const long long mod = 1e9+7;
	std::ios::sync_with_stdio(false);
	while(std::cin>>n,n){
		m = n>>1;
		s = m*(m+1)%mod * (m<<1|1) %mod;
		s = s * 333333336 % mod * 4 % mod; 
		if(n&1){
            s += m+1;
		} else {
            s -= n*n%mod;
            s += m;
		}

		std::cout << (s+mod)%mod << '\n';
	}
	return 0;
}

Exam Schedule

题意

周1到周5排考，每天是11节课，某些时间段已经被占用，求所有能安排的时间段。

思路

典型模拟题。

先用数组记录（当然也可以用位运算）所有已经占用的时间段。
对于不同的时长要求的考试，预存下所有的检测时间段。
枚举每天，检测对应时间段是否可以安排考试，可以就记录下结果。
最后输出结果即可。

标程

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
#include <iostream>
#include <cstdio>
#include <string>
int getDay(std::string day){
	std::string dd[7]={"Mon","Tue","Wen","Thur","Fri","Sat","Sun"};
	for(int i=0;i<7;i++) if(day==dd[i]) return i;
	return 7;
}

int check(int *t,int L,int R){
	for(int i = L;i <= R;i++) if(t[i]==1) return 0;
	return 1;
}

int main(){
	int K,N,T;
	//freopen("input_0","r",stdin);
	std::string day[5]={"Mon","Tue","Wen","Thur","Fri"};
	int seq[3][8][2]={{{0,1},{1,2},{2,3},{4,5},{5,6},{6,7},{8,9},{9,10}},
	                  {{0,2},{1,3},{4,6},{5,7},{8,10}},
	                  {{0,3},{4,7}}
	                 };
	int len[3] = {8,5,2};
	std::ios::sync_with_stdio(false);
	std::cin >> K;
	while(K--){
		std::cin >> N >> T;
		int  tt[55]={0};

		for(int i=0;i<N;i++){
			std::string dy;
			int dd,start,en;
			std::cin >> dy >> start >> en;

			dd = getDay(dy);
			if(dd > 4) continue;
			for(int j=dd*11+start-1;j<dd*11+en;j++)
                tt[j] = 1;

		}

		int ans = 0,offset;
		char buf[55][20];
		T -= 2;
		for(int i = 0 ;i < 5; i++){
			offset = i * 11;
			for(int j=0;j<len[T];j++){
				if(check(tt,offset+seq[T][j][0],offset+seq[T][j][1])){
					sprintf(buf[ans++],"%s %d %d",day[i].c_str(),seq[T][j][0]+1,seq[T][j][1]+1);
				}
			}
		}
		
		std::cout << ans << '\n';
		for(int i=0;i<ans;i++){
			std::cout << buf[i] << '\n';
		}
	}

	return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！