日记

今天也是不用考试，也是可以补题。

上午#

补状压dp。

P10975 Mondriaan’s Dream solution#

我不是就在写题解吗，那我还加 solution 链接干什么
设 $dp_{i,j}$ 表示前 $i - 1$ 行都被填满了且 $i - 1$ 行突出到 $i$ 行的方案数。然后我们可以预处理每个状态 $j$ 可以由那些状态转移而来，设转移状态的集合为 $a_j$ ，那么有：

初始化 $dp_{1,0} = 0$ 我们就可以得到答案为 $dp_{h + 1,2 ^ w - 1}$

P2831 [NOIP2016 提高组] 愤怒的小鸟 solution#

设 $dp_i$ 表示死猪状态为 $i$ 时的最少消耗。那么有朴素的转移：枚举两个点 $i,j$ ，与原点确定抛物线，然后再枚举一个点 $k$ ，看 $k$ 是否再之前所确定的那条抛物线上。时间复杂度 $O(T \times n^3 \times 2^n)$ 。总共要算 $18^3 \times 2^{18} \approx 1.5 \times 10^{10}$ 次，绝对要T。
我们考虑怎么优化。预处理 $vis_{i,j}$ 表示原点与 $i$ 点和 $j$ 确定出来的抛物线经过的点，那么就不用枚举 $k$ 了，时间复杂度 $O(T \times n^2 \times 2^n)$ ，算了一下大概要算 $8.4 \times 10^9$ 次，还是要T。
我们继续优化。我们发现，如果先打 $1,3$ 两头猪再打 $2,4$ 两头猪，和先打 $2,4$ ， 再打 $1,3$ 效果事一样的，那么我们就可以预处理一个数组 $low_i$ 表示最小（或最大）的 $x$ ，使得 i & (1 << x) 为 $0$ 。那么我们就只用枚举一个 $i$ ，时间复杂度降到了 $O(T \times n \times 2^n)$ 就可以过了。

下午#

把昨天的T3改了。

[ARC099E] Independence（就是昨天T3）#

因为个人觉得那些题解讲的都太水了，所以就不放 solution 链接了。
他说要把这一个图分成两个完全子图，我们考虑取补图。根据补图的性质，原图每条边的两个端点在补图里都不直接连通或不连通，而题目让我们分两个子图，使得子图里的点两两之间都有边，那么在补图里，他们就是两两都没边。我们就可以发现，就是要把补图二分图染色。在染色过程中我们就可以判断是否无解。而我们又想求最少有多少条边属于一个完全子图（在原图中的），我们设一个子图的点数为 $a$ ，另一个子图的点数为 $b$ 。那么我们的答案就是 $ans = \frac{a (a - 1) + b(b - 1)}{2}$ 。我们考虑dp。在染色的时候，我们记录一下，对于一个二分子图（因为取补图后不保证连通）染成颜色 $1$ 的点数为 $cnt_1$ ，染成颜色 $2$ 的是 $cnt_2$ 。用 bitset 记录哪几个完全子图大小能凑出来（因为 bitset 常数小到爆），然后枚举每一个 $i \in [0,n]$ 记录最大的 $ans$ ，这题就做完了。

今天是 wgc 的 $15$ 岁生日，让我们祝他生日快乐！！

晚上#

P3959 [NOIP2017 提高组] 宝藏 solution
我们看这个：要让访问所有宝藏屋的代价和最小，那不就是最小生成树吗？但是 $n$ 如此小，肯定有鬼。一看：代价不直接是边长 $L$ ，而是 $K \times L$ 。这里还多了一个 $K$ ，所以贪心不对。因为有这个 $K$ ，我们考虑把这个生成数分成 $k$ 层。我们设 $dp_{k,i}$ 为访问到了第 $k$ 层，总共访问的状态为 $i$ 的最小代价。那么我们肯定要从 $i$ 的子集转移而来。我们枚举每一个子集，并枚举子集里的点，找出它到补集中的任意一个点的最短路，然后把子集里的每一个点到补集的最短路求和，就可以得到答案。形式化讲：$dp_{k,i} = \min\limits_{j \subset i}(dp_{k - 1,j} + \sum\limits_{u \not \in j,u\in \complement_{i}j}w_{u,j})$ ，其中，$w_{u,j}$ 表示子集 $j$ 里的点 $u$ 到补集 $\complement_{i}j$ 里的任意一个点的最短路，也就是 $\min\limits_{v \in \complement_{i}j}(dis_{u,v})$ 。初始化会在代码里说明。

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

for (int i = 1; i <= n; i++)
        for (int j = 1; j < (1 << n); j++)
            for (int k = 1; k <= n; k++)
                if (!(j & (1 << (i - 1))) && (j & (1 << (k - 1))))
                    w[i][j] = min(w[i][j],dis[i][k]);//预处理w[i][j]
    for (int i = 1; i <= n; i++)
        dp[1][(1 << (i - 1))] = 0;//初始化
    for (int i = 1; i < (1 << n); i++)
    {
        for (int j = i & (i - 1); j; j = i & (j - 1))
        {
            int tmp = 0;
            for (int k = 1; k <= n; k++)
            {
                if ((1 << (k - 1)) & (i - j))
                {
                    if (w[k][j] > inf)
                        tmp = inf;
                    else
                        tmp += w[k][j];//记录子集里的每一个点到补集的最短路求和
                }
            }
            for (int k = 2; k <= n; k++)
                if (dp[k - 1][j] != inf && tmp != inf)
                    dp[k][i] = min(dp[k][i],dp[k - 1][j] + tmp * (k - 1));
        }
    }