半平面交对偶转凸包树分治归并排序求闵可夫斯基和用李超线段树维护答案。     题意：给一颗树，每条边的边权是一个关于t的一次函数，问你在每个t下树的直径是多少。   如果t是定值，那么就是求直径。求直径的方法除了dfs两遍，还有一个方法是树分治，类似分治法求最大子段和。   考虑树分治，找到重心，枚举所有从重心延伸到每个点的一次函数y=ax+b。这个是比较套路的，先统计每个子树的信息嘛。   统计信息的时候我们先做两个优化：   1、首先能够想到因为题目给出的a,b均正，又让求最大直径。所以只有从重心延伸到叶子节点的一次函数才是有用的。此处可以进行剪枝，仅保留到叶子节点时的信息。   2、每个...

Solution     A   计算机组成原理送分题，本场签到题，构造的方法有很多，最简单的一种就是2147483647再加上一个数，注意-1构造不出来即可。   https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40782114     B   先预处理一个阶乘在不同模系下的值作为hash值，然后判断两个数组hash值的乘积是否相等即可。   https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40782123     C   有两种...

AC才发现打的是道假题，不知道发生了啥…。题意：给你n（n<=4）个模式字符串，然后给你一个长度为l的操作序列，一开始是空字符串，接下来按照操作序列进行操作，问你每个时刻至少再加几个字符，使得你操作的字符串的后缀中出现至少一个模式字符串。（即字符串的结尾出现模式串）预备知识：基于有限自动机的KMP算法构造思想https://blog.csdn.net/unoboros/article/details/33106353因为n<=4，所以想到先对每个字符串建一个KMP“自动机”。对于输入操作，依次操作4台自动机，同时开4个数组记录每个时刻每台自动机所在的匹配状态。碰到退格键就使用记录数...

题意：维护一种数组结构，支持区间内所有元素自幂mod，区间求和的操作。   同ZOJ 4009，地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4009   因为模数比较小，考虑自幂多次后会产生循环节。可以使用KMP算法和floyd判环（龟兔赛跑算法）辅助寻找循环节。   KMP可以求出循环长度。   floyd判环则更加强大，不但能求出循环圈的大小，并且能够区分循环部分与非循环的部分   本题使用floyd判环的模板帖进去会得到如下结论：   1、所有数字均会在多次自幂之后进入一个长度为6的循环节。   2、一开...

题意：给你一个长度为n/2，并且是2,4,6,8,…n的排列，让你再往其中插入1,3,5,7,9…n-1共n/2个数，使最后长度为n的序列逆序数最小。考虑从小到大依次将奇数插入到序列中，可以贪心的想，如果每次都插入到与其他数字组成逆序数最小的位置，那么最后总逆序数最小。可以建立一颗平衡二叉树，并在其中插入两种节点，一种用来表示当前序列中的数字，权值赋为inf，另一种为决策点，权值为把当前数字插入到这个位置与其他数字构成的逆序数。维护最小值和产生最小值的节点编号。 比如案例中的2,6,4。建好树以后如下图  那么此时将1插入在最左边的决策点所在的位置，并且这将会引入新的两个决策点。权值与插入位置...