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,速度很快