洛谷P1184《高手之在一起》题解报告

女爷i 2023-02-09 11:52 5阅读 0赞

# 题目 #

[屠龙宝刀点击就送][Link 1]

# 解法一 #

## 一、分析 ##

### （一）处理空格 ###

根据题意，每一行输入的字符串可能包含空格。如果直接使用cin来读取，则cin碰到空格或换行符就不再读取。

#### 例1： ####

#include <iostream>
    using namespace std;
    
    int main()
    { 
        cout << "输入字符串：";
        string s;
        cin >> s;
    
        cout << "输出字符串：";
        cout << s;
    
        return 0;
    }

运行结果：

输入字符串：abc def
    输出字符串：abc

所以要想办法读取空格。可使用getchar()来读取每行中的空格。因为空格可能不止一个，可使用for循环来处理。

#### 例2： ####

#include <iostream>
    #include <cstdio>
    using namespace std;
    
    int main()
    { 
        cout << "输入字符串：";
        string s;
        cin >> s;
        while(getchar() == ' ') //读到空格
        { 
            string tmp;
            cin >> tmp;
            s += tmp;
        }
    
        cout << "输出字符串：";
        cout << s;
    
        return 0;
    }

运行结果：

输入字符串：ab cd ef
    输出字符串：abcdef

### （二）使用map ###

map里面放的是数据对。可以把高手方便去的地点先处理掉空格后再放到map中，并把这个地址标记为true。

比如高手方便去的地方有“ab cd ef”和“gh ij”,这两个地址处理掉空格后，变成了“abcdef”和“ghij”，接着把<“abcdef”， true>和<“ghij”， true>存入到map中，即map\[“abcdef”\]=true，map\[“ghij”\]=true。

然后对于小萝莉去的地方，跟map里面的key即地址比对，若该key为true，说明这个地方高手也可以去。此时答案加1。

## 二、AC代码 ##

#include <iostream>
    #include <map>
    #include <cstdio>
    using namespace std;
    
    int n, m;
    string place;
    int ans = 0;
    map<string, bool> mp;
    
    int main()
    { 
    	cin >> n >> m;
    
    	for(int i = 1; i <= n; i++)
    	{ 
    		cin >> place;
    		string tmp;
    		while(getchar() == ' ') //读取空格
    		{ 
    			cin >> tmp;
    			place += tmp;
    		}
    		mp[place] = true;
    	}
    
    	for(int i = 1; i <= m; i++)
    	{ 
    		cin >> place;
    		string tmp;
    		while(getchar() == ' ')
    		{ 
    			cin >> tmp;
    			place += tmp;
    		}
    
    		if(mp[place])
            { 
                ans++;
            }
    	}
    
    	cout << ans;
    
    	return 0;
    }

# 解法二 #

## 一、分析 ##

也可以把高手方便去的地方存储到set里面。然后将小萝莉每天去的地方与set里的地址比对，若set里有这个地址，则答案加1。

set里查找某个元素存在与否，可使用count()或find()。  
因为set里的元素不能重复，所以count()的函数的返回值只能是1或0。为1时表示set里此元素有1个，为0时表示set里无此元素。  
若用find()，则set.find(XXX) != set.end()表示set中存在XXX元素。

## 二、AC代码 ##

#include <iostream>
    #include <set>
    #include <cstdio>
    using namespace std;
    
    int n, m;
    string place;
    int ans = 0;
    set<string> s;
    
    int main()
    { 
    	cin >> n >> m;
    
    	for(int i = 1; i <= n; i++)//高手可去的地方
    	{ 
    		cin >> place;
    		string tmp;
    		while(getchar() == ' ') //getchar()的头文件是cstdio
    		{ 
    			cin >> tmp;
    			place += tmp;
    		}
    		s.insert(place);
    	}
    
    	for(int i = 1; i <= m; i++)//第i天小萝莉会去的地方
    	{ 
    		cin >> place;
    		string tmp;
    		while(getchar() == ' ')
    		{ 
    			cin >> tmp;
    			place += tmp;
    		}
    
    		if(s.count(place)) //count若不为0，表示set中存储了这个地方，即高手方便去这个地方
            { 
                ans++;
            }
    	}
    
    	cout << ans;
    
    	return 0;
    }

# 解法三：使用getline函数 #

## 一、分析 ##

### （一）Windows和Linux中换行符的区别 ###

