【拾题杂谈】LuoguP4503 企鹅QQ
题面大秦为你打开题目传送门
题目描述两个字符串相似的定义：当且仅当这两个字符串等长且恰好只有一位不同。
例如“Penguin1”和“Penguin2”是相似的，但“Penguin1”和“2Penguin”不是相似的。
给定N个字符串，判断它们有多少对是相似的。
给定的字符串长度均等于L，且只包含大小写字母、数字、下划线以及 ‘@’ 共64种字符，而且不存在两个相同的字符串。
思路由于每个字符串的长度相当的小，也就说，我们完全可以枚举那个不一样的位，哈希求最长连号时顺便统计即可。
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include<bits/stdc++.h>using namespace std;typedef unsigned long long ull;const ull P = 131;int n, L;char s[30010][210];ull hsh[30010][210];ull power[210];u ...
【拾题杂谈】LuoguP6739 Three Friends
题面大秦为你打开题目传送门
题目描述有三个好朋友喜欢在一起玩游戏,A君写下一个字符串S,B君将其复制一遍得到T,C君在T的任意位置(包括首尾)插入一个字符得到U.现在你得到了U,请你找出S.
思路我们直接，大力枚举这个插入的字符，然后大力哈希判断即可。
代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include<bits/stdc++.h>using namespace std;typedef unsigned long long ull;const int N = 2e6 + 10;const int B = 31;ull Power[N];int n;string s;ull hsh[N];inline ull Hash(int l, int r) { return l <= r ? hsh[r] - ...
【拾题杂谈】HDU1083 Longest Common String
题面大秦为你打开题目传送门
题目描述给定两个字符串，请找出它们的最长公共子串。
思路由于本人不会后缀数组，所以我们就哈希淼过罢。
直接大力二分哈希找长度，搞定。
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102#pragma GCC optimize(2)#pragma GCC optimize(3, "Ofast", "inline")#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef __int128 int128;typedef unsigned long long ull;namespac ...
【拾题杂谈】UVA10298 Power String
题面大秦为你打开题目传送门
题目描述求出一个字符串最短的循环节个数。
思路不难想到 KMP，KMP 的 next 数组的定义就是长度最长且相等的真前后缀，直接去找 $n-next[n]$ 这个长度就是我们要找的最短循环节长度，用总长除以他即可（别忘了前提是得整除）
代码1234567891011121314151617181920212223242526272829303132333435363738#include<bits/stdc++.h>using namespace std;const int N = 1e6 + 10;char s[N];int n;int nxt[N];inline void Input() { scanf("%s", s + 1); if(s[1] == '.') return exit(0);}inline void InitNxt() { for(int i = 2, j = 0; i <= n; i++) { while (j & ...
【算法介绍】字符串算法
算法简介：玉颗珊珊月中落这篇文章是字符串算法的大集合，会提到字符串哈希，字典树，KMP以及AC自动机等常用算法。字符串哈希作为非常常用的基本手段，是读者不得不会的一种算法。KMP 算法可以快速地经行字符串的匹配、比对，以及他和字典树的结合体，AC自动机，都是非常重要的知识点。
算法演示：云台团团降芦菔字符串哈希：妙受琼阁那么作为最最基础的，这个字符串哈希应该最先讲。字符串哈希的主要思路，就是把这个字符串看成一个高进制数，从而进行比对的一种哈希算法。
那么说到把字符串转化为高进制数，不难想到位值原理，就是说每一位的值都是不一样的，对于 $B$ 进制数的第 $i$ 位（个位算作第 $0$ 位，十位是第 $1$ 位，以此类推）这一位上的 “ $1$ ” 表示的是 $B^i$ 。
那么常规的，我们考虑到数字上的一些习惯，我们不妨也设这个字符串数字的左边是高位，右边是地位，那么如何去哈希呢？不难想到了其实：
hash_i = hash_{i - 1}\times Base + Hash(s_i)这一个式子中，$hash_i$ 表示前 $i$ 位的哈希结果，$Base$ 表示这个字符串数字是几进 ...
【拾题杂谈】HDU4064 Carcassonne
题面大秦为你打开题目传送门
题目描述小朋友要玩，卡卡颂。
在开始游戏之前他们要拼地图，有 $n$ 行 $m$ 列的格子，每个格子上有一个小方块，每个小方块的四条边可能是城市 $(C)$ ，道路 $(R)$ 或者空地 $(F)$ 。现在要求旋转这些小方块，使得相邻的小方块对应的边上是相同的建筑。
问有多少种旋转方案，不准对方块翻转，不准交换方块的位置。
思路这题也是直接一眼轮廓线DP，直接处理出所有方块旋转以后的值，然后处理出这个轮廓线边缘的所有值，由于三进制的计算十分的复杂，我这里就直接用了字符串来处理。我用 $1$ ~ $m$ 表示这个轮廓线的底边的值，再用 $m + 1$ 表示这个轮廓线突出来能看到的这个右边的边（如下图）
这样就简单了，直接递归做就可以了，算是一个非常玄学的代码了，，
代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777 ...
【拾题杂谈】HDU4804 Campus Design
题面大秦为你打开题目传送门
题目描述有 $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 ...
【算法介绍】轮廓线DP
算法简介：晨曦酒庄的大公子轮廓线 DP 作为状压 DP 的一大变种，难度极高，模板即是紫题，这里浅浅的讲一讲。
算法演示：清算黑暗的炎之剑例题选讲：钢铁炽焰用宽为 $2$ 高为 $1$ 的砖头去平铺一个宽为 $w$ ，高为 $h$ 的矩形，问有多少种不同的方案。
如下图所示，平铺 $4\times2$ 的有 $5$ 种方案， $3\times2$ 有 $3$ 种方案。
例题思路：流火焦灼这就是一道轮廓线 $\tt DP$ 的模板题，我们设一个轮廓的状态为这一行的某一个点有或没有填充，用二进制表示。
那么首先可以列出状态：$dp[i][mask]$ 当第 $i$ 行的轮廓长这样的时候，方案的数量。
这里定义一下我们所谓的《第 $i$ 行轮廓》当我们枚举到点 $(i,j)$ 的时候，轮廓长这样：
那么递推怎么递推呢？我们只考虑当前的这一个点如何填充的话，那么不重不漏的考虑应该只需要讨论以我这个点为右下角的横竖两种摆法。那么其实转移方程也好想，我们枚举一个 $m ask$ 表示上一行的轮廓，那么如果上面那一行未被填充，这里就是竖着排，不然排不满；如果上一行的这里已经填充，那么我这个位置就 ...
【拾题杂谈】517八段第六课B
题面题目链接大秦 为你打开 题目传送门
备用题面在二分图中，所有点被划分成了两个不相交的集合 $A$ 和 $B$ ，每条边都恰好连接着某个 $A$ 和某个 $B$ 。一个匹配是一个边集，满足没有任何两条边有相同的端点。我们称一个匹配 $M$ （不一定是最大匹配）覆盖了点集 $V$ 当且仅当 $V$ 中的每个点都是M中至少一条边的端点。
给定一个二分图，每个点有一个正整数权值。定义一个点集的权值为其中所有点的权值之和。
给定一个参数 $t$ ，请统计有多少点集 $V$ ，满足 $V$ 的权值不小于 $t$ ，且 $V$ 被至少一个匹配 $M$ 覆盖。
思路考虑当前合法的一个点集s，如果他合法，那么一定有一个完备匹配的点集包含这个点集，也就是两边都满足hall定理的话这两边拼起来的点集也满足要求
所以分别状压两边点集用hall定理转移判断当前点集是否合法，然后分别对两边点集的权值和排个序双指针扫一下计算答案即可
代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484 ...
【拾题杂谈】517八段第六课C
题面题目链接大秦 为你打开 题目传送门
备用题面有 $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 ...
