2016 UESTC Training for Math D – 熄灯啦! 讨论

ProLightsfx 2016-7-8 124 7/8

D - 熄灯啦!讨论

 

 

Source

2016 UESTC Training for Math

My Solution

本题的精髓在于对奇偶性的讨论。

当n>k时的讨论:

--情况 1: 若 n 为 奇数 --

1.1 若k 为偶数 => 无解

证明:

若要让所有硬币最终翻面,则每个硬币都要翻面奇数次,共有奇数个硬币,

所以所有硬币的翻面总数为奇数,但每次只能翻面偶数个硬币,显然不可能

证毕。

1.2若k为奇数=> p为不小于n/k的最小奇数

(例l n=7. k=5,那么 n/k=1.4则p=3)

(例2  n=20,k=7,那么 n/k=25/7 则 p = 5)

证明:

必要性:

若要让所有硬币最终翻面,则每个硬币都要翻面奇数次,共有奇数个硬币,所以所有硬币的翻面总数为

奇数,而每次只能翻奇数个硬币,所以总的翻转次数必然是奇数次,而翻转次数不到n/k次时,

并不能使所有硬币至少翻面1次,所以p至少是不小于n/k的最小奇数。

充分性:

·当k = n - 2时,只要3次翻转即可

结硬币编号为l-n,

第1次翻转编号:1~ n-2

第2次翻转编号:1~ n-3、n-i

第3次翻转编号:1~ n-3、n

Dome!(前n-3个硬币翻面3次,后3个翻面1次

·当n/3 <= k < n-2时,依然只要3次翻转

只要让前面的(3*k - n)/2 个硬币翻转3次, 后面的(3*n - 3*k)/2个硬币翻转1次即可。 这显然可以做到的

·当k < n/3时,需要翻转p次(p为不小于n/k的最小奇数)

根据定义, p^k >= n, (p - 2)*k < n,由于k < n,所以 p^k < 3*n,,这意味者翻转p次后,

平均来说,每个硬币翻面次数小于3次。只要让前面的(p^k - n)/2个硬币翻转3次,

后面的(3*n - 3*k)/2个硬币翻转1次即可。

--情况 2: 若 n 为 偶数 --

2.1若n/2 < k < n - 1 且为偶数 => p=3

只要让前面的(3*k - n)/2个硬币翻转3次,后面的(3*n - 3*k)/2个硬币翻转1次即可

这个情况,和n为奇数是类似的。

2.2若n/2 < k < n -l且为奇数=>p为不小于n/(n-k)的最小偶数

这种情况比较特殊。

首先由奇偶性得出翻转次数必为偶数,而每一枚硬币翻转的次数为奇数,则每枚硬币至少不翻转1次

其次,每次有n/k枚不翻转,所以p 必须不小于n/(n - k).

方案:让前面(k*p - n*p + 3*n)/2 硬币翻转p-1次,后面(n*p - k*p - n)/2硬币翻转p-3次

2.3若k <= n/2且为偶数=>p为不小于n/k的最小整数

当k = n/2时,显然 p = 2,

反之,只要让前面的(p*k - n)/2个硬币翻转3次,后面的(3*p - p*k)/2个硬币翻转1次即可。

2.4若k <= n/2且为为奇数=> p为不小于n/k的最小偶数

当k = n/2;时,显然p=2,

反之,首先由奇偶性得出翻转次数必为偶数,

只要让前面的(p*k - n)/2个硬币翻转3次,后面的(3*n - p*k)/2个硬币翻转1次即可

综上所述:

若n为奇数:

·若k为偶数 => 无解

·若k为奇数 => p为不小于n/k的最小 奇数

若n为偶数:

·若k为偶数,且n/2 < k < n - 1 => p = 3

·若k为奇数,且n/2 < k <= n - 1 => p 为不小于n/(n-k)的最小 偶数

·若k为偶数,且k <= n/2 => p 为不小于n/k的最小 整数

·若k为奇数,且k <= n/2 => p 为不小于n/k的最小 偶数

呵呵哒, 这么多字, (┬_┬)

复杂度O(1)

注意点:

WA8 2次, 那个地方忘了加括号了if((n/k + 1) % 2 == 0) ans = n/k + 1;

前面写成if(n/k + 1 % 2 == 0) ans = n/k + 1; (┬_┬),时不时智障。

另外注意, 一些带 / 的不等式,作为判断条件时, 注意可能会有精度损失

比如if(n/2 < k && k < n - 1)

还是改成 if(n < k*2 && k < n - 1) 比较保险, 不然可能会WA

 

#include 
#include 
using namespace std;

int main()
{
    int n, k, ans = 0;
    scanf("%d%d", &n, &k);
    if(n & 1){
        if(k & 1){
            if(n/k*k == n){
                if(n/k % 2 == 1) ans = n/k;
                else ans = n/k + 1;
            }
            else{
                if((n/k + 1) % 2 == 1) ans  = n/k + 1;
                else ans = n/k + 2;
            }
        }
        else{
            ans = -1;
        }
    }
    else{
        if(k & 1){ // ans 为不小于n/(n-k)的最小 偶数
            if( n < k*2 && k <= n - 1){
                if(n/(n-k)*(n-k) == n){
                    if(n/(n-k) % 2 == 0) ans = n/(n-k);
                    else ans = n/(n-k) + 1;

                }
                else{
                    if((n/(n-k) + 1) % 2 == 0) ans = n/(n-k) + 1;
                    else ans = n/(n-k) + 2;
                }
            }
            else{
                if(n/k*k == n){
                    if(n/k % 2 == 0) ans = n/k;
                    else ans = n/k + 1;
                }
                else{
                    if((n/k + 1) % 2 == 0) ans = n/k + 1;
                    else ans = n/k + 2;
                } //cout<<"here"<<endl;
            }
        }
        else{ //k 为偶数
             if(n < k*2 && k < n - 1) ans = 3;    //k , n 都是偶数, 故 k 不可能 电影 n - 1
             else{
                if(n/k*k == n)
                    ans = n/k;
                else
                    ans = n/k + 1;
             }
        }
    }
    printf("%d", ans);
    return 0;
}

 


非特殊说明,本博所有文章均为博主原创,未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx

- THE END -

ProLightsfx

11月15日21:32

最后修改:2024年11月15日
0

非特殊说明,本博所有文章均为博主原创,未经许可不得转载。

共有 0 条评论