Windows系统中，换行是由两个字符“\\r\\n”组成的。  
’\\r’为回车，其ASCII码是13，作用是回到当前行的第一列。  
’\\n’为换行，其ASCII码是10。作用是到达下一行的当前列。”\\r\\n”作用是跳到下一行的第一列。  
Linux中，’\\n’的作用是跳到下一行的第一列，相当于Windows下的“\\r\\n”。

### （二）测试数据对应的十六进制数 ###

p1184\_1.in第一个测试点的输入数据（这句话说明我这道题没能一次性通过，哈哈）为：

1 1
    WC
    WC

使用UltraEdit编辑器，可以看到上面的数据的十六进制形式为  
![图1.png][1.png]

图1

上面的数据分为三部分：左侧的00000000h表示是十六进制形式，中间部分即为十六进制的值，最右侧为原始数据。  
十六进制的31等于十进制的49，49是字符’1’的ASCII码。  
十六进制的20对应于十进制的32，32是空格的ASCII码。  
十六进制的0D等于十进制的13，13是回车符’\\r’的ASCII码。  
十六进制的0A等于十进制的10，10是换行符’\\n’的ASCII码。  
十六进制的57等于十进制的87，87是’W’的ASCII码。  
……  
从0D可看出，这个测试点的数据是在Windows操作系统下生成的。据上可推测本题的所有测试数据都是在Windows下生成的。所以在编程时，需要处理回车符’\\r’。

### （三）cin读取数据 ###

当使用键盘输入数据时，数据是存放在内存的输入缓冲区中。使用cin时，如果读取到的是空格，则会忽略空格并将空格从输入缓冲我中移除。  
语句cin >> n >> m，第一次读取到的是1，赋值给n，此时n = 1，并且1会从输入缓冲区中移除。接着会读取到空格，忽略掉并将空格从输入缓冲区中移除。接着读取到第二个1，赋值给m，即m = 1，并且1会从输入缓冲区中移除。

### （四）getline()读取数据 ###

getline(cin, str)的作用是读取一行数据（不包含行末的换行符）到字符串str中，并在str末尾添加’\\0’，同时将行末的换行符’\\n’从输入缓冲区中移除。

### （五）过滤回车符和换行符 ###

在cin >> n >> m里，在输入缓冲区中，第一行还保留”\\r\\n”。处理这两个数据有两种方式。  
第一种是两次getchar()，即

getchar();
    getchar();

第一个语句是读取回车符’\\r’并将回车符从输入缓冲区中移除；第二个语句是读取换行符’\\n’并将换行符从输入缓冲区中移除。

第二种方法是使用getline(cin, str)，把’\\r’读取到str中，同时从输入缓冲区中移除’\\n’。

### （六）处理最后一行的格式 ###

有换行的数据末尾是以’\\r\\n’结尾的，没有换行的数据末尾没有’\\r\\n’。有些数据的最后一行之后有换行，有些没有换行。比如测试点1的最后一行就没有换行，这从图1中可以看出来。所以咱们可对最后一行做处理，如果最后一行没有换行，就加上’\\r’，这样就跟其他行一样了。代码为：

if (m == i && place[place.size() - 1] != '\r')
            {
                place += char(13);//char(13)等价于'\r'
            }

这里的m == i也可以不写。不写表示对每一行进行判断。当然除了最后一行，其他行肯定都换行了，所以对于其他行，m==i必然为假。

## 二、AC代码 ##

#include <iostream>
    #include <set>
    #include <cstdio>
    using namespace std;
    
    int main()
    { 
        //freopen("P1184.in", "r", stdin);
    
    	string place;
    	set<string> st;
    
    	int n, m, ans=0;
    	cin >> n >> m;
    
        getline(cin, place); //用两次getchar()也可以
    	for (int i=1; i<=n; i++)
    	{ 
    		getline(cin, place);//读入整行的字符串
    		st.insert(place);
    	}
    
    	for (int i=1; i<=m; i++)
    	{ 
    		getline(cin, place);
    
    		//本题测试数据在win下生成，最后一行是否少了回车符，这里m==i不写也可以，表示每行都判断
    		if (m == i && place[place.size() - 1] != '\r')
            { 
                place += char(13);//char(13)等价于'\r'
            }
    
    		if (st.find(place) != st.end())
            { 
                ans++;
            }
    	}
    
    	cout<<ans;
    
    	return 0;
    }

了解信息学奥赛请加微信307591841（QQ同号）

[Link 1]: https://www.luogu.com.cn/problem/P1184
[1.png]: https://img-blog.csdnimg.cn/20200519091529311.png?x-oss-process=image