标签：那么 log 复杂度 Day5 矩阵枚举 dp

Day 5

模拟赛

T1

设 $dp_{i, j, k, 0/1}$表示走到第 $i, j$ 个格子，前面异或和为 $k$ 的方案数

$0 / 1$ 表示前面的每个路径丢了 $/$ 没丢

转移方程：

$f_{i,j,k,0} = f_{i-1,j,a_{i,j} \oplus k,0} + f_{i,j - 1,a_{i,j} \oplus k,0} + f_{i-1,j,k,1} + f_{i,j-1,k,1}$

$f_{i,j,k,1} = f_{i-1,j,a_{i,j} \oplus k,1} + f_{i,j - 1,a_{i,j} \oplus k,1}$

$O(mna)$

code:

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=gt();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
    return x*f;}
const int p = 998244353;
long long n, m, a[305][305], f[305][305][257][2];
int main()
{
    n = read(), m = read();
    for(int i = 1; i <= n; ++ i)
    {
        for(int j = 1; j <= m; ++ j)
        {
            cin >> a[i][j];
        }
    }
    f[1][1][0][0] = 1;
    f[1][1][a[1][1]][1] = 1;
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= m; ++ j)
            for(int k = 0; k <= 127; ++ k)
            {
                if(i == j && j == 1)continue;
                f[i][j][k][0] = ((f[i - 1][j][a[i][j] ^ k][0] + f[i][j - 1][a[i][j] ^ k][0]) % p+ f[i - 1][j][k][1] + f[i][j - 1][k][1]) % p;
                f[i][j][k][1] = (f[i - 1][j][a[i][j] ^ k][1] + f[i][j - 1][a[i][j] ^ k][1]) % p;
            }
    ll ans  = 0;
    for(int i = 0; i <= 127; ++ i)ans += i * f[n][m][i][0] % p, ans = ans % p;
    cout << ans;
    return 0;
}

T2

考虑将一条合法的路径在 LCA 处计算进答案。可以设 $f_{i,j}$ 表示 $i$子树内一条祖先-儿子链，且祖先 > 儿子，最后一个点是 $j$ 的方案数，$g_{i,j}$ 则是祖先 < 儿子，最后一个点是 $j$ 的方案数。

当 $u$ 合并一颗子树 $v$ 的时候，答案会增加

$ad\sum_{a < b}f_{u,a} \times g_{v, b} + f_{u,b} \times g_{v, a}$

时间复杂度 $O(n^2)$

code

T3

见数位dp

T4

见决策单调性

区间DP

朋友

有 $n$ 个房间，$m$ 个人。第 $i$ 个人能进入第 $[li, ri]$ 个房间。

若最终一个房间里有 $x$ 个人，则这个房间会有 $x$ 的快乐值。

问最大的快乐值是多少。

$n ≤ 300$

可以证明，最优的答案存在一个房间，使得这个房间的人最多，且能到这个房间的人全部来了。

因为对于任何一个最大值，有个人没来，那么这个人到这里来之后一定会使答案增大。

所以设 $f_{i,j}$ 表示只考虑只能到区间 $[i, j]$ 里面的人，最大的快乐值是什么。

枚举最大值在 $k$，那么 $f_{i,j} = \max f_{i,k−1} + f_{k+1,j} + v$

其中 $v$ 表示这里面能到 $k$ 的人。

$v$ 不太好求，正难则反，考虑不能到 $k$ 的人，他们的区间一定在 $[i, k - 1]$ 或 $[k + 1,j]$ 里

减去即可

复杂度 $O(n ^ 2)$

AGC033D

定义一个矩阵的凌乱度是：

如果这个矩阵字符全部相等，那么是 $0$；

否则将这个矩阵切一刀，得到两个矩阵的凌乱度 $(a, b)$，对所有

$\max(a, b) + 1$ 求最小值就是这个矩阵的凌乱度。

现在给定一个 $n \times m$ 的矩阵，求它的凌乱度。

$n, m ≤ 185$

最暴力的 dp：设 $f_{i,j,k,l}$ 表示左上角 $(i, j)$，右下角 $(k, l)$ 的矩阵

的凌乱度，那么转移直接枚举切了哪一刀就行。

时间复杂度 $O(n^5)$ 优化可以做到 $O(n^4)$ 很难通过。

但是可以注意到，$f_{i,j,k,l}$ 会很小：

具体地，若区间长或宽不等于 $1$，则可以将它对半切开

这样的答案即是 $\log n + \log m$

所以上面 $f_{i,j,k,l}$ 的状态有很多其实是浪费（重复）的

因为它们的 dp 值一样。

显然 $i, j, k$ 不变，$f_{i, j, k, l}$ 不随 $l$ 增大减小

所以设 $g_{i, j, k}$ 表示最大的 $l$ 使得 $f_{i, j, k, l} < l$

状态数 $O(n^3logn)$

考虑转移：

若横切，则贪心使上下都尽可能多，

则上面切到 $p = g_{t -1, i, j, k}$ 下面切到 $g_{t-1,i,p+1,k}$

此为横切最小凌乱度

若竖切，则枚举切在 $x$ 右边

则 $g_{t,i,j,k} = \max\min(g_{t-1,i,j,x}, g_{t-1,x+1,j,k})$

但仍无法通过

可以发现，随 $x$ 增大，$g_{t-1,i,j,x}$ 增大， $g_{t-1,x + 1,j,k}$减小

所以找最大的 $x$ 使 $g_{t-1,i,j,x} < g_{t-1,x + 1,j,k}$ 算在 $x$ 还是在 $x + 1$ 右边切更优

