祝馀宫

题面 ：幸苦的工作（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 ...

题面题目描述　　南非世界杯组委会指定了在此期间可提供的一些旅馆供球迷租赁，名为阿凡达的即是其中一所。因为阿凡达旅馆房子的数目不超过26，所以它们可以用26个大写字母表示。有一天，刘经理的电话响了，他接到了一个租赁房屋的请求，要求从6月12日晚起租到6月19日中午。于是他察看了预定表，但是并没有发现一间房屋能够直接满足要求。比如房主可能因为一些私人原因需要留在自己的房子中，所以这个游客不得不在其中的一间先住上几天再搬到另一间住上几天。他详细检查了预定表后，对旅客说：“我将你先在B安置3天，再将你安排到F去度过剩余的旅途。”　　你的目标是使得游客从一间房屋搬到另一间房屋的次数最少。　　注意在旅馆的计费中，总是将某一天的晚上到第二天的中午视作一天。　　　 输入格式：　　输入文件包括多组数据。每组数据输入文件第一行包括两个整数M和N。M表示日程表上的天数，N表示公寓的数目。天数不超过100天，从1开始计数，公寓不超过26个，从A开始计数。接下来M行，每行包括N个字母，表示从第i天晚到次日中午，该公寓是否已经被出租，X代表被出租，O代表未被出租。最后一行包括两个整数s,t，代表旅客从第s天晚入住 ...

题面题目描述N个士兵排成一队进行军事训练，每个士兵的等级用1…K范围内的数来表示，长官每隔1小时就随便说出M个等级a1,a2…am（1≤ai≤K，M个等级中允许有重复），如果这M个等级组成的序列是排成一队的N个士兵等级序列的子序列，那么训练继续；否则训练结束。长官想知道，M至少为多少时，训练才有可能结束。例：士兵等级序列为1 5 3 2 5 1 3 4 4 2 5 1 2 3，长官说出的等级序列为5 4，那么训练继续，如果长官说出的等级序列为4 4 4，那么训练结束。 输入格式：第一行为两个整数N和K（1≤N≤100000，1≤K≤10000），下面N行，每行一个数，按队伍顺序表示每个士兵的等级。 输出格式：包括一行，只包含一个数M，表示当长官至少说出M个等级的时候，训练才有可能结束。 思路首先看到这道题，先简化题意：找到最短的不是该数列子序列的数列，元素都得在 1 ~ k 里面选 第一个比较傻的想法是：数量最少的数字数量 + 1，显然是不对的。因为假设我就两种状态，1 和 2 然后有 114514 个 1 和 2，那么数数字数量加一答案就是 114515 但是我们要最短，不难想到可以 ...

题面题目描述在二维平面坐标轴里面，有 $N$ 只蚂蚁，第i只蚂蚁所在的点的坐标是 $(x_i, y_i)$ ，坐标都是整数。所有蚂蚁的移动速度都相等，都是每秒移动 $1$ 个单位。每只蚂蚁都有一个固定的移动方向，是如下4种方向之一，都是平行于坐标轴的： $\tt N$ 表示向北（即朝上）， 则 $y$ 坐标正方向。 $\tt E$ 表示向东（即朝右）， 则 $x$ 坐标正方向。 $\tt S$ 表示向南（即向下）， 则 $y$ 坐标负方向。 $\tt W$ 表示向西（即向左）， 则 $x$ 坐标负方向。 当 $2$ 只或多只蚂蚁在某个时刻碰（不一定是整数时刻）撞到一起，那么这些蚂蚁都会立即消失。 例如蚂蚁 $A$ 的初始位置是 $(0, 0)$ 且方向是向东，蚂蚁B的初始位置是 $(1, 0)$ 且方向是向西，那么 $0.5$ 秒后，两只蚂蚁会在点 $(0.5, 0)$ 处碰撞，两只蚂蚁瞬间都消失。当所有的碰撞结束后，还有多少只蚂蚁存在？不管蚂蚁最终移动到哪里，只要没有消失，都算是存在。 输入格式：第一行，一个整数 $N\ (1 ≤ N ≤ 50)$。第二行，一个长度是 $N$ ...