HBCPC2021-河北省大学生程序设计竞赛重现赛 H & K

H-信号传输

• 思路：二分答案，check每个mid；check: 给出一个mid，可以dp求**$mi{n}_{基站间距离}$** >= mid下的$ma{x}_{民众满意度}$，再与w比较。

  #include <bits/stdc++.h>
  using namespace std;
  typedef long long ll;
  const int N = 2e5 + 5;
  int nums[N];
  ll f[N];
  int main () {
      int n;
      ll w;
      scanf("%d%lld", &n, &w);
      for(int i = 1; i <= n; i ++) scanf("%d", &nums[i]);
      if(w == 0) {printf("%d", n + 1); return 0;}
      int l = 0, r = n, mid;
      while(l < r) {
          mid = (l + r + 1) >> 1;
          memset(f, 0, sizeof f);
          for(int i = 1; i <= n; i ++) {
              f[i] = f[i-1];
              if(i - 0 >= mid && n + 1 - i >= mid) f[i] = max(f[i], f[i-mid] + nums[i]);
          }
          if(f[n] >= w) l = mid;
          else r = mid - 1;
      }
      if(l) printf("%d", l);
      else printf("-1");
      return 0;
  }
  

K-Kate and Company Management

• 大意：给出n个不同的数，求ans = $ma{x}_k$ ，存在k个数满足：k >= 3，组成的递增序列的相邻元素间gcd != 1 即不互质；若不存在这样的k，ans = -1;

• 思路：一眼dp，但会T，O($n^2$);

  for(int i = 1; i <= n; i ++) {
      dp[i] = 1;
      for(int j = 1; j < i; j ++) {
          if(gcd(nums[i], nums[j]) != 1) dp[i] = max(dp[i], dp[j] + 1);
      }
  }
  

  所以我们考虑优化，我们发现内层循环负责在前 i-1 个数里找与$num{s}_i$不互质的数，然后尝试更新dp[i]；那在此做优化，试着更快去找这样的数。

  #include<bits/stdc++.h>
  using namespace std;
  typedef long long ll;
  const int N = 1e5 + 5;
  int nums[N];
  int prime[N], cnt;
  vector<int> apart[N];
  bool vis[N], st[N];
  void apartNums(int n) {
      vis[1] = 1;
      if(st[1]) apart[1].push_back(1);
      for (int i = 2; i <= n; ++i) {
          if (!vis[i]) {
              prime[cnt ++] = i;
              if(st[i]) apart[i].push_back(i);
              for (int j = i + i; j <= n; j += i) {
                  vis[j] = true;
                  if(st[j]) apart[j].push_back(i);
              }
          }
      }
  }
  map<int, int> mp;
  int res[N];
  int main() {
      int n, ans = 1;
      scanf("%d", &n);
      for(int i = 1; i <= n; i ++) {scanf("%d", &nums[i]); st[nums[i]] = true;}
      sort(nums + 1, nums + n + 1);
      apartNums(1e5);
  //    for(int i = 1; i <= n; i ++) {
  //        for(int v : apart[nums[i]]) printf("%d ", v);
  //        puts("");
  //    }
      for(int i = 1; i <= n; i ++) {
          res[i] = 1;
          for(int v : apart[nums[i]]) {
              if(mp[v]) {
                  res[i] = max(res[i], res[mp[v]] + 1);
              }
              mp[v] = i;
          }
          ans = max(res[i], ans);
      }
  //    for(int i = 1; i <= n; i ++) printf("%d ", res[i]);puts("");
      if(ans < 3) printf("-1");
      else printf("%d", ans);
  	return 0;
  }
  

  • 优化：先排序；

    定义map <key: 质因子，val: 目前质因子中有key的最后一个数的id >；

    st[], vis[], prime[]辅助apartNums函数对nums[]分解；（你应该看出来了，我对埃式筛做了小修改以用来分解n个数）

    apart[nums[i]]存nums[i]分解后的质因子；

• Q：为什么map会有这么奇怪的定义？

  A：首先，两个数有相同的质因子，显然两数不互质；res[i]表示以nums[i]结尾的满足题意的最长序列长度；若当前数的质因子存在于map（即与之前某数nums[val]不互质），则可接在以nums[val]结尾的满足题意的序列后。
  我讲不清， 不明白就取消注释，看看res[]。

说明：

如有转载请在显著位置给出博文链接和作者姓名。