利用单调性找 $x$：当 $i, j$ 不变时，若 $k$ 变成 $k+1$

则刚刚找到的 $x，g_{t−1,i,j,x}$ 不变，$g_{t−1,x+1,j,k}$ 可能变大。

所以当 $k$ 变大时，$x$ 也会跟着变大。

双指针，枚举 $k$ 的同时，维护$x$ 即可。

时间复杂度 $O(n^3\log n)$

数位DP

Luogu P9387

给定 $n, m$，设 $x = 1 ⊕ 2 ⊕ · · · ⊕ n − 1 ⊕ n ⊕ m$

求有多少组 $(a, b, c)$，满足 $a + b + c ≤ n$ 或 $a + b + c = m$，

且 $(a + b + c) ⊕ a ⊕ c = x, b > 0，$ 对 $10^9 + 7$ 取模。

（如果 $a + b + c$ 既比 $n$ 小也等于 $m$，那么需要算两次）

$n, m ≤ 10^{18}$，多组数据，每组数据要求复杂度 $O(log n)$。

T3

先不管 $a + b + c = m$，会了 $a + b + c ≤ n$ 自然就能得到

$a + b + c = m$ 的方案数。

可以从低到高进行 dp，设 $f_{i,j,0/1,0/1}$ 表示从低到高 dp 完前 $i$ 位，

向第 $i + 1$ 位进位的个数使 $j，b$ 是否大于 $0$，$a + b + c$ 的低 $i$ 位

是否大于 $n$。转移暴力枚举 $a, b, c$ 的低 $i$ 位是什么就行，最后答

案是 $f_{60,0,1,0}$。

单组时间复杂度 $O(\log n)$。

可以类似上面的题，但由于要算和

所以分别要记 $f_{i,j}$ 表示所有

数确定完低 $i$ 位，且低 $i$ 位的和等于 $m$ 的低 $i$ 位的方案数，

$g_{i,j}$表示所有合法方案中的异或和。

转移的话，$f_{i,j}$ 直接枚举第 $i + 1$ 位有几个 $1$，设为 $x$，

然后只要 $x + j$ 的奇偶性和 $m$ 第 $i + 1$ 位一样就行。

$g_{i,j}$ 有两个部分的贡献：

一个是低于 $i + 1$ 位的贡献，一个是第 $i + 1$ 位的贡献。

分别算即可。即

$g_{i, j} \times \binom{n}{x} + 2 ^ {i + 1} \times \binom{n}{x}$

时间复杂度 $O(n ^ 2\log m)$

决策单调性

T4

首先，假设当我们已经选好了每个点的标准，那么每个人就一定会贪心地去他所能到达的店中标准最高的。

那么，跟刚刚的题一样，仍然可以枚举这个区间的最大值

即设 $f_{i,j}$ 表示只考虑区间 $[i, j]$ 里的人的最大收益

然后枚举标准最高的点 $k$，设能到达 $k$ 的人有 $t$ 个，

那么就是 $f_{i,k}−1 + f_{j,k+1} + g_{k,t}$

其中 $g_{k,t}$ 表示有 $t$ 个人到第 $k$ 家店，合理选择标准能达到的最高收益

那么接下来就是求出所有 $g_{k,t}$。

由于每个人都求这个（过程一样），

于是下面用 $c_i$ 代表标准为 $i$ 的花费，$f_j$ 表示有 $j$ 个人来的最高收益

显然 $f_j = \max i × j − c_i$。

这个是一个标准的斜率优化式子，建出凸包来即可。

但是斜率优化是有限制的，比如这些都是能放在平面直角坐标系

上面的直线（也就是说贡献都可以写成 $kx + b$）的形式。

有一种通用性更高，且理解起来并不比斜率优化复杂的决策单调性优化方法

对于一个 $j$，假设 $i_1 < i_2$，且这个时候选 $i_2$ 比 $i_1$ 更加优秀，

那么对于所有 $k > j$，$i_2$ 都会比 $i_1$ 优秀，那么 $i_1$ 在这之后就没有用了。

按 $i$ 从小到大的顺序加入 $i × j − c_i$ 这条直线。

假设已经处理完了之前的所有直线，那么对于所有可能成为最优选择的

$i_1 < i_2 < · · ·i_k$，一定有 $i_x$ 是 $i_{x−1}$ 后面一些点的最优解。

我们对每个 $i_x$ 记录 $p_x$ 表示对于 $j < p_x$，$i_x$ 比 $i_{x+1}$ 优，

之后则是 $i_{x+1}$ 优，那么显然 $p_1 < p_2 < · · · p_{k−1}$。

否则若 $p_x > p_{x+1}$，那么在 $i_{x+1}$ 比 $i_x$ 优之前，$i_{x+2}$

就已经比 $i_{x+1}$ 优了，所以 $i_{x+1}$ 就不可能成为最优选择了。

那么加入 $i$ 的时候，先算出来 $i$ 比 $i_k$ 什么时候优（因为 $i > i_k$，所以一定有个时间更优）

设为 $y$，那么如果 $x_k−1 > y$，那么根据上面 $p_x$ 单调的解释，

就需要删除 $i_k$，那么这样做就能维护出对于所有 $j$，什么 $i$ 最优。

做完这个之后直接枚举 $ j$，然后双指针不断从前往后扫到最后一个 $p_x < j$ 的 $x$，$i_x+1$ 就是最优的答案。

这样的时间复杂度是线性。于是，整个题时间复杂度 $O(n^3 + nk)$

标签：那么,log,复杂度,Day5,矩阵,枚举,dp
From： https://www.cnblogs.com/qinzh/p/17588659.html

Day5