题解：P15618 [ICPC 2022 Jakarta R] Nightmare Brother

Jason2013awa · 2026-03-07 18:57:17 · 题解

注意到 N,M 范围很小，因此可通过枚举假提示是哪一条，再分别模拟将线索字符串放入答案字符串做一遍来得出答案。

注意有可能有多个答案，所以用一个 vector 来存。

最终判断答案数量输出即可。

时间复杂度：枚举假提示和 O(NM) 模拟乘起来，最终复杂度 O(N^2M)。

注意答案重复和所有线索全部为真的情况。

#include<bits/stdc++.h>
using namespace std;
int id[100005];
string s[10005];

vector<string>v;
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>id[i]>>s[i];
    for(int i=1;i<=n;i++){
        string ans;
        ans.resize(m,0);
        int ac=1;//答案是否有效
        for(int j=1;j<=n;j++){
            if(j==i)continue;
            for(int k=0;k<s[j].size();k++){
                if(ans[k+id[j]-1]&&ans[k+id[j]-1]!=s[j][k])ac=0;//矛盾
                ans[k+id[j]-1]=s[j][k];
            }

        }
        for(int k=0;k<m;k++)if(!ans[k])ac=0;//有不确定的位置
        if(ac){
            v.push_back(ans);
        }
    }
    //也有可能没有假的
    string ans;
    ans.resize(m,0);
    int ac=1;
    for(int j=1;j<=n;j++){
        for(int k=0;k<s[j].size();k++){
            if(ans[k+id[j]-1]&&ans[k+id[j]-1]!=s[j][k])ac=0;
            ans[k+id[j]-1]=s[j][k];
        }   
    }
    for(int k=0;k<m;k++)if(!ans[k])ac=0;

    if(ac){
        v.push_back(ans);
    }
    //注意v中多个字符串全部相同不算作-2
    auto len=unique(v.begin(),v.end());//len：去重后的v.end()
    auto tt=v.begin();
    tt++;//此时应该的v.end()是v[1]
    if(v.size()==0)cout<<-1;
    else if(len!=tt){
        cout<<-2;
    }
    else cout<<v[0];
    return 0;
}