B题
https://ac.nowcoder.com/acm/contest/9716/B
int dp[1001][1001]; class Solution { public: /** * * @param n int整型 乐谱总音符数 * @param m int整型 重音符数 * @param k int整型 重音符之间至少的间隔 * @return long长整型 */ long long solve_bangbang(int n, int m, int k) { // write code here memset(dp,0,1001*1001*4); if(m==0) return 1LL;//这个是坑点 if(n==0) return 0LL; int dev=1e9+7; for(int i=0;i<n;i++){ dp[i][1]=1; if(i-k>0){ for(int j=1;j<m;j++) dp[i][j+1]=dp[i-k-1][j]%dev; } if(i){ for(int j=1;j<=m;j++) dp[i][j]=(dp[i][j]+dp[i-1][j])%dev; } } return (long long)dp[n-1][m]; } };
C题,暂时只想到二分查找
https://ac.nowcoder.com/acm/contest/9716/C
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param n int整型 * @return long长整型 */ int func(int v,int low,int high,int n){ int mid,x,ans; while(high>=low){ mid=(low+high)/2; x=n/mid+((n%mid)?1:0); if(x<v){ high=mid-1; }else{ low=mid+1; ans=mid; } } return ans; } long long Sum(int n) { // write code here int low=1,v,high; long long ans=0; while(low<=n){ v=n/low+((n%low)?1:0); high=func(v,low,n,n); ans+=(high-low+1)*v; low=high+1; } return ans; } };