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

px_poxiao · 2026-03-05 21:50:35 · 题解

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

做题第一步，先看数据范围：1 \le N \le 100；1 \le M \le 100，太好了我们可以直接暴力了。

对照题意，模拟即可，把每一条提示都假设为假提示，跑一遍即可。注意要判断没有假提示的情况，以及解不止一种的情况。

有两处细节需要注意：
第一，一个位置只有当两条提示给出了不同的信息时，这个猜测才会无效，不能只判断这个位置有没有使用过。
第二，两个解只有当字符的组成不同时，才能输出-2。因此，当得出两个解的时候，要判断这两个解是否完全一样，我用的是字符串比较。

AC code

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int n, m, used[110], cnt, loc[110];
string s[110], ans, tmp;
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    ans.resize(110);
    for(int i = 1; i <= n; i++){
        cin >> loc[i] >> s[i];
    }
    for(int i = 0; i <= n; i++){
        tmp.clear();
        tmp.resize(110);
        memset(used, 0, sizeof used);
        int allow = 1;
        for(int j = 1; j <= n; j++){
            if(i == j)
                continue;
            for(int k = loc[j]; k < loc[j] + s[j].size(); k++){
                if(used[k] && tmp[k] != s[j][k-loc[j]]){
                    allow = 0;
                    break;
                }
                tmp[k] = s[j][k-loc[j]];
                used[k] = 1;
            }
        }
        for(int i = 1; i <= m; i++){
            if(!used[i]){
                allow = 0;
                break;
            }
        }
        if(allow == 0)
            continue;
        if(cnt == 1 && ans != tmp){
            cout << -2;
            return 0;
        }
        if(cnt == 0){
            ans = tmp;
            cnt = 1;
        }
    }
    if(cnt == 0){
        cout << -1;
        return 0;
    }
    for(int i = 1; i <= m; i++)
        cout << ans[i];
}