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;
}