2022“杭电杯” 中国大学生算法设计超级联赛（5）6 7 题解

1006-BBQ

题目大意：
给定一个字符串，每次操作可以删除或是插入一个字符，要求操作若干次后字符串从头开始，每四个一组，每组都符合"abba"的形式，问最少操作几次。

思路：
区间dp，dp[i]表示使区间[1,i]成为合法区间所需的最少操作次数。
转移的方程为
dp[i+k] = dp[i] + cal(i+1, i+k) k=[1,7]
向后转移的时候最多只要枚举长度为7的区间即可，因为将长度为8以上的区间变成合法区间的代价一定会大于长度在7以下的区间。
那么现在的问题就是如何计算区间[i+1, i+k]的代价了。
可以发现对于一个长度为4的区间，abcd和efgh是等价的，二者变成合法区间的代价相同。
那么我们可以对一个子区间进行编码，最大长度为7，因此最多出现7种字符加上空字符一共8种。采用8进制，字母出现的顺序从小到达编码。
接下来就是预处理各种区间编码合法化的代价了。
因为编码种类不多，直接暴力+二维dp求解即可：
枚举每一种编码，枚举每一种合法区间的编码，计算将当前编码转化成合法编码的代价。

AC代码：

#include 
const int N = 1e6 + 10;
using namespace std;

int t[10];   // 当前序列
int g[8][5]; // g[i][j]表示当前序列的前i个转化成合法序列的前j个所需的最小操作数
int w[N];    // 合法化代价
int dp[N];
char s[N];
void dfs(int n, int c) //区间长度为n,最大编码为c
{
    int m;
    if (n)
    {
        m = n; //全部删除的代价
        for (int a = 1; a <= 7; a++)
        {
            for (int b = 1; b <= 7; b++)
            {
                int p[5] = {0, a, b, b, a}; //合法序列
                memset(g, 0x3f, sizeof(g));
                for (int i = 0; i <= 4; i++)
                    g[0][i] = i;
                for (int i = 0; i <= 7; i++)
                    g[i][0] = i;
                for (int i = 1; i <= n; i++)
                    for (int j = 1; j <= 4; j++)
                        g[i][j] = min({g[i - 1][j] + 1, g[i][j - 1] + 1, g[i - 1][j - 1] + (t[i] != p[j])});
                //转移的两种情况:
                // 1、t[i]!=p[j]，从(i+1,j)的情况中删去一个字符或是从(i-1,j)的情况中插入一个字符，代价为1
                // 2、t[i]==p[j]，代价为0
                if (g[n][4] < m) m = g[n][4];
            }
        }
    }
    if (n)
    {
        int idx = 0;
        for (int i = 1; i <= n; i++)
            idx = idx * 8 + t[i];
        w[idx] = m;
    }
    if (n == 7) return;
    n++;
    for (int i = 1; i <= c + 1; i++)
    {
        t[n] = i;
        dfs(n, c + 1);
    }
}

void solve()
{
    cin >> s + 1;
    int n = strlen(s + 1), vis[130], idx, num;
    for (int i = 1; i <= n; i++)
        dp[i] = 1e9;
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < n; i++)
    {
        idx = num = 0;
        for (int j = 1; j <= 7; j++)
        {
            if (!vis[s[i + j]]) vis[s[i + j]] = ++idx; // vis数组记录每个字符出现的顺序
            num = num * 8 + vis[s[i + j]];
            dp[i + j] = min(dp[i + j], dp[i] + w[num]);
        }
        for (int j = 1; j <= 7; j++) //将vis数组还原
            vis[s[i + j]] = 0;
    }
    cout << dp[n] << endl;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    dfs(0, 0);
    int T;
    cin >> T;
    while (T--)
        solve();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

1007-Count Set

题目大意：
给定一个序列p，从中选出k个数作为序列T，要求对于任意x∈序列T，p_x != x。
求出序列T的构造方案数。

思路：
序列p可以处理成若干个有向环（如果环的大小为1，那就忽略，这个数肯定不能选）。
问题就变成了从这些环中选择k个数，且这k个数在环中不相邻。
当时想到了这一步，但是卡在了怎么算不相邻的组合数，下面是题解给的一种算法：
对于长度为m的普通序列，记选出的数为长度为2的段（保证了不相邻），不选的数为长度为1的段，从中选出k个数的方案就是C(k, m-k)，相当于从m-k个段里选k个段使得长度为2。
对于环来说，只要选择一处断开即可成为普通的序列。
对断开处进行讨论：

• 如果断开处恰好是长度为2的段，那么方案数为C(k-1, m-k-1)，因为确定了断开处为长度为2的段，所以问题变成从m-2的序列中选k-1个数。
• 如果断开处不是长度为2的段，那么和普通的序列相同，C(k, m-k)。

