【题目描述】：
    有n个带标号的珠子，第i个珠子的价值为a[i]。现在你可以选择若干个珠子组成项链（也可以一个都不选），项链的价值为所有珠子的价值和。现在给所有可能的项链排序，先按权值从小到大排序，对于权值相同的，根据所用珠子集合的标号的字典序从小到大排序。请输出第k小的项链的价值，以及所用的珠子集合。
【题目解法】：
    我们可以考虑用bfs来扩展出第一问的答案，如何快速扩展出来呢？
    显然我们要使得扩展出来的状态尽量优并且无关状态尽量少
    因此我们考虑贪心，我们现将a数组排序，然后用(x,y)表示最大值为a[x]总和为y的状态
    然后我们扩展：(x+1,y-a[x]+a[x+1]) (x+1,y+a[x+1])，也就是a[x]是否选
    然后每次拿出最小y的状态来扩展，扩展k次即可得出答案。
    我们证明一下正确性：
    显然如果没有扩展到(x,y)，那么也就是说最大x的状态为(x1,y1)其中x1<x
    那么显然如果某个状态(x,y)比(x1,y1)都要优，那么显然y1<y
    然后我们构造一个方案：(x3,y2=y1-a[x1]+a[x])，由于x<x1那么a[x]<a[x1]，因此y2<y1，并且x3<x1，因此(x1,y1)不是最优的
    因此我们这样扩展保证了所有没有扩展出来的状态至少比队列中的某一个状态要差，因此扩展的状态一定是最优的
    然后我们考虑复杂度，由于每次扩展一个节点变成两个节点，因此每次总的多了一个节点，队列中最多有k个节点，因此复杂度为O(K log K)
    然后我们考虑第二问。我们假设第一问答案为ans
    那么显然我们知道方案<=ans最多有k个
    因此我们顺着字典序暴力dfs，每次我们找到最高前的且加上去不超过ans的数的位置，然后向下dfs
    这样子由于每次的总和保证小于ans，因此最多dfs到k个状态，每次查找使用线段树
    总的复杂度为O(K log n)

阅读更多……

【题目描述】：

【题目解法】：
    首先既然是平行光，那么投影的图形应该与原图形相同
    因此就变成了这样(转自Claude的blog)

    也就是一堆圆和梯形的面积并
    我们直接上自适应simpson求积分就好了
    simpson是牛顿科斯特公式当n=2时的情况，相当于二次函数求积分面积

阅读更多……

【题目描述】：
    树是一种很常见的数据结构。
    我们把N个点，N-1条边的连通无向图称为树。
    若将某个点作为根，从根开始遍历，则其它的点都有一个前驱，这个树就成为有根树。
    对于两个树T1和T2，如果能够把树T1的所有点重新标号，使得树T1和树T2完全相同，那么这两个树是同构的。也就是说，它们具有相同的形态。现在，给你M个有根树，请你把它们按同构关系分成若干个等价类。
【题目解法】：
    首先很容易想到枚举每棵树的每个点作为根，然后判断是否重构
    现在问题转化为判断两个有根树是否重构
    解法一：最小表示法。我们用括号序列表示一棵树，每次我们求以一个点为根的子树的最小表示，我们可以划分为求其儿子的最小表示，然后把这些括号序列排序再串起来，两边补一个()即可。然后我们可以对每一颗树求出最小字典序的最小表示法，然后判断即可
    解法二：hash。其实和上面差不多，只不过需要一个比较好的hash函数即可
    复杂度O(N^3)
    下面代码中给出了两种解法
    其中hash快一点

阅读更多……

【题目描述】：

