【题目描述】：
    比特哈顿镇有n*n个格点，形成了一个网格图。一开始整张图是完整的。
    有k次操作，每次会删掉图中的一条边(u,v)，你需要回答在删除这条边之后u和v是否仍然连通。
【题目解法】：
    %%%神题
    考虑题目的两个性质：
    1.平面图
    2.只有删边操作
    我们最初的想法是离线并查集，然而题目强制在线
    考虑为啥要离线来做并查集捏？很简单，因为并查集只能高效的处理加边操作，对于删边操作他就无能为力了
    因此我们不妨转化为对偶图，即将每四个点包围的区域作为一个点
    这样我们发现对于删边操作，相当于这些区域之间的加边操作
    我们不妨给每一块区域编号，对于整个网格外面的部分把他们变成一样的号码
    然后删边：
    1.删除(x,y)和(x,y+1)的边
      相当于把(x-1,y)和(x,y)这两个区域连起来
    2.删除(x,y)和(x+1,y)的边
      相当于把(x,y-1)和(x,y)这两个区域连起来
    然后什么时候会导致两个点不联通呢？区域形成了环
    我们发现如果区域成环，一定会把其中一个点包含在里面，区域的环相当于原图中这些边全部断掉，那么这个点与环外界的点不联通
    并查集维护即可
    复杂度O(N^2)

阅读更多……

【题目描述】：
    给n个人安排座位，先给每个人一个1~n的编号，设第i个人的编号为ai（不同人的编号可以相同），接着从第一个人开始，大家依次入座，第i个人来了以后尝试坐到ai，如果ai被占据了，就尝试ai+1，ai+1也被占据了的话就尝试ai+2，……，如果一直尝试到第n个都不行，该安排方案就不合法。然而有m个人的编号已经确定(他们或许贿赂了你的上司...)，你只能安排剩下的人的编号，求有多少种合法的安排方案。由于答案可能很大，只需输出其除以M后的余数即可。
【题目解法】：
    考虑最后一定是每一个人都入座
    因此合法的充要条件就是：编号<=i的至少有i个人
    这样我们就可以无视入座的顺序了，那么我们考虑动态规划
    令f[i][j]表示编号<=i的有j个人
    每次枚举编号为i+1的有几个人
    令s[i]表示已经确定的编号>=i的人数，a[i]表示确定的编号=i的人数
    f[i][j]*C[n-j-s[i+1]][k-a[i+1]]->f[i+1][j+k] (j>=i)
    答案就是f[n][n]啦
    然后就可以WA了TAT
    注意题目说无解输出NO，这并不是出题人SB的做法，而是出题人BS你的做法
    因为f[n][n]=0并不说明无解，可能说明它的方案数mod M=0，因此我们需要令开一个bool记录g[i][j]是否有解
    复杂度O(N^3)

阅读更多……

【题目描述】：
    在星历2012年，星灵英雄Zeratul预测到他所在的Aiur行星在M天后会发生持续性暴雨灾害，尤其是他们的首都。而Zeratul作为星灵族的英雄，当然是要尽自己最大的努力帮助星灵族渡过这场自然灾害。
