2020校队预选赛A-字符矩阵-题解

关于本次比赛

首先道个歉，卡掉了时空复杂度为 $n^3$ 的 $dp$ 做法确实是不应该，零基础的话能自学到掌握基本 $dp$ 的程度应该是很优秀的水平了。

而本次组题问题也很多，包括没有一个总的命题人来把握整体难度 和 “祖安” 一题出现意料外的解法(正则表达式)等。再次对我们命题工作的不当导致大家不好的比赛体验道个歉。

但每个题所涉及的知识点多为算法竞赛中实用的算法或技巧，数据也经过多次验证，欢迎大家赛后补题。

题目来源

Div.1 #517 B 的简化版本

题解

回到本题，题目大意为给你一个 $n*n$ 大小的矩阵，每个位置上有一个小写字母，从 $(1,1)$ 开始每次向右或向下移动到达 $(n,n)$ 并按顺序取走路径上的字符来形成一个字符串，请你求出其中字典序最小的解。

O(n^3)

考虑使用动态规划，$f[i][j]$ 表示从 $(1,1)$ 出发到 $(i,j)$ 所能形成的字典序最小的字符串，转移方程为:

$$f[i][j] = min(f[i-1][j],f[i][j-1]) + s[i][j];$$

其中 $s[i][j]$ 表示矩阵 $(i,j)$ 位置的字符，$”+”$ 表示字符串的拼接。

这个 $dp$ 看起来状态只有 $n^2$，但转移实际上是 $O(n)$ 的，因为字符串字典序的比较(包括std::string)是 $O(n)$ 的，因此总体时间复杂度为 $O(n^3)$，$n=2000$ 时计算次数约为 $8e9$，而较快的评测机大概 5s 可以跑 $1e9$，无法通过本题，而且空间复杂度也为 $O(n^3)$，交上去会 $MLE$。

int n;
string f[MAXN][MAXN];
char s[MAXN][MAXN];
int work()
{
    scanf("%d",&n);
    fp(i,1,n)scanf("%s",s[i]+1);
    f[1][1]=s[1][1];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i!=1||j!=1)
            {
                if(i==1)f[i][j]=f[i][j-1];
                else if(j==1)f[i][j]=f[i-1][j];
                else f[i][j]=min(f[i-1][j],f[i][j-1]);
                f[i][j].pb(s[i][j]);
            }
        }
    }
    printf("%s",f[n][n].c_str());
    return 0;
}

O(n^2)

考虑一个朴素的贪心算法，由于字典序比较的特殊性，我们需要让靠前的字母尽量的小，因此从 $(1,1)$ 出发每次选择较小的字符进行转移。

但考虑

bba
bbb
bbb

的情况，我们无法确定从 $(1,1)$ 开始下一步应该转移到哪里，如果使用 $dfs$ 的话复杂度也是 $n!$ 级别。

但实际上对于这种无法确定的转移一定是在同一对角线上的(对应的字符串长度相同)，我们可以去重后全部保留，这种转移数总级别是 $O(n^2)$ 级别的，考虑到扩展一个字符是 $O(1)$的，因此我们可以得到一个 $O(n^2)$ 的算法：

顺序考虑字符串第 $i$ 位的字符 $(1<=i<=2*n-1)$:

1. 建立一个待扩展队列，初始时只有 (1,1)
2. 查找待扩展队列中最小的字符，记 c，同时为答案末尾添加上 c
3. 保留队列中 s[i][j]==c 的 (i,j)
4. 对于保留下来的 (i,j)，添加 (i+1,j) 和 (i,j+1) 到新扩展队列中
5. 将旧扩展队列替换为新扩展队列
6. 若没到达 (n,n) 从第二步开始重复

实际写法类似于 $bfs$，时空复杂度均为 $O(n^2)$ 可以通过本题。

int n;
vector<pr> v,t;
string ans;
char s[MAXN][MAXN];
bool vis[MAXN][MAXN];
int main()
{
    cin >> n;
    fp(i,1,n)fp(j,1,n)cin >> s[i][j];
    ans.clear(),v.clear(),t.clear(),t.push_back({1,1}),vis[1][1]=1;
    while(1)
    {
        char c='z'+1;
        for(auto p:t)c=min(s[p.fi][p.se],c);
        ans.push_back(c);
        if(t.front().fi==n&&t.front().se==n)break;
        v.clear();
        for(auto p:t)if(s[p.fi][p.se]==c)
        {
            if(p.fi!=n&&!vis[p.fi+1][p.se])
                v.push_back({p.fi+1,p.se}),
                vis[p.fi+1][p.se]=1;
            if(p.se!=n&&!vis[p.fi][p.se+1])
                v.push_back({p.fi,p.se+1}),
                vis[p.fi][p.se+1]=1;
        }
        swap(v,t);
    }
    cout << ans << endl;
    return 0;
}