- 2024-09-26SpainOI XXIV
GYM105325B题目描述有\(N\)个站,站之间有\(M\)条单向道路。一条路径的代价为:令你经过的边权为\(w_1,w_2,\dots,w_k\),则你的代价为\(w_1\cdotk+w_2\cdot(k-1)+\dots+w_k\)。求你从\(0\)到其他点的最少代价。思路令\(dp_{i,u}\)表示还要走\(i\)条边,当前在\(u
- 2024-09-17骨牌铺方格二
描述有一个大小是2xn的网格,现在需要用2种规格的骨牌铺满,骨牌规格分别是2x1和2x2,请计算一共有多少种铺设的方法。输入输入的第一行包含一个正整数T(T<=20),表示一共有T组数据。接着是T行数据,每行包含一个正整数N(N<=30),表示网格的大小是2行N列。
- 2024-08-19状压 dp
定义在动态规划中,可能存在以“集合”为状态的动态规划,应为集合不易表示,所以通常用一个二进制数来表示集合。具体的,二进制数的第\(i\)位即表示当前集合是否包含第\(i\)个元素。技巧因为许多位运算的运算优先级很迷,所以搞不明白就尽量用括号。二进制操作将\(n\)位二进
- 2024-08-13棋盘覆盖
//372.棋盘覆盖.cpp:此文件包含"main"函数。程序执行将在此处开始并结束。///*https://www.acwing.com/problem/content/374/给定一个N行N列的棋盘,已知某些格子禁止放置。求最多能往棋盘上放多少块的长度为2、宽度为1的骨牌,骨牌的边界与格线重合(骨牌占用两个格
- 2024-07-18闲话 718:1x2 骨牌的矩形覆盖计数
注:以下的\(i\)不在下标时均代表虚数单位,\([n]=\{1,2,...,n\}\)。首先把格子当成点,连一个图出来:上下格子连向上的边,左右格子交替连向左/向右的边。这样求完美匹配方案数即可。这样假设搞出来的邻接矩阵是\(S\)。那么\(ans=Pf(S)=\sqrt{\detS}\)。通过对行的缩放操作(即初等变
- 2024-07-17闲话 717 - LGV 引理的小应用
这是我们的某一天的联考题目:\(n\le500\)。显然使用平面图完美匹配计数可以获得\(O(n^6)\),但是有一种神秘的对路径的双射。当时我们都认为这是超级人类智慧,但是今天看书发现是书上的某个例的题的方法(有不同)。。考虑对正六边形的菱形密铺方案数(上图)。可以等价的问题是完美匹
- 2024-07-09匈牙利算法——棋盘覆盖
题目描述棋盘覆盖给定一个N行N列的棋盘,已知某些格子禁止放置。求最多能往棋盘上放多少块的长度为2、宽度为1的骨牌,骨牌的边界与格线重合(骨牌占用两个格子),并且任意两张骨牌都不重叠。输入格式第一行包含两个整数N和t,其中t为禁止放置的格子的数量。接下来t行每行包含两个整数x
- 2024-06-077-3 sdut-C语言实验-骨牌铺方格
7-3sdut-C语言实验-骨牌铺方格分数20全屏浏览切换布局作者 马新娟单位 山东理工大学斐波那契数列(Fibonaccisequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(LeonardoFibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,很多题目由此衍生而来,骨牌铺方格便是
- 2024-03-04si-shi-liu-c
四十六(C)link考虑第一问。将地图黑白染色,那么每个骨牌占了一黑一白。删去一个骨牌会得到两个空格。由题目知道,这两个空格位置一一对应一个状态。我们只需计数有多少种可能的空格出现的方案。考虑一个骨牌移动,等价于将一个空格从头部前一格移到尾部。那么建图,每个骨牌的头部前
- 2024-02-17P1380 T型骨牌 题解
本题每个位置有$5$种可能,据题中$n,m$均小于五,所以可以用搜索直接过。上代码#include<cstdio>usingnamespacestd;boolmp[15][15];intn,m,ans;intdt[4][5][2]={{{-1,-1},{0,-1},{1,-1},{0,0},{0,1}},{{-1,0},{0,0},{1,-1},{1,0},{1,1}},{{0,
- 2023-11-06Domino for Young
题目给出了一张杨表,要求你能够放上去的最多的骨牌数量。证明看这里。只能说妙蛙!补充一些题解认为显然的证明。任何一张网格图(相邻的点视作有边),按照\(i+j\)(下标)的奇偶性划分,可以证明这是一张二分图(有点显然)。\(\forall(x,y),color(x+1,y)\neqcolor(x,y),...\),因为相邻格子
- 2023-11-052023年11月第一周第二次总结
1.动态规划在我看来动态规划就是用一种缓存机制来保存之前求解的答案,如果要再次用到已经求解过的答案就直接把缓存里面的答案给他而不必再次求解,也就是用空间换取时间那么要解决动态规划问题,最好按照以下步骤来求解用暴力递归来求解问题能用记忆化搜索就先用记忆化搜索
- 2023-09-02CF 1863D 题解
CF1863DTwo-ColoredDominoes题解Links洛谷CodeforcesDescription有一个\(n\timesm\)的棋盘,上面铺着一些\(1\times2\)的多米诺骨牌(横竖均有可能),骨牌之间没有重叠。你需要找到一种染色方案满足以下条件:每个多米诺骨牌一端被染白,另一端被染黑。其他没有骨牌的格子
- 2023-05-26「解题报告」P9195 [JOI Open 2016] JOIRIS
发现上午高强度想题之后下午就啥都不想干了。神秘构造题,我属实是啥也不会了。先把下标改成从\(0\)开始。首先看到格子上的连续\(k\)的骨牌显然能想到将格子\(k\)染色。而由于有删除一行的操作,按照普通的染色方法好像并不好看,所以我们按列染色。这样我们统计每个颜色上的
- 2023-04-25棋盘覆盖问题——分治法
问题描述有一个 x (k>0)的棋盘,恰好有一个方格与其他方格不同,称之为特殊方格。现在要用如下图所示的L形骨牌覆盖除了特殊方格以外的其他全部方格,骨牌可以任意旋转,并且任何两个骨牌不能重复。请给出一种覆盖方式。 样例:输入:输出: 思路——分治法:将一个规模为n的问题分解
- 2023-03-25递推 HDU Problem K 骨牌铺方格
骨牌铺方格TimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSub
- 2023-02-10CF1268B题解
CF1268B题解题目翻译给你一个杨表,用一个有\(n\)个元素的数组\(a\)表示杨表每一列的高度。你需要用\(1\times2\)或\(2\times1\)的骨牌填充这个杨表,求出最多
- 2023-02-042019计蒜之道初赛第一场 A 商汤的AI伴游小精灵(DFS)
Description北京市商汤科技开发有限公司面向青少年研发了一款智能伴游机器人--AI伴游小精灵。一经推出,深受孩子们的喜爱,可爱又机智的小精灵会想出很多有趣的小游戏来启迪
- 2022-11-08CF1368G Shifting Dominoes 题解
CF1368GShiftingDominoes题解题目传送门CF1368GShiftingDominoes题目大意给你一个\(n\timesm\)的棋盘,上面有\(\frac{n\timesm}{2}\)个不重叠的骨牌,你可以
- 2022-11-02骨牌铺方格 SDUT
状态转移方程:dp[i]=dp[i-1]+dp[i-2]。当前行,可能是由上一行转移过来的,那么当前行就只能横着铺,所以方案数是dp[i-1]。当前行,可能是由i-2行转移过来的,那
- 2022-10-25P1282 多米诺骨牌
题意:有一堆多米诺骨牌,骨牌被分为上下两部分,每部分写有1-6的一个数(真的不是骰子吗)。试颠倒一部分骨牌,使得所有骨牌 上部点数之和 和 下部点数之和 之差 最小。求
- 2022-10-11CF1237F 题解
传送门题意给你一个\(n\timesm\)的棋盘,上面已经放了\(k\)个\(1\times2\)的骨牌。对于一个骨牌的每个格子,不能有其他骨牌的格子与它在同一行、同一列。你可以
- 2022-09-23Split Into Two Sets CodeForces - 1702E
SplitIntoTwoSetsCodeForces-1702EPolycarp有一副有n张牌的(数字n为偶数)多米诺骨牌.每张多米诺骨牌上写有两个在1到n之间的数字.请问能否把骨牌分成两