- 题解
拿石子题解
- 2024-1-24 20:41:51 @
这题改自CSP-J2023的T1小苹果,原题见洛谷
本人参赛的时候0分,厚礼蟹!
今天我来造福大众
先看第一个问题:
要几轮才能拿完石子? 我们只需要模拟出来一轮会拿走几个石子,再一轮一轮拿,每轮计数器+1,直到拿完,输出计数器的值 至于每轮拿几个,上打表法! k=2时:
n=1,2,3 | n=4,5,6 | n=7,8,9 | ... |
---|---|---|---|
1 | 2 | 3 | ... |
由此可以得出k=2时,每轮要拿(n+2)/3个石子 再然后另外两个打表也能得出来:
k=3时,每轮要拿(n+3)/4个石子
k=4时,每轮要拿(n+4)/5个石子
如果你特别聪明,一定发现了:
每轮你可以拿(n+k)/(k+1)个石子
再看第二个问题:
拿走第n个石子是在第几轮? 这个问题可以画图研究:
●○○○……○(k+1个)●○○○…○●……●○○○…○(k+1个)●
可以看出,在剩余石子能被分成若干个k+1还剩余一个时(即n%(k+1)==1),就能拿走第n个石子 那么只要满足这个条件就行吗?
NO!!!!
让我们看看n=7, k=2的情况
- ●○○●○○● 此时第7个已经被拿走
- ●○○●虽然也满足n%(k+1)==1,但如上面所说,第7个早被拿走了,不符合条件
所以,我们必须保证是第一次满足这个条件,第n个石子才会被拿走,那该怎么办呢?
Flag~~
只要用一个flag标记一下首次就行了
由此得代码:
#include<bits/stdc++.h>
using namespace std;
int main(){
long long n,k,a=0,ans,flag=0;
//a是拿的轮数, ans为拿走第n个石子的轮次,flag是标记“第一次满足n%(k+1)==1”
cin>>n>>k;
while(n!=0){
a++; //每拿一轮轮次数+1
if(n%(k+1)==1&&flag==0){
ans=a;
flag++; //若是第一次满足,就给flag+1,完成标记
}
n-=(n+k)/(k+1); //刚推的公式
}
cout<<a<<" "<<ans;
return 0; //好习惯
}
看完这里,点个赞再走吧❤
2 条评论
-
@ 2024-1-24 21:31:01
哇靠
-
2024-1-24 21:24:55@
写题解不易,看客老爷们点个赞吧!
👍 2
- 1