zcmimi's blog

arrow_backnoip共7篇文章

avatar
zc
2020-10-27 20:44:01

查看原题

点击跳转

解法一

最小权覆盖集 = 全集 - 最大权独立集

动态dp

只要把强制取点,不取点可以分别把点的权值改为正无穷与负无穷

解法二

倍增/树链剖分+树形dp

每次修改的两个点a,b构成一条链

可以链上连接的子树与链中间的点的结果不受修改影响,只有a,b的转移受影响,需要单独处理

那么我们可以把子树的答案都预处理出来,链中间部分可以用倍增或树链剖分维护

这样只需要处理a,b

f(i,0/1)表示i选/不选,以i为根的子树的最小代价,g(i,0/1)表示整棵树除了以i为根的子树的最小代价,可以通过树形dp求出

F(i,j,0/1,0/1)表示i选/不选,i2^j级祖先选/不选,i子树到ii2^j级祖先子树的最小代价,可以倍增求出

avatar
zc
2020-10-27 12:19:30

查看原题

点击跳转

既然对考虑每条边断开后产生的重心比较麻烦,那么换个方式:

考虑每个点成为重心的次数

首先找出重心作为树根

设当前节点为x,子树大小为siz_x,孩子的最大子树大小为g_x,割掉一条边后,另一棵树大小为S

考虑x不是重心的情况:

2(n-S-siz_x)\le n-S2g_x\le n-S

也就是

S\in [n-2siz_x,n-2g_x]

我们可以用树状数组维护并统计每个点割掉与父亲之间的边后形成的S

显然这条边不能在x的子树内,那么减去 进入x子树前后求和的差

考虑x为重心的情况:

ux重儿子,vx次重儿子

若割掉的边在u的子树中: 2siz_v\le n-S,即S\le n-2siz_v

否则: 2siz_u\le n-S,即S\le n-2siz_u

avatar
zc
2020-10-23 12:34:55

查看原题

点击跳转

根据平方和公式可以发现分越多段越好

而进一步又可以发现最后一段的总和越小越好

以下是88分代码(高精什么的懒得写了):

avatar
zc
2020-10-23 12:34:55

查看原题

点击跳转

在dfs的过程中维护一个栈st

假设当前遍历节点为x,栈顶st[tp]

x与栈顶形成一个括号对,那么弹出栈顶,将新的栈顶权值+1

栈顶权值表示:

如果有新的右括号入栈,以这个右括号结尾,能形成多少合法括号串

avatar
zc
2020-10-23 12:34:55

查看原题

点击跳转

95分(未特判2^{64})

#include<iostream>
int n;unsigned long long k;
int main(){
    std::cin>>n>>k;
    k^=k>>1;
    while(~--n)std::cout<<(k>>n&1);
}

100分简洁代码:

avatar
zc
2020-10-21 10:05:27

查看原题

点击跳转

这题考场上可能打表稳一点

n/m 1 2 3 4 5 6 7 8
1 2 4 8 16 32 64 128 256
2 4 12 36 108 324 972 2916 8748
3 8 36 112 336 1008 3024 9072 27216
4 16 108 336 912 2688 8064 24192 72576
5 32 324 1008 2688 7136 21312 63936 191808
6 64 972 3024 8064 21312 56768 170112 510336
7 128 2916 9072 24192 63936 170112 453504 1360128
8 256 8748 27216 72576 191808 510336 1360128 3626752

不妨设n<m(不难发现表格是对称的)

不难发现:

  1. n=1时,ans(n,m)=2^m
  2. n>1,m>n+1时,ans(n,m)=ans(n,m-1)\times 3

打表+快速幂就完事了

avatar
zc
2020-10-19 19:55:41

查看原题

点击跳转

f(i,j,0),f(i,j,1)表示:

i个时间段,已经用了j个机会,选择c_i与选择d_i(换/不换教室)的最小期望

dis(i,j)表示i,j之间最短距离

转移方程:

f(i,j,0)=\min \begin{cases} f(i-1,j,0)+dis(c_{i-1},c_i)\\ \begin{aligned} f(i-1,j,1) &+dis(d_{i-1},c_i)\times k_{i-1}\\ &+dis(c_{i-1},c_i)\times(1-k_{i-1}) \end{aligned} \end{cases}

f(i,j,1)=\min \begin{cases} \begin{aligned} f(i-1,j-1,0) &+dis(c_{i-1},d_i)\times k_i\\ &+dis(c_{i-1},c_i)\times (1-k_i) \end{aligned}\\ \begin{aligned} f(i-1,j-1,1) &+dis(d_{i-1},d_i)\times k_{i-1}\times k_i\\ &+dis(c_{i-1},d_i)\times (1-k_{i-1})\times k_i\\ &+dis(d_{i-1},c_i)\times k_{i-1}\times (1-k_i)\\ &+dis(c_{i-1},c_i)\times (1-k_{i-1})\times (1-k_i)\\ \end{aligned} \end{cases}

1/1
Search
search