一道二分图性质的应用 + 树形DP ？ 看博客里都说是树形DP，但我觉得应该是树上前缀和更加合适一些 题意： 给你一个图，让你删除一条边，使得剩下的图是二分图。 输出可删边数并顺序输出边的序号。 思路： 首先你必须知道判定二分图的充要条件 —— 不存在奇环。 如果只是让你判定二分图的话，倒是随便搜一遍就可以解决的问题。 但是这里必须让你删掉一条边…… 写不来……感觉不好写，最后无奈去看题解了…… 先整理一下判断思路： 1. 如果不存在奇环，那么原图本来就是一张二分图，每一条边都满足条件 2. 覆盖了所有的奇环，并且不能覆盖偶环的所有边 为什么同时不能覆盖偶环，这个我还真没想到，但是在纸上画一画就是很显然的了，同时覆盖奇环和偶环的边删去后，两个环会变成一个新的环，偶数+奇数 还是奇数。所以不能覆盖偶环。 因此得出如下具体实现，随便生成一棵生成树，用树上前缀和计算出每一条树边覆盖的奇环数和偶环数。 如果奇环数量大于 1 ，那么非树边必定不可能是满足条件的，因为非树边最多只能覆盖一个环，两个及以上就是重边了。因此非树边只有在奇环数量等于 1 的…
刚看完，特想大喊一声：“爽！” 真的，光是100层BOSS战对我来说来回看个10遍还是很过瘾！！ 等等，100层BOSS说好不是茅场么？？ 不管是那种应对庞然大物，咬牙切齿挥舞着两把剑，还是在刀刃下切割的肉体，这种激烈的战斗场面真的只有 虚拟的 二次元中才会拥有！！当然整部动漫的战斗场面更是在BOSS战中达到了巅峰！！ 抛开战斗场面不说，情怀分就可以达到满分，两季TV出现的角色都会在这里以各种形式出现，因为要夺取SAO幸存者的记忆，虚拟现实的玩家锐减，角色的出现显得比较自然，在最后BOSS战中又是还原了各自最具有特色的装备，在情怀上也是上升到了极致。 另外在剧场版再次强调了亚丝娜正宫的位置，狗粮发的也是诚意满满，在洗面奶的那个场景亚丝娜居然没有一点脸红，观众席都是一片哗然…… 话说字幕组对亚丝娜的名字翻译总是在亚丝娜和明日香之间来回随机跳跃是几个意思呀……强迫症表示受不了…… 因为有yuna这样的唱歌辅助角色存在，整部影片在音乐上也是无可挑剔的，顺便说一声影片结束后别急着离开，最后放的音乐也是超好听的！！！ 至于剧情方面嘛，我放到最后讲，也因为它只能在及格线吧…
本文基于V站上一个大佬的博文，在此之上的一些启发与思考。 在此先对原作者致敬。 前置 基本上的编程语言的rand函数的实现原理是，通过一个算法，得出一个序列，影响序列生成的因素压缩成若干个变量。 换句话说，若作为影响因素的参数不变，rand所得的随机数是固定的。 为了达到我们 “ 随机 ” 的目的，我们将当前时间作为参数，使得序列有一定的随机性。 关于rand函数的实现，wiki上有详细介绍，传送门 错误的使用 假设我们现在的rand函数是完全意义上的随机。我现在要求一个 [ 0,N ) 的随机数。 一般人包括我自己都是这样使用的 srand(time(NULL)); int r = rand()%N; 但实际上存在一个疏忽的地方，因为存在取模，所以 [ 0, RAND_MAX %N ) 被随机到的概率会比 [ RAND_MAX%N , N )多一次。 而我们严格意义上的随机数是均匀分布的，也就是说这是不被我们所允许的。 尝试解决 其实解决方法很简单，…
后缀数组 + 单调栈好题 网络赛时的后缀数组可以用这个思路解，但是我并不是很会，今天补上。 题意： 给你两个串，问你长度不小于 k 的重复子串的数量。 思路： 若只是对于一个字符串，问它长度不小于 k 的重复子串数量，那么考虑对height根据 k 分组，然后记录一下就可以了，将 height 去重后，每个 height 的贡献为 ( max ( 0, height – k +1 ) ) 个人猜测，后果不计 但这题是两个字符串，我们可以将两个字符串用一个特殊字符连接，并将后缀通过第一个字符串长度区分开来，对于同一个 height 组中，当前的 height 只能跟另一个 height 组相比求 lcp 。 一个可行的方法是，将组内不同的height都记录下来，再对于每一个当前height，我把它跟另一个height组一一求贡献。但是这个复杂度为 ( O…
这种题目就是专门针对我的……
思路简单，所需注意细节多。
题意：
给你每个元素所在集合，问你有多少个，分割，聚集，映射关系。
思路：
首先很直接的思路就是把每个集合的元素都表示出来，进一步的说hash一下，但集合元素多，集合数量也不少，hash有点困难。
考虑将不同集合的所有相同元素用一个元素表示 (这个只要排序去重即可)
那么对于两个存在这个相同元素的集合 A, B，有如下四种讨论情况：
1. A有若干个元素而B没有 —-> 聚集
2. B有若干个元素而A没有 —-> 分割
3. A,B各自存在不同元素是另一个集合不存在的 —–> 不参与讨论
4. 不存在相异的元素 —-> 映射
顺便提示一下集合编号在 int 范围内， 要离散化……
淦
AC Code
#include
一眼以为KMP能解，上去就是一WA…… 但是我还不知道KMP的错误点……可惜看不了提交的代码了…… 这道题因为我在比赛的时候被一道煞笔树形DP卡到了，因为图没清空，所以没什么时间去看，虽然最后还是有一个小时给我，但我还是没有做出来。 比赛的时候天海的解法用到了单调栈，但我看了题解还有另一个非常巧妙的做法。 题意： 给你一个字符串，问你刚好出现 k 次的子串数量。 思路： 看了大佬的题解，只给了一个方程。枚举区间为 k – 1 的 height 数组，也就是 k 的 sa，贡献为 $ max(0, lcp( i , i + k – 1 ) – max(height[ i ], height[ i + k ]) $ 一开始听蒙蔽的，略加思考就察觉到了方程的正确性，对于每个区间的 LCP ，如果跟区间外的后缀一旦有重复的，那么这个公共部分就不能算及在内。因为这个部分就不是刚好出现…
思维题，老实说我并没有想出来，应该说是我想歪了……
看了一个大佬的代码，真的是超整洁，这是我目前见过最整洁的代码。值得借鉴。
题意：
每个点距源点有几条单项路径，路径有个花费和另一个时间。要你买构造来回路径使得中间间隔时间不小于 k 。
思路：
首先按照日期排序，菜鸡第一想到的是按照花费权值排序
在相同日期的路径中找出所有花费权值最小的加入集合并维护其最小。如果集合已满就记录当前日期的花费。
一个道理在正向前往目的地来一次，反向返回来一次。
就得到了当前日期正向的的最小值，当前日期反向返回的最小值。
再正向找出当前日期之前的最小值，当前日期之后返回的最小值，使得中间区间尽可能大，越往中间花费越小。
再枚举间隔区间，将往返花费相加找出最小值就是答案。
AC Code
#include
分治+字典树+MST 综合好题 标题即题意，但是不一样的是边权是点权的异或。 不可能会出什么边权也是给定的完全图最小生成树计数的啦，现在看来，也算是套路题了。 当然点数不能太多………… 不卡常才是一个好题的前提条件。写 Trie 习惯性用了类，虽然慢了一些，但也不至于太慢。 题意： 给你 n 个点的点权，边权为其异或值，要你求出最小生成树，以及最小生成树的个数。 思路： 这道题的核心思想还是分治。 我们对给定区间的点权进行处理，并假设这个区间的前面 k – 1 位全部相同。那么对于第 k 位，我们根据 01 将其划分为两个集合，这时候两个集合的前 k 位分别相同，再对这两个集合分别进行同样的处理。 其正确性不言而喻。 在处理的过程中，我们需要将两个集合之间建边，因为是MST，所以要找最小的边。将其中一个集合插入 字典树，再让另一个集合的每一个点以常数级别的复杂度去找到最小异或值，再更新答案与边数。 最小生成树的个数只要根据乘法原理将边的数量相乘即可。…