夢に僕らで帆を張って
来るべき日のために夜を超え

标签 前缀和 下的文章

November 5, 2019

洛谷P4427/BJOI2018 求和

题意给出一棵树,$m$个询问,求从点$u$到点$v$的路径上所有节点深度的$k$次方和$\bmod \ 998244353$数据范围:$1 \le n,m \le 300000,1 \le k \le 50$题解对每一个$k$求一个树上前缀和答案为$$u+v-lca(u,v)-fa[lca(u,v)]$$代码:#include<iostream> #include<cstd...
November 4, 2019

洛谷P3157/CQOI2011 动态逆序对

题意对于序列$A$,它的逆序对数定义为满足$i < j$,且$A_i > A_j$的数对$(i,j)$的个数给出$1$到$n$的一个排列,按照某种顺序依次删除$m$个元素,求在每次删除一个元素之前整个序列的逆序对数数据范围:$N \le 100000,M \le 50000$题解将删除顺序$t_i$视为一维,值$a_i$视为一维,位置$d_i$视为一维,此问题即为三维偏序在满足$...
November 4, 2019

洛谷P3455/POI2007 ZAP-Queries

题意求$$\sum_{i=1}^a \sum_{j=1}^b [\gcd(i,j)=k]$$数据范围:$1 \le d \le a,b \le 50000$题解假设$a\le b$$$ \begin{aligned} \sum_{i=1}^a \sum_{j=1}^b [\gcd(i,j)=k] &= \sum_{i=1}^{\lfloor\frac{a}{k}\rfloor} \s...
November 2, 2019

洛谷P4158/SCOI2009 粉刷匠

题意windy有$n$条木板需要被粉刷,每条木板被分为$m$个格子,每个格子要被刷成红色或蓝色windy每次粉刷,只能选择一条木板上一段连续的格子,然后涂上一种颜色 每个格子最多只能被粉刷一次如果windy只能粉刷$t$次,他最多能正确粉刷多少格子?一个格子如果未被粉刷或者被粉刷错颜色,就算错误粉刷数据范围:$1 \le n,m \le 50,1 \le t \le 2500$题解$\tex...
November 2, 2019

洛谷P2466/SDOI2008 Sue的小球

题意略数据范围:$n \le 1000$题解区间$\text{dp}$容易证明,在完成一个区间后处于左/右端点最优由于输入无序,首先按$x$排序,并统计$v$的前缀和以优化计算;另外起始点不一定有球,因此加入起始点用$f[l][r][0/1]$表示已接到区间$[l,r]$的球,现在处于$0$(左端点)/$1$(右端点)失去的最小价值那么区间$[l,r]$由$[l+1,r]$或$[l,r-1]...
October 28, 2019

洛谷P1314 聪明的质监员

题意略数据范围:$1 \le n,m \le 200000,s \le 10^{12}$题解二分$W$,更新$|S-Y|$在每次验证的时候用前缀和维护$\ge W$的$w_i$的数量与总和代码:#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #i...
October 18, 2019

洛谷P3594/POI2015 WIL-Wilcze doły

题意给定一个长度为$n$的序列,你有一次机会选中一段连续的长度不超过$d$的区间,将里面所有数字全部修改为$0$。请找到最长的一段连续区间,使得该区间内所有数字之和不超过$p$数据范围:$1 \le d \le n \le 2000000,0 \le p \le 10^{16}$题解首先能够想到枚举区间左右端点$l,r$,再减去区间内和最大的一段,用前缀和表示为$$s[r]-s[l-1]-\...
October 18, 2019

洛谷P4099/HEOI2013 SAO

题意给出一个连成树的有向图,求拓扑序数量数据范围:$1 \le n \le 1000$题解树形$dp$,用$f[i][j]$表示以$i$为根的子树中,节点$i$的排名为$j$的方案数考虑转移,对于$u$为$v$的父节点,$x$在原序列中排名为$p_1$,新序列中排名为$p_3$;$y$在原序列中排名为$p_2$,新序列中排名为$p_4$,从$f[u][p_1]$与$f[v][p_2]$转移到...