6/29~9/26 做题总结 POJ篇

好久没更新了,一起写了

POJ

2871  A Simple Question of Chemistry

水

2877  Chambers Ceramic Conundrum 

就是东北赛热身的那题,DFS,注意题目已经规定放的顺序了,可以判重剪枝

2449  Remmarguts' Date

类似东北赛Discovery Land那题,k短路,A*算法,思想有点像Ugly Number,用堆维护,然后扩展

1248  Safecracker

做的人不多的水题,描述有点长,DFS

1742  Coins

普通多重背包,生成函数都TLE.....要用O(n*v)的,就是加上记录到达某个重量用了多少个i种货币

3620  Avoid The Lakes

DFS/BFS水过

3624  Charm Bracelet

很直接的背包

3449  Geometric Shapes

4k多的代码....

判断图形相交,转化为判断线段相交,说下正方形根据对角线求另外两点坐标的方法:

取中点,到其中任意一个端点,向量为(x,y),则旋转90度后为(-y,x)  (画图很清楚)

实际操作时候可以把坐标都<<1,这样就没有小数了

3348  Cows

求凸包的面积,以前写的Melkman的模板很稳定....

2079  Triangle

WA一次,TLE一次

求完凸包后有点像旋转卡壳

对于某两个确定的点i,j,枚举k,则三角形i-j-k的面积函数的图像一定有最高点

到达最高点后移动j,重新枚举k,大循环枚举i,画个图比较容易理解

1018  Communication System

枚举带宽,我用了sort+lower_bound,挺方便

2575  Jolly Jumpers

囧,水题浪费了一次WA...可以不存数,直接处理

2756  Autumn is a Genius

java水...注意正数前加+号是无法直接识别的

2762  Going from u to v or from v to u?

好题,求弱连通分量

求SCC后缩点重新构图,就是个DAG

每对顶点间单连通则必存在一条链经过所有的顶点


首先入度为0的点必为1个(存在多个不构成链,是DAG,不可能不存在)


开始的想法是根据出度数+去重边直接判定...后来发现有点bug,不一定是树


比如


3 3


1 2


1 3


3 2





比较暴力就是从入度0的点开始DFS遍历所有路线,记录最大深度


之后想到用拓扑排序,每次从栈中取出顶点u,压入栈的u的邻点必定只有一个


但是时间还是一样,应该是求SCC花的时间占的多,对于随机数据缩点后的图点数,边数应该都会减少.      

2959  Ball bearings


水题,画个图,PI用2*acos(0)很方便,精度也没问题





1144  Network




求割点个数,很多书上都有的算法,判断树中节点有无到祖先的边





3159  Candies


SSSP....SPFA模板华丽地挂了.....Heap Dijkstra效率不错





1325  Machine Schedule


二分图中,|最小点覆盖|=|最大匹配|





2392  Kindergarten


|最大团|=|补图的最大独立集|


补图是二分图


二分图中,|最大独立集|=|V|-|最大匹配|





2060  Taxi Cab Scheme


|最小边覆盖|   (--> 拆点转二分图)  =|V|-|最大匹配|





3216  Repairing Company


同2060





1562  Oil Deposits


水题,BFS/DFS





2608  Soundex


还是水





2696  A Mysterious Function


勉强算个记忆化搜索,mod要单独处理





3740  Easy Finding


比较懒得写剪枝.....直接贴DLX过的





1466  Girls and Boys


二分图最大独立集





1631  Bridging signals


看了LRJ的算法艺术前传,里面的LIS写的真好,故重写此题....



scanf("%d",&n);
for(int i=0;i<n;++i)
{
	scanf("%d",&a[i]);
}
fill_n(g,n,INF);
ans=1;
for(int i=0;i<n;++i)
{
	int j=lower_bound(g,g+ans,a[i])-g;
	//d[i]=j+1;
	if(ans<j+1)
	{
		ans=j+1;
	}
	g[j]=a[i];
}
printf("%d/n",ans);




 





2455  Secret Milking Machine


二分答案+最大流验证


尝试SAP,速度很快