T2 题解

前言

这道题目其实不难，不需要什么奇怪的算法，是一道正宗的模拟题，主要可以检测大家的代码实现能力。然而答题情况却与我预想的相差甚远。我怀疑其中有看不懂题目/不理解题意的问题。如果是因为题目描述不够清晰导致的，我在此表示我最诚挚的歉意。

如果对这个游戏感兴趣也可以在线玩一玩：wordlewordle.net 。

思路

初看题目，我们可能会想到利用尝试的单词及颜色推断出每个字母是否存在以及它们出现的位置（还有它们不能出现的位置）。由于输入的词库按照字典序排列，我们只需要遍历词库中所有单词，找到第一个合法的单词输出即可。

然而这样写还是太麻烦了。我们注意到 $m \le 5$ 并且 $n \le 10^5$，并且时间限制为 1s，那么时间复杂度为 $O(nm)$ 的程序完全可以通过本题。因此，我们只需要遍历词库中的所有单词，依次检查是否符合所有的猜测，并输出第一个合法的答案即可。

那么如何判断一个答案是否合法呢？

假设我们要判断一个单词 $D$ 是否合法，我们可以使用一个长度为 26 的数组 p[c-'a']，表示小写英文字符 c 在 $D$ 中出现的位置，如果这个字母不存在，将其设置为一个很大的值表示区分。

接着我们遍历每次猜测，假设某一次猜测的单词是 $S$，对应的颜色是 $T$：

1. 如果 $T_i$ 为 #，那么 $S_i$ 这个字母就一定为答案的第 $i$ 个字母。我们检查 p[S[i] - 'a'] 是否等于 i，如果不是，答案一定不合法。
2. 如果 $T_i$ 为 @，那么 $S_i$ 这个字母就一定出现在答案中，并且不出现在这个位置上。我们检查 p[S[i] - 'a'] 是否小于 5，并且不等于 i，如果不是，答案一定不合法。（如果你的下标 i 从 1 开始，那么需要检查是否小于等于 5。如果这个字母在 $D$ 中不存在，我们先前已经将这个东西设为了一个很大的值，因此小于 5 表示 $D$ 中有这个字母）。
3. 如果 $T_i$ 为 .，那么 $S_i$ 这个字母就一定不出现在答案中。我们检查 p[S[i] - 'a']是否大于等于 5，如果不是，那么答案一定不合法。 （如果你的下标 i 从 1 开始，那么需要检查是否大于 5，详细的解释同上）
4. 如果这个单词 $D$ 的所有 5 个字母都通过了以上所有检查，那么这就是一个合法的答案。

另，有很多方法可以判断，以下是一种简单做法（代码量少且思路简单）。当然很多其他做法也是可以通过本题的（本题条件非常宽松），你可以发在这篇帖子下面启发后人。

以上。

总结

我简单浏览了一些人的第二题代码。

首先，我想要隔空喊话是 jyc 同学：

为 什 么 不 加 上 花 括 号 啊 ！

我们贴上他原来的代码（5分）：

#include<bits/stdc++.h>
using namespace std;
bool checkWord(const string&word,const string&guess,const string&color)
{
    for(size_t i=0;i<5;i++)
	{
        char c=color[i];
        if(c=='#')
            if(word[i]!=guess[i])
                return false;
        else if(c=='@')
            if(guess[i]==word[i]||word.find(guess[i])==string::npos)
                return false;
        else if(c=='.')
            if(word.find(guess[i])!=string::npos)
                return false;
    }
    return true;
}
// ...

注意看 checkWord 函数中的判断语句。这里出现了嵌套的if，但是这位同学 没！有！加！上！花！括！号！ 因此，else if(c=='@') 这个语句匹配的是最接近的那个if语句，也就是 if(word!=guess[i])。这个缩进非常具有迷惑性，让人认为其匹配的是 if(c=='#')。可惜这是 c++ 而不是 python。

只需要一个非常小的改动，这段代码就可以 AC：

bool checkWord(const string&word,const string&guess,const string&color)
{
    for(size_t i=0;i<5;i++)
	{
        char c=color[i];
        if(c=='#'){
            if(word[i]!=guess[i])
                return false;
        }else if(c=='@'){
            if(guess[i]==word[i]||word.find(guess[i])==string::npos)
                return false;
        }else if(c=='.'){
            if(word.find(guess[i])!=string::npos)
                return false;
        }
    }
    return true;
}

