祝馀宫

题面大秦为你打开题目传送门 题目描述小朋友要玩，卡卡颂。 在开始游戏之前他们要拼地图，有 $n$ 行 $m$ 列的格子，每个格子上有一个小方块，每个小方块的四条边可能是城市 $(C)$ ，道路 $(R)$ 或者空地 $(F)$ 。现在要求旋转这些小方块，使得相邻的小方块对应的边上是相同的建筑。 问有多少种旋转方案，不准对方块翻转，不准交换方块的位置。 思路这题也是直接一眼轮廓线DP，直接处理出所有方块旋转以后的值，然后处理出这个轮廓线边缘的所有值，由于三进制的计算十分的复杂，我这里就直接用了字符串来处理。我用 $1$ ~ $m$ 表示这个轮廓线的底边的值，再用 $m + 1$ 表示这个轮廓线突出来能看到的这个右边的边（如下图） 这样就简单了，直接递归做就可以了，算是一个非常玄学的代码了，， 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777 ...

题面大秦为你打开题目传送门 题目描述有 $n\times m$ 个格子的矩形，有些格子已经填充，其余格子用 $1\times 2$ 、 $2\times1$ 、$1\times1$ 的木块去填充，其中 $1\times1$ 的木块的使用个数必须 $≥c$ 且 $≤d$ ，$1\times2$ 和 $2\times1$ 的没有限制，求能把矩形都填满的方案数。 思路首先出门右转这道题的削弱版。 然后这道题就简单了，直接在那道题的基础上，增加一维，然后多处理一个已填充和 $1\times1$ 的转移。 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293// #pragma GCC optimize(2)// #pragma GCC optimize(3, "Ofast&quo ...

题面题目链接大秦 为你打开 题目传送门 备用题面在二分图中，所有点被划分成了两个不相交的集合 $A$ 和 $B$ ，每条边都恰好连接着某个 $A$ 和某个 $B$ 。一个匹配是一个边集，满足没有任何两条边有相同的端点。我们称一个匹配 $M$ （不一定是最大匹配）覆盖了点集 $V$ 当且仅当 $V$ 中的每个点都是M中至少一条边的端点。 给定一个二分图，每个点有一个正整数权值。定义一个点集的权值为其中所有点的权值之和。 给定一个参数 $t$ ，请统计有多少点集 $V$ ，满足 $V$ 的权值不小于 $t$ ，且 $V$ 被至少一个匹配 $M$ 覆盖。 思路考虑当前合法的一个点集s，如果他合法，那么一定有一个完备匹配的点集包含这个点集，也就是两边都满足hall定理的话这两边拼起来的点集也满足要求 所以分别状压两边点集用hall定理转移判断当前点集是否合法，然后分别对两边点集的权值和排个序双指针扫一下计算答案即可 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484 ...

题面题目链接大秦 为你打开 题目传送门 备用题面有 $n$ 个箱子编号从 $1$ 到 $n$ 。 它们的长宽高分别为：$w_1,w_2,w_3,…,w_n$ ；$l_1,l_2,l_3,…,l_n$ ；$h_1,h_2,h_3,…,h_n$ 。对于两个箱子 $i,j$ ，如果 $w_i<w_j,li<lj,hi<hj$ 同时成立。那么可以把 $i$ 套进 $j$ 中。 一个大箱子最多可以直接套一个小箱子，箱子不能旋转。 问最少可以变成多少个箱子。 思路由于只能套一层，所以说这个就是最大独立集问题了，，，然后就又双叒叕是模板题。。。 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788#include<bits/stdc++.h>using namespace std;type ...

题面大秦 为你打开 题目传送门 题目翻译军队要开始演习了。有 $N$ 名队员，从 $0$ 到 $N-1$ 编号。现在要将队员分成红队和蓝队。它们中有 $M$ 对人是好朋友，如果处于两队中的队员是好朋友，可能会影响到演习的公平性。 请删除几名队员，使得处于两组的队员不是好朋友。 按照队员编号从小到大输出，如果有多组合法解，输出字典序最小的一个。 思路很简单，我们首先记录一个没有修改过的最大匹配，然后删除某一个队员后，如果最大匹配变小了，这个点就一定是答案之一。 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412 ...

题面大秦为你打开题目传送门 题目描述今年高考后，老师在班上做了一个关于学生成绩的调查。这个班有 $n$ 个学生，从 $1$ 到 $n$ 进行编号。学生们不想告诉老师他们的确切分数，只告诉老师他们在省里的排名。 老师问了所有的学生之后，发现有些学生没有说实话。例如，学生 $1$ 说他在 $5004$ 到 $5005$ 之间，学生 $2$ 说他在 $5005$ 到 $5006$ 之间，学生 $3$ 说他在 $5004$ 到 $5006$ 之间，学生 $4$ 说他也在 $5004$ 到 $5006$ 之间。这种情况显然是不可能的。所以至少有一个人说了谎。 因为老师认为他的学生大多数是诚实的，他想知道最多可能有多少学生说真话。若有多解，输出字典序最大的。 思路首先这是一眼最大匹配，但是如何做到字典序最大呢？因为匈牙利算法的特性，我们直接从 $n$ ~ $1$ 去增广求最大匹配就好了。 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556 ...

题面题目链接大秦 为你打开 题目传送门 备用题面给定R行C列的格点，某些格点上有怪物,总共N个。可以在某行或者某列放置大炮，来消灭对应的行或列。 问最少要多少门大炮，才能把这些怪物完全消灭，以及安放的位置。 思路如果把一个怪兽看作行号和列号相连的一条边，那么这时候答案其实就是这个二分图的最小点覆盖。然后就又是模板了 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283#include<bits/stdc++.h>using namespace std;const int N = 1010;int R, C, n;int mp[N][N];int indr[N], indc[N];int ma[N], tma[N];int vis[N];int visr[N], visc[N];void Input() { ...

题面大秦为你打开题目传送门 题目描述一共有 $N$ 个学生（从 $1$ 到 $N$ 编号）跟 $P$ 门课程（从 $1$ 到 $P$ 编号）,每位学生有自己感兴趣的课程，只能选自己感兴趣的课当课代表， 现在要求每个学生至多担任一门课代表，且一门课代表至多只能由一个学生担任，问是否每一门课能配到一个课代表。 思路这不用想了把，，，，一眼二分图最大匹配模板题，，，， 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include<bits/stdc++.h>using namespace std;int p, n;int mp[110][310];int vis[310];int chk[310];void Input() { scanf("%d%d", &p, &n); int m, x; for(int i = 1; i <= p; i++) { ...

题面大秦 为你打开 题目传送门 题目翻译一场NOI比赛即将举行。现在有X名队员，要给该些队员发放T恤。每名队员有一个合适的T恤尺码区间，然后给出每种尺码T恤的数目，问是否每个队员能分配到合适的尺码T恤。 T恤尺码由小到大依次是S(小号)，M(中号)，L(大号)，X(特大号)，T(超特大号)。 思路那么显而易见的，这种队员和衣服对应的关系就是一张二分图，我们发现这里的 $N$ 实在是太太太小了，区区 $20$ ，我们直接用它给我们的区间大力建图，跑二分图最大匹配，搞定。 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495#include<bits/stdc++.h>using namespace std;const int N = 510;const int M = ...