P14609 [NWRRC 2025] Judging Problem

Refrained · 2025-11-27 19:41:51 · 题解

超劣解。

我们令第 i 个题目名称的两个字符串分别为 a_i,b_i。

1. 题目分析

简单来说，如果一个字符串的相似字符串还没有用完，那么就是不合法的，否则合法。一个很好想的做法就是用两个 \text{set} 记录字符串 a_i 的相似字符串集合和字符串 b_i 的相似字符串集合，出完一道题就将它从它对应的相似字符串集合删去，不合法即为出这道题的时候上一道题的相似题目的集合非空。

于是很简单的做完了，复杂度是 O(\sum n\log\sum n) 的。

2. 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
string a[N],b[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        int n,flag=1;cin>>n;
        unordered_map<string,set<int>>visA,visB;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i]>>b[i];
            visA[a[i]].insert(i);
            visB[b[i]].insert(i);
        }
        visA[a[1]].erase(1),visB[b[1]].erase(1);
        for(int i=2;i<=n;i++)
        {
            if(a[i]==a[i-1]||b[i]==b[i-1])goto MAI;
            if(!visA[a[i-1]].empty()||!visB[b[i-1]].empty()){flag=false;break;}
            MAI:;visA[a[i]].erase(i),visB[b[i]].erase(i);
        }
        if(flag)cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}