9.26

Posted on Edited on In

上午改题加透彻树形dp

  • 树形dp的最小点覆盖与最小边覆盖大有千秋

最小边覆盖只需要考虑：这条边是由他还是他儿子控制，即边的两个端点

而最小点覆盖：需要考虑一个点是由他儿子还是他自己或者是他父亲节点控制，状态有三维

其中最小边覆盖，一定包含所有边与点

而最小点覆盖，一定包含所有点，但是不一定包含所有边，例子不难举出反例

P2016战略游戏是需要全部边被占，包含全部点被占的情况，而保安站岗并不一定所有边都会被占

  • 考试第一题

一个一元二次sb算术题，但是要考虑精度问题，在\([x, x+1]\)之间都要算一下

  • 考试第二题

大致题意：每次可以选择一条边在其一端加1，在另一端点减1，但是有一个权值范围，求\(\sum i \times val[i]\)

由于在第一题浪费太多时间，看第二题的时候第一反应是写暴力，但是tm暴力部分分比正解还要难写难调

solution：搜出所有联通块，显然在一个联通块里面所有的点都是可达的，无论通过何种操作，我们都可以使得一个点加1一个点减1

所以，贪心的倒序枚举点的编号，尽量满足编号大的，所有联通块所贡献出来的和就是答案

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
inline int fuck(int x) 
{
    sort(v[x].begin(), v[x].end());
    int s = v[x].size(), ret(0), i, y;
    for (i = 0; i < s; ++ i)
    {
        y = v[x][i];
        val[y] = 1;
    }
    w[x] -= s;
    for (i = s - 1; i >= 0; -- i)
    {
        y = v[x][i];
        val[y] += min(L - 1, w[x]);
        if (val[y] != L) w[x] = 0;
        else w[x] -= (L - 1);
        if (w[x] <= 0) break;
    }
    
    for (i = 0; i < s; ++ i)
    {
        y = v[x][i];
        ret = ret + y * val[y];
    }
    return ret;
}