Codeforces Round 1024

發表於 更新於 分類於 ， Disqus： 文章字數： 2.7k 所需閱讀時間 ≈ 9 分鐘
D(LIS,DP)E(DP,点分治)F()

https://codeforces.com/contest/2101

D Mani and Segments

给定1~n排列，问有多少子串满足

LIS+LDS=len+1

3s

我的思路

排列保证了两两不同

lis: dp[i] = idx_lower_bound(a[i])-1

显然 lis 和 lds如果两两不同，那么它们的共有元素最多有一个

有一个共有元素时: lis-1 + lds-1 + 1 <= size(所有元素) = len

             (len+1) - 1 <= size(所有元素) = len

没有有元素时: lis + lds <= size(所有元素) = len

             (len+1) <= size(所有元素) = len

说明了 恰好有一个共有元素，且两个序列占满整个数组

钦定这个共有元素

它向左延伸，要么链接更小要么链接更大, 必须要满足匹配，向右同理

1
2
3
4
5
6
7
8
9
10
fix i
   min = a[i]
   max = a[i]
   for j = i+1 ... n:
       if a[j] > max:
           max=a[j]
       elif a[j] < min:
           min = a[j]
       else:
           break

当出现纯单调序列时，这个共有元素不是唯一的

   1  3 4 5 6 2, 这样共有也不是唯一的， 上面方案没有完成去重的问题

   1 4 3 2 5, 这样 共有的一定不是最大或者最小，

校验方案:

   dp[i][0] = i作为下降时, 上升侧的最小值

   dp[i][1] = i作为上升时, 下降侧的最大值

   dp[i][0] = min(dp[i-1][0] if a[i] < a[i-1], a[i-1] if a[i] < dp[i][1],  INF)

   dp[i][1] = max(dp[i-1][1] if a[i] > a[i-1], a[i-1] if a[i] > dp[i][0], -INF)

这个dp会受到 前面内容的影响, 感觉局部性还不如钦定共有

反面: 什么是不合法的

 a<b,c<d
   d   b
 c   a

a,b无法同时连bc，所以一个连b一个连c，显然不行, 其中a,d相邻

好像也不好搞

另一个角度 如果 a[l..r] 合法

那么 a[l..mid], a[mid…r] 也合法，因为从共有元素角度看，如果包含，那么就有包含的方案，如果不包含发生了分裂，也就是 切割的mid处 可以作为共有点

所以 合法的l..r 的任何切割 总有一半是切割点是共有点

还是单独来，就钦定共有点，但是保证共有点是可选区间最左点

题解

首先 交差于一点是对的

后续变成二维空间长方形覆盖面积统计就好了

以i为钦定交差点，的左合法可选2，右合法可选4

那么也就是二维平面上 $x \in [i-1,i],y\in [i,i+4]$ 的矩形

那么就是n 个顶点在[i,i] 向左上方延伸的矩形的覆盖面积和

而且有特点, i < j, 那么x的最小值 也有同样的偏序关系, y的最大值同样有偏序关系

那么 每次的增量 = i_x_len * i_y_len(新矩形面积)-(last_max_x-i_x_min)*(last_max_y-i_y_min) (和上一个重叠的面积)， 因为上面的特性保证了 若和前面任何一个有重叠都在和上一个矩形的重叠范围内，这里稍微要注意的就是取个max(value,0), 简化写法，（虽然不会出现相邻单点，因为任意三个数必定可行

这个是很关键的，因为如果下一个作为交叉点，左侧合法要尽量的长，那么当前位置 属于上升还是下降是唯一确定的

这里唯一确定不只对下一位（下一位比较显然）

对于未来也是这样, 如果 a[i] > a[i+1], 那么a[i]放在DEC里，如果未来j 与i有关，而i在INC里，那么i+1没有合法位置，j就不可能和i有关，若有关都是在DEC里

另一方面 上面的while保证了不论放哪里，stack里都是两个单调的

而p控制了长度, 对于i合法的D/I, 倒回去一定能产生

而引起p的变化, 只需要stack顶部即可，stack的残余部分没有任何用啊

E Kia Bakes a Cake

6s

512mb

n 2e5

|s| = n, 01串s

树T 有n个点

k = s中1的个数

