zxl的爆零日常（9.29）
......
干紫题！！！
AM
A: 字符串匹配
现定义两个仅由大写字母组成的字符串的匹配程度如下：将某一字符串的首字符与另一字符串的某一字符对齐，然后后面的字符也一一对齐，直至某一字符串的串尾为止。对于每一组对齐的两个字符，若这两个字符相等，则计数。匹配程度为每种对齐方法的计数的最大值。最后计算这个匹配程度的 2 倍，与两串总长度的最大比值。
挺恶心的这题
本题是简单字符串处理，暴力枚举两串匹配的首字母，不断更新最大匹配值即可，最后的答案需要对最大匹配值和两串总长进行辗转相除。
这是基本思路，但还有n多的小细节
- 要用短的去匹配长的
- 由于可能超出范围，所以要正反匹配两次
- 1/1=1
总之就这些玩意儿恶心我了半个多小时，提交地都紫了T_T
B: 树的同构
树是一种很常见的数据结构。
我们把N个点，N-1条边的连通无向图称为树。
若将某个点作为根，从根开始遍历，则其它的点都有一个前驱，这个树就成为有根树。
对于两个树T1和T2，如果能够把树T1的所有点重新标号，使得树T1和树T2完全相同，那么这两个树是同构的。也就是说，它们具有相同的形态。
现在，给你M个有根树，请你把它们按同构关系分成若干个等价类。
还没做，题解明天写
C: 兔子与兔子
很久很久以前，森林里住着一群兔子。
有一天，兔子们想要研究自己的 DNA 序列。
我们首先选取一个好长好长的 DNA 序列（小兔子是外星生物，DNA 序列可能包含 26 个小写英文字母）。
然后我们每次选择两个区间，询问如果用两个区间里的 DNA 序列分别生产出来两只兔子，这两个兔子是否一模一样。
注意两个兔子一模一样只可能是他们的 DNA 序列一模一样。
兔兔那么可爱，为什么要吃兔兔
直接正向哈希，单次询问直接利用前缀和的思想求解就行了
D: Matrix
给定一个M行N列的01矩阵（只包含数字0或1的矩阵），再执行Q次询问，每次询问给出一个A行B列的01矩阵，求该矩阵是否在原矩阵中出现过
和上道题差不多，但是变成了二维哈希
将所有位置哈希值求出来，然后利用相加减求得某个矩阵的值，与原矩阵比较即可。
E: Necklace
有一天，达达捡了一条价值连城的宝石项链，但是，一个严重的问题是，他并不知道项链的主人是谁！
在得知此事后，很多人向达达发来了很多邮件，都说项链是自己的，要求他归还（显然其中最多只有一个人说了真话）。
达达要求每个人都写了一段关于自己项链的描述： 项链上的宝石用数字0至9来标示。
一个对于项链的表示就是从项链的某个宝石开始，顺指针绕一圈，沿途记下经过的宝石，比如项链： 0-1-2-3 ，它的可能的四种表示是0123、1230、2301、3012。
达达现在心急如焚，于是他找到了你，希望你能够编写一个程序，判断两个给定的描述是否代表同一个项链（注意，项链是不会翻转的）。
也就是说给定两个项链的表示，判断他们是否可能是一条项链。
开始想用KMP的，但后来我旁边的巨鉴说了一个思路，然后瞬间就会了
对于两个字符串，如果他们是相同的，那么他们的最小字典序形式也是相同的
所以直接将两个字符串的最小字典序形式求出来，然后进行比较就OK了
比较最好用string型比较（直接a==b）。
F: 周期(Period)
For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as AK ,that is A concatenated K times, for some string A. Of course, we also want to know the period K.
一个字符串的前缀是从第一个字符开始的连续若干个字符，例如”abaab”共有5个前缀，分别是a, ab, aba, abaa, abaab。
我们希望知道一个N位字符串S的前缀是否具有循环节。
换言之，对于每一个从头开始的长度为 i （i>1）的前缀，是否由重复出现的子串A组成，即 AAA…A （A重复出现K次,K>1）。
如果存在，请找出最短的循环节对应的K值（也就是这个前缀串的所有可能重复节中，最大的K值）。
KMPYYDS
题意就是让你去求一个字符串所有前缀的最小循环节，直接KMP的next处理出来就行了
之前有提到过，如果n%(n-next[n])==0,则循环次数为n/(n-next[n])
还是请自行网上查找
PM
A: [JSOI2010]满汉全席
题面太长，链接->[(https://www.luogu.com.cn/problem/P4171)]
开始想的数据怎么小，直接搜索啊，然后开开心心的打了个搜索，然后就WA了
淦
正解：
建图+tarjan求环
根据题干描述，评委的要求为或关系（如果看了题解就可以跳了）
所以，只需要满足其中一种就OK了
将每道菜视作一个点，因为每道菜有2种做法，故一共2n个点（将相应的两个点视作一个点的两种状态）
所以当某个评委的其中一个要求不满足时，便要满足其另一个要求
用图来说就是用不满足要求的那个点的不满足状态去连应满足要求的那个点的满足状态（相当于可以通过这个点推出另外的那个点的状态）
然后就tarjan跑完所有点，如果某一个点的两种状态会同时存在，那就是不行的（因为同一道菜不会以两种不同的做法出现），这时输出BAD
反之则整个体系是相容的，输出GOOD
B: [JSOI2010] 部落划分
聪聪研究发现，荒岛野人总是过着群居的生活，但是，并不是整个荒岛上的所有野人都属于同一个部落，野人们总是拉帮结派形成属于自己的部落，不同的部落之间则经常发生争斗。只是，这一切都成为谜团了——聪聪根本就不知道部落究竟是如何分布的。
不过好消息是，聪聪得到了一份荒岛的地图。地图上标注了 nnn 个野人居住的地点（可以看作是平面上的坐标）。我们知道，同一个部落的野人总是生活在附近。我们把两个部落的距离，定义为部落中距离最近的那两个居住点的距离。聪聪还获得了一个有意义的信息——这些野人总共被分为了 kkk 个部落！这真是个好消息。聪聪希望从这些信息里挖掘出所有部落的详细信息。他正在尝试这样一种算法：
对于任意一种部落划分的方法，都能够求出两个部落之间的距离，聪聪希望求出一种部落划分的方法，使靠得最近的两个部落尽可能远离。
例如，下面的左图表示了一个好的划分，而右图则不是。请你编程帮助聪聪解决这个难题。
研究啥不好，非要研究野人
初看：什么玩意
最后看：最小生成树...
我TM 哔------------（手动消音）
将所有点之间的距离按照从小到大的顺序排序，然后用并查集将他们合并在一起，直到所有都被合并并且数量为K就可以了
最后的答案就是剩余边中最长的那条。
C: [JSOI2010]冷冻波
WJJ喜欢“魔兽争霸”这个游戏。在游戏中，巫妖是一种强大的英雄，它的技能Frozen Nova每次可以杀死一个小精灵。我们认为，巫妖和小精灵都可以看成是平面上的点。
当巫妖和小精灵之间的直线距离不超过R，且巫妖看到小精灵的视线没有被树木阻挡（也就是说，巫妖和小精灵的连线与任何树木都没有公共点）的话，巫妖就可以瞬间杀灭一个小精灵。
在森林里有N个巫妖，每个巫妖释放Frozen Nova之后，都需要等待一段时间，才能再次施放。不同的巫妖有不同的等待时间和施法范围，但相同的是，每次施放都可以杀死一个小精灵。
现在巫妖的头目想知道，若从0时刻开始计算，至少需要花费多少时间，可以杀死所有的小精灵？
明天写
D: [JSOI2010] 蔬菜庆典
题长，链接->[(https://www.luogu.com.cn/problem/P7221)]
明天写
---The End