2018暑期集训7.19习题题解

2018暑期集训7.19习题题解

A(Alice和Bob的决斗)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
int t,n;
int a[10000];
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i = 0;i < n; i++){
scanf("%d",&a[i]);
}
sort(a,a + n);
if(a[n/2]%2 == 0) printf("Alice\n");
else printf("Bob\n");
}

return 0;
}

B(小程四级高分过)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
#include<cstring>
using namespace std;
char a[11][10] = {"Zero","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten"};
int main()
{
char s[10];
while(scanf("%s",s) != EOF){
for(int i = 0;i < 11; i++){
if(strcmp(a[i],s) == 0){
printf("%d\n",i);
break;
}
}
}

return 0;
}

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
30
31
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn = 1005;
int a[maxn][maxn];
int main()
{
int n,m,k;
while(scanf("%d%d%d",&n,&m,&k) != EOF && (n||m||k)){
for(int i = 0;i < maxn; i++){
fill(a[i],a[i] + maxn, 0);
}
int x1,x2,y1,y2,cnt = 0;
for(int i = 0;i < k; i++){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
for(int x = x1 - 1;x < x2; x++){
for(int y = y1 - 1;y < y2; y++){
a[x][y] = 1;
}
}
}
for(int i = 0;i < n; i++){
for(int j = 0;j < m; j++){
if(a[i][j] == 1) cnt++;
}
}
printf("%d\n",cnt);
}

return 0;
}

D(括号匹配)

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
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1005;
int main()
{
char s[maxn];
while(gets(s) != NULL){
int cnt = 0,flag = 1,len = strlen(s);
for(int i = 0;i < len; i++){
if(s[i] == '(') cnt++;
else if(s[i] == ')'){
if(cnt == 0){
flag = 0;
break;
}else if(cnt > 0){
cnt--;
}
}
}
if(flag == 0 || cnt > 0) printf("No\n");
else printf("Yes\n");
}

return 0;
}

E(复原二叉树)

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
#include<cstdio>
#include<cstring>
using namespace std;
typedef struct node{
char c;
struct node *lchild,*rchild;
}tree;
tree* findtree(char *pre,char *in,int len){
if(len == 0) return NULL;
tree *temp = new tree;
temp->c = *pre;
int i = 0;
for(i = 0;i < len; i++){
if(*(in + i) == *pre){
break;
}
}
temp->lchild = findtree(pre + 1,in,i);
temp->rchild = findtree(pre + i + 1,in + i + 1,len - i - 1);
return temp;
}
void output(tree* now){
if(now != NULL){
output(now->lchild);
output(now->rchild);
printf("%c",now->c);
}
}
int main()
{
char pre[1005],in[1005];
while(scanf("%s %s",pre,in) != EOF){
tree *root = findtree(pre,in,strlen(pre));
output(root);
printf("\n");
}

return 0;
}

F(空心三角形)

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
#include <stdio.h>
int main()
{
char a;
int i,j,k=0,n;
scanf("%c",&a);
while (a!='@')
{
scanf("%d",&n);
if(k!=0)
printf("\n");
for (i=0;i<n-1;i++)
{
for (j=1;j<n+i;j++)
if((n-j)%n==i)
printf("%c",a);
else
printf(" ");
printf("%c\n",a);
}
n=n*2-1;
while(n--)
printf("%c",a);
printf("\n");
k++;
getchar();
scanf("%c",&a);
}

return 0;
}

G(这层树海星)

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<iostream>
#include<cmath>
using namespace std;
const int maxn = 1005;
int a[maxn];
int main()
{
int n,d;
while(scanf("%d",&n) && n != 0){
fill(a,a + maxn, -1);
for(int i = 1;i <= n; i++){
scanf("%d",&a[i]);
}
scanf("%d",&d);
for(int i = pow(2,d - 1);i < pow(2,d); i++){
if(a[i] == -1){
if(i == pow(2,d - 1)) printf("EMPTY");
break;
}else{
if(i == pow(2,d - 1))printf("%d",a[i]);
else printf(" %d",a[i]);
}
}
printf("\n");
}

return 0;
}

