祝馀宫

题面题目描述​ 今有 $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 ...

题面：残缺的序列（Seq.cpp）题目描述​ 很久以前，有一个长为 $n$ 的排列 $P$ 。随着时间的流逝，$P$ 中的一些数字遗失了，只能看清 $m$ 个数（这 $m$ 个数的相对位置不会发生变化)。​ 现在我们想通过这 $m$ 个数来还原排列 $P$ 。可能的 $P$ 也许不是唯一的，你只需要输出所有可能的 $P$ 中字典序最小的那一个。​ 字典序：对两个同样长的序列 $A,B$ ，如果他们的前 $k$ 位相同，且 $A_{k+1}B_{k+1}$ ，则称 $A$ 的字典序大于 $B$ 。 思路贪心，小的放前面 代码略

题面​ 小C喜欢步行，只有缓慢的步行，小C才能沉浸于其中，享受旅途中那些美好的瞬间。​ 小C来到了一座新的城市生活，这座城市可以看成 $n$ 个点，$n-1$ 条长度为 $1$ 的无向边连接的连通图，也就是说这个城市的结构是一棵树。小C计划在这个城市旅行，他对这个城市的每一个节点都进行了初步的了解，并制定了一个旅行计划，他按照自己的兴趣等因素，为每一个节点设定了游览次数 $v_i$，表示他计划在第 $i$ 个节点游览多少次。​ 在这之后，小C想要找出一个游览序列。游览序列是一个长度为 $S=\sum v_i$ 的序列，对于 $i∈[1,n]$ ，$i$ 在序列中出现 $v_i$ 次，设这个序列为 $A$ 。确定序列后小C将会沿着 $A_1,A_2,…,A_S$ 的顺序步行游览，每次从一个点走最短路径到下一个点，并最终从 $A_S$ 返回 $A1$ ，游览序列中相邻的两位以及 $A_S$ ，A可以相同，这个时候小C的步行距离为0。小C喜欢步行，因此他希望他的总步行距离尽可能长。小C发现这一座城市还会时常发生交通管制事件，在这样的情况下，一条原有的 ...

题面​ 小 B 忘记做作业了！昨天的作业是对 $n$ 个不同的数从小到大进行排序，然而小 B 作业本上的数依旧是乱序的。老师正在检查作业，还要检查 $m$ 个同学就要到达小 B 这里了，检查每个同学的时间都是 $t/m+10^{-100}$ 秒( $t$ 为本题时限)。 ​ 小 B 知道，自己的作业如果做的太差，一定能得到和老师谈心的好机会。不过好在，老师已经把答案写在了黑板上,因此这时小 B 的作业可以看成一个长度为 $n$ 的排列 $a_1,a_2,\dots,a_n$ ，$a_i$ 表示小 B 作业中第 $i$ 位的数在 $n$ 个数中是第 $a_i$ 小。而且老师也公布了评分的标准：按字典序评分。也就是说对于两种排序方式，分别为 $p_1,p_2,…,p_n$ 和 $q_1,q_2,…,q_n$ ，设 $x_0 = min\{x|p_x ≠q_x\}$ ，那么第 $x_0$ 位较小的那个排序方式可以获得更高的分数。 ​ 由于数字很多，抄已经来不及了。于是小 B 打算使用交换的方式，在老师检查到每个同学的时候，小 B 都会观察出一个区间 ...

题面题目描述求：$\sum\limits_{i = 0}^{N}\sum\limits_{j = 0}^{M}i\or j$ ，其中 $\or$ 表示按位或运算。 思路因为或是按位操作，不难想到计算每个二进制位的贡献，那么可以记： $n1[i]$ 为在 $0 -n$ 中第 $i$ 位为 $1$ 的有多少个。 $m1[i]$ 为在 $0-m$ 中第 $i$ 位为 $1$ 的有多少个. 结果即为 $n1[i]\times m+m1[i]\times n-n1[i]\times m1[i]$ 。 代码1234567891011121314151617181920212223242526272829303132333435363738#include<bits/stdc++.h>using namespace std;typedef long long ll;const int P = 1e9 + 7;ll n, m;void Input() { scanf("%lld%lld", &n, &m);}ll count ...

题面题目描述请你将一个 $16×16$ 的数独填写完整，使得每行、每列、每个 $4×4$ 十六宫格内字母 $A$ ~ $P$ 均恰好出现一次。 保证每个输入只有唯一解决方案。 输入格式输入包含多组测试用例。 每组测试用例包括 $16$ 行，每行一组字符串，共 $16$ 个字符串。 第 $i$ 个字符串表示数独的第 $i$ 行。 字符串包含字符可能为字母 $A$ ~ $P$ 或 $−$（表示等待填充）。 测试用例之间用单个空行分隔，输入至文件结尾处终止。 输出格式对于每个测试用例，均要求保持与输入相同的格式，将填充完成后的数独输出。 每个测试用例输出结束后，输出一个空行。 思路不多说了，纯模拟 代码一次纪念我有史以来写过最长的模拟题代码（230行） 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990 ...