状态转移习题

发表于 更新于 分类于 ， 阅读次数： Waline： 本文字数： 2.8k 阅读时长 ≈ 10 分钟

题意：

给你一个数组[𝑝1,𝑝2,…,𝑝𝑛] ，其中所有元素都是不同的。

你可以对它执行几个(可能是零)操作。在一个操作中，你可以从 p 中选择一个连续的子段，然后从该子段中删除所有元素，除该子段中最小的元素。例如，如果选择p = [3, 1, 4, 7, 5, 2, 6]，并选择从，并选择从3元素到−𝑟𝑑元素到6元素的子段，那么得到的数组就是−𝑡ℎ元素的子段，那么得到的数组就是[3, 1, 2, 6]。

如果数组 a可以从可以从p中通过上述几种也许是零种操作得到，那么这个数组中通过上述几种(也许是零种)操作得到，那么这个数组a 就叫做可达数组。计算可达数组的个数，并打印出它的模数 998244353。

题解：

根据题目答案数据范围，很容易想到通过区间修改暴力答案是不可行的。于是转向dp想法，一个简单的构型是，对于每个i结尾的结果数组计算贡献值。思考状态转移，需要计算如何在保留 𝑎𝑖 的情况下的贡献值。

考虑操作对于保留最小值的设定，该操作具有结合律，可以想到， 𝑎𝑖 是后缀操作区间（如进行[n-1,n],[n-3.n-2]的操作等同于操作后缀[n-3,n]）最小值一定成立。则状态转移为其中dp(i)+=dp(j)(其中a[j]<a[i])另外一种情况则是，不对i进行操作。考虑上一个比a[i]小的数为\(l*{a_i}\)下标为，则小于且大于下标为j，则小于j且大于l{aj}的下标的下标均无法转移至，显然的下标k的下标idx均无法转移至i，显然l{ai}是无法通过操作区间中比它大的数移除的，这是可以推广的，即对任意下标小于的下标如果其不等于是无法通过操作区间中比它大的数移除的，这是可以推广的，即对任意下标小于j的下标x如果其不等于\(l*{a_x}\)则无法转移到i。

总结状态转移为\(f*i = \sum*{k={l*{a_i}+1}}^{i-1} f_k + \sum*{k=l^x(l*{a_i})}^{k>0}f*{k}\)

前缀和处理即可。

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
	void slove(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];

    s[top] = {-1,-1};
    for(int i = 1;i <= n;i++) {
        while(top && s[top].x > a[i]) top--;
        l[i] = s[top].y;
        s[++top] = {a[i],i};
    }

    // for(int i=1;i<=n;i++) cout<<l[i]<<' ';
    // cout<<endl;

    for(int i=0;i<=n;i++) pre1[i] = pre2[i] = 0;

    f[0] = 1;
    pre1[0] = 1;
    for(int i=1;i<=n;i++) {
        if(l[i]!=-1) pre2[i] = pre2[l[i]] + f[l[i]] % MOD;
        int t = l[i] == -1 ? 0: pre1[l[i]];
        f[i] = (pre1[i-1] - t) % MOD ;
        // cout<<(pre1[i-1] - t)<<' ';
        f[i] += pre2[i];

        pre1[i] = pre1[i-1] + f[i] % MOD;
        // cout<<i<<' '<<pre1[i]<<' '<<pre2[i]<<' '<<f[i]<<nline;
    }

    int mi = 1e18,ans = 0;
    for(int i=n; i>=1; i--) {
        mi = min(mi,a[i]);
        if(mi==a[i]) {
            ans = (ans + f[i]) % MOD;
        }
    }
    cout<<ans<<endl;
}

题意：

给你一个整数数组 1, 2,…, ，它的所有元素都是不同的。

首先，要求你在数组中再插入一个整数 an+1 。 an +1 不应等于 a1, a2,…, an中的任何一个。

然后，你必须使数组中的所有元素相等。一开始，你选择一个正整数 x。在一次操作中，你将 x 恰好加到数组的一个元素上。注意， x 在所有操作中都是一样的。

选择 +1 和 x 后，使所有元素相等的最小操作次数是多少？

题解：

容易误解的点在于——对一个新增的数x，能否找到 ∑𝑖=1𝑖=𝑛𝑥−𝑎𝑖(𝑥−𝑎𝑖) 小于 ∑𝑖=1𝑖=𝑛𝑚𝑥−𝑎𝑖(𝑚𝑥−𝑎𝑖) （mx表示数组中的最大值）由于笔者太拉昆了，暂时先不证明了。。。

