【2024信友队 - 提高模考】Day 4 提高1 T3：世界杯租房
题面题目描述 南非世界杯组委会指定了在此期间可提供的一些旅馆供球迷租赁，名为阿凡达的即是其中一所。因为阿凡达旅馆房子的数目不超过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天晚入住 ...
【2024信友队 - 提高模考】Day 4 提高1 T2：士兵训练
题面题目描述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 但是我们要最短，不难想到可以 ...
【2024信友队 - 提高模考】Day 4 提高1 T1：蚂蚁
题面题目描述在二维平面坐标轴里面，有 $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$ ...
单调栈
概念：引入单调栈
请先阅读相关知识：单调队列
同样的，单调栈是一个为了维护单调性弹出元素的栈，他从栈顶到栈底是单调的。
模拟：了解单调栈其实和本质单调队列一样。单调栈可以在时间复杂度为 $O(n)$ 的情况下，求解出某个元素左边或者右边第一个比它大或者小的元素。
下面我们以数组 [4, 3, 2, 5, 7, 4, 6, 8] 为例，模拟一下「单调递减栈」的进栈、出栈过程。具体过程如下：
以数组 $[4, 3, 2, 5, 7, 4, 6, 8]$ 为例，遍历顺序为从左到右。
步骤
待插入元素
操作
结果（左侧为栈底）
作用
1
4
4 入栈
$ [4] $
元素 4 的左侧无比 4 小的元素
2
3
4 出栈，3 入栈
$[3]$
元素 3 的左侧无比 3 小的元素
3
2
3 出栈，2 入栈
$[2]$
元素 2 的左侧无比 2 小的元素
4
5
5 入栈
$[2, 5]$
元素 5 的左侧第一个比 5 小的元素是：2
5
7
7 入栈
$[2, 5, 7]$
元素 7 的左侧第一个比 7 小的元素是：5
6
4
7 出栈，5 出栈，4 入栈
...
单调队列
概念：什么是单调队列单调队列，顾名思义就是单调的队列，那有些人就说了 “那你这单调队列和 priority_queue 有什么区别” 区别可大了，首先 priority_queue 是一个堆，其次，单调队列维护单调性的方式可不是把里面的东西排序，而是直接弹出元素。
单调队列的好处就是可以在 $O(n)$ 的时间内知道一个数组所有长度为一个固定值的子区间中的极值。
模拟：单调队列如何维护单调性假设现在我们有一个序列：
A = \{ 1,3,-1,-3,5,3,6,7 \}我们要求他所有长度为 $3$ 的子区间中的最大值，现在我们就假设我们只有一个队列，看看如何得出我们要的答案
123456789101112131415161718192021222324252627282930/*初始值：Q = empty插入 1 ，队列：Q = {1}插入 3 ，由于我们的队首需要是答案，所以把1弹出：Q = {3}插入 -1，-1 < 3 符合队列头部是答案的需求，不用动Q = {3, -1}插入 -3，由于 3 已经超出了规定子区 ...
CF11D - A Simple Task
题面题目链接大秦 为你打开 题目传送门
题目翻译给定一个简单无向图，求里面简单环的个数。
注：简单环是顶点和边不重复的环。
思路一样的，用状态标注经过的点，记录最后一个点，然后更新，如果绕绕绕绕回了走过的点，那就有环。
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include<bits/stdc++.h>using namespace std;int n, m;int mp[20][20];long long dp[1 << 20][20];void Input() { scanf("%d%d", &n, &m); int u, v; for (int i = 1; i <= m; i++) { scanf("%d%d", &u, &v); ...
517七段第六课C
题面题目链接大秦 为你打开 题目传送门
备用题面看不了题目的看下面喵！
有一个矩形状的迷宫，它被分为 $n \times m$ 个位置。有序对（行号，列号）表示迷宫中的位置，行号从 $1$ 到 $n$ 编号，列号从 $1$ 到 $m$ 编号。
从当前位置移动到下一个位置花费一步，而且只有同时满足以下条件才能移动到下一个位置：
1、下一个位置与当前位置相邻（上下或左右，4个方向）；
2、开着的门是可以通行的，但锁着的门不是；
3、不能通过一堵墙。
游戏开始时，所有的门是锁着的，一种类型的钥匙只能打开对应类型的门。只有在拿到对应钥匙之后才能打开相应的门。
经过某格子时，即可获得该格子所有钥匙。
请计算一下从 $(1,1)$ 到 $(n,m)$ 最少要花费几步。
思路典型的走迷宫 BFS 题。但是这次他有门和钥匙，那我们状压的东西也很明显了，就是我们身上有几把钥匙，这样就可以解决门的问题了，其他基本就是最最简单的 BFS 。详见代码。
代码12345678910111213141516171819202122232425262728293031323334353637383940414243 ...
HDU5691 Sitting in Line
题面大秦 为你打开 题目传送门
思路这道题说数字分两种，固定的和非固定的，让你给非固定的排列，让相邻数字的乘积和最大。
同样数据范围很小，$n$ 只有 $16$ ，显然还是状压 DP，状态同样是排好了什么什么数字，最后一个排好的数字是什么。因为我们默认是把要排的数字一位一位排下来，这样就更方便递推。
这道题相对简单，初始化要分情况：
第一个固定，只有固定的数字是第一
第一个不固定，谁都可以是第一个
代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include<bits/stdc++.h>using namespace std;int n;int a[20], p[20];int b[20];int dp[1 << 20][20];void Input() { scanf("%d", &n); ...
POJ3311 Hie with the Pie
题面大秦 为你打开 题目传送门
题目翻译：有 $n$ 个地方（标号 $1$ 到 $n$ ）要从标号为 $0$ 的地方出去，经过所有的地方之后回来，求最短的时间，输入 $(n+1)$ 的矩阵 $a$，$a[i][j]$表示顶点 $i$ 到顶点 $j$ 所需要的时间。
第一行输入一个整数 $n(1≤n≤10)$ 。
接下来 $𝑛+1$ 行，每行 $n+1$ 个整数，表示矩阵中的元素，矩阵中的元素在区间 $[1,1000]$ 内。
思路这道题我们要同时兼顾经过了哪些点（因为要经过所有点），所以最好的方式就是把经过的点存下来，但是想要在递推过程中记录这些东西，有点困难。发现数据范围只有 $10$ 不难想到状压DP。因为状压DP是基于集合的DP，每经过一个点，就在状态中标记。
另外要处理某两个点之间的最短路，因为只有 $10$ 的数据范围，所以这个可以用 floyd 水水过。
此外，在标记每一个点的是否经过，还有一个很重要的元素是最后一个点是哪里。就比如说：
121 4 3 2 1 2 3 4
同样是经过了点 1 2 3 4 但是顺序不一样，路程就可能有变化，另外我们要从最后一个经过的点往 ...
状压DP
概念：引入状压在我们做题的过程中，有很多选或不选的题目，因为递归不好优化代码也长，我们可以使用状态压缩来解决这个问题。
状压状压，是状态压缩的缩写，向上面举的例子，状态就是选或不选，想要把 $n$ 个物品的状态压缩。能想到的就是二进制吧，我们把第 $i$ 个物品的状态放在第 $i$ 位。当然，状压可以不是二进制状态。
运用：熟悉状压比如，我现在要枚举什么什么数量最大的组合，那么使用状压可以写出如下代码。
123456789for(int i = 0; i < (1 << n); i++) { int tot = 0; for(int j = 0; j < n; j++) { if((1 << j) & i) { tot += a[j]; } } ans = max(ans, tot);}
复杂度 $O(n\times2^n)$ 这就是状压的最基本运用。
拓展：状态压缩DP某一些 DP 的数据范围比较小，大概是 ...
