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;
}
坚持原创技术分享,您的支持将鼓励我继续创作!