可以凭直觉猜出一个解法，最大的数不变𝑎𝑛𝑠=∑𝑑𝑖𝑓(𝑚𝑥,𝑎[𝑖])(𝑑𝑖𝑓(𝑚𝑥,𝑎[𝑖]))+𝑎𝑑𝑑𝑡𝑖𝑜𝑛其中addtion为以最大公倍数为步减的最大值(𝑚𝑥−𝑎𝑛+1)/(𝑑𝑖𝑓(𝑚𝑥,𝑎[𝑖]))。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void slove(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    int mx = -INF;
    for(int i=1;i<=n;i++) {
        mx = max(mx,a[i]);
    }

    for(int i=1;i<=n;i++) d[i] = mx - a[i];

    int gd = 0;
    for(int i=1;i<=n;i++) gd = __gcd(d[i],gd);

    if(!gd) {cout<<1<<endl;return ;}

    ll sum = 0;
    set<int> S;
    for(int i=1;i<=n;i++) sum += (mx - a[i]) / gd,S.insert((mx - a[i]) / gd);
    int t = 1;
    while(1) if(S.count(t)) t++;else break;
    cout<<sum + t<<endl;
}

题意：

对一个数组的所有非空子区间，计算这个公式\[w = \sum_{i=l}^{i=r} \sum_{j=l}^{j=r}a_i \oplus a_j \]的和。

题解：

非常经典的题目，看见了就再巩固一下。

  1. 拆位， 对于异或这个操作来看，是以位为单位进行的（而且根据数据范围也很容易想到）。我们需要对位进行处理。 即将整个数组拆分为\(\lceil log_2mx\rceil\)个数组。计算每一位的贡献。

当拆位后原式子会变为这样的 \[ allW = \sum_{l=1}^{l=r}\sum_{r=l}^{r=n}\sum_{i=l}^{i=r}\sum_{x=0}^{x=\lceil log_2mx\rceil}cnt(a_{i-x} != a_{x}) \] 这个复杂度仍然是爆炸的，因此需要继续优化

很容易想到的一个优化就是，对于\[a_i \oplus a_j\]他是满足交换律的，即\[a_i \oplus a_j = a_j \oplus a_i\]因此我们仅需要计算单边值即可（然后乘2。

因此将原有的式子改写\[w =2 \times (\sum_{i=l}^{i=r} \sum_{j=l}^{j=i}a_i \oplus a_j) \]虽然对于\[a_i\]本身来说，他仍是对自身算一次的，但异或一定为0，因此不考虑。