断开处是否为长度为2的段决定了两种分类不存在重复的情况。

那么在一个长度为m的环中选出k个数的方案就是：C(k-1, m-k-1) + C(k, m-k)。

然后列出每个环的生成函数，用分治NTT合并即可。

AC代码：

#include 
const int N = 1e6 + 5;
const long long mod = 998244353;
using namespace std;

int n, k, p[N], sz[N];
bool vis[N];

namespace poly
{
    typedef long long ll;
    const ll G = 3, Gi = 332748118;
    ll fac[N], facinv[N];
    int RR[N];
    ll ksm(ll base, ll power) //快速幂
    {
        ll result = 1;
        base %= mod;
        while (power)
        {
            if (power & 1)
                result = (result * base) % mod;
            power >>= 1;
            base = (base * base) % mod;
        }
        return result;
    }

    void getinv(int n) //线性求阶乘和阶乘逆元
    {
        fac[0] = facinv[0] = 1;
        for (int i = 1; i <= n; i++)
            fac[i] = fac[i - 1] * i % mod;
        facinv[n] = ksm(fac[n], mod - 2);
        for (int i = n - 1; i >= 1; i--)
            facinv[i] = facinv[i + 1] * (i + 1) % mod;
    }

    ll calc(int a, int b) //组合数,从a个里面选b个
    {
        if (a < b) return 0;
        if (b == 0 || a == b) return 1;
        return fac[a] * facinv[b] % mod * facinv[a - b] % mod;
    }

    ll inv(ll x) { return ksm(x, mod - 2); } //求逆元

    int limit, L;

    void NTT(vector<ll> &A, int type)
    {
        for (int i = 0; i < limit; ++i)
            if (i < RR[i])
                swap(A[i], A[RR[i]]);
        for (int mid = 1; mid < limit; mid <<= 1)
        {
            ll wn = ksm(G, (mod - 1) / (mid * 2));
            if (type == -1) wn = ksm(wn, mod - 2);
            for (int len = mid << 1, pos = 0; pos < limit; pos += len)
            {
                ll w = 1;
                for (int k = 0; k < mid; ++k, w = (w * wn) % mod)
                {
                    int x = A[pos + k], y = w * A[pos + mid + k] % mod;
                    A[pos + k] = (x + y) % mod;
                    A[pos + k + mid] = (x - y + mod) % mod;
                }
            }
        }

        if (type == -1)
        {
            ll limit_inv = inv(limit);
            for (int i = 0; i < limit; ++i)
                A[i] = (A[i] * limit_inv) % mod;
        }
    }
    //多项式乘法
    void poly_mul(vector<ll> &a, vector<ll> &b, int tot)
    {
        a.resize(tot * 2);
        b.resize(tot * 2);
        for (limit = 1, L = 0; limit <= tot; limit <<= 1)
            L++;
        for (int i = 0; i < limit; ++i)
        {
            RR[i] = (RR[i >> 1] >> 1) | ((i & 1) << (L - 1));
        }
        NTT(a, 1);
        NTT(b, 1);
        for (int i = 0; i < limit; ++i)
            a[i] = a[i] * b[i] % mod;
        NTT(a, -1);
    }

    vector<ll> cal(int l, int r) //分治NTT
    {

        if (l == r)
        {
            vector<ll> res;
            res.resize(sz[l] / 2 + 1);
            res[0] = 1;
            for (int i = 1; i <= sz[l] / 2; i++) //生成函数构造
                res[i] = (calc(sz[l] - i, i) + calc(sz[l] - i - 1, i - 1)) % mod;
            return res;
        }
        else
        {
            int mid = (l + r) / 2, len;
            vector<ll> lp = cal(l, mid);
            vector<ll> rp = cal(mid + 1, r);
            len = lp.size() + rp.size();
            poly_mul(lp, rp, lp.size() + rp.size());
            if (lp.size() > k + 1)
                lp.resize(k + 1);
            else
                lp.resize(len - 1);
            return lp;
        }
    }
}
using poly::cal;

void solve()
{
    int cnt = 0;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i];
        vis[i] = 0;
    }
    if (k == 0)
        cout << "1" << endl;
    else
    {
        for (int i = 1; i <= n; i++)
        {
            if (vis[i]) continue;
            vis[i] = 1;
            int it = p[i];
            if (p[it] != it)
            {
                sz[++cnt] = 1;
                while (!vis[it])
                {
                    vis[it] = 1;
                    sz[cnt]++;
                    it = p[it];
                }
            }
        }
        if (cnt == 0)
            cout << "0" << endl;
        else
            cout << cal(1, cnt)[k] << endl;
    }
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    poly::getinv(N - 1);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170