程序员进阶之算法练习（二十三）
前言
7月，忙着学习ReactNative相关，这部分后续再详细介绍，先抽点时间补上算法文集的更新。
正文
1、Tennis Championship
题目链接 ** 题目大意：** n个人参加若干个比赛，比赛是1v1，输的人不能再参加比赛。 如果一个人赢了k次，那么他只会与赢次数不小于k-1次的人比赛； 问，赢得最多的那个人，能赢多少次； (n<=1e18)
** Example**
** input**
4
output
2
样例解释：四个人假设是ABCD，那么可以(A, B)，(C,D)分配，A和C赢了；再分配(A,C)，A赢了，共2次。
题目解析： 如果n个人，直接两两匹配，赢的人再两两匹配，这样会浪费一部分人，因为赢k次的人是可以和k-1次的比赛； 那么，保证每场比赛都是赢k次和k-1次的人，即可满足最优解；（注意，赢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
题目链接 ** 题目大意：** 给出一个整数n（n<=2e9）； 现在把n分成k个数的和，假设是a[i]，那么有： a[1]+a[2]+a[3]...=n；（要求a[i]>=2, k>=1) 分出数字a[i]的cost，为a[i]的最大因子；（除去a[i]） 分成k个数的代价为k个数字的cost和；
给出n，求分成若干个数字的最小cost。
** Examples**
** input**
4
** output**
2
样例解释：4=2+2，2的代价是1，于是 cost=1+1=2
** 题目解析：** 分出数字a[i]的cost为a[i]的最大因子，那么分出素数的cost为1； 由哥德巴赫猜想可以知道： 1、任一大于2的偶数，都可表示成两个素数之和； 2、任一大于5的整数都可写成三个质数之和。 于是有： 素数是1； 偶数是2； 如果是奇数， 那么最大为3； 还有一种情况是奇数=2+素数，因为2也算素数，如果能拆出这种答案为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个连续的格子可以放下一艘ship，总共有a艘ship； ships可以相邻，但是不能多个ship覆盖同个格子； 现在朝这n个格子开枪，目前已经打了k枪，但是没有打中一艘ship； 现在问，还需要打多少枪，保证至少能打中一艘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 分别对应n、a、b、k；
00100 表示第3个格子已经开枪打过；（题目保证1的数量等于k）
题目解析： 贪心。 从左到右，只要出现连续的b个空的格子就打一枪，假设总共打了m枪； 最后因为有a艘船，答案就是m-a+1;（假设有3个位置，2艘船，那么只要打两枪即可）
4、Anton and Tree
题目链接 ** 题目大意：** n个点的树，树的节点有两种黑色（黑、白），有两个操作： 1、path（u, v)：表示u到v的最短路径，包括u、v； 2、paint(v)：u是树上任意点，假如path(u, v)上所有节点的颜色相同，那么u的颜色会change（黑白互换）；
如图，给出一棵树：
对节点3进行paint操作之后：
现在给出一棵树和节点颜色，求最少需要几次paint操作，使得树上所有的节点颜色相同。 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
** 题目解析：** 相同的颜色缩点，得到一个黑白交替的树。 要使得整棵树的节点颜色变成相同，可以找到最长的链，然后对着链的中间节点k，不断进行paint(k)操作即可。 答案为最长链的长度/2。
要点：并查集缩点+dfs找最长链。
总结
第1题其实是斐波那契数列，但是用题意很好的包装起来； 第3题是典型的贪心题目，但是增加了a艘ship的变量，对思考造成一定的影响； 1、3都很适合作为面试的题目，2、4对一个未接触过该方面知识的人来说不可解。 代码都可以在github可以找到。