test617 - test714 解题记录集锦

· · 个人记录

test617

b

使用 kmp自动机，再动态规划即可

乘积筛

暴力枚举时间复杂度 O(\frac{n}{\max\{p,q\}})

记忆化 \max\{p,q\} <= \sqrt n 的部分

时间复杂度 O(n \sqrt n)

国战

对每个点到根节点的 p_i 维护一颗值域线段树

对于一个点 son，它依托于 fa 建一棵树

具体使用 可持久化线段树

对于每个询问只需知道 u,v,lca(u,v) 到根节点的线段树

使用 二分 查询

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

test703

最小基因序列

简单贪心，考虑后缀字典序最大，使用 vector ，遍历一次刷掉一些，注意如果位数不够后要从后面继续遍历，玄学时间复杂度

等差数列

明显是个环，分类讨论，另外一种情况是要看补集。

然后先找到公差 d，再算首项，就可以了。

策略游戏

发现差不会变，我们记表示（a,d）表示手上的两个数字为 (a, a + d)。

二元组的第二个元素状态数只有的因数级别。

状态不会超过1344个，直接转移即可。

简单记忆化搜索。

int dfs(int a, int b) {
    if(a == 1) return 0;
    if(f[a][b] != 0) return f[a][b];
    int ans = a - 1;
    //if(b == 1) return a - 1;
    int now = b;
    for(int i = 2; i * i <= b; i++) {
        if(now % i == 0) {
            int d = i;
            ans = min(ans, dfs(a / d, b / d) + 1 + a - a / d * d);
            ans = min(ans, dfs(Ceil(a, d), b / d) + 1 + Ceil(a, d) * d - a);
            while(now % i == 0) now /= i;
        }
    }
    if(now != 1) {
        int d = now;
        ans = min(ans, dfs(a / d, b / d) + 1 + a - a / d * d);
        ans = min(ans, dfs(Ceil(a, d), b / d) + 1 + Ceil(a, d) * d - a);
    }
//  cout << endl;
    return f[a][b] = ans;
}

test 707

异或平方和

需要拆开处理，对于 a_i\oplus a_j 可以变成 \sum_{k = 1}^{Len}(a_{i,k}\oplus a_{j,k})

那如何变成平方呢？

想下竖式乘法的过程，需要对每一位分别乘上下一个数的每一位，换言之，当 a_{i,k} 和 a_{j,l} 均为 1 时，那么它的贡献为 2^{k+l-2}。

现在有四个变量 i,j,k,l 分别表示竖式乘法正在算 i 的第 k 位 \times j 的第 l 位，数量级分别为 O(n) O(n) O(logn) O(logn) , 看似跑起来比暴力还慢，但是实际上我们只需要枚举 i,k,l 即可

j$ 可以通过预处理求出，考虑一下会对答案做出贡献的 $j$ 的实际意义：$a_{i,k} \oplus a_{j,k} = 1$ 且 $a_{i,l} \oplus a_{j,l} = 1

只需要记 f_{i,j,k,l} 表示满足第 i 位为 k，第 j为 l 的个数即可

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

除雪

将一个点拆成 a_i 个点，然后进行匹配

记 f_i 表示的该子树内最大的匹配数，g_i 表示取到时能够向上匹配的最小数量

贪心即可，没什么好说的。

天堂之战

结论题，得出结论后使用倍增维护

记录 nxt[i][j] 表示 i往后跳j 个的点

# test710 ## 城市天际线 先使用并查集，维护所有联通块，先对每个联通块都分别连一个环，有多的边就对每一个联通块内部进行连边，若还有多的边，就对每个联通块两两进行连边，注意**不能创造一个大环**。 ## 景点距离 记 $cnt[i]$ 表示路径长度为 $i$ 的路径的个数。 $f[i][j]$ 表示 以 $i$ 为根节点的子树的所有点到 $i$ 的路径长度恰为 $j$ 的路径个数 很明显使用 $f[i][j]$ 来维护 $cnt[i]

删边操作不好计算，不如离线改成加边操作。

排列

易得 f_i = f_{i-1}+f_{i-3}+1，使用矩阵快速幂即可。

test712

生命游戏

求时间最大，很明显二分时间

对于时间 t， 如何求出初始点呢？

若一个点到离它最近的一个"."的距离 > t ,那么称这个点为初始点

求出初始点可以用 BFS 实现

最后对所以得初始点模拟 t 秒，即可，也使用 BFS

Bajka

定义状态 f[i][j] 表示 s 匹配到第 i 个， t 匹配到第 j 个

对于一个 t[i] ，找到所有的 s[j] = s[i]，从左到右，从右到左分别扫一遍即可

memset(b, 0, sizeof(b));
for(int j = 1; j <= n; j++) {
    int x = s[j] - 'a' + 1;
    if(b[x]) f[j][i] = min(f[j][i], f[b[x]][i] + abs(b[x] - j));
    b[x] = j;
}
memset(b, 0, sizeof(b));
for(int j = n; j >= 1; j--) {
    int x = s[j] - 'a' + 1;
    if(b[x]) f[j][i] = min(f[j][i], f[b[x]][i] + abs(b[x] - j));
    b[x] = j;
}

序列修改

假如要修改 a[i] 为 x ，考虑它带来的影响

对于下一个与 a[i] 相同的 a[j]，它会对 [i, j - 1] 这个区间的 c[i] 减一，带来 - (i + j) \times (j - i + 1) / 2 的影响

为保证 a[i] - x 的绝对值最小，用一个 set 即可

test714

valk

建两棵字典树后，进行 DFS

记 dfs(x,y,f) 表示第一棵字典树在 x ，表示第二棵字典树在 y , 轮到谁出手，当前局面谁赢

selotejp

轮廓线 DP

papricice

50pts

使用 DFS 序，枚举两个点并判断是否为祖孙关系，分类讨论

100pts

只枚举一个点，另一个点最优使用 set 维护，判断是否为祖先关系可以使用一个栈