H(愿天下有情人都是失散多年的兄妹)

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
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn = 100005;
struct node{
int dad,mom;
char sex;
node(char a = 0,int b = -1,int c = -1){sex = a,dad = b,mom = b;}
}p[maxn];
bool have[maxn],vis[maxn],flag;
char sex[maxn];
void find(int n,int x){
if(x == 5){
return;
}
if(n != -1 && have[n] == true){
vis[n] = true;
find(p[n].dad,x + 1);
find(p[n].mom,x + 1);
}
}
void judge(int n,int x){
if(x == 5) return;
if(n != -1 && flag == true && have[n] == true){
if(vis[n] == true){
flag = false;
return;
}else{
judge(p[n].dad,x + 1);
judge(p[n].mom,x + 1);
}
}
}
int main()
{
int n,k;
scanf("%d",&n);
fill(have,have + maxn, false);
int my,f,m;
char sex[5];
for(int i = 0;i < n; i++){
scanf("%d %s %d %d",&my,sex,&f,&m);
p[my].sex = sex[0];
p[my].dad = f;
p[my].mom = m;
have[my] = have[f] = have[m] = true;
p[f].sex = 'M';
p[m].sex = 'F';
}
int a,b;
scanf("%d",&k);
for(int i = 0;i < k; i++){
scanf("%d %d",&a,&b);
if(p[a].sex == p[b].sex){
printf("Never Mind\n");
}else{
fill(vis,vis + maxn, false);
find(a,0);
flag = true;
judge(b,0);
if(flag == false){
printf("No\n");
}else{
printf("Yes\n");
}
}
}

return 0;
}

I(最高分是多少)

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
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 30005;
int a[maxn],tree[(maxn<<4)+5];
void creattree(int l,int r,int now){
if(l == r){
tree[now] = a[l];
return;
}
int mid = (l + r)/2;
creattree(l,mid,now << 1);
creattree(mid + 1,r,(now << 1) + 1);
tree[now] = max(tree[now << 1],tree[(now << 1) + 1]);
}
void change(int l,int r,int x,int y,int now){
if(l == r){
tree[now] = y;
return;
}
int mid = (l + r)/2;
if(x <= mid) change(l,mid,x,y,now << 1);
else change(mid + 1,r,x,y,(now << 1) + 1);
tree[now] = max(tree[now << 1],tree[(now << 1) + 1]);
}
int find(int l,int r,int x,int y,int now){
if(l >= x && r <= y){
return tree[now];
}
int ans = 0,mid = (r + l)/2;
if(x <= mid) ans = max(ans,find(l,mid,x,y,now << 1));
if(y > mid) ans = max(ans,find(mid + 1,r,x,y,(now << 1) + 1));
return ans;
}
int main()
{
int n,m,x,y;
char s[5];
while(scanf("%d %d",&n,&m) != EOF){
for(int i = 1;i <= n; i++){
scanf("%d",&a[i]);
}
creattree(1,n,1);
for(int i = 0;i < m; i++){
scanf("%s %d %d",s,&x,&y);
if(s[0] == 'U'){
change(1,n,x,y,1);
}else if(s[0] == 'Q'){
printf("%d\n",find(1,n,x,y,1));
}
}
}

return 0;
}

J(Maximum Element In A Stack)

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
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 100000;
int stack[maxn];
int Maxstack[maxn];
int stack_top = 0,Maxstack_top = 0;
int n,p,q,m,ans = 0;
unsigned int SA,SB,SC;
unsigned int rng61(){
SA ^= SA << 16;
SA ^= SA >> 5;
SA ^= SA << 1;
unsigned int t = SA;
SA = SB;
SB = SC;
SC ^= t ^ SA;
return SC;
}
void gen(){
scanf("%d%d%d%d%u%u%u",&n,&p,&q,&m,&SA,&SB,&SC);
for(int i = 1; i <= n; i++){
if(rng61() % (p + q) < p){
int x = rng61() % m + 1;
stack[stack_top++] = x;
if(Maxstack_top == 0 ||(Maxstack_top != 0 && x >= Maxstack[Maxstack_top - 1])){
Maxstack[Maxstack_top++] = x;
}
}else{
if(stack_top != 0) {
stack_top--;
if(stack[stack_top] == Maxstack[Maxstack_top - 1]) Maxstack_top--;
}
}
if(stack_top != 0) ans ^= (i*Maxstack[Maxstack_top - 1]);
}
}
int main()
{
int t;
scanf("%d",&t);
for(int x = 1;x <= t; x++){
ans = 0,stack_top = 0,Maxstack_top = 0;
gen();
printf("Case #%d: %d\n",x,ans);
}

return 0;
}