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