CCC 2015 總結&回顧

最後一次CCC就在上周四悄悄地結束了……能參加也算是在帝都的福利吧。

3h，5題。最終結果290分，和第9&10名分數一樣但是似乎因為送出比較晚于是被卡在了線下……簡直是noip差5分的重演。

題目大意（資料範圍記不清了，選用的字母也和原題有差異）：

1.Pairs

給一個N和一個M以及一組有N個數的數列{an}，求滿足以下兩個條件的數對的個數：

a. i < j

b. ai + aj <= M

其實可以發現a的限制隻是表示每個數不能自己與自己相加且交換順序相加是相同的一對。是以我們可以sort成升序之後再處理。

然後進行協同查找。sort之後取兩個變量作為數組下标的指針i,j，初始值分别為1和n。每一次循環中移動j，保證i<j，直至ai+aj <= M，然後ans就可以加上j-i。每次循環結尾i向後移動一格。當i == j時循環停止。

時間複雜度是nlogn+n，其實還是O(nlogn).

100.

2. Mismatch

給兩個隻含有小寫字母的字元串a/b，并給兩個數字x/y。請問将字元串a複制x次組成的新字元串A與字元串b複制y次組成的新字元串B在首位對齊時相同位置上字元不同的位數有多少個。輸入資料保證A的長度與B相同。

考場上隻想到了既然給了輸入資料的保證，那麼總長度一定是a與b長度最小公倍數的倍數。但是資料範圍太大眼見過不了，于是就這樣寫了暴力模拟最小公倍數之内的部分然後再乘，30。

後來機智的同學發現其實這道題很數學，兩個字元串的對應與它們的最大公約數很有關。

e.g.

abc

abcde

(3,5)=1.是以以第一個字元串的角度看，每個字元都和所有下面的字元比較了一遍；

abcdabcdabcd

abcdef

(4,6)=2.同樣以第一個字元串的角度看，每個字元都與下面每兩個字元比較一遍。（對于a,比較第1,3,5個）

3. Symmetric Cross 

輸入M，N，以及M*N的隻有0和1組成的矩陣。問半徑最大的symmetric cross半徑是多大，以及中心的坐标。symmetric cross的定義是一個十字，在将其以中心為軸旋轉90°之後與原十字相同。

例：

0 0 0 0 0

0 1 0 0 0

0 0 0 1 0

最大的十字是以（2,2）為中心的半徑為1的十字。（非原樣例資料）

暴力枚舉30……

4. Maze

有兩個人在一個有N間房間的迷宮中探險，一個人從一個房間走到下一個房間需要2min，另一個人從一個房間走到下一個房間需要1min。給出一個長度為N的數列，其中ai = j表示第i個房間通向第j個房間。路是單向的。兩個人從任意兩個不同的房間出發，輸出他們從出發到第一次相遇的最短時間。輸入資料保證這兩個人一定會碰面。

哇這道題絕對是考場上覺得最簡單的一題……

由題意可以知道，有n扇門和n條路，那麼至少有1個環。假如有2個或多個環呢，那麼兩個人就可以分别陷在不同的環裡永遠繞下去。但是輸入資料保證不會出現這一點，可知整個圖有且僅有一個環。

那麼我們就可以讓走得慢的人從環上最長的支鍊的那一端開始出發。由于環和支鍊在其他地方都沒有交點，我們可以保證讓另一個人之前在環上怎麼繞兩個人都不會相遇。那麼我們一定可以構造這樣一種情況使得走的慢的人剛剛到達環上的點時，走的快的人剛好在他前面那一格。

100.

5.Pass the courses

對于每個學生都有一個努力值X和一個天指派Y，對于每一門課也都有相應的兩個值a和b。當且僅當a*X + b*Y > 1時，該學生能夠通過這門課。（X,Y,a,b均為實數）

有Q次操作，每次操作規則如下：

輸入的第一個字元為0：建立一個新的課程。輸入該課程的a,b,以及編号。

輸入的第一個字元為1：删除某個課程。輸入該課程的編号。

輸入的第一個字元為2：查詢某個學生。輸入該學生的X,Y，若該學生能夠通過所有現存課程，輸出1；否則輸出0.

暴力30……