　　要渡过这场自然灾害，Zeratul自然要安排很多很多事情，其中一件就是将雨水疏导到大海里去。星灵族在重建家园的时候建造了N条河流，这些河流连接了共N+1个城市，当然其中包括了星灵首都。城市的编号为0…N，星灵首都的编号为0。
　　当然水流是有方向的，除了星灵首都以外，其余的城市都有且仅有一条河流流入。如果一个城市没有流出去的河流，那么这个城市就是一个沿海城市，可以认为流入这个城市的河流是直接流入大海的。
　　聪明的星灵族在建造河流的时候是不会让其出现环状结构的，也就是说所有的河流都是能够流入大海的。
　　每一条河流都是有一个最大流量的，一旦超过这个最大流量，就会发生洪水灾害。因此从星灵首都流入大海的总水流量是有一个最大值的。
　　例如有3条河流：第一条是从城市0流向城市1，最大流量为4；第二条是从城市1流向城市2，最大流量为2；第三条是从城市1流向城市3，最大流量为3。此时从星灵首都(城市0)流入大海的总水流量最大为4，方案有两种：
　　A. 第一条河流的流量为4，第二条河流的流量为2，第三条河流的流量为2。
　　B. 第一条河流的流量为4，第二条河流的流量为1，第三条河流的流量为3。
　　由于离暴雨到来还有时间，因此Zeratul可以扩大某些河流的最大流量来使得从星灵首都流入大海的总水流量增大。比如将上面这个例子的第一条河流的最大流量增大1，那么从星灵首都流入大海的总流水量也可以增大1，变成了5。
　　当然将河流的最大流量扩大是需要时间的，将一条河流的最大流量扩大1所需要的时间为1天。离暴雨到来还有M天，因此Zeratul也有M天的时间来扩大河流的最大流量。
　　不过由于河流周围的地形限制，每条河流并不是能够无限扩大的，因此每条河流的可以扩大到的最大流量也是有限制的。
　　而此时Zeratul正忙着安排别的工作，因此他将这个艰巨的任务交给了你。你需要安排一种方案，使得从星灵首都流入大海的总水流量最大。不过现在你只需要告诉Zeratul这个最大值即可。
【题目解法】：
    很好的题目orz
    考虑网络流，连边(x,y,A,0) (x,y,B-A,1)
    不断增广，直到费用等于m为止（当然可能无法继续增加）
    这样做显然TLE
    考虑用树链剖分+dfs序维护这棵树
    一棵线段树维护链上容量最小值，另一棵线段树维护叶子结点的费用最小值
    一开始所有边的费用为0，容量为A
    每次找到费用最小的叶子节点，然后将他到树根的路径上所有边的权值减去最小值
    然后我们找出所有边权=0的边
    1.如果他本来是费用为0的，我们将他改为1，容量B-A，并且对应修改他所控制的叶子节点
    2.如果他本来的费用为1，我们将他的容量改为INF，然后对应控制的叶子节点费用也变成INF
    注意特殊处理一些细节：
    1.最后一次增广不一定可以将一条链上的容量全部增广
    2.最后不一定可以将所有费用用完
    3.为了方便我们可以将边的权值下放到下面的结点，将根节点的权值变成INF即可
    复杂度O(N log N log N)

阅读更多……

【题目描述】：
    给定一个长度为n的正整数序列a，每个数都在1到10^9范围内，告诉你其中s个数，并给出m条信息，每条信息包含三个数l,r,k以及接下来k个正整数，表示a[l],a[l+1],...,a[r-1],a[r]里这k个数中的任意一个都比任意一个剩下的r-l+1-k个数大（严格大于，即没有等号）。
    请任意构造出一组满足条件的方案，或者判断无解。
【题目解法】：
    考虑对于两个点，如果需要满足a[x]<a[y]，那么连一条有向边(x,y)
    然后拓扑排序dp，令f[i]表示i的最小编号，f[i]=max(f[j]+1,val[i])
    val[i]表示一开始确定的权值，如果没有确定就为0，j是i的所有前继节点
    然后复杂度就是O(N^2)的，TLE+MLE ...
    我们考虑优化构图，显然每次连边都是一块一块的连，因此我们不妨使用线段树
    然后区间[l,r]->x，我们把[l,r]拆成log个区间连向x，然后线段树中每个儿子连向父亲
    然后对于m个限制，我们建立额外的m个点，每个限制对应的点连向每条限制中出现的k个数
    然后限制的区间向这个限制对应的点连边
    这样空间复杂度为O(M log N)
    然后注意，为了节省空间，线段树内部从儿子到父节点的边可以不连，我们只需要将他们的入度+1即可
    然后拓扑dp的时候需要特殊处理以下情况：
    1.只有连向某个序列中的点的边更新时，才需要+1
    2.如果一个已经确定的权值的边，他的max(f[j]+1)>val[i]说明无解
    复杂度O(M log N)