1
2
3
4
for i in 1..n:
    if s[i] == 1:
         创建点 i
    weight[i][j] = dis(i,j) in T, 其中 s[i]==1,s[j]==1

这样得到 k个点的完全图，无向，但边有权重

简单路径 如果经过的边 每条权重 >= 上一条的2倍, 那么是好的简单路径（那么总长不会太长 log级别）

对于每个i(s[i]==1)

计算从i开始的 最大简单路径长度

我的思路

换句话说，不用新建立图

就是在原来的树T上移动，有点点标为1，有的点是0，每次从1到1，然后长度要大于上次移动的2倍距离，问每个1点出发的最大次数

然后 simple path的要求就是每个点最多访问一次

首先说，如果贪心能到的最近的点，怎么保证后续的点能2倍

1
2
3
4
A-1-B-3-C-4-D
从C出发，先D再A可以两次，先B再D可以两次（这样也就是B,D在不同分支））
A-1-B-2-C-4-D-8-E-16-F-32-G
从B开始向右5次到G，向左ACEG 更短

对于simple path限制的观察是，不会出现，因为最后一次如果是从 a-b,那么上一次<=1/2距离，再上一次<=1/4 距离 所以前面距离和 不会等于当前距离，，所以如果重复到前面的点，那么一定不满足2倍距离，

那么这样的话，就不用记录走过哪些点

一个想法是所有点“一起”走，但问题是没有贪心 怎么知道哪些点

ans[i] = max(dp[j][dis(i,j)])+1

dp[i][d] = max(dp[j][dis(i,j)]+1, dis(i,j) >= 2*d)

但是这个n感觉 做不了n^2

题解

hint1 也是我上面观察到的 路径中不会出现重复的点

hint2 路径长度是log级别

hint3 如何使用 动态规划

hint4 如何优化动态规划？我没想出

首先就是 长度不会超过n-1,所以log(n)级别的答案

然后显然不会重复点

dp[i][j] 从j开始走i步 的 最大weight, 倒着更新

为了优化这一点，我们使用了中心点分解的后缀技巧，每次都保留最多两个后缀

也就是 dp[i][j] 的结果，可以去更新 j为中心, 半径为 dp[i][j]/2 的点v的 dp[i+1][v] 的值

也就是 for i(step)

然后又批量的 每个点的半径更新，这个就是点分治来优化效率

对于点分治的当前的根root, 和一个点v 以及半径r，首先处理root和v的直接更新，常数代价，然后处理v的r覆盖会超过（越过root）的更新

这部分 记录 要更新的深度和之前的深度，例如 v—root—w, 那么 (h[v]+h[w])*2 < dp[i][v], 所以先lazy的记录 h[w] 的范围对应的 {h[v]}, 再批量更新即可

代码

https://codeforces.com/contest/2101/submission/327416389

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
#include <bits/stdc++.h>
using namespace std;
typedef int i32;
#define rep(i,a,n) for (i32 i=a;i<(i32)n;i++)
#define per(i,a,n) for (i32 i=n;i-->(i32)a;)
i32 read() { i32 r;scanf("%d", &r);return r; }
// ----------------------------------------------------------------------------------------

const int N = 70000 + 10, lg = 17; // log2(70000)
char s[N]; // 读入, 节点1-index
int a[N];
int dp[lg + 1][N]; // dp[step][vertex i] 从i向后走step步, 可以接受的上一次最大距离
int sz[N];// subtree size
int cut[N]; // 点分治时的标记
int h[N]; // height
int branch[N]; // 是根的哪个分支
vector<int> G[N]; // 原树的临接表
vector<int> centG[N]; // 点分治的临接表 centG[i] = list[i的临接子块的 重心], 都是父向子的边
template<class T>
void setMax(T& a, T b) { a = max(a, b); }
#define foru for(int u : G[v]) if (u != p and !cut[u])

void dfs0(int v, int p) { // 计算子树大小和高度, h[root]=0
    sz[v] = 1;
    h[v] = (p == -1 ? 0 : h[p] + 1);
    foru{
        dfs0(u, v);
        sz[v] += sz[u];
    }
}

int findCent(int v, int p, int tot) { // 保证v的子树 > 一半节点
    foru if (2 * sz[u] > tot) return findCent(u, v, tot); // 如果u存在唯一
    return v;
}

