leetcode周赛 248

A：模拟题。

 1 class Solution {
 2 public:
 3     vector<int> buildArray(vector<int>& nums) {
 4         int n=nums.size();
 5         vector<int> ans(n);
 6         for(int i=0;i<n;i++){
 7             ans[i]=nums[nums[i]];
 8         }
 9         return ans;
10     }
11 };

B：一眼能够看出来的贪心题。

求出一个怪物到达时间数组，然后将其排序，直接枚举时间（也是编号）即可。

【注】如果怪物是刚好在2时刻到达的话，你是来不及将其击杀的，所以还得保存dist/speed是否整除的信息。

 1 class Solution {
 2 public:
 3     int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
 4         int n=dist.size();
 5         vector<pair<int,int>> v(n);
 6         for(int i=0;i<n;i++){
 7             v[i].first=dist[i]/speed[i];
 8             if(dist[i]%speed[i]==0)
 9                 v[i].second=0;
10             else
11                 v[i].second=1;
12         }
13         sort(v.begin(),v.end());
14         int res=0;
15         for(int i=0;i<n;i++){
16             if(v[i].first<i||(v[i].first==i&&v[i].second==0))
17                 break;
18             res++;
19         }
20         return res;
21     }
22 };

C：组合数学计数问题+快速幂

 1 typedef long long LL;
 2 const LL mod=1e9+7;
 3 class Solution {
 4 public:
 5     LL qmi(LL a,LL b){
 6         LL res=1;
 7         while(b){
 8             if(b&1)
 9                 res=res*a%mod;
10             b>>=1;
11             a=(a*a)%mod;
12         }
13         return res%mod;
14     }
15     int countGoodNumbers(long long n) {
16         LL t1=n/2+(n%2==1);
17         LL t2=n/2;
18         LL res=(qmi(5,t1)*qmi(4,t2))%mod;
19         return res%mod;
20     }
21 };

D：待补充。。。