再转头考虑所有子区间的问题，一个数组的所有子区间显然是\[n^2\]级，因此枚举或计算子区间都是无意义的。根据之前的推论，使用经典方法，确定右端点，变化左端点。考虑对每个左右端点i,j计算当前包含的区间数为\[i\times (n-j+1)\]（下标从1开始），则对任意i,j，其贡献值为以下公式 \[ w(bt,{i,j}) = (i\times (n-j+1) * (1<<bt) * (bit(x,a_i)\not=bit(x,a_j)) \] 施展数学的神奇魔法！

提取公因子，我们便会惊奇的发现，整个问题变成了对于以j结尾的子区间计算\[a_j\] 与\[a_i|i<j\]的在x位上的贡献值。此时静下心来思考维护的数据则是，当前位为0的下标之和与为1的下标之和。

最后，让我们总结一下，其实很多做法很常见，比如枚举右端点，比如交换律，比如提取公因子，可以说这是基本。总的来讲，这个题就仅仅考了拆位而已，符合小白赛难度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void slove(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    ll ans = 0;
    for(int bt = 0;bt <=29;bt++) {
        ll s1=0,s2 =0;
        for(int i=1;i<=n;i++) {
            if(a[i] >>bt&1) {
                ans = (ans + s2 * (n-i+1) % MOD * (1<<bt) % MOD) % MOD;
                s1 += i;
                s1 %= MOD;
            }
            else {
                ans = (ans + s1 * (n-i+1) % MOD * (1<<bt) % MOD) % MOD;
                s2 += i;
                s2 %= MOD;
            }
        }
    }
    cout<<(2ll * ans)%MOD<<endl;
}

不知不觉已经写了这么多，这题上次见还是许久之前，没想到再见已有这么长时日了，我居然看了这么久，mark。。。

题意：

给定m条线段，求将1-n覆盖两次的所有方案数

题解：

离散数据之后，直接设计dp即可。首先应该注意到对端点进行离散化，然后为简化思考量，我们将整体线段二键值排序。可以观察到，如果出现了悬空（并不前缀）的二次覆盖，如(1-4,2-5)，出现1未二次覆盖，而2覆盖的情况是必然非法的。因为二键值排序使得1永远也不会被覆盖了。因此很容易想到对一次覆盖，二次覆盖的前缀状态做dp。

个人认为dp最好的老师是暴力，因此本篇将会贴出tle的暴力解法。

状态表示这样设计：\[dpi,j,k\]表示对前i段线段，覆盖两次最长前缀长度j，覆盖一次最长浅醉长度k的所有方案数。

之后可以根据segs[i].x 是否小于两个前缀长度做转移了。暴力转移code如下

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
void slove(){
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        cin>>segs[i].x>>segs[i].y;
        poss.push_back(segs[i].x);
        poss.push_back(segs[i].y);
    }
    poss.push_back(0);
    poss.push_back(n);
    sort(all(poss));
    poss.erase(unique(all(poss)),poss.end());

    for(int i=0;i<poss.size();i++) mp[poss[i]] = i;

    sort(segs+1,segs+1+m);

    dp[0][0][0] = 1;
    for(int i=1;i<=m;i++) {
        for(int ii=0;ii<i;ii++) {
            for(int j=200;j;j--) {
                for(int k = 200;k;k--)
                    dp[i][j][k] = dp[ii][j][k];
            }
            for(int j=200;~j;j--) {
                for(int k = 200;~k;k--) {
                    if(mp[segs[i].x] <= j+1) {
                        if(mp[segs[i].x] > k+1) {
                            dp[i][max(mp[segs[i].y], j)][k] =
                                (dp[i][max(mp[segs[i].y],j)][k] + dp[ii][j][k]) % MOD;
                            // if(dp[i][max(mp[segs[i].y], j)][k]&&dp[ii][j][k]) {
                            //     cout<<ii<<' '<<j<<' '<<k<<endl;
                            //     cout<<"!"<<i<<' '<<max(mp[segs[i].y], j)<<' '<<k<<' '<<dp[i][max(mp[segs[i].y], j)][k]<<nline;
                            // }
                        }
                        else {
                            dp[i][max(mp[segs[i].y], j)][max(k,min(j,mp[segs[i].y]))] =
                                (dp[i][max(mp[segs[i].y], j)][max(k,min(j,mp[segs[i].y]))] + dp[ii][j][k]) % MOD;
                            // if(dp[i][max(mp[segs[i].y], j)][max(k,min(j,mp[segs[i].y]))]&&dp[ii][j][k]) {
                            //     cout<<ii<<' '<<j<<' '<<k<<endl;
                            //     cout<<"?"<<i<<' '<<max(mp[segs[i].y], j)<<' '<<max(k,min(j,mp[segs[i].y]))<<' '<<
                            //         dp[i][max(mp[segs[i].y], j)][max(k,min(j,mp[segs[i].y]))]<<nline;
                            // }
                        }
                    }
                }
            }
        }
    }

    cout<<dp[m][mp[n]][mp[n]]<<endl;
}

这段代码中显然有一个很严重的问题：时间复杂度为\[1.6e^{9}\]略微有点超出复杂度

其次，对于转移中直接用hax过的值判断是否能够转移是错误的，因为单单hax过后的左端点==右端点+1是不能证明两个区间可以合并的（如：1-3,5-6）hax过后为（1-2,3-4）显然，哈希后合并而实际并不合并。简单！我们只需要存储左端点减1即可。

时间如何优化？

首先注意到，（经典的错误）我们每次都需要从前面的每一个i进行转移，我们更改状态的表示，使得，最后的代表前面所有方案数，即在枚举j，k时f[i][j][k] += f[i - 1][j][k];于是时间复杂度完成。再根据官方题解的优化掉只转移覆盖一次的状态（显然二键值排序后导致这种情况必然不存在方案数）。于是复杂的暴力代码变成了下面的形状。

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
void slove(){
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        cin>>segs[i].x>>segs[i].y;
        segs[i].x--;
        poss.push_back(segs[i].x);
        poss.push_back(segs[i].y);
    }
    poss.push_back(0);
    poss.push_back(n);
    sort(all(poss));
    poss.erase(unique(all(poss)),poss.end());

    for(int i=0;i<poss.size();i++) mp[poss[i]] = i;

    sort(segs+1,segs+1+m);

    for(int i=1;i<=m;i++) {
        segs[i].x = mp[segs[i].x];
        segs[i].y = mp[segs[i].y];
    }

    f[0][0][0] = 1;
    for (int k = 1; k <= m; k++) {
        for (int i = 0; i <= mp[n]; i++) {
            for (int j = i; j <= mp[n]; j++) {
                if (f[k - 1][i][j] == 0) {
                    continue;
                }
                f[k][i][j] += f[k - 1][i][j];
                f[k][i][j] %=MOD;
                if (segs[k].x <= i) {
                    f[k][max(i, min(j, segs[k].y))][max(j, segs[k].y)]+=f[k - 1][i][j];
                    f[k][max(i, min(j, segs[k].y))][max(j, segs[k].y)]%=MOD;
                }
            }
        }
    }

    cout<<f[m][mp[n]][mp[n]]% MOD<<endl;
}