Voldemort's blog

Voldemort's blog

我好菜啊

题解 AT3600 【[ABC076C] Dubious Document 2】

posted on 2020-08-27 13:34:10 | under 题解 |

题解 AT3600 【[ABC076C] Dubious Document 2】
由于 AtCoder 的端口炸了,所以这份代码是在 AtCoder 上直接提交的,记录详情:

Solution

如果这道题目的字符串长度加强一下那这题会变得十分恐怖,但是由于长度都小于等于50,所以我们可以考虑暴力
怎么暴力呢? 我们枚举每一个配对情况,看一下是否可以配对,如果可以就看一下是否可以更新答案,最后输出即可。
看不懂上面文字的(应该都看得懂吧)我们来看一下这一堆图来加强理解:
我们以第一组样例为例

我们发现目标串的对应位置是一个未知元素,因此可以和我们的字符c匹配成功,于是指针j后移一位。

我们发现目标串中是已知元素t,不能与o进行匹配,所以匹配失败。指针i向后移一位,指针j复原。
(一下省略 infinity 张图……)

所以这就是这道题暴力的算法,还是比较简单的,觉得评个黄题是不是过了,给个橙差不多……

Code

#include <bits/stdc++.h>
using namespace std;

string ans = "";
string s,t,tmp = "";
int ls,lt,flag;

int main() {
    cin >> s >> t;
    ls = s.size();lt = t.size();
    if(ls < lt)  {  //如果子串比目标串都长,那么肯定失配
        puts("UNRESTORABLE");
        return 0;
    }
    for(int i = 0;i < ls - lt + 1;i++) {
        tmp = s;flag = 0;   //用tmp代替目标串
        for(int j = i;j < i + lt;j++) {
            if(tmp[j] == '?') tmp[j] = t[j - i];    //如果是未知元素,那么匹配
            else {
                if(tmp[j] != t[j - i]) {    //如果不是未知元素且不相等,那么失配
                    flag = 1;
                    break;
                }
            }
        }
    //  cout << tmp << "\n";
        if(flag == 0) {
            for(int j = 0;j < ls;j++) { //对于没有匹配到的未知元素附以字典序最小的a
                if(tmp[j] == '?') tmp[j] = 'a';
            }
            if(ans == "") ans = tmp;
            else ans = min(ans,tmp);
        }
    }
    if(ans != "") cout << ans << "\n";
    else puts("UNRESTORABLE");
    return 0;
}