94全國賽 6. 下棋問題

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
數據範圍N到5000，但是記憶體卻只給到約略N^2/2。







首先因為我想不到在線(Inline)的作法，故從離線(Offline)開始想起。



當沒有任何阻隔時，任兩個棋子A, B都可以形成一個矩形。



這個矩形出現的時間是max(A, B)，也就是兩個棋子都被下下去始，直到他們中間有其他棋子出現。



也就是如果我們可以枚舉每對棋子，並且快速地算出這個矩形被破壞的時間，這題便可以做了！



而他被破壞的時間就是這個矩形區間中最早放下去的棋子。



所以變成每次查詢一個矩形，問矩形內最早放下的棋子。



這很明顯就是二維的RMQ問題！而二維RMQ可以用Sparse Table作到每次查詢O(lg^2 N)







所以我們就得到一個算法了：



**枚舉每個矩形，查詢那個區間最早被放下的棋子。



**之後我們會得到N(N-1)/2個區間 每個區間代表這個該個矩形的生命週期。



**之後對這些區間進行排序，線性掃過後可以求出每一個時間點場上"存活"的矩形有幾個。



這樣總複雜度會是O(N^2 lg^2 N)，但是記憶體非常不理想地是(N^2 lg^2 N)，



除了執行速度太慢之外，記憶體空間也不足。











以此，需要更優化此算法。



也就是要在O(N^2)以內的複雜度內求出每個矩形的生命週期。



我們想到了分而治之法。(Divide & Conquer)





首先沿中線將棋盤分為左右兩塊，左塊內的矩形及右塊內的矩形可以透過遞歸做出。



現在我們要處理的就是跨越中間線的矩形。







如上圖所示，該矩形會被中線切割為藍色塊跟紅色塊。



該矩形的死期(?)理當為Min(藍色塊內最早被放下的點, 紅色塊內最早被放下的點)



而該怎麼求出每一個點對的每個色塊呢？



我們繼續觀察下去，觀察P對B這個矩形。



我們會發現他在中間線左邊那個紫色塊完全把上圖藍色塊包含了。







也就是其實我們可以用O(點數)求出左邊每個以P為左下角的色塊 內最早被放下的點，



就只要沿著Y軸遞增掃下去即可。





如此每個矩形只會被中線切一次，故總計算量實際上是O(N^2)，也就是矩形數量。







至於記憶體(內存)不夠的問題呢，會發現只要改一下計算順序，記憶體總共只需要N的常數倍，顯然夠用。

















以上。





=====題外話：=====



這題是在94年全國賽的難題之一，



最近幾年全國賽無論是測試數據強度或是題目難度感覺都有點比不上以往...





當年賽後，有選手提出了這題的在線作法



也就是每次加入一個點，算出這個點增加了幾個、破壞了幾個

OIBH 2006 模擬試題3 prob 3 情书抄写员

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

http://mail.bashu.cn:8080/BSoiOnline/showproblem?problem_id=1629





顯而易見可以得到第n天的情書數量有F(n) = F(n-1) + k * F(n-2)









先講結論，gcd(F(a), F(b)) = F(gcd(a, b))

以下證明 by willyliu

Lemma 1 : gcd(F(n), k) = 1

proof :

gcd(F(n), k)

= gcd(F(n-1) +F(n-2)k, k)

= gcd(F(n-1), k)

= ... = 1



Lemma 2 : gcd(F(n), F(n+1)) = 1

proof :

gcd(F(n), F(n+1))

= gcd(F(n), F(n) + F(n-1)k)

= gcd(F(n), F(n-1)) ∵Lemma 1

= ... = 1



Lemma 3 : F(a+b) = F(a)F(b+1) + F(a-1)F(b)k

proof :

F(a+b)

= F(a+b-1) + F(a+b-2)k

Induction on b,

= ( F(a)F(b) + F(a-1)F(b-1)k ) + ( F(a)F(b-1) + F(a-1)F(b-2)k )k

= F(a) * ( F(b) + F(b-1)k ) + F(a-1) * ( F(b-1) + F(b-2)k )k

= F(a)F(b+1) + F(a-1)F(b)k



Theorem : gcd(F(a), F(b)) = F(gcd(a, b))

proof :

WLDG a ≧ b,

