2020-2021:teams:legal_string:lgwza:序列自动机
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:legal_string:lgwza:序列自动机 [2020/10/06 14:27] lgwza 创建 |
2020-2021:teams:legal_string:lgwza:序列自动机 [2020/10/06 14:28] (当前版本) lgwza |
||
|---|---|---|---|
| 行 72: | 行 72: | ||
| else puts("NO"); | else puts("NO"); | ||
| } | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | [[https://ac.nowcoder.com/acm/contest/7831/D|2020牛客国庆集训派对day4 D Shortest Common Non-Subsequence]] | ||
| + | |||
| + | **题意**：求两个字符串最短的公共的非子序列，即该序列既不是 $A$ 的子序列也不是 $B$ 的子序列。 | ||
| + | |||
| + | **题解**：考虑填答案DP。设输入字符串分别为 $s$，$t$，答案为 $q$。 | ||
| + | |||
| + | 对于最后的答案, 由于它是最短的, 所以把他删掉最后一位之后, 它**或者**是 $s$ 的子序列, **或者** 是 $t$ 的子序列. 从空的答案开始. | ||
| + | |||
| + | 如果 $q$ 的第一个位置是 $0$。那么就会匹配到 $s$ 的第一个 $0$ 和 $t$ 的第一个 $0$。 | ||
| + | |||
| + | 否则 $q$ 的第一个位置是 $1$。那么就会匹配到 $s$ 的第一个 $1$ 和 $t$ 的第一个 $1$。 | ||
| + | |||
| + | 然后考虑第二个位置，如果是 $0$，那么就会匹配到下一个 $0$。 | ||
| + | |||
| + | 这样一直匹配下去。直到最后匹配到 $s$ 的末尾的后一位，$t$ 的末尾的后一位，这时候的 $q$ 是 $s$，$t$ 的公共非子序列。 | ||
| + | |||
| + | 这题还要一个最小字典序。DP 的时候从后往前遍历。$dp[len(s)+1][len(t)+1]=0$。最后答案即为 $dp[0][0]$。 | ||
| + | |||
| + | **代码**： | ||
| + | |||
| + | <hidden> | ||
| + | <code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | const int N=4005; | ||
| + | char a[N],b[N]; | ||
| + | int nxta[N][2],nxtb[N][2]; | ||
| + | int dp[N][N],f[N][N]; | ||
| + | int lena,lenb; | ||
| + | vector<int>ans; | ||
| + | int dfs(int x,int y){ | ||
| + | if(x==lena+1&&y==lenb+1) return 0; | ||
| + | if(dp[x][y]) return dp[x][y]; | ||
| + | int tmp1=dfs(nxta[x][0],nxtb[y][0]); | ||
| + | int tmp2=dfs(nxta[x][1],nxtb[y][1]); | ||
| + | if(tmp1<=tmp2) f[x][y]=0; | ||
| + | else f[x][y]=1; | ||
| + | return dp[x][y]=min(tmp1,tmp2)+1; | ||
| + | } | ||
| + | void getans(int x,int y){ | ||
| + | if(x==lena+1&&y==lenb+1) return; | ||
| + | ans.push_back(f[x][y]); | ||
| + | getans(nxta[x][f[x][y]],nxtb[y][f[x][y]]); | ||
| + | } | ||
| + | int main(){ | ||
| + | scanf("%s%s",a+1,b+1); | ||
| + | lena=strlen(a+1); | ||
| + | lenb=strlen(b+1); | ||
| + | nxta[lena+1][0]=nxta[lena+1][1]=lena+1; | ||
| + | nxtb[lenb+1][0]=nxtb[lenb+1][1]=lenb+1; | ||
| + | for(int i=lena;i>=0;i--){ | ||
| + | nxta[i][0]=nxta[i+1][0]; | ||
| + | nxta[i][1]=nxta[i+1][1]; | ||
| + | if(a[i+1]=='0') nxta[i][0]=i+1; | ||
| + | else nxta[i][1]=i+1; | ||
| + | } | ||
| + | for(int i=lenb;i>=0;i--){ | ||
| + | nxtb[i][0]=nxtb[i+1][0]; | ||
| + | nxtb[i][1]=nxtb[i+1][1]; | ||
| + | if(b[i+1]=='0') nxtb[i][0]=i+1; | ||
| + | else nxtb[i][1]=i+1; | ||
| + | } | ||
| + | dfs(0,0); | ||
| + | getans(0,0); | ||
| + | for(int i=0;i<ans.size();i++) printf("%d",ans[i]); | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/lgwza/序列自动机.1601965657.txt.gz · 最后更改: 2020/10/06 14:27 由 lgwza
