BZOJ

tg.BZOJ 4403序列统计 pj.BZOJ 4403序列统计 没啥用的题解 \(QWQ\)——无脑思考 首先要想怎么求单调不上升序列的个数，因为可能会有重复的数，所以不能直接用排列组合。 那这道题怎么打呀？ 我不知道啊\(\dots\) \((~:\) 因为原来是单调不下降序列，将第 \(i\ ......

题目传送门 前置知识 排列组合 | 卢卡斯定理 解法 记 \(m=r-l+1,0 \le k \le n-1\) ，枚举长度 \(i\) ，等价于求 \(\sum\limits_{j=1}^{m}x_j=i\) 的非负整数解的数量。接着推式子就行。 \(\begin{aligned} \sum\li ......

大豆说过：最大权独立集你就会个二分图，你又不会一般图，往二分图上想。 先看第二个条件：不互质的数可以连边。所以现在只剩下互质的数了。 然后看第一个条件（再联想到大豆说的：二分图先想奇偶性）：互质的数只存在：奇数和偶数；奇数和奇数。 两个奇数肯定能表示成如下形式：\(2 \cdot a + 1\) 和 ......

题解 建出原图的圆方树。由于原图无重边，不妨把桥看作二元环建树，这样圆点只与方点直接相连。 圆方树定某一圆点为根后，若点 \(u\) 是圆点，定义点 \(u\) 的子仙人掌为点 \(u\) 子树中的圆点在原图的导出子图，定义该子仙人掌的根为点 \(u\)；若点 \(u\) 是方点，定义点 \(u\) ......

bzoj #2958 非常好的容斥 dp 题 发现这道题分为没有找到颜色 \(B\) ，找到连续 \(K\) 个颜色 \(B\) 但没找到颜色 \(W\) 以及都找到了三种状态，因此我们考虑把这些状态记为 \(0,1,2\) 设到 dp 中 设计状态：设 \(dp_{i,j,k}\) 表示前 \(i ......

本题解思路类似 kczno1 在 [POI2010] KOL-Railway 的题解。 如果 \(l_i < l_j < r_i < r_j\) 则连边 \((i, j)\)，题目转化为判断该图是否是二分图，如果是则给出染色方案。 不妨先找出一个生成森林，然后染色并判断所有同颜色的点是否没有边相连。 ......

题目描述 你需要计算一个函数 \(F(x, y)\)，其中 \(x, y\) 是两个正整数序列。 bool F(std::vector<int> x, std::vector<int> y) { if (W(x).size() != W(y).size()) return false; if (W( ......

bzoj #4069 二进制？按位考虑。 或操作而且最小？按位贪心。 从最高位往下贪，记录一个 \(x\) 表示当前最高位确定了哪些位可以为 \(0\) (其中存在为 \(0\) 方案的位上值为 \(1\) ) 考虑 dp 处理对于第 \(t\) 位能否为 \(0\) ： 设计状态：设 \(dp_{ ......

bzoj #2863 设 \(dp_i\) 表示 \(i\) 个点的 DAG 个数。发现一个 DAG 删去出度为 \(0\) 的点后显然还是一个 DAG ，因此不妨枚举出度为 \(0\) 的点的个数： \(dp_i = \sum\limits_{j=1}^i dp_{i-j}\binom{i}{j} ......

preface 网上目前还没看到我的方法，就大概讲一下做法 solution 首先想到贪心，考虑 \([l, r]\) 的最大次数，一定是找到最小的 \(x\) 满足 \(l \sim x\) 的位数的和大于等于 \(k\)，然后递归的求解 \([x + 1, r]\)，易证。 还是考虑将 \(Qu ......

原题(需要魔法) 原题(不需魔法) 强制在线做法 \(O(n \log n)\) 考虑每一次标记点：只会影响其子树中的点 所以使用DFS序+线段树就可以辣！ 离线做法 \(O(n \log n)\) 考虑将每一次标记的时间记录到点上 然后使用倍增 \(LCA\) 的思想向上倍增 离线做法 \(O(n ......

题目背景 翰翰 18 岁生日的时候，达达给她看了一个神奇的序列 $ A_1,A_2,\dots ,A_n $ 。她被允许从中选择不超过 $ M $ 个连续的部分作为自己的生日礼物。 翰翰想要知道选择元素之和的最大值。 你能帮助她吗？ 解题思路 可以先合并序列中连续的同为正或负的值，使原序列变为一个一 ......

题目链接 description 给定一个长度为 \(n\) 的数组 \(a\)，求有多少对 \(i,j,k(1\leq i<j<k\leq n)\) 满足 \(a_k-a_j=a_j-a_i\) \(n\leq 10^5\) 值域大小 3e4. solution 三个数，看起来就不好用数据结构维护 ......

\(f_{i,j}=f_{i-1,j-1}+f_{i-1,j+1}(j+1)\) 看成生成函数就有 \(F_n=xF_{i-1}+F_{i-1}'\)，思路是凑微分，想凑出一个 \(G_i\) 是和 \(F_i\) 有关的，然后 \(G_i\) 有比较简单的形式。 这里就 \(G_n=F_n\tim ......

题目链接 description 厉害题。 给定一棵树，按照题面要求求一个错误点分治的期望执行次数。（不想描述题面了qwq） solution 考虑拆开计算每个点期望几层点分治后被删除。这个期望值显然就是它对答案的贡献。 我们不妨以这个点为根，那么相当于要求每次删除一个未被删除的点的子树，求删完的期 ......

题目链接：[https://hydro.ac/d/bzoj/p/3732](https://hydro.ac/d/bzoj/p/3732) 题目大意： 给定一个图，每次询问两个点 $u$ 和 $v$，在 $u$ 到 $v$ 的所有路径中找一条路径，且这条路径上的所有边的边权最大值最小。 解题思路： ......

https://hydro.ac/d/bzoj/p/3569 实际上，考虑类 tarjan 的过程，从这方面入手能更快地有思路。 考虑先找一棵 dfs 树，那么对于未被删去的树边，我们并不需要管。 若对于一条被删去的树边，那么需要底下能返祖！如果底下返不了祖，那么在这里一定就不连通了。换言之，底下的 ......

### 题目大意 对于正整数 $n$，定义 $f(n)$ 为 $n$ 所包含质因子的最大幂指数。例如 $f(1960)=f(2^3 \times 5^1 \times 7^2)=3$，$f(10007)=1$，$f(1)=0$。 给定正整数 $a,b$，求下式的值： $$\sum^{a}_{i=1} ......

##**题目描述** 给你一个$n$元一次方程，判断是否有解，方程给出的格式为 $a-b=c$ ##**思路** 这道题看上去是一道题目看上去就是判断给出条件是否有矛盾，所以就自然而然的可以使用带权并查集 但是因为~~我太懒了并且~~这道题目要求使用**差分约束系统**进行求解，于是就需要将题目转化 ......

### 简述题意 给出一个长度为 $n$ 的序列 $A(A_1,A_2,\dots,A_n)$。如果序列 $A$ 不是非降的，你必须从中删去一个数，并重复这一操作，直到 $A$ 非降为止。求有多少种不同的操作方案，答案模 $10^9+7$。 ### 题面转换 ......

[原题](https://vjudge.net/problem/%E9%BB%91%E6%9A%97%E7%88%86%E7%82%B8-3364) 简化题意：有一棵 $n$ 个点的树， $q$ 组询问，每次询问回答两点间的距离。 令 $dis[i][j]$ 表示 $i$ 到 $j$ 的距离，根节点 ......

https://vjudge.net/problem/%E9%BB%91%E6%9A%97%E7%88%86%E7%82%B8-3337 # 题意 试维护一个序列，支持以下 $11$ 种操作： | 输入格式 | 说明 | 示例 $a = (5, 2, 6, 3, 1, 4)$ | | : : | : ......

[link](https://hydro.ac/d/bzoj/p/2064) 通过数据范围，容易想到应该是将状态压缩。我们发现合并操作是容易简单描述的，而分裂比较复杂。分析能得到，初始的状态要达到结束状态，我们可以先合并再分裂，这样做答案不会更差（想想应该很容易理解），由于最后几次都是分裂操作，等价 ......

在硬盘里翻到了当时没推完的这个题，今天补完了最后几步。 题目链接：https://hydro.ac/d/bzoj/p/4321 对任意相邻两个元素差的绝对值不为 $1$ 的 $n$ 阶排列计数。 $\mathcal{O}(n^2)$ 做法是考虑按照值域由小到大逐步插入，记录 $f_{i,j}$ 为长 ......

长链剖分优化 DP 板子题了，但是虽然是板子这个转移方程也很难想。 ## problem 树。求 $\sum_{1\leq i 点击查看代码 Rename $height,len\to hei$，$g\to h$。 ``` #include #include #include #include us ......

先说思路： 因为我们是比对较短的$B$与较长的$A$的子串，所以我们求不变的$B$的$next$ 对于这道题我们可以使用树状数组查询前缀和维护数的排名。 对于相同的数我们查询的排名是有误的，因此不仅要比对小于等于该数的前缀和，也要比对小于该数的前缀和。 如:对于$A=2$ $2$,$B=1$ $2$ ......

[题目](https://tg.hszxoj.com/contest/35/problem/5) ```cpp #include #include #include #include #include using namespace std; int N, L, K; double f[210][2 ......

> 赛时公告 > > 现在呢？：现在有弹窗了吗 「2023-07-19 16:45:07」 此时无声胜有声。 ### F.「BZOJ2406」矩阵 http://222.180.160.110:1024/contest/3825/problem/7 这是头一次见识到把矩阵和网络流结合在一起的题目。不 ......

考虑设计一个哈希函数 $hash(x) = f(x) \times base^x$。 其中 $f(x)$ 表示 $\sum_{j=1}^{i-1} [j #define int unsigned long long #define lowbit(x)(x&(-x)) using namespace ......

# BZOJ #3784. 树上的路径 ## 题意 给一颗树，求所有路径长度中前 $k$ 大。 ## 题解 首先对于前 $k$ 大，我们有一个常见的方法，二分。 二分第 $k$ 大的路径长度，然后使用点分治统计，点分治内部还要二分，所以时间复杂度 $O(nolg^3n)$ 。 二分显然是行不通了，想 ......