gcd( F(a), F(b) )

= gcd( F(a-b + b), F(b) )

= gcd( F(a-b)F(b+1) + F(a-b-1)F(b), F(b) ) ∵Lemma 3

= gcd( F(a-b)F(b+1), F(b) )

= gcd( F(a-b), F(b) ) ∵Lemma 2

= gcd( F(a mod b), F(b) )

= F( gcd(a, b) ) Q.E.D.

NOI2010 航空管制

　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　


　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　



先附個題目連結，

http://hi.baidu.com/%D2%DD%C3%F7%BE%A8%C8%CB/blog/item/4bb3383d07f175cf7d1e71d5.html





第一部分很簡單，就把所有限制建構成一個DAG，



把頂點依照"最遲起飛時間"排序，由小到大儘量滿足即可。



由於保證有解，所以這部分相信不是大問題。複雜度O(N+M)









第二部分先講一下我首先想到的想法：



如果該架飛機的起飛時間在[1, K]之間，然後我們二分搜K顯然可以得到答案。



二分搜之後我們可以變成把該節點的最遲起飛時間變成K，然後做一次第一題檢查是否有解



對每個的複雜度是O((N+M)lgN)，總複雜度約O(NMlgN)



而且其實二分搜的範圍很小，應該運行速度不會太慢。





如果有把第一題弄成一個function實作難度會降低很多。





另外附一個剛才在網路上找到的不錯思路：



http://yzm-blog.appspot.com/2010/08/8/NOI-2010.html



用Heap實作，複雜度差不多。

USACO Jan. 2011 Gold

不愉悅orz                                   



一直有人在問我數學XD


這次pB pC可解 不過pC稍微難寫一點


pA猜個N lg N + K lg^2 N 好了

感覺就是輕重鏈剖分orz

Practice : Asia Beijing 2008 / 2009

北京賽區。據說當年五題+不錯的Penalty就可以拿到金獎  雖然不知道金獎怎麼定義XDD                             .

Beijing (China)

 

ID Problem Title Download Hint Ranking 4322 Destroying the bus stations YES 4323 A simple stone game YES 4324 Ugly Windows YES 4325 Tornado YES 4326 Minimal Ratio Tree YES 4327 Parade YES 4328 Priest John's Busiest Day YES 4329 Ping pong YES 4330 Timer YES 4331 Elevator YES

pA 給你一張有向圖(V=50 E=4000)和K，問至少要拔幾個點才使得1->N的最短路大於等於K
(邊權皆為1、1->N沒有直接連邊)

用最大流想法：增廣到該次最短路長度>=K就結束，輸出目前源點流量   不過依然WA

pB給你N和K，兩人輪流取石頭，第一個人第一次只能拿1~N-1顆、
以後每個人每次拿的數量不能超過上衣個人K倍，問先手必勝的第一步？

沒想法，不過應該是經典題

pC給你一張NxM圖片，問你有幾個矩形框在最上層？

模擬，但是注意回字型。

pD有一個龍捲風路徑是一條射線，給你他的速度，還有一個人在兩點之間等速往復運動，問龍捲風到人的最近距離？

沒想法

pE給一張無向有權完全圖，你要輸出一組M個點的生成樹且邊權和/點權和最小，且點排好後的字典序最小。

爆搜，注意一下精度問題。

pF給一張NxM網格(N=100,M=10000)，橫向(M方向)每條路徑都有兩個權重，v跟k。
從最底下任意一點開始，到最上面任意一點。只能往上或左右走，且走過路徑不能再走，
且每層(依照N分層)走過的路徑sum k要小於給定的K，求出整條路徑sum v的最大值。

DP，每層轉移需要Deque，不過我還在WAorz

pG給你很多區間(N=100000)代表婚禮，牧師必須選擇一段連續段來進行證婚。
這段必須要大於區間大小的一半，且牧師只有一個人不能分身，問有沒有可能替所有婚禮證婚？

Greedy (by worm)，還不會

pH給你一個序列ar(長度=100000)，問有幾個三數對A,B,C符合位置A<B<C且ar[B]介於ar[A]和ar[C]之間。

頗裸的Binary Indexed Tree

pI, pJ沒看題目


總體而言打得很失敗orz

不過要感謝suhorng, jurrasickill

