The 2016 ACM-ICPC Asia Beijing Regional Contest

发表于   |   分类于   |     |   阅读次数

补题解。
好久不写了，但是再不好好写大三就废了。
不废话了。

A

原题戳这里

题意

有 n 本书, 每本书的格式为CATEGORY 1/CATEGORY 2/..../CATEGORY n/BOOKNAME, 现在要重新格式化这些书的格式. 第 n 个 category 前面需要有 4(n-1) 个空格, 如果这本书在第 n 个 category 上, 那么它前面要有 4n 个空格. 同一 category 里面, category 和书名都按照字典序排序, 但是 category 要排在书前面. 第一个 category 需要按照字典序排列。

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
B/A
B/A
B/B
0
A1/B1/B32/B7
A1/B/B2/B4/C5
A1/B1/B2/B6/C5
A1/B1/B2/B5
A1/B1/B2/B1
A1/B3/B2
A3/B1
A0/A1
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
Case 1:
B
    A
    B
Case 2:
A0
    A1
A1
    B
        B2
            B4
                C5
    B1
        B2
            B6
                C5
            B1
            B5
        B32
            B7
    B3
        B2
A3
    B1

题解

hzy解了这题。建树并排序就可以了。

Code

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>

typedef long long LL;
const int maxn = 100005;

struct book{
	char nm[105];
};

struct tree{
	book bk;
	int sons,son[100];
	bool shu;
};

tree a[maxn];
book b[100];
int tot,now;
char c;

bool vali(char x){
	if(x>='A'&&x<='Z')return true;
	if(x>='0'&&x<='9')return true;
	return (x==' '||x=='/');
}

void getstr(int x){
	c=getchar(); 
	if(c==EOF)return;
	while(!vali(c)){
		c=getchar();
		if(c==EOF)return;
	}
	int len=0;
	while(vali(c)){
		b[x].nm[len++]=c;
		c=getchar();
		if(c==EOF)return;
	}
	b[x].nm[len]='\0';
}

bool big(int x,int y){
    for(unsigned int i=0;i<strlen(b[x].nm)&&i<strlen(b[y].nm);i++){
    	if(b[x].nm[i]>b[y].nm[i])return 1;
    	if(b[x].nm[i]<b[y].nm[i])return 0;
    }
    return strlen(b[x].nm)>strlen(b[y].nm);
}

bool yes(int x,int y,unsigned int z){
	int i;
	for(i=0;z<strlen(b[y].nm) && b[y].nm[z]!='/';z++,i++)
		if(a[x].bk.nm[i]!=b[y].nm[z])return 0;
	if(a[x].bk.nm[i]!='\0')return 0;
	if(z>=strlen(b[y].nm)&&a[x].shu==false)return 0;
	if(z<strlen(b[y].nm)&&b[y].nm[z]=='/'&&a[x].shu)return 0;
	return 1;
}

void ins(int s,int x,unsigned int y){
	for(int i=1;i<=a[s].sons;i++)
		if(yes(a[s].son[i],x,y)){
			while(y<strlen(b[x].nm)&&b[x].nm[y]!='/')y++;
			if(y>=strlen(b[x].nm))return;
			ins(a[s].son[i],x,y+1);
			return;
		}
	++tot;
	a[s].sons++;
	a[s].son[a[s].sons]=tot;
	int j;
	for(j=0;y<strlen(b[x].nm)&&b[x].nm[y]!='/';y++,j++)
		a[tot].bk.nm[j]=b[x].nm[y];
	a[tot].bk.nm[j]='\0';
	if(y>=strlen(b[x].nm)){
		a[tot].shu=1;
		return;
	}else
		a[tot].shu=0;
	ins(tot,x,y+1);
}

bool biger(int x,int y){
	for(unsigned int i=0;i<strlen(a[x].bk.nm)&&i<strlen(a[y].bk.nm);i++){
    	if(a[x].bk.nm[i]>a[y].bk.nm[i])return 1;
    	if(a[x].bk.nm[i]<a[y].bk.nm[i])return 0;
    }
    return strlen(a[x].bk.nm)>strlen(a[y].bk.nm);
}

void swap(int &x,int &y){
	int t=x; x=y; y=t;
}

void s_sort(int x){
	for(int i=1;i<a[x].sons;i++)
		for(int j=i+1;j<=a[x].sons;j++)
			if(biger(a[x].son[i],a[x].son[j])){
				swap(a[x].son[i],a[x].son[j]);
			}
}

void deal(int x,int y){
	if(x>0){
		for(int i=1;i<=y;i++)putchar(' ');
		printf("%s\n",a[x].bk.nm);
	}
	s_sort(x);
	for(int i=1;i<=a[x].sons;i++)
		if(a[a[x].son[i]].shu==false)
			deal(a[x].son[i],y+4);

	for(int i=1;i<=a[x].sons;i++)
		if(a[a[x].son[i]].shu)
			deal(a[x].son[i],y+4);
}

int main(){
	//freopen("d:/shit.txt","r",stdin);
	int id=0;
	while(1){
		tot=0; now=0;
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		while(1){
			++now; 
			getstr(now);
			if(c==EOF){
				--now;
				break;
			}
			if(strlen(b[now].nm)<=2&&b[now].nm[0]=='0'){
				--now;
				break;
			}
		}
		for(int i=1;i<=now;i++){
			ins(0,i,0);
		}
		id++;
		printf("Case %d:\n",id);
		deal(0,-4);
		if(c!='\n')return 0;
	}
}

