sgu246 Black & White -电脑资料

题目大意：

    给你一个2?N?1个珠子组成的环形项链，珠子只有黑色和白色两种颜色，输入2?N?1，要你求出这串项链中最少要有多少个黑色珠子(MAX)，使得对于所有拥有MAX个黑色珠子的项链总可以找到一对黑色珠子使得去掉这两个黑色珠子将项链分成两段并且其中总有一段珠子的个数为N，

sgu246 Black & White

解题思路：

    首先我们观察发现，ans<=N，这是显然的，但是显然是N。

    我们考虑构造一个方案使得有K个黑色珠子并且不满足上面的要求，那么ans=K+1。

    首先如果第1个放了黑色珠子，那么第1+(n+1)个一定得放白色珠子，第1+(n+1)?2可以放置黑色珠子，意识流之后脑补一下这样构造好像是最大的，那么我们就这么构造了。

    我们假设第i个放黑色，那么我们就可以每次隔n+1放置一个反色的珠子，比如黑白黑白……..

    然后我们发现从i出发最少进行L=LCM(N+1,2?N?1）N+1次就会回到i，那么如果i放置黑色，那么这一次轮回一共可以放置?L2?个黑色珠子，然后一共有2?N?1L个轮回，那么K=2?N?1L??L2?，所以ans=K+1=2?N?1L??L2?+1

AC代码：

<code class="hljs cpp">#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include #include<iostream>using namespace std;int n;int gcd(int a,int b){return a%b==0?b:gcd(b,a%b);}int main(){    scanf("%d",&n);    n=n/2+1;    int Gcd=gcd(n+1,2*n-1);    int L=(long long)(n+1)*(2*n-1)/Gcd/(n+1);    printf("%d",(2*n-1)/L*(L/2)+1);    return 0;}</iostream></cmath></cstring></cstdlib></cstdio></code>