COCI 2009/2010 #3 p5

標題好長XD


簡單的說

第一行有兩個數字N, C

接下來給你一條數列S  ，長度是N(<=300,000)，裡面的數字範圍是1~C(<=10,000)

第三行是一個數字M(<=10,000)表示有幾組詢問

接下來M組詢問，每組有L, R(1<=L<=R<=N)

問你閉區間[L, R]中有沒有哪個數字出現超過一半？有的話問是哪個數字？

Sample input:
10 3
1 2 1 2 1 2 3 2 3 3
8
1 2
1 3
1 4
1 5
2 5
2 6
6 9
7 10

Sample output:
no
yes 1
no
yes 1
no
yes 2
no
yes 3


全國賽那天晚上戰的COCI的題目(轉

小鬼當時說他會做了不知道跟官方solution一不一樣(欸

shik表示：蒙地卡羅應該會過


不過官方solution好好玩(打滾











========================solution===================


先不要考慮原題目，來想另一個遊戲：

給你一個序列S，每次可以把S裡面相異兩個數字抹掉。

直到全部都剩下同一個數字時遊戲結束

例如 12312323->312323->1323->33m 時結束。

這時紀錄兩個數 candi表示剩下的數字是什麼  count表示結束狀態多長

例如上述例子   candi=3 count=2




引理：如果有個數字出現超過length/2次，那他一定會是candi，無論過程

那麼，我們只要維護一棵seg tree就可以作到區間查詢candi了ˇ

就是分L.candi==R.candi以及L.candi!=R.candi時比兩個count大小

然後求出這個區間的candi，再去用另一棵seg tree計算他出現幾次

如果出現>length/2次就是yes  否則則是no

IOI &#39;05 Mean Sequence

這題被小乃瞬秒XD    不過其實還頗有趣的                                                                                                         .


Description:

定義一個數列S的Mean序列M:

Mi = (Si + S(i+1))/2

例如   序列1, 1, 3, 5, 15的M為: 1, 2, 4, 10



給你一個有n項的序列M，請問有多少S使得

1. S的Mean序列為M

2. S1 <= S2 <= S3 <= ... <= S(n+1)


n<= 5,000,000







Solution:

M2-M1 = (S3-S1)/2

依此，可以把奇數項和偶數項分開討論，例如範例就變成

(a), (b), (a+2), (b+4), (a+14)

再由條件2.

(a)<= (b)<= (a+2)<= (b+4)<= (a+14)

解不等式  加上a+b = 2(M1)驗證


總複雜度O(n)

IOI &#39;06 Joining Points

這題沒有Judge，所以自己寫了一個應該是可以AC的啦XD                                                                           .




很棒的題目。


Description:


Joining Points是一個獨人遊戲。

平面上有g個綠點  r個紅點   (2 <= g,r <= 50 000)

所有點都是整數座標   座標範圍是0~s (s <= 200 000 000)


保證(0,s)和(s,s)有綠點  (s,0)和(0,0)有紅點 並且任三點不共線

遊戲勝利的條件是  用g-1條線段把所有綠點連起來  用r-1條線段把所有紅點連起來

並且所有線段不交叉(共端點不算交叉)

保證一定有解  請輸出任意一種連線方案


Input

第一行: 整數g。接下來g行: 從綠點的編號1開始到g，每一行有二個以空白隔開的整數，
代表一個綠點的xi與yi 座標。第g+2行: 整數 r。接下來r行: 從紅點的編號1開始到r，
每一行有二個以空白隔開的整數，代表一個紅點的xi與yi 座標。

Output

共應輸出g-1+r-1行
每行包含兩個整數一個字元   前兩個整數代表這條線段所連接兩點編號
字元表示所連接兩點顏色


Sample Input
6
0 1000
1000 1000
203 601
449 212
620 837
708 537
8
0 0
1000 0
185 300
314 888
416 458
614 622
683 95
838 400


Sample Output
1 3 g
3 1 r
3 5 r
4 6 r
6 5 r
4 6 g
1 2 g
1 2 r
5 2 g
2 6 g
7 8 r
8 2 r



Solution:






這題目是很棒的D&C。時間複雜度：O(n lg n)


核心思想：

考慮一個三角形  v1 v2 v3 ，其中 v1,v2同色   v3異色

(1)如果中間沒有其他點    結束
(2)如果中間全部剩下的點同色    把那些點全部連到同一個頂點    結束
(3)其他：
選出一個跟v3同色的內部點vp，連v3-vp
然後對v1,v2,vp    v2,v3,vp   v3,v1,vp遞迴



很顯而易見遞迴三角形個數是和(g+r)同數量級，

如果對每個三角形O(g+r)檢查，就有了一個O((g+r)^2)算法   值55分


但是可以發現，其實對同一層    只需要合計O(g+r)的複雜度就可以
總共不會超過lg級別層，所以複雜度O(n lg n)ˇ



至於實做，我是以串列實做。










code(Judge程式，會告訴你是哪裡出錯)

http://codepad.org/rwc0RnZq

對了提一下，檢查是用Disjoint Set確定連通性，Sweep Line Algorithm檢查是否有交點




code(AC code)

http://codepad.org/q6v18QD5




testdata / solution (official)

http://olympiads.win.tue.nl/ioi/ioi2006/contest/day2/points/

4. 工作順序問題 [97全國賽]

DP.                                                                                                          .


不依啦zerojudge會MLE

算了

#include<stdio.h>
long long dp[10000010],n,m;
main(){
	freopen("4.in","r",stdin);
	freopen("4.out","w",stdout);
	scanf("%I64d%I64d",&n,&m);
	dp[1]=1;dp[0]=0;
	for(int i=2;i<=n;i++)
		dp[i]=((dp[i-1]*(i-1))%m+(dp[i-2])*(i-2))%m;
	printf("%I64d\n",dp[n]);
}

遞推式子不會很難想

就前一個*(n-1)個位置插入

+

前一個剛好有一組不合法的(即兩個相鄰->結合成一個點

大概這樣XD

3. 找關鍵人物 [97全國賽]

頗單純的樹型DPˊˇˋ                                                                                                     .


寫得爛爛的orz

 應該是O(n^2)吧不會估XD

//************************

#include<stdio.h>
int n,a,b;
struct edge{
	int j;
	edge *next;
	void set(int jj,edge *n){
		j=jj;next=n;
	}
}E[40020],*V[20010];
int edgeCnt;
void set(int i,int j){
	//printf("set %d %d\n",i,j);
	edge *p=E+edgeCnt++,*q=E+edgeCnt++,*r;
	r=V[i];
	V[i]=p;
	p->set(j,r);
	r=V[j];
	V[j]=q;
	q->set(i,r);
}
int dp[20010],max[20010],son[20010];
int treedp(int now,int fa){
	//printf("treedp %d %d\n",now,fa);
	if(max[now])return son[now];
	int sub=0,tmp;
	for(edge *p=V[now];p;p=p->next){
		if(p->j == fa)continue;
		//printf("now %d now %d\n",now,p);
		sub++;
		son[now]+=treedp(p->j,now)+1;
		//printf("now %d son %d %d\n",now,p->j,son[p->j]);
		if(dp[now]<dp[p->j] || dp[now]==dp[p->j]&&max[now]>max[p->j]){
			dp[now]=dp[p->j];
			max[now]=max[p->j];
		}
	}
	if(sub==0){
		max[now]=-1;
		return son[now]=dp[now]=0;
	}
	tmp=son[now]*(n-son[now]-1);
	for(edge *p=V[now];p;p=p->next){
		if(p->j == fa)continue;
		for(edge *q=p;q;q=q->next){
			if(q->j == fa)continue;
			if(p->j!=q->j){
				tmp+=(1+son[p->j])*(1+son[q->j]);
			}
		}
	}
	if(tmp>dp[now] || tmp==dp[now]&&now<max[now]){
		max[now]=now;
		dp[now]=tmp;
	}
	return son[now];
}
main(){
	freopen("3.in","r",stdin);
	freopen("3.out","w",stdout);
	scanf("%d",&n);
	for(int i=0;i<n-1;i++){
		scanf("%d%d",&a,&b);
		set(a,b);
	}
	treedp(1,1);
	//for(int i=1;i<=n;i++)
	//	printf("node %d son %d dp %d max %d\n",i,son[i],dp[i],max[i]);
	printf("%d %d\n",max[1],dp[1]);
}