nearby luogu 3047 cows

### [在洛谷中查看](https://www.luogu.com.cn/problem/P2801) ## $1$ 思路： #### $1.0$ 我们考虑使用分块做，但查询操作也不能预处理啊，$c$ 可是 $10^9$ 级别的。 #### $1.1$ 那么让我们来学习一下分块的找 大于/小于 $ ......

[题目链接](https://www.luogu.com.cn/problem/UVA10678) ## 思路 一道简单模拟题。 经过模拟，我们不难发现，牛的活动轨迹是一个椭圆。根据椭圆形面积公式得到 $S = \pi a b$。其中，牛可以到的最左边或最右边时 $a = \frac{l}{2}$， ......

### 题意分析 我们首先想到，枚举贝茜在 $x$ 点，枚举度数大于 $2$ 的点为 $y$。设 $x$ 的度数为 $a$，$y$ 的度数为 $b$。 我们首先发现每个 $x$ 点都有一个初始的贡献为 $a$ 条通往叶子的路径。 如果点 $y$ 到最近的叶子节点的距离大于到 $x$ 的点的距离（农夫 ......

[Problem](https://www.luogu.com.cn/problem/P9345) ### Description 给定一个整数$n$，有一个数组$a$的内容是$1,2,3$……$n$。（不一定按照顺序排列，只保证内容）特别地，我们令$a_{n+1}=1$。 还有一个数组$b$，满足 ......

# Great Cow Gathering G ## 思路 换根dp，[Tree Distances I](https://www.cnblogs.com/ybtarr/p/17632352.html) 强化版，同样的先思考单个的，那么对于子树 $u$ 对于每一个儿子 $v$ 都有：$f_u = f ......

# STEP 1：分析 题目大意：给定一个 8 位数的日期，请你计算该日期之后下一个回文日期和下一个 ABABBABA 型的回文日期各是哪一天。 这一题一眼看出是 P2010 的升级版，所以要先考虑到超时问题，因为如果一天一天地枚举，时间复杂度会非常高，所以我们不能直接枚举。因为题目只要"回文"，所 ......

[Problem](https://www.luogu.com.cn/problem/P3205) ### Analysis 一道分类讨论dp 我们发现本题满足大区间包含小区间，区间之间可以互相推导，符合区间dp。 再看看我们需要记录什么？我们发现哪一个数最后放会影响到决策，所以我们需要记录这一层状 ......

[Problem](https://www.luogu.com.cn/problem/P1725) ### Description 若当前在$pos$位置，每次可以在$[pos+l,pos+r]$区间内任选一个点跳。每跳到一个地方就可以获得这个地方的值，最后跳到位置$pos \geq n$即为结束， ......

### [在洛谷中查看](https://www.luogu.com.cn/problem/P2863) 模板题，缩完点后扫一遍就行了。 巩固基础。 ```cpp #include using namespace std; const int N = 1e4+5; int n,m,dfn[N],lo ......

[原题](https://www.luogu.com.cn/problem/P7154) 我们先思考如果没有极大匹配这个限制该怎么做 ysx曾经说过：dp要先考虑递推顺序 看到这个题的限制$s_i \leq t_i$，可以想到这题要先按照$s_i$和$t_i$的顺序排序 不妨设$dp_{i,j}$表 ......

[Problem](https://www.luogu.com.cn/problem/P1280) ### Analysis 首先，如果一个时间只有一个任务开始，则她必须做。如果一个时间有多个任务开始，她可以选一个去做。我们发现这样的决策是取决于后面的空暇时间，而不是前面。所以在dp的时候需要从后往 ......

[TOC] # 题目 [题目链接](https://www.luogu.com.cn/problem/P4200) # 解题思路 首先，此题有明显的插入、删除、查找，所以必须要使用平衡树。 考虑如何使用平衡树维护每个鸟的状态。发现很不方便，因为鸟的位置改变，整个平衡树的值都要修改。 考虑针对每个节点 ......

记 $f_S$ 为所有人以当前信息推断出 $S$ 这种情况是否合法，$g_S$ 表示假如真实情况是 $S$，应该有哪些人喊出来了。 每一轮中，通过告诉你的 $k$ 条消息可以推断出哪些集合不合法，将其 $f_S$ 赋为 $0$，然后根据新的 $f_S$，有些人可能可以据此喊了，所以根据新的 $f_S ......

注意到： $$\varphi\left(\dfrac{\mathrm{lcm}(i,j)}{\gcd(i,j)}\right)=\varphi\left(\dfrac{ij}{\gcd^2(i,j)}\right)=\varphi\left(\dfrac{i}{\gcd(i,j)}\right)\v ......

[Link](https://www.luogu.com.cn/problem/P9504) 这题我们发现如果直接去枚举生命和法力值显然是不行的，又看到说最小的生命值，不禁想到最短路，但是怎么跑？ 我们令经过一条边之前魔力值为 $k$，那么该边的边权为 $\lfloor\dfrac{w}{k}\rf ......

# 通往奥格瑞玛的道路 ## 题目背景 在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士，他是部落的中坚力量。 有一天他醒来后发现自己居然到了联盟的主城暴风城。 在被众多联盟的士兵攻击后，他决定逃回自己的家乡奥格瑞玛。 ## 题目描述 在艾泽拉斯，有 $n$ 个城市。编号为 $1,2,3,\ldots,n ......

[Problem](https://www.luogu.com.cn/problem/P2014) ### Solution 我们发现本题中有好多主从关系，即要想取用一个儿子必须先取用她的父亲。构成了一个森林，处理不便。 有个小技巧，就是将0号节点参与建树，最后所求节点数就变成了$m+1$，且把森林 ......

[Problem](https://www.luogu.com.cn/problem/P1880) ### Solution 本题还有一个弱化版，见[Luogu P1775](https://www.luogu.com.cn/problem/P1775) 我们发现本题和弱化版唯一区别就是本题有环。 ......

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

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

[Problem](https://www.luogu.com.cn/problem/P1853) ### Solution 刚开始看这道题的时候不自主的想到了[纪念品](https://www.luogu.com.cn/problem/P5662),但其实本题和纪念品还是有区别的。 - 纪念品规定 ......

[Problem](https://www.luogu.com.cn/problem/P5662) ### Description 类似于炒股票，有买进有卖出，**当天可以既买进又卖出无限次**，现在有若干件物品，每件物品都有一个价格，每天每件物品的价格不一致，你初始有$m$元钱，想要通过若干次购进 ......

[Problem](https://www.luogu.com.cn/problem/P1466) ### Description 有一个长度为$n$的数组为$1-n$,求有多少种选择方案使得选择数之和等于序列和的一半 ### Solution 题面翻译成这样是不是就好做了？ 首先，序列和的一半我们 ......

[Link](https://www.luogu.com.cn/problem/P2296) 很简单的一道图论题。 要在一个有向图上找一条 $s$ 到 $t$ 的最短路，要求这条路径上的所有点都满足：该点的所有出边所连点都能到达终点 $t$。 看上去很乱，我们简单分解一下，先在所有点中找到与终点有路 ......

[Problem](https://www.luogu.com.cn/problem/P2340) ### Solution 乍看可能没有思路。我们注意到本题是牵扯到一头奶牛选or不选的问题，非常自然地想到**01背包**。 接下来我们就尝试将本题背景转换成01背包问题。 我们可以将智商转换成容量， ......

[Problem](https://www.luogu.com.cn/problem/P1352) ### Solution 经典树上dp。 我们发现一个节点统计 or不统计答案影响下一级，所以dp时需要加上这个状态。 树上dp虽然名义上叫dp，但一般是基于记忆化搜索实现（ 第二层状态就统计以其为根 ......

[Problem](https://www.luogu.com.cn/problem/P1877) ### Description 共$n$次操作，每次操作有一个值$a_i$,同时给定一个初始值$start$,对于每次操作，可以将值$k$加或减$a_i$($k$初始=$start$),求经过这$n$ ......

[TOC] # 题目链接 [P4592 [TJOI2018] 异或](https://www.luogu.com.cn/problem/P4592) # 解题思路 读完题目首先发现很像最大异或和问题 但是在树上操作 一开始想到树剖 但是树剖有两个 $\log$ ~~但是树剖常数小~~ 考虑`dfs` ......

[Link](https://www.luogu.com.cn/problem/P2420) 看到是树，又多组询问，立马想到类似的求和问题，异或不好理解，我们想求和怎么做，维护 $dis_i$ 表示 $i$ 节点到根的权值和，那么对于 $u,v$ 两点路径上的权值和就是 $dis_u+dis_v-2 ......

[Link](https://www.luogu.com.cn/problem/P6816) **题意** 给定一个小写字母串 $s$，求： - 有多少字符串 $t$ 可以超出头尾地，可重复地覆盖 $s$。 - 在上面的条件下，最短的 $t$；如果有多个，输出字典序最小的。 $|s| \leq 2 ......