题意:在n*m的土地上,一块连通的(上下左右),且所占格数大于K的区域称为大区域.现在定义危险的格子:它们或者属于大区域,或者往上下左右任意方向走都必须经过同一块大区域.求危险格子数.
bfs,假设每个格子四条边上都是管道,一个大区域构成边界的管道使其中一些管道被封闭,那么从土地边界上任意一点flood-fill一遍就可以得出所有大区域的边界.所有属于大区域的格子或四边管道有一边没有水的格子之和就是答案.
题意:王国有N个城市(1~N),首都在1.已知有M条路,其中N-1条路构成一棵树T,保证从首都到所有节点的最短路都在这棵树上.现在要求每个节点在当树T上从1到该节点的路径的最后一条边坏掉的情况下的从1到它的最短路.
LCA.对于每个节点v,题目所求的最短路或者是在它的子树T'外的点连一条边到它,或者是在它的子树T'外的点连一条边到T'中任意一点,延最初的最短路走到该点.这样,对于每个节点,处理每条与其相连的不在树T上的边.设边上另一点为u,则按照LCA(uv)=i不同值建立不同的集合Ti.然后按照从1到v的路径的顺序来,每次在当前可使用的边选出最小值加上沿树T往上走到节点i的值去更新对于i的答案,同时把Ti中所有边置为可使用.
sgu371+sgu381
题意:the city of S***的地铁有两种路线:一种是环线,环线由若干个环(节点数在3~10之间),所有的环构成一条链,每个环仅与其相邻的环有一个公共节点,且每个节点最多只能在2个环上,如此串成链;另一种是支线,每个环上的不是两环连接处的节点最多可以延伸一条支线.现在给出节点数N和边数M,求地铁建设方案.
水题.多一环可多一边.先建环,后加点,最后加支线.
题意:给一个图,每条边e连接的两点uv都有权值w(eu)和w(ev).权值只有1和-1两种.有向图指的是每条边e上的权值积为-1.有一种操作是对于某个点v,对于所有e若存在w(ev),则w(ev)*=-1.求最少的操作使图变为有向.
水题.当一个连通块上任意点确定是否执行操作后,整个连通块每个点是否执行操作就确定了.
题目意思很简单,就是在平面上有n(<=2*10^5)个匹萨店,每个匹萨店覆盖范围wi(曼哈顿距离),若某个匹萨店被其他至少k个匹萨店覆盖则可以取消.求那些匹萨店可以被取消.
这个问题可以被简化成一个很简单的问题:求某个点被多少个矩形覆盖.这个问题用线段树解决.
由于每个匹萨店按照覆盖范围展开后,将边界上的点连接恰可视为一个正方形.如果我们将坐标轴旋转45度,那么这个正方形的边就平行于坐标轴.剩下的就是上面一段提到的问题了.至此这题就被ac了.
LuCKYDAY的意思是这样的:给一个数据列s[1]=ss[2]=bs[i]=(x*s[i-1]+y*s[i-2]+z) mod pp是质数且p<10007.给定区间[lr],求l<=k<=r使s[k]=c的个数.
这题我写了个p^2的裸的找环的,构造了一个将近10^8的环和20000组询问,两组时间我最后优化到只要6s多就行了,所以我估计那些最后花了将近20s的就是写的相当完美的了.
其实这题标准的做法是借鉴了 Baby-step giant-step 策略.wiki上说的很详细了我也就不多说了.这题我们可以简化:求出环的大小,以及环中每个c的位置.这里只讨论xy均不等于0的情况.定义向量f(i)=(s[i]s[i+1]1)和转移矩阵A,使得f(i+1)=A * f(i).因为所有数都是对P取模的,讨论一下就知道环中所有元素都有唯一前驱和后继的,所以f(1)必定是环中的一个点,环的大小就变成求f(k+1)==f(1)的最小k,这与第2个问题是相似的.
由题设知f(k+1)=A^k*f(1),设k=i*m-j,其中m为环的长度的平方根(本题为p),0<=j<p,这样就变成了(A^m)^i*f(1)=A^j*f(k+1).对于每个j的A^j*f(k+1)可以先存下来(这里只要算p次),再计算等式左边 i 从1到p变化的结果(因为环最长为p^2),满足最小的那个 i 就是我们需要的,i*m-j就是我们要求的环的大小.其他问题就都好解决了.
sgu做到290道了,这个月的目标也算达成了.
这道题就是骑士遍历问题:给定n*n的棋盘,从任意一点出发,按马的规则,求一条遍历棋盘的路径.本质上这是个哈密尔顿路,因为在棋盘上有很多优化的方法.这道题其实也算是论文题,如果知道Warnsdorff's rule的话就很容易了.如果知道这个启发式规则还不能ac就是在度数相同的点中处理的先后顺序的排法上乱搞,或者继续找论文.我是把输入分成2类,一类是坐标和小的排在前能出解,一类是坐标和大的排在前能出解.
又是算法想的出手速跟不上.纠结是d还是e也纠结了一会.把我想的算法贴一下,或许是我想的太挫了才导致没调对.
D的意思是:给你n(<=10^5)个线段,有1种操作:某条线段[lr]变成[l+1r+1]或者[l-1r-1].最多操作k次.问最多能包含几个LN.
二分枚举答案(log(2^19)),对于每个答案,从左往右枚举合法区间,时间复杂度O(mlogm).枚举前线段排序.对于每次右移,将需要右移才能包含的线段和需要左移包含的线段是可以只用一个数组记录的,每次左移对于已经在左边或右边不包含当前或移动到左边的值加入的结果维护是常数的.对于包含的情况用个小根堆维护,key为右端点.这样由于右到左就一次,所以时间复杂度为O(nlognlogm).
算法:线段树.先将add按li排序,然后a从左往右扫描并维护包含当前点i的add值.这里用到第一个线段树,用来记录对该点有影响的add的线段以及该add起效后的情况.满足条件的LN大概有20个左右,我们用每个LN依次减去a[i],然后在线段树中查等于该值的add以及下一个add,并将其构成线段集L.
然后是统计结果.这个问题本质上是:在平面上给你n个平行于x轴的线段,和m个平行于y轴的线段,让你统计有多少个交点.x轴是命令编号,y轴是线段的坐标.这就是个明显的线段树了.
这道题其实是道水题,之所以A掉的人不到三位数我觉得就是一些特殊情况没考虑.
算法就不说了.本菜鸟其实也卡了很久,能给的提示就是:input: 1397803 output 480 .这组对了基本上就能过了吧.