一战通offer第四题解法
题意是由A先选珠子，让B去串，问A至少选几个蓝珠子一定能赢。
我们把珠子从0...n-1编号。
下面所有加减法都默认取模了。
如果A选了x号点，那么如果x-(n/2-1)或x+(n/2-1)是蓝色的，就一定能把项链分成一部分是(n+1)/2的。
那我们把x和那两个点连线，对于整个图都这么做就能画出一个图形（n＝5是五角星）（n＝7是七芒星）。
我们换个问题，A最多选几个蓝色的点使得 一定存在A输的情况 。加一就是原题答案。
现在问题变成如何选出最多的点使得没有两个点是有边相连的（有相连的A就能赢）。
如果我们按我们画出来的图去串项链，那么就变成一串(或者几串)新的项链，而且问题就变成了如何选点使得这个(些)新的项链上没有相邻两个点被同时选中。显然是选一个空一个这样去选能选出最多的。
所以最后问题变成了，把原来的项链分解成几个不相交的部分，每一个部分选出最多的点，加起来就是最多能选多少个蓝色的点使得一定存在A输的情况。加一就是原题的答案。
至于怎么找这些不相交的部分，用循环暴力找就行。
public class Chain {
public int findK(int n) {
boolean[] vis = new boolean[n];
int step = n / 2 - 1;
int ans = 0;
for (int i = 0; i < n; i++) vis[i] = false;
for (int i = 0; i < n; i++) {
if (!vis[i]) ans += findCircle(i, step, n, vis);
}
ans++;
return ans;
}
int findCircle(int i, int step, int n, boolean[] vis) {
int cnt = 0;
while (!vis[i]) {
vis[i] = true;
cnt++;
i = (i + step) % n;
}
return cnt / 2;
}
public static void main(String[] args) {
Chain c = new Chain();
System.out.println(c.findK(5));
System.out.println(c.findK(7));
System.out.println(c.findK(9));
}
}
查看10道真题和解析
