省选、noi正式比赛oj数据相关1poi

1、POI2008未完整解决的有：rob 未写per 不会做题号算法具体细节clo图论+构造+并查集对于每个连通块，若不存在环，则边数少于点数，无解。否则，对于每个连通块，利用并查集找到一条环上的边(i,j)，将 i 与(i,j)匹配，以 i 为根 DFS，每个点（除了 i）与到达它的边匹配即可。klo枚举+数据结构从左至右扫描，长度为 m 的一段区间的中位数 y，不超过中位数的数的和 x，全部数字的和 z。Ans=min(m and 1) * y + z - 2x)平衡树，双堆，线段树等均可完成这些操作。pla贪心+栈等价于山顶的个数（见 ks1030peaks），可以用栈在 O(n)的时间求出

2、。rob稀疏性优化+BFS以船最左上的点(x,y)代表船当前的位置，对于每个点(i,j)判断船是否可以到达，剩下的工作就只有 BFS 了。一行一行进行判断，因为船是凸多边形，故每列只需要考虑最近的一个物的影响。容易证明，每个物在该行影响的格子必然是连续一段，求出这 N 个区间的并，那么该行中其余的格子就是可以到达的。细节：(x,y)移出不代表整个船移出。szk模拟+排序+并查集由光路的可逆性知， 必然为 n/2，即任意点的光路终点都是确定的。因为点的个数不超过 300000，故考虑模拟求出所有的光线从而求出匹配方案。将图形选择 45 度，然后以 x 为第一关键字，y 为第 2 关键字排序，则同

3、一行中相邻的点间必然有水平光线。然后y 一 x 二排序，则同一列中相邻点间必然有竖直光线。求出所有光线后，将有光线相邻的点并入一个集合，则最后属于同一集合的顶点则是一对匹配点。细节：顶点只允许通过一个方向（水平或竖直）的光线，故求另一方向光线时应忽略这些顶点。优化：用 cpp 的 qsort 吧，比 pas 手写的快一倍。blo无向图的割顶利用 DFS 求出 i 及其 的后向边指向的最高节点，统计深搜树中每个节点的大小 Si。Ansi=2*(Sj*Sk+(n-Sj-1)* Sj+n-1)j,k 及其的后向边不高于 ibbb枚举+最小前缀和+贪心+为 1，-为-1，将序列一遍。令 Fi表示以 i

4、 为起点的最小前缀和。Fi=min(Fi+1,0)+wi对于限制 2：设 i=0 则不需操作 1，否则必要且只需要将前(1-a-Fi)/2 个-改为+。对于限制 1：在满足限制 2 的基础上，若 a+w=b 则只需改变后(a+w-b)/2 个-，否则改变后(b-a-w)/2 个+。故 Ans=min0,(1-a-Fi)/2+|b-a-w|/2注意，这里的w 指的是操作 1 已进行完后的w。pochash+区间最大值利用 rk-hash 将相同的字符串放到一起，每次交换元素只需在 O(1)内求出变化值即可求出新的 hash 值。故问题转化为集合的操作，即给定若干集合，每次将某个集合中的元素取出，

5、移到另一个集合，或形成新的集合，问每个元素呆过的最大集合的大小。首先求出所有的事件（ ，删除）以及出现过的集合， 共 4M+N 个事件，最多 N+2M 个集合。单独处理与每个集合有关的事件，令 Si表示 i 时刻该集合大小，则若字符串 I 于 L 时刻 R 时刻删除，则用 maxS L.R）更新 I 的 。区间最大值可以利用线段树，+-1RMQ，LCA，ST，队列优化+二分等实现。maf贪心+图论问题 1，最少死几个人：没有入度的点必然不死，不死的点指向的点必死。使用拓扑排序实现，若最后剩下环且环上所有点都不死，则每个环 人数为(L+1)/2。问题 2，最多死几个人：没有入度的点必然不死，若存

6、在没有叶子且长度大于 1的环，则该环上有一个人不死。其余人都可以 。uci动态规划+滚动数组F0.3,a,b,c,d 表示对于四边与目标距离分别为a,b,c,d 且人在某个角上时走到终点的方案数。 Fx,a,b,c,d=Fx,a,b,c,d-1+Fx,a,b,c-1,d使用滚动数组优化空间复杂度。lam数学+度由定义可推出 Fi=(1-Fjji)/pi。为了方便度处理，令 Si=1-Fj(j=i)，那么上式变为Si=(Si+1)*(pi-1)/(pi) Fi=(Si+1)/(pi)需要的度运算只有乘单精，单精。kup最大矩阵若存在 ai,jk,2k直接输出。否则将 ai,j2k 的点看做 物，

7、用递推求 Fi,j表示由 i,j 往左有多长的连续一段不存在 物，类似的 Gi,j表示往右的长度。因为 ai,jk，故相邻前缀和不可能从2k。故若存在 Si,l.r2k 则必然存在 Si,l.pk,2k，求 F 值时判断是否有 Si,j-Fi,j+1.jk,2k即可。否则 利用 F 与 G 求出最大 矩阵 Smax（经典算法，不赘述）。若 Smaxk 则无解，否则必然存在 Smax 的前缀和k,2k。tro枚举+叉积枚举一个点 i 作为三角形最左边的点，该点右边的点按极角序排序，那么这种情况下的三角形面积和为2S=(xjyk-xkyj)(jk)=yk*xj-xk*yj（jk）每一项中后面的数用一个变量统计即可。时间复杂度 O(n2logn)pod枚举+位运算优化Sum=di-2e(i,j) i,jAns枚举所有的划分方案取最优。枚举时每加入一个点 i， Sum+=di-2*calc(Ei and Ans) Ans+=2iAns 表示加入 i 前的集合，Ei 与 i 相连的点集，均用二进制表示；calc(x)表示 x 的二进制中 1 的个数calc 可以参考 Matrix67 大牛关于位运算的文章。优化：限制点 1 在集合中。时间复杂度 O(C(2n-1,n-1)*O(calc)sta目标转化+树形动归设 选 i 为总部，那么对