中午在机房做的…没回宿舍感觉真爽…(我们宿舍没空调啊mmp!!!)

懵逼的 题目

病毒
[问题描述]
  有一天,小y突然发现自己的计算机感染了一种病毒!还好,小y发现这种病毒很弱,只是会把文档中的所有字母替换成其它字母,但并不改变顺序,也不会增加和删除字母。
  现在怎么恢复原来的文档呢!小y很聪明,他在其他没有感染病毒的机器上,生成了一个由若干单词构成的字典,字典中的单词是按照字母顺序排列的,他把这个文件拷贝到自己的机器里,故意让它感染上病毒,他想利用这个字典文件原来的有序性,找到病毒替换字母的规律,再用来恢复其它文档。
  现在你的任务是:告诉你被病毒感染了的字典,要你恢复一个字母串。
[输入格式]
virus.in
  第一行为整数K(≤50000),表示字典中的单词个数。
  以下K行,是被病毒感染了的字典,每行一个单词。
  最后一行是需要你恢复的一串字母。
  所有字母均为小写。
[输出格式]
virus.out
   输出仅一行,为恢复后的一串字母。当然也有可能出现字典不完整、甚至字典是错的情况,这时请输出一个0。
[输入样例]

  6
  cebdbac
  cac
  ecd
  dca
  aba
  bac
  cedab

[输出样例]

  abcde

扯淡的 题解

不会装影子系统嘛不会装影子系统嘛不会装影子系统嘛(划掉)
请忽略那些难看的字体QAQ
思路
大体就是这个意思…以大小关系建图,然后走一遍拓扑排序,得到的就是字母表…emm…然后…翻译就吼辣~
再次安利onenote(逃)

Update: 2017.09.01 意外发现居然传错了代码!QAQ…而且原来的代码不见了!QAQ…
Update: 2017.09.03 码完了…而且过了QAQ
在判错方面增加了改进…记录了图中的所有节点…如果整个图中的节点还比passw的长度小的话就puts("0");居然就解决了…吐槽数据水…

沙茶的 代码

// virus.cpp : 定义控制台应用程序的入口点。
//

//#include "stdafx.h"
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <string>
#include <queue>
#define MAXS (50000 + 5)
#define MAXN (26 + 5)
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
bool g[MAXN][MAXN];
int du[MAXN];
int totalpha = 0;
bool failed = false;
string srs[MAXS];
string passw;
int keyword[MAXN];
int sn;
void inp();
void init();
void tp();
inline int zh(const char x)
{
    return x - 'a' + 1;
}
int main()
{
//    freopen("virus.in", "r", stdin);
//    freopen("virus.out", "w", stdout);
    inp();
    /*for (int i = 1; i <= 26; i++)
    {
        printf("%d ", du[i]);
    }
    puts("");*/
    /*for (int i = 1; i <= sn; i++)
    {
        cout << srs[i] << endl;
    }
    cout << passw << endl;*/
    totalpha++;
//    printf("%d\n\n", totalpha);
    if (failed || (totalpha < passw.length()))
    {
        puts("0");
        return 0;
    }
    tp();
    if (failed)
    {
        puts("0");
        return 0;
    }
    int n = passw.length();
/*    for (int i = 1; i <= 26; i++)
    {
        printf("%d ", keyword[i]);
    }
    puts("");*/
    for (int i = 0; i < n; i++)
    {
        if (keyword[(int)passw[i] - 'a' + 1] == 0)
        {
            puts("0");
            return 0;
        }
    }
    for (int i = 0; i < n; i++)
    {
        cout << (char)(keyword[(int)passw[i] - 'a' + 1] + 'a' - 1);
    }
    return 0;
}
void inp()
{
    cin >> sn;
    for (int i = 1; i <= sn; i++)
    {
        cin >> srs[i];
    }
    cin >> passw;
    init();
}
void init()
{
    for (int i = 1; i < sn; i++)
    {
        for (int j = i + 1; j <= i + 1; j++)
        {
            int dqn = min((srs[i].length()), (srs[j].length()));
            if (srs[i] == srs[j])
            {
                failed = true; 
                return ;
            }
            for (int k = 0; k < dqn; k++)
            {
                if (srs[i][k] != srs[j][k])
                {
                    int fromz = zh(srs[i][k]);
                    int toz = zh(srs[j][k]);
                    if (!g[fromz][toz])
                    {
                        g[fromz][toz] = true;
                        du[toz]++;
                        totalpha++;
                    }
                    if (g[toz][fromz])
                    {
                        failed = true;
                        return ;
                    }
                    break;
                }
            }
        }
    }
}
void tp()
{
    int n = 26;
    //queue<int> q;
    bool v[27];
    memset(v, false, sizeof(v));
    for (int i = 1; i <= n; i++)
    {
        int k = 0;
        for (int j = 1; j <= n; j++)
        {
            if (!du[j] && !v[j])
            {
                if (!k)
                {
                    k = j;
                    break;
                }
                else
                {
                    failed = true;
                    return;
                }
            }
        }
        v[k] = true;
        if (!k)
        {
            failed = true;
            return ;
        }
        for (int j = 1; j <= n; j++)
        {
            if (g[k][j])
            {
                g[k][j] = false;
                du[j]--;
            }
        }
        keyword[k] = i;
    }
}
/*
6
cebdbac
cac
ecd
dca
aba
bac
cedab
*/

By 干啥啥不行代码还能传错的 Cansult