$Day-7$停课了，好耶！可以颓七天了 今天打$lmki$神仙出的模拟赛，被其他学校神仙暴虐/kk $100+40+40+0$我是什么fw $t1$博弈论，还是挺好看出结论的。 $t2$有点懵，随便打了一个搜索和一个部分分。考完后才知道这是$lmki$自己出的题目，正解是$dp$+树状数组优化，还 ...

题目描述洛谷 题解题目中有多个生产者，考虑建一个虚点连向所有的生产者，这样保证了图连通。显然我们要按照拓扑序处理每个节点。 一个生物死亡只有当且仅当所有指向它的生物死亡，如果它的入度为$1$比较好处理，但如果大于$1$呢？ 让捕食者向被捕食者再建一条边，当遍历到一个捕食者有多条连向它的被捕食者的边时 ...

题目描述 题解一种显然的做法是$dfs$枚举所有路线，但这样时间复杂度爆炸。注意到$n<=100$，考虑记忆化，记录$dp[i][j][3]$表示到坐标$(i,j)$走了$s$ $mod$ $3$所需的最小花费。 一个小优化是将$dfs$改为像$bfs$的搜索，优先拓展花费小的状态。 Code ...

题目描述洛谷 题解由于题目不强制在线，我们可以将所有询问离线解决。 思考如果只有一个询问如何解决？显然可以用二维前缀和搞定。 对于每个询问，我们只需要求出四个点的答案，假设对角坐标（左下和右上）为$(a,b),(c,d)$，我们只需要求出$(a-1,b-1),(c,b-1),(a-1,d),(c, ...

题目描述洛谷 题解？dp方程还是比较好推的吧……但是有一些细节需要注意。 这是我一开始80分的代码 #include <bits/stdc++.h>using namespace std;int read(){ int sum = 0 , f = 1; char c = get ...

题目描述洛谷 CF 题解题目要求对给定的$u$节点的子树进行操作，使其$0$级节点加上$val$，$1$级节点减去$val$，$2$级节点加上$val$，以此类推。 由于对子树进行操作，考虑节点的$dfs$序，计算每个节点第一次被访问和回溯时的时间戳，则它的子树$dfs$序都在这段区间内，由此将树上 ...

题目描述洛谷 CF 题解看到题目问的是最小值的最大值，显然可以二分求解 给出的高度在$10^9$范围内，需要先对高度进行离散化 假如我们二分出了一个$mid$，怎么判断它是否合法？可以这么解决，将所有数大于等于$mid$的数赋为$1$，其余赋为$0$，那么就是判断$[l,r]$之间是否存在一个长度 ...

题目描述 题解首先考虑如何求树上的任意个点连通的边集的总长度的最小值 可以对树上的点进行一次$dfs$求出它们的$dfs$序，将所求点按$dfs$序排序后相邻两点（包括头尾）的距离之和即为使这些点连通的边集的总长度的最小值的两倍 如图（蓝色为各点$dfs$序） 假设我们要让$1,2,3,5$连通 ...

题目描述 题解记$dp[i][j]$表示在以$i$为根的子树中保留$j$个牛棚需要摧毁的最小道路数，显然$dp[i][1]$等于与$i$相连的道路数。 对于所有的$v \in son_{i}$,我们可以枚举在$v$的子树中保留的牛棚树进行转移。方程: $dp_{k,j} = min(dp[k][j ...

题目大意设$F[i]$为斐波那契数列的第$i$项，其中$F[1]=1,F[2]=1$。 给定$a,b$，判断$F[a]$能否整除$F[b]$,如果能输出1，否则输出0 思路先说结论，若$n|m$,则$F[n]|F[m]$。 证明： 首先 $F[n] = F[n-1]+F[n-2]$ $F[n] = ...