精华内容
下载资源
问答
  • 现在怎么恢复原来的文档呢!小y很聪明,他在其他没有感染病毒的机器上,生成了一个由若干单词构成的字典,字典中的单词是按照字母顺序排列的,他把这个文件拷贝到自己的机器里,故意让它感染上病毒,他想利用这个...

    题目

    有一天,小y突然发现自己的计算机感染了一种病毒!还好,小y发现这种病毒很弱,只是会把文档中的所有字母替换成其它字母,但并不改变顺序,也不会增加和删除字母。
    现在怎么恢复原来的文档呢!小y很聪明,他在其他没有感染病毒的机器上,生成了一个由若干单词构成的字典,字典中的单词是按照字母顺序排列的,他把这个文件拷贝到自己的机器里,故意让它感染上病毒,他想利用这个字典文件原来的有序性,找到病毒替换字母的规律,再用来恢复其它文档。
    现在你的任务是:告诉你被病毒感染了的字典,要你恢复一个字母串。

    输入格式
    第一行为整数K(≤50000),表示字典中的单词个数。
    以下K行,是被病毒感染了的字典,每行一个单词。
    最后一行是需要你恢复的一串字母。
    所有字母均为小写。

    输出格式
    输出仅一行,为恢复后的一串字母。当然也有可能出现字典不完整、甚至字典是错的情况,这时请输出一个0。

    样例

    样例输入
    6
    cebdbac
    cac
    ecd
    dca
    aba
    bac
    cedab
    样例输出
    abcde


    思路


    这一道题最先看的时候,发现这什么鬼题?
    之后我看了题解后,我终于知道怎么套进 用拓扑排序了


    我们可以使用stringstring来存储输入的字符串。
    我们可以比较相邻两个词第一个不相同的字母,后面就不能比较了,因为我们无法确定它们的顺序。
    因为拥有字符串之间的大小关系,所以可以快快乐乐 建图了。之后就可以使用拓扑排序,把病毒的字母大小的排列方式拿出来,同时再与真实字符串相联系起来(可以用MapMap),最后求出正确字符串。

    在这当中,一定要注意00的情况:
    1、若其中没有字母入度为零,即代表有环,那么就无解(想一想,一个最小的却要求比最开始的要大,肯定不可能)
    2、若最后字符串中映射不完整,那么就代表所给词典不完整


    这一题,主要突破点在于字符串字符的有序性,所以可以做出来。

    代码

    #include<cstdio>
    #include<vector>
    #include<iostream>
    #include<algorithm>
    #include<map>
    using namespace std;
    const int M=10005;
    int in[M],qwq[M];
    map<char,char> ma;
    vector<int> G[M];
    int main(){
    	int n;
    	scanf("%d",&n);
    	string s[M],need;
    	for(int i=1;i<=n;i++){
    		cin>>s[i];
    	}
    	cin>>need;
    	for(int i=2;i<=n;i++){
    		int len=min(s[i].length(),s[i-1].length());
    		for(int j=0;j<len;j++){
    			if(s[i][j]!=s[i-1][j]){
    				int x=s[i-1][j]-'a'+1,y=s[i][j]-'a'+1;
    				G[x].push_back(y);
    				in[y]++;
    				qwq[y]++,qwq[x]++;
    				break;
    			} 
    		}
    	}
    	int tot=0;
    	for(int i=1;i<=n;i++){
    		if(qwq[i]) tot++; 
    	}
    	for(int i=1;i<=tot;i++){
    		int j=1;
    		while(j<27&&(in[j]||!qwq[j])) j++;
    		if(j>26){
    			printf("0\n");
    			return 0;
    		}
    		ma[j+'a'-1]='a'+i-1;
    		in[j]=-1;
    		int siz=G[j].size();
    		for(int k=0;k<siz;k++){
    			int id=G[j][k];
    			in[id]--;
    		}
    	}
    	string ans;
    	for(int i=0;i<need.length();i++){
    		if(!ma[need[i]]){
    			printf("0\n");
    			return 0;
    		}
    		ans[i]=ma[need[i]];
    	}
    	for(int i=0;i<need.length();i++){
    		cout<<ans[i];
    	}
    	return 0;
    }
    
    展开全文
  • 「题解」病毒

    2020-08-19 22:01:25
    现在怎么恢复原来的文档呢!小y很聪明,他在其他没有感染病毒的机器上,生成了一个由若干单词构成的字典,字典中的单词是按照字母顺序排列的,他把这个文件拷贝到自己的机器里,故意让它感染上病毒,他想利用这个...

    题目描述

    有一天,小y突然发现自己的计算机感染了一种病毒!还好,小y发现这种病毒很弱,只是会把文档中的所有字母替换成其它字母,但并不改变顺序,也不会增加和删除字母。

    现在怎么恢复原来的文档呢!小y很聪明,他在其他没有感染病毒的机器上,生成了一个由若干单词构成的字典,字典中的单词是按照字母顺序排列的,他把这个文件拷贝到自己的机器里,故意让它感染上病毒,他想利用这个字典文件原来的有序性,找到病毒替换字母的规律,再用来恢复其它文档。

    现在你的任务是:告诉你被病毒感染了的字典,要你恢复一个字母串。

    输入格式

    第一行为整数K(50000)K(≤50000),表示字典中的单词个数。

    以下KK行,是被病毒感染了的字典,每行一个单词。

    最后一行是需要你恢复的一串字母。

    所有字母均为小写。

    输出格式

    输出仅一行,为恢复后的一串字母。当然也有可能出现字典不完整、甚至字典是错的情况,这时请输出一个00

    样例

    样例输入

    66
    cebdbaccebdbac
    caccac
    ecdecd
    dcadca
    abaaba
    bacbac
    cedabcedab

    样例输出

    abcdeabcde

    分析

    因为未被病毒入侵之前,所有的单词都是按字典序排列的,所以说被病毒入侵之后,词典的排列顺序是唯一寻找病毒入侵规律的方法,我们将每两个单词按位比较,如果相等,那么说明被病毒入侵之前,这两位字母是同样的,如果不同的话,那么说明被病毒入侵之前,靠前的单词的那一位字母,比另一单词的同一位的字典序靠前,如果长度不等且较短单词全部被另一单词匹配(如abcabcabcdabcd),那不能说明任何问题。。。

    其实,我们根本不用两两比较,比如说ababacacadad,我们在相邻比较中已经得到了b<cb<cc<dc<d,就不用去求得b<db<d了。

    我们如果求得了完整的大小顺序了,就可以用mapmap来存储我们得到那个恼火的病毒的入侵规律了。

    就差怎么求大小顺序,练同类型题的同学应该知道,这是拓扑排序的题,难道不是吗?我们就用一个简简单单的拓扑排序就完事儿了呀。

    代码

    #include <map>
    #include <cstdio>
    #include <vector>
    #include <string>
    #include <cstring>
    #include <cstdlib>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    const int M = 5e4 + 5;
    string s[M], obj;
    char ans[M];
    int used[M];
    int in[M];
    int n;
    
    map <char, char > de_bug;				//映射
    vector <int > e[M];
    
    int main() {
    	scanf("%d", &n);
    	for (int i = 1; i <= n; i ++) {
    		cin >> s[i];
    	}
    	cin >> obj;
    	for (int i = 1; i < n; i ++) {
    		int siz = min(s[i].length(), s[i + 1].length());
    		for (int j = 0; j < siz; j ++) {
    			if (s[i][j] != s[i + 1][j]) {
    				e[s[i][j] - 'a' + 1].push_back(s[i + 1][j] - 'a' + 1);
    				in[s[i + 1][j] - 'a' + 1] ++;
    				used[s[i][j] - 'a' + 1] ++;				//记录出现过的字符
    				used[s[i + 1][j] - 'a' + 1] ++;
    				break;
    			}
    		}
    	}
    	int cnt = 0;
    	for (int i = 1; i <= 26; i ++) {
    		if (used[i]) { ++ cnt; }
    	}
    	for (int i = 1; i <= cnt; i ++) {					//TopuSort
    		int j;
    		for (j = 1; j <= 26 && (in[j] || !used[j]); j ++);
    		if (j > 26) {
    			printf("0");
    			return 0;
    		}
    		de_bug[j + 'a' - 1] = i + 'a' - 1;				//映射
    		in[j] = -1;
    		for (vector <int > :: iterator it = e[j].begin(); it != e[j].end(); it ++) {
    			in[*it] --;
    		}
    	}
    	int siz = obj.length();
    	for (int i = 0; i < siz; i ++) {				//记录ans并且判断完整性
    		if (!de_bug[obj[i]]) {
    			printf("0");
    			return 0;
    		}
    		ans[i + 1] = de_bug[obj[i]];
    	}
    	printf("%s", ans + 1);
    	return 0;
    }
    
    展开全文
  • 4. 感谢网友008提醒,号码格式化字符%d已被替换为%u。 Version 2.4 (2008-7-24) 1. 好友添加。 2. Packed with pthread library. 3. 删除注销命令(可能引发异常) 4. 重发时长为6秒 Version 2.3 (2008-7-22) ...
  • 你必须知道495个C语言问题

    千次下载 热门讨论 2015-05-08 11:09:25
    3.7 是否可以安全地认为,一旦&&和||左边表达式已经决定了整个表达式结果,则右边表达式不会求值? 3.8 为什么表达式printf("%d%d",f1(),f2());先调用了f2?我觉得逗号表达式应该确保从左到右求值顺序...
  • <p><em>想跳过技术细节直接看怎么实践同学可以拖到文章底部,直接看最后一节。</em></p> 目前社区有很多关于微前端架构介绍,但大多停留在概念介绍阶段。而本文会就某一个具体类型场景,...
  • 4. 感谢网友008提醒,号码格式化字符%d已被替换为%u。 Version 2.4 (2008-7-24) 1. 好友添加。 2. Packed with pthread library. 3. 删除注销命令(可能引发异常) 4. 重发时长为6秒 Version 2.3 (2008-7-22) ...
  • javascript函数解释

    2011-02-26 11:03:52
    其实就是搞清做什么,怎么问题,先把流程图画出来,拆解开,一个个做好了然后再合并。理论东西我不会讲,直接举例哈! function g(o){return document.getElementById(o);} function hitover(n) { for(i=1...
  • 《你必须知道495个C语言问题》

    热门讨论 2010-03-20 16:41:18
    3.7 是否可以安全地认为,一旦&&和||左边表达式已经决定了整个表达式结果,则右边表达式不会求值? 36  3.8 为什么表达式printf("%d %d", f1(), f2()); 先调用了f2?我觉得逗号表达式应该确保从左到右...
  • 3.7 是否可以安全地认为,一旦&&和||左边表达式已经决定了整个表达式结果,则右边表达式不会求值? 36  3.8 为什么表达式printf(%d %d, f1(), f2()); 先调用了f2?我觉得逗号表达式应该确保从左到右求...
  • 1.3 我保存错了怎么恢复到之前版本? 7 1.4 让你战斗力瞬间飙涨10000+快捷键! 8 1.5 屏幕上你看到,不一定都会打印! 12 1.6 滥用空格键! 14 1.7 回车还有软硬之分? 16 1.8 回车并不是用来调节...
  • 8.3.8 把字符串一部分替换成另一个字符串 226 8.3.9 把字符串填充到字符串中 226 8.3.10 在小写和大写之间进行转化 227 8.3.11 移除前导空格和尾部空格 228 8.3.12 重复一个表达式N次 228 8.3.13 重复...
  • Windows XP(包括 Windows 2000)控制台命令是在系统出现一些意外情况下一种非常有效诊断和测试以及恢复系统功能工具。小编的确一直都想把这方面命令做个总结,这次辛苦老范给我们整理了这份实用秘笈。 ...
  • MongoDB权威指南--详细书签版

    热门讨论 2013-02-04 13:31:06
    3.3.5 返回已更新的文档 38 3.4 瞬间完成 41 3.4.1 安全操作 41 3.4.2 捕获“常规”错误 42 3.5 请求和连接 43 第4章 查询 45 4.1 find简介 45 4.1.1 指定返回的键 46 4.1.2 限制 46 4.2 查询...
  • 400个DreamWeaver插件

    2013-03-28 15:30:13
    mxp/如果你页面包含在某个框架中,则可以显示出一些自定义信息 mxp/见过有一种很特别没有边框,没有Title窗口吗?很多朋友都问过这个窗口是怎么了。就是用这个插件 mxp/在代码编辑模式状态下,点击右键...
  • Visual Studio程序员箴言--详细书签版

    热门讨论 2012-10-16 20:37:39
    技巧4.9 使用Ctrl+F6键和Ctrl+Shift+F6键在打开的文档窗口间导航 78 技巧4.10 使用Ctrl+F4键关闭编辑器中当前打开的文档 78 4.1.4 MDI模式 78 技巧4.11 进入MDI模式 78 技巧4.12 在“窗口”对话框中显示...
  • vc++ 开发实例源码包

    2014-12-16 11:25:17
    这个例子就是查询任何可执行文件版本信息并且 C++builder 和 VC 都通用,只需要把 AnsiString 替换成 CString 就行了。 gh0st v3.6 源码 - 可下断点调试! 如题。详细见源码。 GMem 内存管理单元源码。GMem.cpp...
  • vc++ 应用源码包_1

    热门讨论 2012-09-15 14:22:12
    这个例子就是查询任何可执行文件版本信息并且 C++builder 和 VC 都通用,只需要把 AnsiString 替换成 CString 就行了。 gh0st v3.6 源码 - 可下断点调试! GMem 内存管理单元源码。GMem.cpp和GMem.h是内存管理...
  • vc++ 应用源码包_6

    热门讨论 2012-09-15 14:59:46
    这个例子就是查询任何可执行文件版本信息并且 C++builder 和 VC 都通用,只需要把 AnsiString 替换成 CString 就行了。 gh0st v3.6 源码 - 可下断点调试! GMem 内存管理单元源码。GMem.cpp和GMem.h是内存管理...
  • vc++ 应用源码包_2

    热门讨论 2012-09-15 14:27:40
    这个例子就是查询任何可执行文件版本信息并且 C++builder 和 VC 都通用,只需要把 AnsiString 替换成 CString 就行了。 gh0st v3.6 源码 - 可下断点调试! GMem 内存管理单元源码。GMem.cpp和GMem.h是内存管理...
  • vc++ 应用源码包_5

    热门讨论 2012-09-15 14:45:16
    这个例子就是查询任何可执行文件版本信息并且 C++builder 和 VC 都通用,只需要把 AnsiString 替换成 CString 就行了。 gh0st v3.6 源码 - 可下断点调试! GMem 内存管理单元源码。GMem.cpp和GMem.h是内存管理...
  • vc++ 应用源码包_4

    热门讨论 2012-09-15 14:38:35
    这个例子就是查询任何可执行文件版本信息并且 C++builder 和 VC 都通用,只需要把 AnsiString 替换成 CString 就行了。 gh0st v3.6 源码 - 可下断点调试! GMem 内存管理单元源码。GMem.cpp和GMem.h是内存管理...
  • vc++ 应用源码包_3

    热门讨论 2012-09-15 14:33:15
    这个例子就是查询任何可执行文件版本信息并且 C++builder 和 VC 都通用,只需要把 AnsiString 替换成 CString 就行了。 gh0st v3.6 源码 - 可下断点调试! GMem 内存管理单元源码。GMem.cpp和GMem.h是内存管理...
  • 1.2.8 对大数据平台中元数据管理是怎么理解,元数据收集管理体系是怎么,会对大数据应用有什么样影响 1.2.9 你理解常见如阿里,和友商大数据平台技术体系差异以及发展趋势和技术瓶颈,在存储和计算两...
  • 1 理解计算机是怎么运行程序 2 运行一个已解释程序 3 运行一个已编译程序 4 C++在哪里 5 理解Visual c++中程序文件 6 创建源代码文件 7 理解并创建头文件 第二章 结构和语法 8 理解计算机语言 9 理解计算机...
  • 1 理解计算机是怎么运行程序 2 运行一个已解释程序 3 运行一个已编译程序 4 C++在哪里 5 理解Visual c++中程序文件 6 创建源代码文件 7 理解并创建头文件 第二章 结构和语法 8 理解计算机语言 9 理解计算机...
  • 1 理解计算机是怎么运行程序 2 运行一个已解释程序 3 运行一个已编译程序 4 C++在哪里 5 理解Visual c++中程序文件 6 创建源代码文件 7 理解并创建头文件 第二章 结构和语法 8 理解计算机语言 9 理解计算机...

空空如也

空空如也

1 2
收藏数 40
精华内容 16
关键字:

被替换的文档怎么恢复