蓝桥 题解 巧克力p8769

# [NOI2021] 路径交点 题解 ## 题意 给定一张 $k$ 层的有向图，第 $i$ 层有 $n_i$​ 个顶点，第 ​$1$ 层与第 $k$​ 层**顶点数相同**。对于第 ​ ​$j$ $(1 \leq j using namespace std; const int N = 205; ......

# 题目大意 给定一棵节点个数为 $N$ 的多叉树，求其通过"**左孩子右兄弟**"表示法转化成的二叉树，高度最高是多少。 # 解决思路 首先分辨出此题目是树状DP，并了解"**左孩子右兄弟**"表示法的转换方式，便开始考虑DP的 **状态** **转移** 方程。 ## 状态 由于每个节点由 $1 ......

题目传送门：[[2023牛客多校] Distance](https://ac.nowcoder.com/acm/contest/57360/B) # 题意 对于任意两个元素个数相同的set：A、B，每次可以执行以下两种操作之一： + 将A中的任意元素加一 + 将B中的任意元素加一 $C(A, B)$ ......

题目传送门：[Click](https://www.luogu.com.cn/problem/P4795)。 蒟蒻看见这道题，想了足足一个小时，过后顿有所悟，故作此篇。 首先，看到题目，光是数据就已经达到了 $\operatorname{O}(nm)$ 的级别，再看一看数据范围：$3 \leq n, ......

# - [1] [蓝桥杯 2013 省 A] 剪格子 洛谷P8601 ## 题目描述 如图 $1$ 所示，$3\times 3$ 的格子中填写了一些整数。  **我们沿着图中 ......

## 题意 二维平面上有 $n$ 个点，给你 $m$ 次操作，每次操作可以插入一个点或者询问所有点中距离给定点最近的哈密顿距离。$n,m\le 3\times 10^5.$ ## 分析 这是一道 K-D Tree 的裸题。 而对于这道题，我们还需要考虑插入操作。我们给出两种方式： 1. 按很多题解的 ......

洛谷的 RMJ 总是 UKE，所以这一题是在 ATcoder 上做的，[记录一](https://atcoder.jp/contests/ttpc2015/submissions/44132887)，[记录二](https://atcoder.jp/contests/ttpc2015/submiss ......

## 大意： 给定一个字符串 $s$ 判断 $s$ 是否符合要求。 1. 由数字，`-` 和大写英文数字 `X`，空格组成，`X` 代表 $10$ 且只能在最后出现。 2. 依次相加前面的数字的总和可以被 $11$ 整除，也就是前缀和，而且刚好 $s$ 只有 $10$ 个数字。 ## 坑点： 1. ......

[题面传送门(luogu)](https://www.luogu.com.cn/problem/CF958E1) | [题面传送门(CF)](https://codeforces.com/problemset/problem/958/E1) 本题的翻译好像少了点东西（建议直接阅读英文题面，推荐一个[ ......

一道小清新的思维题！和 $bocchi$ 酱一样可爱的喵 **30 pts** 首先典中典套路：破环成链，数组复制一份。 设 $to[i] = \max(\mathbb j) (j\geq i \wedge \sum_{i \leq l \leq j} a_l \leq k)$ 枚举起始下标，容易想 ......

#Superbull S题解 ###[题目传送门(可点击)](https://www.luogu.com.cn/problem/P4826) #题面 ##题目描述 $Bessie$和她的朋友们正在一年一度的$Superbull$锦标赛中打球，而$Farmer$ $John$负责让比赛尽可能激动人心。 ......

$f_i$ 为变成 $i$ 的期望步数，那么 $f_0=0$，$f_i=1+\sum_{j=0}^{2^n-1}f_j\cdot p_{i\oplus j}$，理解为从 $i$ 走到 $0$ 的期望步数即可。 尝试用集合幂级数描述这个东西，如果不管 $f_0$ 那么就是 $F=F\times P+I ......

[problem](https://www.luogu.com.cn/problem/AT_jsc2019_qual_d) & [blog](https://www.cnblogs.com/liangbowen/p/17604061.html)。 是一道不难想，但是有趣的构造题阿！没有题解，我来一发 ......

[洛谷传送门](https://www.luogu.com.cn/problem/P7074) ## 1.题目大意 给定一个 $n*m$ 的矩阵，矩阵中每个点 $(i,j)$ 都有一个权值 $f_{(i,j)}$。每次可以向上，向下或向右走。问从 $(1,1)$ 走到 $(n,m)$，经过的路径上点 ......

[Link](https://www.luogu.com.cn/problem/P5022) 因为是道NOIP，那么我们不妨按照考场上的策略一点一点想。 先看部分分，有一档有很明显的特征 $n=m-1$ 这显然构成一棵树，对于一棵树，我们想把他按照题目的要求遍历完，一定是像dfs的遍历顺序一样，对于 ......

听说是签到题。 不难看出设x为i二进制个数下1的个数(还是难的)，则a_i=c^x。那么我们只需要考虑所有0到n的个数。 当n为1111时，可以得到为（1+c）^n次方，那么我们把答案看成两部分一部分是1到111...和1000到n， 那么当si位为1时，可以看成是n去掉前一位后再乘以c，递推得到每 ......

这题的物品数量非常小，但是背包的重量非常大，我们采用压缩到二进制位来考虑，因为最多是n*20的数位*个数，并且上一位dp的状态不影响下一位。所以我们设计当前dp的状态为选取了前i位置时候所能获得的最大值。又因为上一维在数组dp时可能会被上一维的影响所以f[min(2*i+d,s)] =max(f[m ......

## 前言 ### 数学符号约定 $\operatorname{lowbit}(x)$：表示 $x$ 的二进制最低位。 $[a,b]$：表示区间 $a\sim b$，其中包含 $a,\,b$ 端点，其区间长度为 $b - a + 1$。 如非特殊说明，将会按照上述约定书写符号。 ### 题目大意 有 ......

## 前言 在这里首先感谢一下题解区的 [FZzzz](https://www.luogu.com.cn/user/174045)，本人的题解思路主要是基于他并给出了自己的理解。 如非特殊说明，本题解中的数学符号原则上与题目中一致。 ## 题目分析 需要转化的喵喵题。 我们需要把原问题转化成一个图论 ......

## 前言 因为本人尚菜，所以本篇文章没有什么数学符号，请大家放心食用。 ## 题目分析 先吐槽一嘴，这个 `o` 表示 `()`，这个 `x` 表示 `)(`，十分形象。 好，我们先观察原序列，容易得出第一条性质： > `ox` 的加入不会让我们不合法的序列变合法，相反，它会让我们合法的序列变不合 ......

## [P3373 线段树模板 2](https://www.luogu.com.cn/problem/P3373) ![image-20230803010844370](https://zeoy-typora.oss-cn-hangzhou.aliyuncs.com/image-202308030 ......

# HDU 多校 2023 Round #5 题解 $\text{By DaiRuiChen007}$ ## A. Typhoon [Problem Link](https://acm.hdu.edu.cn/showproblem.php?pid=7324) **题目大意** > 给一条 $n$ 个 ......

看到树上数颜色，想到树上启发式合并（dsu on tree）。 这题几乎就是树上启发式合并板子了，感觉讲一下算法的原理比较好。 暴力解法显然是对每棵子树 dfs 一遍，求出子树大小 $\operatorname{size}$、子树颜色出现次数的桶 $\operatorname{cnt}$，以及颜色出 ......

一个显然的思路是：在排列 $p$ 的括号串合法的基础上，使得左括号在原括号串中尽量靠左，这样答案更有可能合法。于是我们求出这个原括号尽量靠左的括号串（下文称为“最优括号串”），然后 check 合法性即可。 下文中 $s$ 是排列 $p$ 的括号串。 当 $n=2$ 时，唯一的填法是令 $s_1\g ......

## 前言 ### 数学符号约定 $n$：任意正整数。 $\#$：从未出现过的小写字母。 $\Sigma$：字符集，这里指小写字母集合。 $S$：最终答案的字符矩阵。 其余符号同题目翻译中所写。 如非特殊说明，将会按照上述约定书写符号。 ## 题目大意 构造一个 $N\times M$ 的小写字母矩 ......

https://www.lanqiao.cn/problems/99/learning/?page=3&first_category_id=1&sort=students_count&second_category_id=3 暴力方法 ```python N, K = map(int, input( ......

> 【问题描述】 > 两种糖果分别有 9 个和 16 个，要全部分给 7 个小朋友，每个小朋友得到 > 的糖果总数最少为 2 个最多为 5 个，问有多少种不同的分法。 > 只要有其中一个小朋友在两种方案中分到的糖果不完全相同，这两种方案 > 就算作不同的方案 > > 答案：5067671 ```py ......

大力相应 teacher 要求。 正难则反，考虑求不合法的三元组的数量。 对于一个不合法的三元组，可以发现条件等价于三元组中有一个点出度为 2。记 $m$ 次操作后每个点出度为 $d_i$，答案就是 $\dbinom{n}{3}-\sum\limits_{i=1}^n\dbinom{d_i}{2}$ ......

[题目链接](https://www.luogu.com.cn/problem/P9445) 数据有点水啊，貌似矩阵大小最大只有 $500$，这导致一堆 bitset 乱搞或者暴力啥的无聊解法能过，这里就不多说了，快进到正题。 二维通配符匹配。 首先根据 Rabin Karp 给每种颜色随机一个权值 ......

[洛谷链接](https://www.luogu.com.cn/problem/CF1359A)&[CF 链接](http://codeforces.com/problemset/problem/1359/A) ## 题目简述 共有 $T$ 组数据。 对于每组数据给出 $n,m,k$，表示 $k$ ......