题解：P17060 [NWERC 2022] Last Guess

· · 题解

题意简述

给定若干次 Wordle 猜测及其反馈。构造任意一个与全部反馈一致的隐藏字符串。

解题思路

先分析一次猜测对某个字母 c 的限制。设反馈为 G 或 Y 的 c 共有 q 个。

若猜测还含反馈为 B 的 c，隐藏字符串中 c 的数量恰为 q。否则全部 c 均已匹配，其数量至少为 q。综合所有猜测，得到每个字母的数量下界 l_c 和上界 r_c。

反馈还会限制每个位置。G 表示该位置必须填写对应字母，Y 和 B 均表示该位置不能填写对应字母。

这些条件也是充分的。对某次猜测中的每个字母，G 的位置已经相同，Y 和 B 的位置均不同。若出现 B，字符总数恰好等于 G 和 Y 的数量；否则字符总数不少于猜测中的出现次数。因此按照题目的匹配顺序，必然能逐个复现全部反馈。

将位置与字母建立二分图。源点向每个位置连容量为 1 的边。位置向所有允许填写的字母连容量为 1 的边。每个字母向汇点连下界为 l_c、上界为 r_c 的边。

为保证所有位置都被选择，从汇点向源点连下界、上界均为 n 的边。问题便成为带下界可行流。对于下界 l、上界 r 的边，保留容量 r-l，并记录两端的流量需求。增加超级源汇后跑最大流。题目保证有解，流量为 1 的位置到字母边给出答案。

图中有 O(n) 个点和 O(26n) 条边。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N=535;
const int E=30005;
struct Edge
{
    int v,nxt,w;
}e[E];
int hd[N],cur[N],dep[N],que[N],cnt;
int id[N][26];
bool ban[N][26];
int add(int u,int v,int w)
{
    e[cnt]={v,hd[u],w};
    hd[u]=cnt++;
    e[cnt]={u,hd[v],0};
    hd[v]=cnt++;
    return cnt-2;
}
bool bfs(int s,int t)
{
    fill(dep,dep+N,-1);
    int l=0,r=0;
    que[r++]=s;
    dep[s]=0;
    while(l<r)
    {
        int u=que[l++];
        for(int i=hd[u];i!=-1;i=e[i].nxt)
        {
            int v=e[i].v;
            if(e[i].w&&dep[v]==-1)
            {
                dep[v]=dep[u]+1;
                que[r++]=v;
            }
        }
    }
    return dep[t]!=-1;
}
int dfs(int u,int t,int f)
{
    if(u==t)return f;
    int res=0;
    for(int &i=cur[u];i!=-1&&res<f;i=e[i].nxt)
    {
        int v=e[i].v;
        if(!e[i].w||dep[v]!=dep[u]+1)continue;
        int d=dfs(v,t,min(f-res,e[i].w));
        if(!d)continue;
        e[i].w-=d;
        e[i^1].w+=d;
        res+=d;
    }
    if(!res)dep[u]=-1;
    return res;
}
int dinic(int s,int t)
{
    int ans=0;
    while(bfs(s,t))
    {
        copy(hd,hd+N,cur);
        ans+=dfs(s,t,N);
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int g,n;
    cin>>g>>n;
    int val[N],mn[26]={},mx[26];
    fill(val,val+n,-1);
    fill(mx,mx+26,n);
    for(int i=1;i<g;i++)
    {
        string a,b;
        cin>>a>>b;
        int sum[26]={};
        bool blk[26]={};
        for(int j=0;j<n;j++)
        {
            int c=a[j]-'a';
            if(b[j]=='G')val[j]=c;
            else ban[j][c]=1;
            if(b[j]=='B')blk[c]=1;
            else sum[c]++;
        }
        for(int j=0;j<26;j++)
        {
            mn[j]=max(mn[j],sum[j]);
            if(blk[j])mx[j]=min(mx[j],sum[j]);
        }
    }
    memset(hd,-1,sizeof hd);
    memset(id,-1,sizeof id);
    int s=n+26,t=s+1,ss=t+1,tt=ss+1;
    int d[N]={};
    for(int i=0;i<n;i++)
    {
        add(s,i,1);
        for(int j=0;j<26;j++)
        {
            if((val[i]==-1||val[i]==j)&&!ban[i][j])id[i][j]=add(i,n+j,1);
        }
    }
    for(int i=0;i<26;i++)
    {
        add(n+i,t,mx[i]-mn[i]);
        d[n+i]-=mn[i];
        d[t]+=mn[i];
    }
    d[t]-=n;
    d[s]+=n;
    for(int i=0;i<=t;i++)
    {
        if(d[i]>0)add(ss,i,d[i]);
        else if(d[i]<0)add(i,tt,-d[i]);
    }
    dinic(ss,tt);
    string ans(n,'a');
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<26;j++)if(id[i][j]!=-1&&!e[id[i][j]].w)ans[i]=char('a'+j);
    }
    cout<<ans<<'\n';
    return 0;
}