阅读更多……

【题目描述】：
    给定N个同心的扇形，求有多少面积，被至少K个扇形所覆盖。
【题目解法】:
    转化以下模型变成：
    给你n个矩形，矩形的下端贴着x轴，询问有多少的面积至少被k个矩形覆盖
    对矩形的竖边扫描线，然后维护一个线段树，每次询问第k大的数字
    注意这里矩形的面积定义为a*h^2，a为底边长，h为高
    复杂度O(N log N)

阅读更多……

【题目描述】：
    A 公司正在举办一个智力双人游戏比赛----取石子游戏，游戏的获胜者将会获得 A 公司提供的丰厚奖金，因此吸引了来自全国各地的许多聪明的选手前来参加比赛。 
    与经典的取石子游戏相比，A公司举办的这次比赛的取石子游戏规则复杂了很多： 
  总共有N堆石子依次排成一行，第i堆石子有 ai个石子。 
  开始若干堆石子已被 A公司故意拿走。 
  然后两个玩家轮流来取石子，每次每个玩家可以取走一堆中的所有石子，但有一个限制条件：一个玩家若要取走一堆石子，则与这堆石子相邻的某堆石子已被取走(之前被某个玩家取走或开始被A公司故意拿走)。注意：第 1堆石子只与第 2堆石子相邻，第N堆石子只与第N-1堆石子相邻，其余的第 i堆石子与第i-1堆和第 i+1 堆石子相邻。  
  所有石子都被取走时，游戏结束。谁最后取得的总石子数最多，谁就获得了这场游戏的胜利。 
    作为这次比赛的参赛者之一，绝顶聪明的你，想知道对于任何一场比赛，如果先手者和后手者都使用最优的策略，最后先手者和后手者分别能够取得的总石子数分别是多少。
【题目解法】：
    博弈论好题，可惜我还是太SB了TAT
    我们可以将题目抽象化，将序列由0作为分界点划分为一段段全都不为0的序列
    考虑两边的序列，如果都是紧贴着边界，那么他们只能从一段依次去取，因此看成是栈
    考虑中间的序列，他们可以从两段去取，因此看成双端队列
    现在变成：给你两个栈和若干个双端队列，如何取最优呢？
    先考虑栈：如果从栈顶到栈底是递减的，显然从栈顶开始依次取是对两边来说都是最优的
    考虑双端队列：如果不存在这样一段：... A B C ...使得 B>=A B>=C，显然从两边依次取最大值是最优的
    因此我们考虑如何将不是上面两种的情况化简
    考虑序列最边界的两个元素A B ... 或者 ... B A
    如果A>=B，显然A B最后选，因为谁都不想选B，不然就被爆了TAT
    但是总数是确定的，因此A B给谁都是确定的，删去A B
    考虑对于序列中... A B C ... B>=A B>=C的情况
    如果某个人被迫选A，那么后面那个人显然把B抢了，因为此时不存在比B更好的方案，否则先手又何必被迫选A呢？
    后手选了B，那么先手肯定选C啦，如果有比C更好的，一开始肯定就不会傻逼的取选A啦QwQ
    所以我们将A B C删去，换成A+C-B即可
    然后就变成了上面的两种情况，把所有的数弄出来，排个序，先后手交替取即可
    复杂度O(N log N)

阅读更多……

我是SB TAT

我发现我根本不会树的计数

其实我只会有度数限制，并且度数限制比较小的做法

对于没有度数限制的树的计数直接看论文吧

反正我是看不懂TAT

【写在前面】：
    之前看了%%%Nanoape的blog后一直想搞懂的东西
    然后上百度搜了一发教程，发现了一个用&$^^&^$%^微分^$%^$%积分^$^解决的办法(-_-|||)
    然后就弃疗了
    昨天在跟dwj讨论了一发，然后膜了膜大神们的代码，大概搞懂了
【参考】：

《无根树的计数统计》 By 赵爽

