前言
7月泪喊，忙著學(xué)習(xí)ReactNative相關(guān)失息，這部分后續(xù)再詳細(xì)介紹，先抽點時間補(bǔ)上算法文集的更新直焙。
正文
1、Tennis Championship
題目鏈接
** 題目大意：**
n個人參加若干個比賽砂轻，比賽是1v1奔誓，輸?shù)娜瞬荒茉賲⒓颖荣悺?br>
如果一個人贏了k次，那么他只會與贏次數(shù)不小于k-1次的人比賽舔清；
問丝里，贏得最多的那個人曲初，能贏多少次体谒；
(n<=1e18)
** Example**
** input**
4
output
2
樣例解釋：四個人假設(shè)是ABCD，那么可以(A, B)臼婆，(C,D)分配抒痒，A和C贏了；再分配(A,C)颁褂，A贏了故响，共2次。
題目解析：
如果n個人颁独，直接兩兩匹配彩届，贏的人再兩兩匹配，這樣會浪費一部分人誓酒，因為贏k次的人是可以和k-1次的比賽樟蠕；
那么，保證每場比賽都是贏k次和k-1次的人靠柑，即可滿足最優(yōu)解寨辩；（注意，贏0次只能贏0次比）
那么k=1的時候歼冰，sum1=2;
k=2, sum2=2+1=3;
k=3, sum3=sum2+sum1=5;
k=4, sum4=sum3+sum2=8;
k=5, sum5=sum4+sum3=13;
...
sum[i] 表示一個人贏k次靡狞，需要sum[i]個人參與；
以此類推隔嫡，可以得到最大的k值甸怕。
2甘穿、Taxes
題目鏈接
** 題目大意：**
給出一個整數(shù)n（n<=2e9）；
現(xiàn)在把n分成k個數(shù)的和蕾各，假設(shè)是a[i]扒磁，那么有：
a[1]+a[2]+a[3]...=n；（要求a[i]>=2, k>=1)
分出數(shù)字a[i]的cost式曲，為a[i]的最大因子妨托；（除去a[i]）
分成k個數(shù)的代價為k個數(shù)字的cost和；
給出n吝羞，求分成若干個數(shù)字的最小cost兰伤。
** Examples**
** input**
4
** output**
2
樣例解釋：4=2+2，2的代價是1钧排，于是 cost=1+1=2
** 題目解析：**
分出數(shù)字a[i]的cost為a[i]的最大因子敦腔，那么分出素數(shù)的cost為1；
由哥德巴赫猜想可以知道：
1恨溜、任一大于2的偶數(shù)符衔，都可表示成兩個素數(shù)之和；
2糟袁、任一大于5的整數(shù)都可寫成三個質(zhì)數(shù)之和判族。
于是有：
素數(shù)是1；
偶數(shù)是2项戴；
如果是奇數(shù)形帮， 那么最大為3；
還有一種情況是奇數(shù)=2+素數(shù)周叮，因為2也算素數(shù)辩撑，如果能拆出這種答案為2。
可怕的隊友提供的想法仿耽，下面是他短小精悍的代碼：
int isprime (int n) {
for (int i = 2; i * i <= n; ++ i)if (n%i==0) return false;
return true;
}
int main (){
int n; cin >> n;
int ans = 0;
if (isprime(n)) ans = 1;
else if(n%2==0) ans = 2;
else {
if(isprime(n-2)) ans = 2;
else ans = 3;
}
cout<<ans<<endl;
return 0;
}
3合冀、Sea Battle
題目鏈接
** 題目大意：**
n個格子排成一行，b個連續(xù)的格子可以放下一艘ship项贺，總共有a艘ship君躺；
ships可以相鄰，但是不能多個ship覆蓋同個格子敬扛；
現(xiàn)在朝這n個格子開槍晰洒，目前已經(jīng)打了k槍，但是沒有打中一艘ship啥箭；
現(xiàn)在問谍珊，還需要打多少槍，保證至少能打中一艘ship急侥。
n, a, b, k (1?≤?n?≤?2e5, 1?≤?a,?b?≤?n, 0?≤?k?≤?n?-?1)
** Examples**
** input**
5 1 2 1
00100
output
2
4 2
樣例解釋：
5 1 2 1 分別對應(yīng)n砌滞、a侮邀、b、k贝润；
00100 表示第3個格子已經(jīng)開槍打過绊茧；（題目保證1的數(shù)量等于k）
題目解析：
貪心。
從左到右打掘，只要出現(xiàn)連續(xù)的b個空的格子就打一槍华畏，假設(shè)總共打了m槍；
最后因為有a艘船尊蚁，答案就是m-a+1;（假設(shè)有3個位置亡笑，2艘船，那么只要打兩槍即可）
4横朋、Anton and Tree
題目鏈接
** 題目大意：**
n個點的樹仑乌，樹的節(jié)點有兩種黑色（黑、白）琴锭，有兩個操作：
1晰甚、path（u, v)：表示u到v的最短路徑，包括u决帖、v厕九；
2、paint(v)：u是樹上任意點古瓤，假如path(u, v)上所有節(jié)點的顏色相同止剖，那么u的顏色會change（黑白互換）腺阳；
如圖落君，給出一棵樹：
對節(jié)點3進(jìn)行paint操作之后：
現(xiàn)在給出一棵樹和節(jié)點顏色，求最少需要幾次paint操作亭引，使得樹上所有的節(jié)點顏色相同绎速。
n (1?≤?n?≤?200?000)
Examples
input
11
0 0 0 1 1 0 1 0 0 1 1
1 2
1 3
2 4
2 5
5 6
5 7
3 8
3 9
3 10
9 11
** output**
2
** 題目解析：**
相同的顏色縮點，得到一個黑白交替的樹焙蚓。
要使得整棵樹的節(jié)點顏色變成相同纹冤，可以找到最長的鏈，然后對著鏈的中間節(jié)點k购公，不斷進(jìn)行paint(k)操作即可萌京。
答案為最長鏈的長度/2。
要點：并查集縮點+dfs找最長鏈宏浩。
總結(jié)
第1題其實是斐波那契數(shù)列知残，但是用題意很好的包裝起來；
第3題是典型的貪心題目比庄，但是增加了a艘ship的變量求妹，對思考造成一定的影響乏盐；
1、3都很適合作為面試的題目制恍，2父能、4對一個未接觸過該方面知識的人來說不可解。
代碼都可以在github可以找到净神。