这份代码的思路完全正确，并且对于 c++ 一些特性使用的熟练程度让我眼前一亮，以至于让我怀疑这是否是某位大佬炸鱼。比初二的我强太多了，%%%。不知道能否加个联系方式呢？（偷偷夹带私货）

然后是 75 分的 czx 同学。(75分的同学应该都是这个问题）。我觉得这是一个非常可惜的分数，得到 75 分是因为没有判断 $T_i$ 为 @ 时，对应的字母不能出现在这个位置。或许只需要再加上一个简单的判断就能通过本题。另，我第一次生成数据时因为没有注意到这个情况导致数据出锅，直到几天后才猛然想到需要做这个判断。这个判断可能过于细节，并且对于整体代码而言其实无伤大雅，经过考量后我给了 75 分。但这也给我们敲响了警钟：注意细节。最后，还是要恭喜我们的 czx 同学荣获本次比赛最高分，并且在 T3 题目出问题的情况下还能骗得 20 分的惊人战绩。

其次是 30 分的 xjy 同学。我觉得这份代码挺奇怪的，其实和正解已经比较接近了。为什么会想到统计字母数量来判断答案正确性呢？我挺不能理解的。（拓展一点高中知识：这是一个必要不充分条件，即如果答案正确，那么这个方法判断出来一定是正确的，但通过这个方法判断出来为正确的答案不一定是正确答案。比如，通过 $a \le 5$ 可以得出 $a \le 100$，但是 $a \le 100$ 不一定能得出 $a \le 5$）。

同样是 30 分的 yyd 同学，我觉得这是一个挺好的思路，可能是时间来不及吧，希望再接再厉。

20 分的 lsr 同学，请原谅我看不懂你的代码，这个命名风格略有点随性。以你能参加 CSP-S 的能力，相信你可以找到代码中问题并改好的（逃

最后是 5 分的 wjh 同学。代码的思路基本正确，我疑心是时间不够没有写完。

因时间问题无法一一做出总结，见谅。

希望大家能再接再厉，勇创佳绩！

最后附上 AC 代码。

标程

如果你看不懂，请先看看最后的附注。

#include<bits/stdc++.h>

std::string dict[100101];
std::string guess[10];
std::string pattern[10];

bool check(std::string& ans, std::string& tst, std::string& pat){
  static int pos[26];
  memset(pos, 0x3f, sizeof(pos));
  for(int i = 0; i < 5; ++i){
    pos[int(ans[i] - 'a')] = i;
  }
  for(int i = 0; i < 5; ++i){
    if(!(
      (pat[i] == '#' && i == pos[tst[i] - 'a'])
      || (pat[i] == '@' && pos[tst[i] - 'a'] <= 5 && pos[tst[i] - 'a'] != i)
      || (pat[i] == '.' && pos[tst[i] - 'a'] > 5)
    )) return false;
  }
  return true;
}

int main(){
  freopen("wordle.in", "r", stdin);
  freopen("wordle.out", "w", stdout);
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int n, m;
  std::cin>>n;
  for(int i = 0; i < n; ++i){
    std::cin>>dict[i];
  }
  std::cin>>m;
  for (int i = 0; i < m; ++i){
    std::cin>>guess[i]>>pattern[i];
  }
  for(int i = 0; i < n; ++i){
    bool ok = true;
    for(int j = 0; j < m; ++j){
      if(!check(dict[i], guess[j], pattern[j])){
        ok = false;
        break;
      }
    }
    if(!ok) continue;
    std::cout<<dict[i];
    break;
  }
  return 0;
}

附注

事实上 using namespace std 并不是必要的，如果代码中无这一行，std里的内容就需要加上std::前缀。这样可以有效防止一些由于重名导致的问题，例如有时候会不小心定义一个max或者pow之类的东西导致标识符冲突，如果去掉这一行那么std里的 max 就需要用 std::max 表示，和自己定义的max不会产生冲突。

下面代码中，std::string 就是 string，以此类推。

std::ios::sync_with_stdio(false) 和 std::cin.tie(0)用于加速cin和cout。