【问题简述】：
    树的计数分为两种：
    1.有根数计数
    2.无根树计数
    但是两者的解法大致相同
    本文就分这两类问题进行讨论
【有根数计数】：
    题目大意：给出n K，求出n个节点的有根树且每个点度数不超过K (n<=1000 K<=10)
    我们考虑动态规划
    f[i][j][k]表示i个点最大的子树大小为j子树个数为k的方案数
    g[i]表示i个点构成的根节点度数<K的有根树个数
    f[i][j][k]=f[i-j*t][j-1][k-t]*C(g[j]+t-1,t)
    g[i]=sigma(f[i][j][k]) (k<K)
【无根树计数】：
    看了上面论文的图片，你就应该明白无根树和有根数的区别了吧
    因此我们先考虑单个重心的情况，也就是说根节点的子树大小不超过(n-1)/2
    然后同样dp一发就可以了
    F[i][j][k]表示i个点最大的子树大小为j子树个数为k的方案数
    F[i]表示i个点构成的根节点度数<=K的有根树个数
    F[i][j][k]=F[i-j*t][j-1][k-t]*C(g[j]+t-1,t)
    G[i]=sigma(F[i][j][k]) (k<=K)

    然后考虑双重心的情况
    考虑这样的情况只可能n为偶数
    此时变成了一颗有两颗大小为n/2的子树构成的树
    那么方案数就加上g[n/2)*(g[n/2]+1)/2即可
【总结】：
    由此看出，在这样的问题中复杂度为O(N^2*K^2)
    在N,K不大时可以胜任
    大概就是这样喽

阅读更多……

【题目描述】：
    比特镇一共有n个房子，编号依次为1到n，这些房子通过n-1条无向道路连通在一起，形成了一棵树的结构。
    Bytesear要在比特镇实施Wifi搭建计划，他要让Wifi覆盖到比特镇的每一条道路。
    Bytesear可以安置无限多个Wifi发射器，但是只能安置在树上的节点上，一个房子可以安置多个Wifi发射器。
    对于一条道路(a,b)，如果它满足以下两个条件之中的至少一个，那么这条边将被Wifi覆盖：
    1.a点放置了Wifi发射器或者和b点放置了Wifi发射器。
    2.与a点或b点直接相邻的点中，至少放置了两个Wifi发射器。
    请帮助Bytesear规划一个最优的放置方案，使得Wifi覆盖到比特镇的每一条道路，且放置的Wifi发射器总数尽可能少。
【题目解法】：
    f[i][j]表示i号节点不放无线电儿子节点放了j个且不需要父亲节点放的最小代价
    g[i][j]表示i号节点不放无线电需要父亲节点放j个的最小代价
    h[i][j]表示i号节点放j个无线电且不需要父亲节点放的最小代价
    ans[i]表示覆盖以i为根的子树的最小代价
    注意f[i][j]中j最多枚举到2即可，大于2都可以默认为2，因为大于2和等于2对转移没有影响
    然后一个节点最多放2个，放多了和放2个没有区别
    然后我们一个个转移
    ans[i]=min(f[i][0],f[i][1],f[i][2],h[i][1],h[i][2])
    考虑f的转移
    1.f[i][0] 那么需要每个儿子从自己的儿子中获得两个无线电，即sigma(f[son][2])
    2.f[i][1] 那么枚举哪个儿子被选中，那个儿子的贡献就是h[son][1]，其他的儿子的贡献是sigma(f[son][1])
    3.f[i][2] 我们令F[i][j]表示前i个儿子有j个放了无线电F[i][j]+h[son][1]->F[i+1][j+1] F[i][j]+ans[son]->F[i+1][j]
    考虑g的转移
    1.g[i][1]
      要么由一个儿子覆盖一个，其他的不需要 那么就是h[Son][1]+sigma(ans[son])
      要么所有儿子都不放，由儿子的儿子提供 那么就是sigma(f[son][1])
    2.g[i][2]=sigma(ans[son])
    考虑h的转移
    1.h[i][1]=sigma(min(ans[son],g[son][1]))+1
    2.h[i][2]=sigma(min(ans[son],g[son][2]))+2
    最后注意一下覆盖一下
    即g[i][j]=min(g[i][j],g[i][j-1])
      h[i][j]=min(h[i][j],h[i][j+1])
      f[i][j]=min(f[i][j],f[i][j+1])
    复杂度O(N)

