[ABC268D] Unique Username 题解

· · 题解

赛时做出了 D 却没做出 C，这是什么原因。。。

本题可以使用深度优先搜索 dfs。

搜索过程如下：

  1. 首先，枚举作为开端的字符串；
  2. 其次，枚举下一个字符串；
  3. 接着，枚举两个字符串之间下划线的数量；
  4. 将目前的字符串当作第一步“开端的”字符串并将当前搜索过的字符串打上标记，返回第二步继续搜索；

在第 2 步中如果用完了所有的字符串，那么就判断一下搜到的字符串是否合法，如果合法那么就输出这个答案。

用一个 std::set 存放所有不能使用的用户名，最终搜到答案时用 find 函数判断答案是否合法即可。

注意，这里有一个坑点，就是最终搜到的答案长度必须不小于 3，赛时被这玩意坑了 2 次 WA。错在这个地方的程序可以用如下的一组数据 hack 掉：

1 1
a
x

正确答案应该是 -1，而错误的程序会输出 a。

放代码：

#include<bits/stdc++.h>
using namespace std;
string a[9];
set<string> b;
bool x[9]; int n,m;
bool dfs(int t,string s){
  if(s.length()>=3&&t>=n&&b.find(s)!=b.end()){
    cout<<s<<endl;
    return true;
  }
  for(int i=1;i<=n;i++)
    if(!x[i]){
      for(int j=1;j<=16;j++){
        string tt=s; for(int k=1;k<=j;k++)tt+="_"; tt+=a[i];
        if(tt.length()>16)break; x[i]=true;
        if(tt.length()>=3&&dfs(t+1,tt))return true; x[i]=false;
      }
    }
  return false;
}
int main(){
  ios::sync_with_stdio(false);
  cin>>n>>m;
  for(int i=1;i<=n;i++)cin>>a[i];
  for(int i=1;i<=m;i++){
    string s; cin>>s;
    b.emplace(s);
  }
  for(int i=1;i<=n;i++){x[i]=true; if(dfs(1,a[i]))return 0; x[i]=false;}
  cout<<"-1\n";
  return 0;
}