20210321 leetcode 第 48 场双周赛

[21.03.21]双周赛（补题已完成）

字符串中第i大的数字

又读错题了，还好这题过于简单，好改。

---

设计一个验证系统

因为我leetcode做得不多，所以这是第一次见到leetcode的C++题（而不是算法题）。

• 成员变量：public, 不需要self.而是直接调用，尽量不要和传参数重名。

  map

  初始化：注意迭代器的参数类型。

  map<string, int>mm;
  map<string, int>::iterator iter;

  遍历：

  for(iter = mm.begin(); iter != mm.end(); iter++)
      string a = iter->first;
      int b = iter->second;

  访问：

  if(mm[key] > 0)mm[key]++;

  待更新。

---

你能构造出连续值的最大数目

数学归纳法思想：

1. 极端构造序列：1,2,4,8,…
2. 一定无法构造：sum(i) + 1 < a[i+1]，一定会停止
3. a[1] = 1，从0-1都可构造，否则连续值为0.
4. a[2] = 1或2，从0-sum(2)都可构造出来
5. 如果0-sum(i-1)都能构造出来，a[i]不是停止点，那么sum(i-1)+a[i]=sum(i)就能构造出来
   综上，若第一个停止点为a[i]，则最大构造为0-sum(i-1)，答案即sum(i-1)+1
   代码：

   class Solution {
       map<int, bool>mm;
       long long maxm;
   public:
       int getMaximumConsecutive(vector<int>& coins) {
           sort(coins.begin(), coins.end());
           int maxm = 0;
           if(coins[0] > 1)return 1;
           for(int i = 0; i < coins.size(); i++){
               if(coins[i] > maxm+1)break;
               maxm += coins[i];
           }
           return maxm+1;
   
       }
   };

---

N 次操作后的最大分数和

gcd+dfs
对2*N个数两两配对，使得sum(igcd())计算值最大。
先暴力gcd一遍，存数组。然后数据范围实在太小了(15\13*11*9*7*5*3*1撑死1e7)，可以直接dfs。

• 写爆搜的熟练度0分啊，注意return之前的状态还原。
• 复习了gcd的写法（顺便发现原来辗转相除可以不递归的）
• vector.pop_back()
• wa之后一顿debug，最终发现sort(vector.begin(), vector.end())有时候会改变内部元素的值？这就奇怪了，不知道是不是pop_back的原因，或是我的边界值有问题。原因之后搜一下。

  class Solution {
      int sss[15][15];
      bool used[15];
      int pair_number;
      vector<int>score;
      int N;
      int max_ans;
      int nn_score[20];
  public:
      int gcd(int a, int b){
          if(a < b)swap(a, b);
          if(b < 1)return a;
          return gcd(b, a%b);
      }
      
      int calculate_score()
      {
          int ans = 0;
          memset(nn_score, 0, sizeof(nn_score));
          for(int i = 0; i < N; i++)nn_score[i] = score[i];
          sort(nn_score, nn_score+N);
          for(int i = 0; i < N; i++){
              ans += nn_score[i]*(i+1);
          }
          return ans;
      }
      
      int dfs(int id)
      {
          if(id >= 2*N){printf("fatal error!");return -1;}
          while(used[id] && id < 2*N)id++;
          used[id] = true;
          for(int i = id+1; i < 2*N; i++){
              if(used[i])continue;
              used[i] = true;
              score.push_back(sss[id][i]);
              pair_number++;
              if(pair_number == N){
                  int ans = calculate_score();
                  if(max_ans < ans)max_ans = ans;
              }
              else{
                  dfs(id+1);
              }
              used[i] = false;
              score.pop_back();
              pair_number--;
          }
          used[id] = false;
          return 0;
      }
      int maxScore(vector<int>& nums) {
          N = nums.size() / 2;
          max_ans = 0;
          pair_number = 0;
          memset(used, 0, sizeof(used));
          score.clear();
          for(int i = 0; i < 2*N; i++){
              for(int j = i+1; j < 2*N; j++)
              {
                  sss[i][j] = gcd(nums[i], nums[j]);
                  sss[j][i] = sss[i][j];
              }
          }
          dfs(0);
          return max_ans;
          
      }
  };