【题目解法】：
    首先我们枚举一对自动机(i,j)，然后判断j是否为i的升级
    我们可以用bfs判定，我们用(x,y)表示在i自动机的第x个节点和j自动机的第y个节点，如果到达某个状态(x,y)使得x是输出节点而y不是输出节点，那么说明存在一个字符串x可以输出y不能输出，因此j就不是i的升级，反之j就是i的升级。
    然后状态只有O(N^2)，因此一次bfs复杂度就是O(N^2)
    如果j是i的升级我们连边i->j
    然后我们得到一个有向图，我们需要求出最长路
    我们先同tarjan求出SCC，对于同一个联通分量里面的点那么可以全部选取
    因此我们用拓扑dp求出最长路即可
    复杂度O(N^4)

阅读更多……

【题目描述】：
     在虐各种最长公共子串、子序列的题虐的不耐烦了之后，你决定反其道而行之。
    一个串的“子串”指的是它的连续的一段，例如bcd是abcdef的子串，但bde不是。
    一个串的“子序列”指的是它的可以不连续的一段，例如bde是abcdef的子串，但bdd不是。
    下面，给两个小写字母串A，B，请你计算：
    (1) A的一个最短的子串，它不是B的子串
    (2) A的一个最短的子串，它不是B的子序列
    (3) A的一个最短的子序列，它不是B的子串
    (4) A的一个最短的子序列，它不是B的子序列
【题目解法】：
    首先预处理出B串的后缀自动机
    然后预处理出next[i][j]表示第i位后面第一次出现j的位置，对A B各求出一个nextA nextB
    Task1：显然我们枚举A中子串的开头，然后再后缀自动机上匹配即可，一旦发现失配那么用当前长度+1更新最小答案
    Task2：显然我们继续枚举A中子串的开头，然后我们贪心的用nextB来进行匹配，同理一旦发现失配那么用当前长度+1更新最小答案
    Task3：我们用f[i][j]表示A串匹配到第i位，后缀自动机上的第j位的最短长度。枚举i和j的上一位设为k，然后j=tree[k].son[a[i]]，然后更新用f[t][k]更新f[i][j]，其中t<i，因此我们用个一位数组即可保存f[1..i-1][j]的最小值，一旦发现失配那么用当前长度+1更新最小答案
    Task4：与Task3类似，只不过我们不再后缀自动机上找，我们贪心的在nextB上面找下一位即可
    总的复杂度为O(N^2)

阅读更多……

【题目描述】：
    在一片古老的土地上，有一个繁荣的文明。
    这片大地几乎被森林覆盖，有N座城坐落其中。巧合的是，这N座城由恰好N-1条双向道路连接起来，使得任意两座城都是连通的。也就是说，这些城形成了树的结构，任意两座城之间有且仅有一条简单路径。
    在这个文明中，骑士是尤其受到尊崇的职业。任何一名骑士，都是其家族乃至家乡的荣耀。Henry从小就渴望成为一名能守护家乡、驱逐敌人的骑士。勤奋训练许多年后，Henry终于满18岁了。他决定离开家乡，向那些成名已久的骑士们发起挑战！
    根据Henry的调查，大陆上一共有M名受封骑士，不妨编号为1到M。
    第i个骑士居住在城Pi，武力值为Fi。
    Henry计划进行若干次旅行，每次从某座城出发沿着唯一的简单路径前往另一座城，同时会挑战路线上武力值最高的K个骑士（Henry的体力有限，为了提高水平，当然要挑战最强的骑士）。如果路线上的骑士不足K人，Henry会挑战遇到的所有人。
    每次旅行前，可能会有某些骑士的武力值或定居地发生变化，Henry自然会打听消息，并对计划做出调整。
    为了在每次旅行时做好充分准备，Henry希望你能帮忙在每次旅行前计算出这条路线上他将挑战哪些对手。
【题目解法】：
    考虑没有修改的情况，我们用T[x]表示root->x的主席树
    然后我们查询的时候只需要在T[x]+T[y]-T[lca(x,y))+T[fa[lca(x,y)]]这颗主席树上二分即可
    现在我们有了修改操作：考虑每次修改操作，影响到的点为子树中的点
    因此我们可以弄出dfs序，那么修改就变成了修改某一段连续点的主席树
    我们可以外层树状数组，内层线段树维护即可
    复杂度O(N log N log 1000)

