祝馀宫

题意问 $n$ 个点组成的二叉树高度大于 $h$ 的有多少个。 题解设状态为 $dp[n][h]$ 表示 $n$ 个点深度不超过 $h$ 的二叉树数量，那么答案即为 $dp[n][h]-dp[n][h-1]$。 考虑转移： dp[n][h]=\sum_{i=1}^ndp[i][h-1]\times dp[n-i-1][h-1]让后我们设置初始状态为：$dp[i][0]=0, dp[0][i]=1$ 。 转移的含义很显然，就是左边所有 $h-1$ 的方案和右边所有 $h-1$ 相匹配然后多了父亲所以深度加一。 代码123456789101112131415#include<cstdio>long long f[37][37];int main() { int n,h; scanf("%d%d",&n,&h); for(int i=0;i<=n;++i) //初始化 f[0][i]=1; for(int i=1;i<=n;++i) //枚举高度 for(int j=1;j<=n;++j) //枚举节点 ...

题意给定一棵树，删除若干条边，求连通块大小之积的最大值是什么 题解实际上这题有两种做法。一个是贪心，一个是动规，但是我只会DP做法。 设状态为 $dp[u][j]$ 表示与 $u$ 相连的连通块大小为 $j$ 的答案（这里的连通块大小是包裹 $u$ 本身的）。 然后整个子树的答案我们存在 $dp[u][0]$ 里，因为我们发现这个状态实际上是没有实际含义的。 接下来考虑转移，我们枚举一个合并好的前缀，然后往两边分配大小。另外这里合并两个答案的大小统计要留到最后，这是为了防止状态的混淆。 细节看代码。 另外有一个超级大坑，就是转移的顺序，一定要从大的往小的转移，因为要防止数据被覆盖qwq。 代码12345678910111213141516171819void Dfs(int u, int fa) { sz[u] = 1; dp[u][1] = 1; for(int i = G.head(u); i; i = G.nt(i)) { int v = G.to(i); if(v == fa) continue; Dfs ...

T1 总结赛时总结若至题。一眼顶针 题目思路数学，模拟，推公式 题目代码无 T2 总结赛时总结一眼题。典中典。 题目思路打表发现，第一项和第二项的系数是斐波那契数列。预处理出后计算即可 题目代码无 T3 总结赛时总结没有难度 题目思路贪，最小是优先未感染，最大是优先感染 题目代码无 T4 总结赛时总结思路正确，实现失误 ：100 -> 55最后一刻，重新提交： 55 -> 5 R2 -> R5 nerd 题目思路把出生死亡和查询看作事件，按照时间排序。出生优先级大于查询大于死亡。余下模拟。 题目代码无

T1 总结赛时总结若至题。一眼顶针 题目思路上数据结构 map 题目代码无 T2 总结赛时总结贪心策略错误，难度排序排成了满意度排序 题目思路贪，按照难度排序 题目代码1234567891011sort(con + 1, con + c + 1);sort(pro + 1, pro + p + 1);ll ans = 0;ll mx = 0, j = 0;for(int i = 1; i <= p; i++) { while(con[j + 1].first <= pro[i].first && j <= c) { mx = max(mx, con[++j].second); } ans += max(0LL, mx - pro[i].second);}printf("%lld", ans); T3 总结赛时总结水题，典中典。 题目思路不难发现横竖无关，单独处理后合并答案 题目代码无 T4 总结赛时总结完全没有思路，部分分拿满 题目思路对于绝对值考虑分解，情况分 ...

题面原题链接大秦 为你打开 题目传送门 题目翻译定义某数组 $x$ 的权值为 \sum\limits_{i=1}^n\sum\limits_{j=i+1}^n(x_i+x_j)^2现在，给定两个长度为 $n$ 的数组 $a,b$。你可以执行若干次操作，每次操作选择一个下标 $i$，并交换 $a_i,b_i$。求在进行操作之后两个数组的权值之和最小能够达到多少。 数据范围： $t$ 组数据，$1\leqslant t\leqslant 40$。 $1\leqslant n,\sum n\leqslant 100$。 $1\leqslant a_i,b_i\leqslant 100$。 Translated by Eason_AC 输入格式Each test case consists of several test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 40 $ ) — the number of test cases. The following is a descriptio ...

题面题目描述​ 今有 $V$ 只怪物，第只怪物的生命值为 $a_i$。​ 你和另外一位玩家正在合力击杀这些怪物，你的攻击力为 $x$ ，对方的攻击力为 $y$。​ 你们需要轮流对活着的怪物进行攻击，第一个回合是你的回合。被攻击的怪物将会损失攻击它的玩家攻击力的生命值，若此后它的生命值非正，怪物将会死亡，击杀它的玩家得到1分。当不存在活着的怪物时，游戏结束。 ​ 在你的回合，你可以选择攻击任意一只怪物，也可以选择不进行攻击。​ 在对方的回合，对方会选择当前存活的，编号最小的怪物进行攻击。​ 你需要合理地安排你的策略，使得你的得分最大，并求出这个得分。 输入格式​ 输入的第一行包含三个整数 $N,x,y$ 。​ 接下来一行 $N$ 个整数，第个整数为 $a_i$。 输出格式​ 输出一行一个整数 $Ans$ ，表示你最大化的得分 思路

O(n) 做法首先我们一开始设置了 $\tt dp_{i,j}$ 表示考虑到 $\tt a$ 数组的第 $\tt i$ 个，$\tt b$ 数组的第 $\tt j$ 个的答案。 这个就分情况转移： $a_i \lt b_j$ ，可以保留，转移方程：$\min\{dp[i-1][j], dp[i-1][j]+p[i]\}$ $a_i>b_j$ ，不可保留，转移方程：$dp[i-1][j]+p[i]$ $a_i = b_i$ ，可以保留，转移方程：$\min\{dp[i-1][j-1],dp[i-1][j],dp[i-1]+p[i]\}$ 然后发现这个做法显而易见会爆掉，优化。 我们给 $\tt dp$ 数组压一维，变成 $\tt dp_i$ 表示考虑到 $\tt a$ 数组的第 $\tt i$ 个的代价。与原来变化不大。如果 $a_i$ 是 $b$ 数组里面的数字，我们需要转移；如果不是，就直接忽略。转移方程： dp_i = \min\limits_{x=1}^{i-1}\left(dp_x+\sum\limits_{k=x+1}^{i-1}[a_k\gt b_{j-1} ...

题面 ：幸苦的工作（Work.cpp）题目描述​ 在工作中，小明有 $n$ 个任务要完成。第个任务有一个基础时间t和额外时间 $p_i$。（ $t$ 是互不相同的，$p_i$ 也是互不相同的）​ 如果在做任务之前小明已经做了 $k$ 个任务，则做这个任务需要 $t+k·p$ 的时间（因为任务繁重，小明累了）现在小明还剩下的时间为 $T$ ，请问他在这段时间内最多能做多少个任务（假定任务之间没有依赖关系）。（题目保证 $t,p$ 不重） 思路：暴搜 & DP (劣) & DP (std)首先的，暴力枚举每个工作的顺序，求答案。代码略（伪代码也别想要） 然后我们开始考虑正解，这道题，一眼丁真就是 DP 。关键在于怎么 DP 。突然发现有点像背包，而且 $t$ 和 $p$ 不重发现完全是可以在 1000 以内完成，给人物按照 $p$ 排序，跑背包即可。 代码：正解代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#incl ...

题面：均匀的括号（Bracket.cpp）题目描述​ 我们按如下方式递归定义一个合法的括号序列及其深度： 空串是一个合法的括号序列，且深度为 $0$ 。 若 $S$ 是一个合法的括号序列且深度为 $h$ ，则 $(S)$ 是一个合法的括号序列且深度为 $h+1$ 。 若 $A,B$ 都是合法的括号序列，且深度分别为 $h_A,h_B$ ，则 $A+B$（其中 + 表示字符串的拼接）是一个合法的括号序列且深度为 $max(h_A,h_B)$ 。 ​ 若一个括号序列是合法的且深度 $≤L$ ，则称其是一个均匀的括号序列。现在给你一个合法的括号序列 $S$ 及正整数 $L$ ，问要使其均匀，至少要修改其中多少个括号。（容易发现，当 $L$ 是正整数时，至少存在一种方案) 思路：暴力 & 正解（贪心）暴力很简单，直接暴力枚举所有状态，然后把合法的串给和原串匹配，取最小值。 1234567def main() : GetSbit() // 获得 S 对应二进制 ans = inf f ...