2022年中国大学生程序设计竞赛女生专场 - I. 宠物对战

Solost

2023 年 04 月 20 日

177 次浏览

暂无评论

2052字数

题目题解

## 题目

![image(1).png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F04%2F20%2Fimage%281%29.png)

## 题目链接

[链接](https://codeforces.com/gym/104081/problem/I)

## 题目大意

给你两个序列a,b每个序列中都有一些字符串，再给一个目标串s，问你这个s是否能由ababab或者babab类似这种形式组成，a表示a序列里面的字符串，b表示b里面的字符串。

## 题解

这个题目刚开始想直接凑就行，但是写的过程中想到一个问题，如果s中有一段从a和b都可以凑出来，但是凑出来的长度不一样，那么就可能导致不一样的结果，`s = abcd~~~~~~`， `a = abcd; b = abc`这种情况，如果从a中选第一个符合的情况那么可能导致后面没办法匹配。后来想的是宽搜，然后超时，优化了一点超空间。所以这道题不能用暴力来写。看了眼题解。正解是dp+trie树。

转移方程`f[i][op] = min(f[i][op], f[j - 1][!op]`代表含义是目标串s的第i个字符，是否可由op的相反面转移而来，`j是指从i到1这一段，是否在a或者b取决于当前op存在一个串能匹配j-i这一段目标串`。

难点是如何快速的求出是否存在这样的一个字串能够使得转移到当前状态`f[i][op]`,然后就可以用到trie树了。为了在检查的时候好检查，我们可以把a类和b类建一个二维trie树，然后来计算，存的时候反着存。检查的时候就可以从i,i-1,i-2，方便状态转移方程的书写。

代码：

```cpp
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 5e5 + 10;

int n, m;
int f[N][2];
int tr[26][N][2], cnt[N][2], idx[2];

void insert(string &s, int op)
{
    int p = 0;
    for (int i = 0; i < s.size(); i++) {
        int u = s[i] - 'a';
        if (!tr[u][p][op])
            tr[u][p][op] = ++idx[op];
        p = tr[u][p][op];
    }
    cnt[p][op]++;
}

void solve()
{
    cin >> n;
    string x;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        reverse(x.begin(), x.end());
        insert(x, 0);
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> x;
        reverse(x.begin(), x.end());
        insert(x, 1);
    }
    string s;
    cin >> s;
    int l = s.size();
    s = " " + s;
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    f[0][1] = 0;
    for (int i = 1; i <= l; i++) {
        for (int op = 0; op < 2; op++) {
            int p = 0;
            for (int j = i; j; j--) {
                int u = s[j] - 'a';
                if (!tr[u][p][!op])
                    break;
                p = tr[u][p][!op];
                if (cnt[p][!op])
                    f[i][op] = min(f[i][op], f[j - 1][!op] + 1);
            }
        }
    }
    int ans = min(f[l][0], f[l][1]);
    if (ans == INF)
        cout << -1 << endl;
    else
        cout << ans << endl;
}
int main()
{
    // IOS;
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 04 月 20 日