题解：P14609 [NWRRC 2025] Judging Problem

Solil1019 · 2025-11-27 20:43:54 · 题解

题目大意

现有 n 道题目，需要在连续的 n 年中每年使用一道。题目选择规则如下：

• 第一年任意选择。
• 后续年份：
  • 如果存在与上一年题目相似且未使用的题目，必须从中选择。
  • 否则可以任意选择未使用的题目。

相似的定义：两个题目的第一个单词相同或第二个单词相同。

给定按时间顺序排列的题目使用序列，判断是否符合上述规则。

解题思路

直接通过模拟选择过程来验证序列的合法性即可。

对于每个位置（从第二个开始）：

1. 检查是否存在与上一年题目相似且未使用的题目。
2. 如果存在，当前题目必须与上一年题目相似。
3. 如果不存在，可以任意选择未使用的题目。
4. 同时确保题目不被重复使用。

做法：

• 使用哈希表 fir 和 sec 分别记录每个第一个单词和第二个单词对应的题目索引。
• 使用集合 vis 记录已使用的题目索引。

具体的可以看代码吧。

Code

#include <bits/stdc++.h>
using namespace std;
int T,n;
bool check(pair<string,string>a,pair<string,string>b){
    return a.first==b.first||a.second==b.second;
}
int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        vector<pair<string,string>>p(n);
        unordered_map<string,vector<int>>fir,sec;
        for(int i=0;i<n;i++) {
            cin>>p[i].first>>p[i].second;
            fir[p[i].first].push_back(i);
            sec[p[i].second].push_back(i);
        }
        bool flag=true;
        unordered_set<int>vis;
        vis.insert(0);//第一个题目已使用 
        for(int i=1;i<n;i++) {
            bool last=false;//检查是否存在与上一年相似且未使用的题目 
            for(int x:fir[p[i-1].first]){//检查第一个单词相同的题目
                if(vis.find(x)==vis.end()){
                    last=true;
                    break;
                }
            }
            if(!last){//检查第二个单词相同的题目
                for(int x:sec[p[i-1].second]){
                    if(vis.find(x)==vis.end()){
                        last=true;
                        break;
                    }
                }
            }
            if(last){//必须选择相似的题目
                if(!check(p[i-1],p[i])){
                    flag=false;
                    break;
                }
            }
            if(vis.find(i)!=vis.end()){//否则可以任意选择未使用的题目
                flag=false;
                break;
            }
            vis.insert(i);
        }
        cout<<(flag?"Yes":"No")<<endl;
    }
}