更新时间:2022-08-19 22:35:20
思路: 贪心+快速幂
分析:
1 题目要求的是找到这个人的最小的分数
2 题目的数据非常大,很明显是有一个O(1)的算法也就是公式
3 我们考虑n个数分成连续的k个树有几段,设x = n/k , 那么我们就可以知道x段连续的区间里面如果每一段都让它错一个那么我们至少可以答对x*(k-1),现在我们去判断x*(k-1) >= m, 如果是那么答案就是m,否则就去判断剩下的问题就是t = n-x*k 和 剩下的答对问题的个数为z = m-x*(k-1),如果t >= z那么ans就是x*(k-1)+z , 否则的话我们知道应该要把后面的错的个数拿来用,那么我们可以求出拿来用的个数t-z。那么接下来只要去求连续的t+(t-z)*k个数的得分加上后面的一段即可
代码:
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int MOD = 1e9+9; int n , m , k; long long Pow(long long m , long long n){ long long ans = 1; while(n){ if(n&1) ans = (ans*m)%MOD; m = (m*m)%MOD; n >>= 1; } return ans; } long long getAns(){ int numk = n/k; // 第一次判断 if(numk*(k-1) >= m) return m; int rest_n = n-k*numk; int rest_m = m-numk*(k-1); // 第二次判断 if(rest_m <= rest_n) return (numk*(k-1)+rest_m)%MOD; // 第三次判断 int t = rest_m-rest_n; int num = rest_n+t*k; long long ans = (numk-t)*(k-1)%MOD; numk = num/k; ans = (ans+num-numk*k)%MOD; ans = ans + 2*(k*(Pow(2 , numk)-1))%MOD; return ans%MOD; } int main(){ while(scanf("%d%d%d" , &n , &m , &k) != EOF){ printf("%lld\n" , getAns()); } return 0; }