int createCentTree(int v) { // 传入任意点 处理该点连通块的分治，返回连通块的重心
    dfs0(v, -1); // 以v为根
    int cent = findCent(v, -1, sz[v]); // 点分治(按)
    cut[cent] = 1; // 标记切割
    for (int u : G[cent]) if (!cut[u]) centG[cent].push_back(createCentTree(u));
    return cent;
}
using hb = pair<int, int>;// height, branch
struct node {
    array<hb, 3> mx; // [0]用于插入,[1],[2]用于保存最大的 // x 新增, mx1,mx2 之前的, 因为对同一个深度染色，只有不同分支最大两个是有效的
    node() { rep(i, 0, 3) mx[i] = { -1e9,-i - 1 }; }
};
vector<node> suff(N);

void solve(int v, int idx) {// 当前根为v, 执行所有点与v之间的互相dp更新，以及所有跨过v的dp更新(跨过的更新用suff优化)
    int root = v;
    dfs0(v, -1);
    rep(i, 0, sz[v] + 1) suff[i] = node();
    auto markhb = [&](node& y, hb x) {
        y.mx[0] = x; // 插入x
        sort(begin(y.mx), end(y.mx));
        if (y.mx[1].second == y.mx[2].second) swap(y.mx[0], y.mx[1]); // 同分支保留大的, 或者说保持 mx[1],mx[2]是不同的分支
        };
    function<void(int, int)> dfs1 = [&](int v, int p) {
        if (2 * h[v] <= dp[idx - 1][root]) setMax(dp[idx][v], h[v]); // v -(h[v])-> root -(dp0[root])->...
        if (2 * h[v] <= dp[idx - 1][v]) setMax(dp[idx][root], h[v]); // root -(h[v])-> v -(dp0[v])->...
        branch[v] = p == -1 ? -1 : (p == root ? v : branch[p]);
        if (branch[v] != -1 && dp[idx - 1][v] >= h[v] * 2) { // v为中心 dp0[v]/2为半径更新dp，会经过 根root
            markhb(suff[min(dp[idx - 1][v] / 2 - h[v], sz[root])], { h[v], branch[v] }); // 先标记在wh，再通过下面的per, 赋值到所有<= wh
        }
        foru dfs1(u, v);
        };
    function<void(int, int)> dfs2 = [&](int v, int p) {
        if (p != -1) {
            auto [h1, b1] = suff[h[v]].mx[1];
            auto [h2, b2] = suff[h[v]].mx[2];
            setMax(dp[idx][v], (b2 == branch[v] ? h1 : h2) + h[v]);
        }

        foru dfs2(u, v); // 递归调用
        };

    dfs1(v, -1); // 所有点与v的更新，要跨过v的点用markhb标记 深度 和 分支
    per(i, 1, sz[v]) for (int t : { 1, 2 }) markhb(suff[i], suff[i + 1].mx[t]); // 简单的后缀转换
    dfs2(v, -1); // 执行染色
    cut[v] = 1;
    for (int u : centG[v]) solve(u, idx);
}

void w() {
    int n = read();
    // clear
    rep(i, 0, lg + 1) rep(j, 0, n) dp[i][j] = -1;
    rep(i, 0, n) G[i] = {};
    rep(i, 0, n) centG[i] = {};
    // read
    scanf("%s", s); // 1-index
    rep(i, 0, n)  a[i] = (s[i] == '1');
    rep(i, 1, n) {
        int u = read() - 1;
        int v = read() - 1;
        G[v].push_back(u);
        G[u].push_back(v);
    }
    // 点分治
    fill(cut, cut + n, 0);
    int root = createCentTree(0);
    rep(i, 0, n) if (a[i]) dp[0][i] = 2 * n;

    rep(i, 1, lg + 1) {
        fill(cut, cut + n, 0);
        solve(root, i);
        rep(j, 0, n) if (!a[j]) dp[i][j] = -1;
    }
    rep(i, 0, n) {
        if (!a[i]) { printf("-1 "); continue; }
        per(j, 0, lg + 1)  if (dp[j][i] >= 1) {
            printf("%d ", j + 1);
            break;
        }
    }
    printf("\n");
}

int main() {
    int t = read();
    while (t--) w();
    return 0;
}