P7017

035966_L3 · 2024-11-10 23:59:55 · 题解

本题是 CERC 2013 Problem K。

本题在 CodeForces 上有提交通道：Gym 100299K。

感谢 Gcc_Gdb_7_8_1 草拟这一算法的名称。

FBWF（Floyd-Bellman-Warshall-Ford）模板题！

很明显，每个字符矩阵都存在一个最长的字符链。比如：

*.........
*.........
*.........
*.........
*.........
*.........
*.........
*.........
*.........
**********

因此，我们需要找到可能出现的最长字符链，然后构造字符矩阵：

0123456789
123456789A
23456789AB
3456789ABC
456789ABCD
56789ABCDE
6789ABCDEF
789ABCDEFG
89ABCDEFGH
9ABCDEFGHI

由于 20 \times 20 的字符矩阵所需的的最长字符链的长度为 20 \times 2-1=39，而本题中字符链的长度最长为 26-1=25（abc...z），因此字符矩阵一定不会超出 20 \times 20 的限制，除非……存在一个字符环。

这个问题便转化为：给定一张 m=26 个结点的有向图，你需要找出有向图中的任意一个（或任意一条最长路径）。

这一问题可以用 Floyd-Warshall 和 Bellman-Ford 的结合体（Floyd-Bellman-Warshall-Ford，FBWF）解决：设 u_{a,b,c} 表示：

• 是否存在长度为 c 的从 a 到 b 的路径；
• 如果有，那么最后一条边是什么。

按 c 升序转移即可。转移结束后，如果存在任意长度的从某个结点到自己的路径，那么存在环。如果没有，那么可以从 m 开始枚举最长路径的长度。按照上面的办法找到路径的终点（或环上的某一个结点）后，就可以倒着找出整个路径（或环）了。

最终的时间复杂度为 O(Tm^4)，空间复杂度为 O(m^3)。数据中 T \le 111，因此这是可以通过的。

AC Code：

#include <bits/stdc++.h>
using namespace std;
bool s[32][32],o[32];
int u[32][32][32];
char r[52];
int go()
{
    int n;
    cin>>n;
    memset(s,0,sizeof s);
    memset(u,0,sizeof u);
    memset(r,0,sizeof r);
    memset(o,0,sizeof o);
    for(int i=1;i<=n;i++)
    {
        char x,y;
        cin>>x>>y;
        x-=96;
        y-=96;
        s[x][y]=true;
    }
    for(int i=1;i<=27;i++)
        s[i][27]=true;
    for(int i=1;i<=27;i++)
        s[27][i]=true;
    for(int i=1;i<=27;i++)
        u[i][i][0]=-1;
    for(int i=1;i<=27;i++)
        for(int j=1;j<=27;j++)
            for(int k=1;k<=27;k++)
                for(int l=1;l<=27;l++)
                {
                    if(s[j][k]) continue;
                    if(!u[l][j][i-1]) continue;
                    u[l][k][i]=j;
                }
    int c=0,d=0,e=0;
    for(d=1;d<=27;d++)
    {
        for(int i=1;i<=27;i++)
            if(u[i][i][d])
            {
                c=i;
                break;
            }
        if(c) break;
    }
    if(c==0)
    {
        d=27;
        for(d=27;d>=1;d--)
        {
            c=0,e=0;
            for(int i=1;i<=27;i++)
            {
                if(c) break;
                for(int j=1;j<=27;j++)
                if(u[i][j][d])
                {
                    c=i;
                    e=j;
                    break;
                }
            }
            if(c) break;
        }
        r[d+1]=e;
        for(int i=d;i>=1;i--)
        {
            e=u[c][e][i];
            r[i]=e;
        }
        if(d<=1) cout<<'a'<<endl;
        else
        {
            for(int i=1;i<=d/2+1;i++)
            {
                for(int j=1;j<=d/2+1;j++)
                    cout<<(char)(r[i+j-1]+96);
                cout<<endl;
            }
        }
    }
    else
    {
        r[d]=c;
        int p=d;
        for(p=d-1;p>=1;p--)
        {
            c=u[r[d]][c][p+1];
            r[p]=c;
        }
        for(int i=d+1;i<=39;i++)
            r[i]=r[i-d];
        for(int i=1;i<=20;i++)
        {
            for(int j=1;j<=20;j++)
                cout<<(char)(r[i+j-1]+96);
            cout<<endl;
        }
    }
    return 0;
}
int main()
{
    int T;
    cin>>T;
    while(T--) go();
}