Misha and Changing Handles
Description
Misha hacked the Codeforces site. Then he decided to let all the users change their handles. A user can now change his handle any number of times. But each new handle must not be equal to any handle that is already used or that was used at some point.
Misha has a list of handle change requests. After completing the requests he wants to understand the relation between the original and the new handles of the users. Help him to do that.
Input
The first line contains integer q (1 ≤ q ≤ 1000), the number of handle change requests.
Next q lines contain the descriptions of the requests, one per line.
Each query consists of two non-empty strings old and new, separated by a space. The strings consist of lowercase and uppercase Latin letters and digits. Strings old and new are distinct. The lengths of the strings do not exceed 20.
The requests are given chronologically. In other words, by the moment of a query there is a single person with handle old, and handle new is not used and has not been used by anyone.
Output
In the first line output the integer n — the number of users that changed their handles at least once.
In the next n lines print the mapping between the old and the new handles of the users. Each of them must contain two strings, old and new, separated by a space, meaning that before the user had handle old, and after all the requests are completed, his handle is new. You may output lines in any order.
Each user who changes the handle must occur exactly once in this description.
Sample Input
5
Misha ILoveCodeforces
Vasya Petrov
Petrov VasyaPetrov123
ILoveCodeforces MikeMirzayanov
Petya Ivanov
3
Petya Ivanov
Misha MikeMirzayanov
Vasya VasyaPetrov123
思路:
逻辑层面没什么好想的,但是数据操作层面会出现很多的问题
(1)字符串数组的覆盖,如果被覆盖的字符串长度更长,则要在新字符串的后面加上'\0',不然容易出现奇怪的字母
(2)然后想思路的时候就不要局限在所给的数组,而要从题目的规则出发,自己构想出一般情况然后再从头开始推
(3)对于每个request的原始姓名而言,他每被修改一次,就给他压进栈一次,利用栈的原理和标记数组实现
#include <iostream>
#include <cstring>
#include <stack>
using namespace std; struct R{
char start[];
char end[];
int val;
}requests[];
stack<int> s;
int vis[]; void cover(char* str1,char* str2)
{
int len = strlen(str2);
for(int i = ;i < len;i++)
str1[i] = str2[i];
str1[len] = '\0';
} bool scmp(char* str1,char* str2)
{
int len1 = strlen(str1);
int len2 = strlen(str2);
if(len1 != len2) return false;
int flag = ;
for(int i = ;i < len1;i++)
if(str1[i] == str2[i]) flag++;
if(flag == len1) return true;
else return false;
} int main()
{
int n;
while(cin>>n)
{
int ans = ;
while(!s.empty())
s.pop();
memset(vis,,sizeof(vis));
for(int i = ;i <= n;i++)
{
cin>>requests[i].start>>requests[i].end;
requests[i].val = ;//i为起点
int flag = ;
for(int j = ;j < i;j++)
if(requests[j].val && scmp(requests[i].start,requests[j].end)) {
cover(requests[j].end,requests[i].end);
requests[i].val = ;
s.push(j);
flag = j;
break;
}
if(requests[i].val) {
ans++;
s.push(i);
}
}
if(requests[n].val) s.push(n);
cout<<ans<<endl;
while(!s.empty()) {
int tmp = s.top();
s.pop();
if(vis[tmp]) continue;
cout<<requests[tmp].start<<' '<<requests[tmp].end<<endl;
vis[tmp] = ;
} }
return ;
}
最新文章
- golang操作文件
- Bootstrap_媒体对象
- nginx-1.7.9快速启动连接手机测移动端页面
- 响应式布局设置--@media only screen and
- 【转】iOS开发网络篇—发送json数据给服务器以及多值参数
- php安装扩展模块(curl模块)
- 基于winpcap的以太网流量分析器(java)
- CF 610E. Alphabet Permutations
- ASP.NET Core轻松入门之Configure中IHostingEnvironment和IApplicationLifetime的使用
- eclipse juint4 出错!!!
- Java_03选择结构
- Windows 的命令行安装Scoop程序管理工具
- jQuery 选择器demo练习
- Zabbix监控MySQL免密码设置
- 同台同时多开DELPHI2007的解决办法
- X32位 天堂2 二章/三章 服务端协议号修改方法
- Objective-C 类别(category)和扩展(Extension)
- vs2010查看quartz.net 2.1.2的源码时其中一报错的解决方法
- [CEOI2017]Building Bridges
- 【HNOI2014】抄卡组