阅读更多……

【题目描述】：
    最近，小栋在无向连通图的生成树个数计算方面有了惊人的进展，他发现：
    ·n个结点的环的生成树个数为n。
    ·n个结点的完全图的生成树个数为n^(n-2)。
    这两个发现让小栋欣喜若狂，由此更加坚定了他继续计算生成树个数的想法，他要计算出各种各样图的生成树数目。
    一天，小栋和同学聚会，大家围坐在一张大圆桌周围。小栋看了看，马上想到了生成树问题。如果把每个同学看成一个结点，邻座（结点间距离为1）的同学间连一条边，就变成了一个环。可是，小栋对环的计数已经十分娴熟且不再感兴趣。于是，小栋又把图变了一下：不仅把邻座的同学之间连一条边，还把相隔一个座位（结点间距离为2）的同学之间也连一条边，将结点间有边直接相连的这两种情况统称为有边相连，如图1所示。
    小栋发现利用通用方法，因计算过于复杂而很难算出来，而且用其他方法也难以找到更简便的公式进行计算。于是，他将图做了简化，从一个地方将圆桌断开，这样所有的同学形成了一条链，连接距离为1和距离为2的点。
    这样生成树的总数就减少了很多。小栋不停的思考，一直到聚会结束，终于找到了一种快捷的方法计算出这个图的生成树个数。可是，如果把距离为3的点也连起来，小栋就不知道如何快捷计算了。现在，请你帮助小栋计算这类图的生成树的数目。
    输入包含两个整数k, n，由一个空格分隔。k 表示要将所有距离不超 过k（含k）的结点连接起来，n 表示有n 个结点。
【题目解法】：
    注意到K<=5，因此我们不妨记录当前5个的点的连通性
    如何表示呢？我们可以考虑使用最小表示法
    很显然，我们可以将这5个点中同一个连通块的的点标成一样的编号
    每个连通块的编号和最左边的的同一连通块的编号一样
    然后从左到右每个连通块的第一个结点编号递增
    这样我们用一个6进制压缩即可（其中0表示没有结点）
    然后我数了数一共有76个合法的状态
    因此我们就可以暴力转移，然后矩阵乘法优化了

阅读更多……

【题目描述】：
    神犇heheda最近得到了UOJ抱枕，蒟蒻yts1999想要玩。于是heheda给yts1999出了一道题：
    一个长度为2n+2的整数数列 按照下式定义：
    A0=0
    A1=C
    Ai+2=(Ai+1+Ai) Mod M (0<=i<=2*N)
    现有n个平面向量v1…vn：
    V1=(A2,A3),V2=(A4,A5)...Vn=(A2n,A2n+1)
    集合S的定义如下：

    其中"vi•vj"表示向量vi和vj的数量积。
    求S集合中不同元素的个数是多少。答案对M取模。
    heheda告诉yts1999，只要他做出了这道题，她就可以把抱枕借给他玩一会。然而yts1999实在是太弱了不会做，于是向你求助。
【题目解法】：
    根据类斐波那契数列的性质：
    F[1]*F[n+m+1]=F[n]*F[m]+F[n+1]*F[m+1]
    F[1]*F[n+1]=F[m]*F[n-m]+F[m+1]*F[n-m+1]
    因此对于两个向量：vi=(F[i],F[i+1]) vj=(F[j],F[j+1])
    那么F[i]*F[j]+F[i+1]*F[j+1]=F[1]*F[i+j+1]
    因此对于所有就是询问本质不同的F[i+j+1]*F[1]
    i+j+1的范围是[7,4n-1]内所有的奇数，全部拉出来sort一发就好

阅读更多……