zcmimi's blog
avatar
zc
2020-10-29 07:02:30

查看原题

点击跳转

考虑离线

把所有数排序后,可以发现经过4种操作后所有数还是有序的

这样我们维护区间加,区间乘,区间加变形,区间覆盖

avatar
zc
2020-10-28 17:01:35

查看原题

点击跳转

题意就是在[-n,n]中取k个整数,使他们和为0,求方案数

为了方便,我们可以理解为在[1,2n+1]中取k个整数,使他们和为k(n+1)

可以发现k\le 10

f(i,j)表示取i个数,和为j

f(i,j)=f(i,j-i)+f(i-1,j-i)

由于最大取到2(n+1),若j超出2(n+1)记得减去超出部分

avatar
zc
2020-10-28 15:23:37

查看原题

点击跳转

难点在于第二问

第一问:

二进制拆位后分别统计就可以了

第二问:

枚举每一位,统计答案该位是否为1

设序列前缀和为S

区间[l,r]区间和二进制下第k位为1,那么(S_r-S_{l-1}) \mod 2^{k+1}\ge 2^k

S_{l-1} \mod 2^{k+1} \le (S_r \mod 2^{k+1})-2^kS_{l-1}\ge 0

S_{l-1} \mod 2^{k+1} \le (S_r\mod 2^{k+1})+2^kS_r<S_{l-1}

离散化后树状数组即可统计

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

查看原题

点击跳转

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-23 12:34:55

查看原题

点击跳转

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

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

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

栈顶权值表示:

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

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

查看原题

点击跳转

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

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

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

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-20 16:36:54

查看原题

点击跳转

建图比较麻烦的最短路问题

将每个城市考虑为4个机场

每个机场两两之间互相连边,若同一个城市,走高速,否则走航线

需要注意的是找出根据三个机场找出第四个机场时的分类讨论

9/74
Search
search