CD2018/12/7BCE题解

发表于 | 评论数： | 阅读次数：

论被王太阳吊打的痛苦，。。。

B

暴力可过的一道字符串签到题。

像Herself32这种蒟蒻，字符串算法一概不会，所以热衷于做可暴力字符串。

难度：橙色的50602l.png

本题标签：可暴力字符串

题目描述

输入1行句子（不多于200个单词，每个单词长度不超过100），只包含字母、空格和逗号。单词由至少一个连续的字母构成，空格和逗号都是单词间的间隔。

试输出第1个最长的单词和第1个最短单词。

输入输出格式

输入格式

一行句子。

输出格式

两行输出：
第1行，第一个最长的单词。
第2行，第一个最短的单词。

INPUT & OUTPUT‘s example

Input’s example

1
I am studying Programming language C in Peking University
窒息

Output’s example

1
2
Programming
I

提示

终于有提示了QAQ。
如果所有单词长度相同，那么第一个单词既是最长单词也是最短单词。

分析

就是暴力

我们使用getline对字符串进行读入和初始化。

首先将字符串线性扫一遍，将里面的,全部处理为（这样比较好处理)。

然后开一个结构体，一遇到就暂停，将整个字符串分解为一个个单词，同时将他们的长度和字符传入结构体。

因为一遇到就暂停并处理，所以字符串前后必须加。

同时强调一下，开一个last变量作为字符串的指针，每一次处理完一个单词就让last=i,这样可以保证下一次循环是方便而迅捷。

最后再次线性扫一遍，找出长度最大和最小的长度，将他们的下标所对应的单词输出即可。

还有，不要忘了：

如果所有单词长度相同，那么第一个单词既是最长单词也是最短单词。

所以，我们可以用两个bool型变量表示是否为第一个MAX或MIN长度的字符串。

也就相当于循环处理时的break，但由于$O(n)$和$O(n \log n)$级别算法时间复杂度的差距很可能决定本题是否可暴力，所以我还是牺牲两个bit的空间吧。

代码

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
/* Headers */
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<climits>
/* define */
#define MAXN 10010
using namespace std;
namespace FastIO{
	const int BUFSIZE=(1<<20);
	char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
	char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
	inline char getch(){
		if(is==it)
			it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
		return (is==it)?EOF:*is++; 
	}
	inline int getint(){
		int neg=0,res=0,ch=getch();
		while(!(isdigit(ch)||ch=='-')&&ch!=EOF){
			ch=getch();
		}
		if(ch=='-'){
			neg=1;ch=getch();
		}
		while(isdigit(ch)){
			res=(res<<3)+(res<<1)+(ch-'0');
		} 
		return neg?-res:res;
	}
	inline void write(int x){
		if(x<0)putchar('-'),x=-x;
		if(x>9)write(x/10);
		putchar(x%10+'0');
	}
	inline void space(int x){
		if(x==0)putchar(' ');
		else putchar('\n');
	}
}
using namespace FastIO;
/* definitions */
string s;
int word[MAXN],len,cnt,last;
int minx=INT_MAX,maxx=-0x7fffff;
string MAX,MIN;
bool visitx=true,visity=true;
struct Node{
    int lens;
    string now;
}str[MAXN];
/* functions */
inline bool cmp(int a,int b){
    return a>b;
}
inline void init(){
    s=" "+s;
    s=s+" "; 
}
int main(int argc,char *argv[]){
    ios::sync_with_stdio(false);
    getline(cin,s);
    init();
    len=s.length();
    for(int i=1;i<=len-1;i++){
        if(s[i]==',')s[i]=' ';
    }
    for(int i=0;i<=len-1;i++){
        if(s[i]==' '){
            str[++cnt].lens=i-last-1;
            for(int j=last+1;j<=i-1;j++){
                str[cnt].now+=s[j];
            }
            last=i;
        }
    }
    for(int i=2;i<=cnt;i++){
        minx=min(minx,str[i].lens);
        maxx=max(maxx,str[i].lens);
    }
    for(int i=2;i<=cnt;i++){
        if(visitx&&str[i].lens==maxx){
            MAX=str[i].now;
            visitx=false;
        }
        if(visity&&str[i].lens==minx){
            MIN=str[i].now;
            visity=false;
        }
    }
    cout<<MAX<<endl<<MIN<<endl;
    return 0;
}

写完才发现，这是Herself32写的题解中分析最长的一篇。

果然我还是太蒻了。

C

一道令人窒息的题目，总之tips很多。

Herself32:就不能让我好好用sort吗？

难度：橙色的50602l.png

题目描述

病人登记看病，编写一个程序，将登记的病人按照以下原则排出看病的先后顺序：

  1. 老年人（年龄$\leq$60岁）比非老年人优先看病。
  2. 老年人按年龄从大到小的顺序看病，年龄相同的按登记的先后顺序排序。
  3. 非老年人按登记的先后顺序看病。

输入输出格式

输入格式

第1行，输入一个小于100的正整数，表示病人的个数；

