zcmimi's blog

categories/刷题记录/共658篇文章

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

图形可以分割成一个个小矩阵

于是我们可以把每个矩形变成两条线段后对这些线段进行排序

如此

那么总共覆盖了多少长度?

线段树求!

那管儿子节点的事干嘛,让他们自生自灭得了

于是,我们想到,除左右端点l,r之外,在线段树的每个节点上维护两个值:该节点代表的区间被矩形覆盖的长度len,该节点自身被覆盖的次数cnt。最初,二者均为0.

注意: 每个节点代表的范围是[l,r+1],最后面的那个节点不算入统计

对于每一个(x,y1,y2,k),我们再[val(y1),val(y2)-1](离散化后的区间)上执行期间修改。该区间被线段树划分成 \log n个节点,我们把这些节点的cnt都加k

对于线段树中任意一个节点 [l,r] ,若cnt>0,则len等于raw(r+1)-raw(l)(离散化前的距离),否则,该店len等于两个子节点的len之和。在一个节点的cnt被修改,以及线段树从下往上传递信息时,我们都按照该方法更新len值。根节点的len值就是整个扫描线上被覆盖的长度

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f_i表示[1,i]最多变成多少个

f_i=\max_{s_i=s_j}(f[j-1]+s_j\times (\sum_{i=j}^i[s_i=s_j])^2)

我们可以发现如果s_j=s_{j'}(j'< j),从j'转移一定比从j

这一条件满足决策单调性!

我们可以用单调队列维护单调性

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

我们可以考虑放n-k个节点然后使深度最大的最小

一开始的时候可以反过来想:树里面长度最大的路径就是树的直径,它的两个端点的度都是1(也就是叶子节点)

我们可以从每个叶子结点开始,向中心包围。可以用队列的方式实现。

(代码很短)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

如果没有时间限制那就是一个裸的完全背包

我们可以先按时间从大到小排序,保证如果选了后面作业能选的话不会影响当前作业

接着背包求出每天的最小花费

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

当我们选中一个i

i,i^2,i^3...,i^k都会被去掉

我们设d_t为可以去掉t的数字的个数

ans = \sum_{i=1}^n \frac 1 {d_i}

那么如何统计呢?

分解质因数

n = p_1^{k_1}p_2^{k_2}p_3^{k_3}p_4^{k_4}...

对于k_i贡献为1+\frac12+\frac12+\frac14+...

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

题意:

给出一个矩阵,要求每行只能选一个节点,每列选的节点不能超过所有选的节点的一半,不能不选, 给出每个节点的选择方案数,求总方案数

解法

考虑到限制是每列选择的不能超过一半,我们可以想到不合法的最多只有一列

我们可以用总方案数减去不符合的

s_i=\sum_{j=1}^m a_{ij}

总方案数:\prod_{i=1}^n (s_i+1) - 1

\because k=\frac {tot}2

所以我们有一个很妙的方法:

设选中目标行之外的权值+1,不选+0,选中目标行权值位+2

最后只要权值> n,那么目标行一定被选了超过\frac n2

f(i,k)表示总共选了i次(也就是选到第i行)权值为k的方案数

f(i,k) += f(i-1,k)*(s_i-a_{ij})(当前行不选目标列

f(i,k+1) += f(i-1,k)(当前行完全不选

f(i,k+2) += f(i-1,k)\times a_{ij}(当前行选中目标列

ans = \prod_{i=1}^n (s_i+1) - 1 - \sum_{i=n+1}^{2n} f(n,i)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f_i为前i个任务的费用,t_i为前i个任务时间的总和,w_i为前i个任务费用的总和

f_i=\min_{j=0}^{i-1}(f_j+s\times(w_n-w_j)+t_i\times(w_i-w_j))

设任意0\le j<k<ij转移比从k转移优,那么

f_j+s\times(w_n-w_j)+t_i\times(w_i-w_j) \le f_k+s\times(w_n-w_k)+t_i\times(w_i-w_k) \\ t_i(w_k-w_j)\le f_k-f_j+s(w_j-w_k) \\ t_i\le \frac{f_k-f_j+s(w_j-w_k)}{w_k-w_j}

维护了个下凸壳交了上去,结果听取\color{red}\text{WA}声一片

仔细看了看|T_i|\le 2^8

这也就意味着我们每次截取的直线的斜率不再单调递增,单调队列不能再满足需要

为了保证决策状态的有序性,我们还是选择用一个单调栈维护下凸包。

因为决策集合已经有序,对于任意直线,我们只用在队列中二分出使截距最小的交点

由于出题人十分毒瘤,我们要把斜率大小的判断从相除改成十字相乘

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先筛选出d_a,d_b,d_c

如果a,b,c的约数都不相同,那么ans = d_a \cdot d_b \cdot d_c

我们来考虑要减去的部分

(a,b,c) , (b,a,c)这样的是不符合的,减去其中一个

也就是减去d(gcd(a,b))\times(d(gcd(a,b)-1))

同理,(a,c,b),(c,b,a)也要减去.

这样的话会多减了一个d(gcd(a,b,c))*(d(gcd(a,b,c))-1),要加回来

...

https://www.luogu.com.cn/blog/lingchi/solution-cf1008d

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

56/66
Search
search