D - 熄灯啦!讨论
Source
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
非特殊说明,本博所有文章均为博主原创,未经许可不得转载。
如经许可后转载,请注明出处:https://prolightsfxjh.com/article/2016-uestc-training-for-math-d/
共有 0 条评论