后面按照病人登记的先后顺序，每行输入一个病人的信息，包括：一个长度小于10的字符串表示病人的ID（每个病人的ID各不相同且只含数字和字母），一个整数表示病人的年龄，中间用单个空格隔开。

输出格式

按排好的看病顺序输出病人的ID，每行一个。

INPUT & OUTPUT’s example

Input’s example #1

1
2
3
4
5
6
5
021075 40
004003 15
010158 67
021033 75
102012 30

Output’s example

1
2
3
4
5
021033
010158
021075
004003
102012

提示

唐：还看题解？

分析

一道极其毒瘤的tips式排序，但仔细一分析很简单。

我们开一个结构体strcut Node来存储每一个病人的信息，即ID和年龄。

将年龄$\geq60$的病人放成一组处理，而年龄$<60$的在另一组处理。

年龄$\geq60$的病人必须将年龄排序，年龄相同的按登记的先后顺序排序。

年龄$<60$的病人不排序。

代码

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
/* Headers */
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<iostream>
#include<cstring>
using namespace std;
/* define */
#define MAXN 100010
#define MAXS 92
namespace FastIO{
	const int BUFSIZE=(1<<20);
	char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
	char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
	inline char getch(){
		if(is==it)
			it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
		return (is==it)?EOF:*is++; 
	}
	inline int getint(){
		int neg=0,res=0,ch=getch();
		while(!(isdigit(ch)||ch=='-')&&ch!=EOF){
			ch=getch();
		}
		if(ch=='-'){
			neg=1;ch=getch();
		}
		while(isdigit(ch)){
			res=(res<<3)+(res<<1)+(ch-'0');
		} 
		return neg?-res:res;
	}
	inline void write(int x){
		if(x<0)putchar('-'),x=-x;
		if(x>9)write(x/10);
		putchar(x%10+'0');
	}
	inline void space(int x){
		if(x==0)putchar(' ');
		else putchar('\n');
	}
}
using namespace FastIO;
/* definitions */
struct Node{
	string s;
	int second;
}p[MAXN];
Node pat[MAXN];
int N,cnt;
/* functions */
inline bool cmp(Node a,Node b){
	return a.second>b.second;
}
int main(int arcg,char *argv[]){
	scanf("%d",&N);
	for(int i=1;i<=N;i++){
		cin>>p[i].s>>p[i].second;
	}
	for(int i=1;i<=N;i++){
		if(p[i].second>=60){
			pat[++cnt]=p[i];
		}
	}
	sort(pat+1,pat+1+cnt,cmp);
	for(int i=1;i<=N;i++){
		if(p[i].second<60){
			pat[++cnt]=p[i];
		}
	}
	for(int i=1;i<=cnt;i++){
		cout<<pat[i].s<<endl;
	}
	return 0;
}

E

经典的初级数据结构练手题目。

洛谷P1739表达式括号匹配的升级版。

难度：橙色的50602l.png

题目描述

假设表达式中允许包含圆括号和方括号两种括号，其嵌套的顺序随意，如([]())或[([][])]等为正确的匹配，[(])或([]()或(()))均为错误的匹配。

本题的任务是检验一个给定的表达式中的括号是否匹配正确。

输入一个只包含圆括号和方括号的字符串，判断字符串中的括号是否匹配，匹配就输出“OK”，不匹配就输出“Wrong”

输入输出格式

输入格式

一行字符，只含有圆括号和方括号，个数小于255。

输出格式

如果括号匹配就输出一行文本“OK“，不匹配就输出一行文本”Wrong”

INPUT & OUTPUT’s example

Input’s example #1

1
[(])

Output’s example #1

1
Wrong

提示

分析

经典的初级数据结构栈的练手题。

我们建一个栈，检测到(和[时将他们压入栈中，然后检测到)和]时查看当前栈顶是否有对应的括号，从而进行匹配。

这里用STL的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
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
/* Headers */
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<stack>
#include<iostream>
using namespace std;
namespace FastIO{
    const int BUFSIZE=(1<<20);
    char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==it)
            it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==it)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
        inline void write(int x){
    	if(x<0) putchar('-'),x=-x;
    	if(x>9) write(x/10);
    	putchar(x%10+'0');
    }
    inline void space(int x){
        if(x!=0) putchar(' ');
        else putchar('\n');
    }
} 
using namespace FastIO;
/* definitions */
stack<int>k;
string s;
/* functions */
inline void exit_return(){
    cout<<"Wrong"<<endl;
    exit(0);
}
int main(int argc,char *argv[]){
    ios::sync_with_stdio(false);
    cin>>s;
    for(int i=0;i<=s.length();i++){
        switch(s[i]){
            case '(':{
                k.push(0);
                break;
            }
            case '[':{
                k.push(1);
                break;
            }
            case ')':{
                if(k.empty())exit_return();
                if(k.top==0)exit_return();
                k.pop();
                break;
            }
            case ']':{
                if(k.empty())exit_return();
                if(k.top==1)exit_return();
                break;
            }
        }
    }
    if(k.empty())cout<<"OK"<<endl;
    else exit_return();
    return 0;
}

409:445

THE END