巅峰赛S2赛季第三场青铜A,B题
A-牛牛打怪:
在第i天里,牛牛能杀死防御力小于等于i的怪物。牛牛每天最多杀一只怪物。这个游戏共有n只怪物,每只怪物的防御力为DEF[i],牛牛想知道最少要到第几天才能把这n只怪物都杀死。
按题意直接模拟
代码
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param n int整型 * @param DEF int整型vector * @return int整型 */ int Minimumdays(int n, vector<int>& DEF) { // write code here sort(DEF.begin(),DEF.end()); int i = 0;int j = 1; while(i<n) { if(j>=DEF[i]) i++; if(i==n) break; j++; } return j; } };
B-简单的公式:
a[1]=2,a[2]=6,对所有的n>=3,a[n] = 2a[n-1] + 3a[n-2]。
b[1]=7,b[2]=35,对所有的n>=3,b[n] = 3b[n-1] + 10b[n-2]。
对所有的n>=1,有c[n] = a[n]b[n]。*
现在给你一个正整数n,返回c[n]%1000000007的值。
即求c[n]%1000000007,要通过c[n] = a[n]*b[n]计算。
无脑打表康一下结果:
列依次是a、b、c数组,容易发现C[n] =
那就上快速幂吧
class Solution { public: /** * 返回c[n]%1000000007的值 * @param n long长整型 即题目中的n * @return int整型 */ __int128 Qpow(__int128 a,__int128 b) { __int128 ret = 1; a = a%1000000007; while(b) { if(b&1) ret = ret*a%1000000007; a=a*a%1000000007; b >>= 1; } return ret; } int Answerforcn(long long n) { // write code here return 14*Qpow(15,n-1)%1000000007; } };