阅读更多……

【题目描述】：
    艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点，好的拉拉队往往能帮助球队增加士气，赢得最终的比赛。所以作为拉拉队队长的楚雨荨同学知道，帮助篮球队训练好拉拉队有多么的重要。拉拉队的选拔工作已经结束，在雨荨和校长的挑选下，n位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起，和对手抗衡，为艾利斯顿篮球队加油助威。一个阳光明媚的早晨，雨荨带领拉拉队的队员们开始了排练。n个女生从左到右排成一行，每个人手中都举了一个写有26个小写字母中的某一个的牌子，在比赛的时候挥舞，为小伙子们呐喊、加油。雨荨发现，如果连续的一段女生，有奇数个，并且他们手中的牌子所写的字母，从左到右和从右到左读起来一样，那么这一段女生就被称作和谐小群体。现在雨荨想找出所有和谐小群体，并且按照女生的个数降序排序之后，前K个和谐小群体的女生个数的乘积是多少。由于答案可能很大，雨荨只要你告诉她，答案除以19930726的余数是多少就行了。
【题目解法】：
    显然我们可以用Manacher求出以i为中间点的最长回文串的长度设为p[i]
    那么显然[1,2*p[i]-1]这一段区间的中所有长度为奇数的串都可以回文
    所以我们开一个数组记录右端点，然后倒序扫一遍即可
    复杂度为O(N)
    然后Manacher都写错了TAT

阅读更多……

【题目描述】：

【题目解法】：    
    首先我们考虑lose[i]=sum[i]-win[i] sum[i]表示i队总共进行的比赛数量
    这样我们答案的式子就变成：(ci+di)*win[i]^2+sum[i]*sum[i]*d[i]-2*d[i]*sum[i]*win[i]
    然后我们考虑将win[i]+1后贡献的式子为：(c[i]+d[i])*(2*win[i]+1)-2*d[i]*sum[i]
    然后我们考虑那个麻烦的win[i]，也就是说贡献的式子和上一次的win[i]有关
    那么我们考虑拆点，把每个点拆成sum[i]个点，每个点表示上次为win[i]这次的贡献
    然后我们再对每个点设置一个阈值节点来控制流入每个点的边数
    这样建完图后就可以跑一边费用流即可

阅读更多……

【题目描述】：

【题目解法】：
    设答案为x
    显然对于每个i，满足a1/x+...+ai/x<=x1+(i-1)*d
    x>=(a1+...+ai)/(x1+(i-1)*d)
    我们把(x1+(i-1)*d,a1+...+ai)看成二维平面上的一个点
    显然后面那个式子去最大时在凸包上
    考虑每次攻击只是在最前面增加了一个点，而其他的点只是整体平移，因此不会影响上凸壳的完整性
    因此可以直接O(1)插入即可
    然后查询的话，凸包满足三分性质，直接三分
    复杂度O(n log n)

阅读更多……

【题目描述】：
    给定两个数字串A和B，通过将A和B进行二路归并得到一个新的数字串T，请找到字典序最小的T。
【题目解法】：
    这里的二路归并并不是真正意义上的归并，因为两个数字串不是单调的
    所以我们这样考虑，对于当前的数字串A B，怎样安排输出的顺序使得最后的数字串最小
    显然，我们对这这两个数字串比较即可，即如果A>B，那么就输出A的第一位，否则输出B的第一位
    然后我们将输出的数字剔除，用新的字符串进行比较，这样的答案就是最优的
    直接这样做复杂度是O((N+M)^2)的
    但是我们发现每次事实上是比较两个串的后缀，于是直接上后缀数组+RMQ即可
    复杂度O((N+M)log(N+M))

阅读更多……