B

原题戳这里

题意

给出n个数p1,p2,…,pn, 你要把把这nn个数划分成若干段(每段都是连续的), 每段的代价这么计算:
从每段中选出m(不够m对的话, 选出最多的对数)对，计算每对数之间的差值，然后求平方和，代价是所有选法的平方和的最大值，记为SPD。
你要划分成最少的段，使得每段的SPD都不大于k。

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
B/A
B/A
B/B
0
A1/B1/B32/B7
A1/B/B2/B4/C5
A1/B1/B2/B6/C5
A1/B1/B2/B5
A1/B1/B2/B1
A1/B3/B2
A3/B1
A0/A1
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
Case 1:
B
    A
    B
Case 2:
A0
    A1
A1
    B
        B2
            B4
                C5
    B1
        B2
            B6
                C5
            B1
            B5
        B32
            B7
    B3
        B2
A3
    B1

题解

hzy解了这题。建树并排序就可以了。

Code

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>

typedef long long LL;
const int maxn = 100005;

struct book{
	char nm[105];
};

struct tree{
	book bk;
	int sons,son[100];
	bool shu;
};

tree a[maxn];
book b[100];
int tot,now;
char c;

bool vali(char x){
	if(x>='A'&&x<='Z')return true;
	if(x>='0'&&x<='9')return true;
	return (x==' '||x=='/');
}

void getstr(int x){
	c=getchar(); 
	if(c==EOF)return;
	while(!vali(c)){
		c=getchar();
		if(c==EOF)return;
	}
	int len=0;
	while(vali(c)){
		b[x].nm[len++]=c;
		c=getchar();
		if(c==EOF)return;
	}
	b[x].nm[len]='\0';
}

bool big(int x,int y){
    for(unsigned int i=0;i<strlen(b[x].nm)&&i<strlen(b[y].nm);i++){
    	if(b[x].nm[i]>b[y].nm[i])return 1;
    	if(b[x].nm[i]<b[y].nm[i])return 0;
    }
    return strlen(b[x].nm)>strlen(b[y].nm);
}

bool yes(int x,int y,unsigned int z){
	int i;
	for(i=0;z<strlen(b[y].nm) && b[y].nm[z]!='/';z++,i++)
		if(a[x].bk.nm[i]!=b[y].nm[z])return 0;
	if(a[x].bk.nm[i]!='\0')return 0;
	if(z>=strlen(b[y].nm)&&a[x].shu==false)return 0;
	if(z<strlen(b[y].nm)&&b[y].nm[z]=='/'&&a[x].shu)return 0;
	return 1;
}

void ins(int s,int x,unsigned int y){
	for(int i=1;i<=a[s].sons;i++)
		if(yes(a[s].son[i],x,y)){
			while(y<strlen(b[x].nm)&&b[x].nm[y]!='/')y++;
			if(y>=strlen(b[x].nm))return;
			ins(a[s].son[i],x,y+1);
			return;
		}
	++tot;
	a[s].sons++;
	a[s].son[a[s].sons]=tot;
	int j;
	for(j=0;y<strlen(b[x].nm)&&b[x].nm[y]!='/';y++,j++)
		a[tot].bk.nm[j]=b[x].nm[y];
	a[tot].bk.nm[j]='\0';
	if(y>=strlen(b[x].nm)){
		a[tot].shu=1;
		return;
	}else
		a[tot].shu=0;
	ins(tot,x,y+1);
}

bool biger(int x,int y){
	for(unsigned int i=0;i<strlen(a[x].bk.nm)&&i<strlen(a[y].bk.nm);i++){
    	if(a[x].bk.nm[i]>a[y].bk.nm[i])return 1;
    	if(a[x].bk.nm[i]<a[y].bk.nm[i])return 0;
    }
    return strlen(a[x].bk.nm)>strlen(a[y].bk.nm);
}

void swap(int &x,int &y){
	int t=x; x=y; y=t;
}

void s_sort(int x){
	for(int i=1;i<a[x].sons;i++)
		for(int j=i+1;j<=a[x].sons;j++)
			if(biger(a[x].son[i],a[x].son[j])){
				swap(a[x].son[i],a[x].son[j]);
			}
}

void deal(int x,int y){
	if(x>0){
		for(int i=1;i<=y;i++)putchar(' ');
		printf("%s\n",a[x].bk.nm);
	}
	s_sort(x);
	for(int i=1;i<=a[x].sons;i++)
		if(a[a[x].son[i]].shu==false)
			deal(a[x].son[i],y+4);

	for(int i=1;i<=a[x].sons;i++)
		if(a[a[x].son[i]].shu)
			deal(a[x].son[i],y+4);
}

int main(){
	//freopen("d:/shit.txt","r",stdin);
	int id=0;
	while(1){
		tot=0; now=0;
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		while(1){
			++now; 
			getstr(now);
			if(c==EOF){
				--now;
				break;
			}
			if(strlen(b[now].nm)<=2&&b[now].nm[0]=='0'){
				--now;
				break;
			}
		}
		for(int i=1;i<=now;i++){
			ins(0,i,0);
		}
		id++;
		printf("Case %d:\n",id);
		deal(0,-4);
		if(c!='\n')return 0;
	}
}

#