题目链接：Here

ABC水题，

D. Not Divisible

看了题解才想到，可以用 Sieve of Eratosthenes，因为 AtCoder Beginner Contest 170 （D~F题，D筛法，E multiset使用，F Dijkstra算法改进） - 图1 最大才 AtCoder Beginner Contest 170 （D~F题，D筛法，E multiset使用，F Dijkstra算法改进） - 图2

但有注意的点

  1. 1
  2. 1
  3. 5
  4. 2 2 2 3 3
  5. 5
  6. 2 2 2 4 4
  7. 5
  8. 1 1 1 1 2

重复出现的数字

简单的说：找出数列中不是其他数的倍数的数的个数（拗口）。用小数筛大数。

  1. const int N = 1e6 + 10;
  2. int a[N], cnt[N];
  3. bool st[N];
  4. int main() {
  5.     cin.tie(nullptr)->sync_with_stdio(false);
  6.     int n; cin >> n;
  7.     for (int i = 1; i <= n; ++i) cin >> a[i], cnt[a[i]] += 1;
  8.     for (int i = 1; i <= N; ++i) {
  9.         if (cnt[i]) {
  10.             if (cnt[i] > 1) st[i] = 1; // 对于重复出现的数据也要标记
  11.             for (int j = i + i; j <= N; j += i) st[j] = 1;
  12.         }
  13.     }
  14.     int ans = 0;
  15.     for (int i = 1; i <= n; ++i) ans += !st[a[i]];
  16.     cout << ans;
  17. }

E. Smart Infants

照着题目模拟就是，问题主要是要用对资料结构。 对于每个 kindergarden 我们需要一个可以高速插入、高速删除、高速查询最大值的容器。

C++ 的 multiset 符合所需。 使用 c++ 的 multiset 要注意的一点是 set.erase(val) 会删除容器中所有值为 val 的 entries，若只想删除一个值为val 的 entry，要用 set.erase(set.find(val))。

即：对每次变换求所有集合最大值中的最小值。用s[]表示各个集合，m表示最大值集合，每次对集合元素删除加入。注意元素有可能相同，所以要用multiset.

  1. int main() { // try new nameing rules and Coding style
  2.     cin.tie(nullptr)->sync_with_stdio(false);
  3.     int N, Q;
  4.     int M = 2e5;
  5.     cin >> N >> Q;
  7.     auto belong = vector<int>(N, -1);
  8.     auto rating = vector<int>(N, -1);
  9.     auto evenesses = multiset<int>();
  10.     auto kdrgrtns = vector<multiset<int>>(M);
  12.     for (int i = 0; i < N; ++i) {
  13.         int A, B;
  14.         cin >> A >> B;
  15.         B--;
  16.         rating[i] = A;
  17.         belong[i] = B;
  18.         kdrgrtns[B].insert(A);
  19.     }
  20.     for (auto k : kdrgrtns) {
  21.         if (!k.empty())
  22.             evenesses.insert(*k.rbegin());
  23.     }
  25.     while (Q--) {
  26.         int C, D;
  27.         cin >> C >> D;
  28.         C--, D--;
  30.         auto &kdrgrtn_src = kdrgrtns[belong[C]];
  31.         auto &kdrgrtn_dst = kdrgrtns[D];
  33.         evenesses.erase(evenesses.find(*kdrgrtn_src.rbegin()));
  34.         kdrgrtn_src.erase(kdrgrtn_src.find(rating[C]));
  35.         if (kdrgrtn_src.size() > 0)
  36.             evenesses.insert(*kdrgrtn_src.rbegin());
  38.         if (kdrgrtn_dst.size() > 0)
  39.             evenesses.erase(evenesses.find(*kdrgrtn_dst.rbegin()));
  40.         kdrgrtn_dst.insert(rating[C]);
  41.         evenesses.insert(*kdrgrtn_dst.rbegin());
  43.         belong[C] = D;
  45.         cout << *evenesses.begin() << "\n";
  46.     }
  47. }

F. Pond Skater

Snuke，水上平衡车，住在一个矩形池塘，可以看成 H 列 W 行，(i, j) 表示第 i 列第 j 行。池塘里长着荷叶，荷叶是不能进入的。如果 cij 是 @，表示荷叶。如果 cij 是 .，表示不是荷叶。

Snuke 每次可以向北、东、南、西的任意同一个方向移动一步到 K 步，但是不能通过荷叶，同时也不能移动到池塘外。

给我们起点坐标 (x1, y1) 和终点坐标 (x2, y2)，要求我们找到最小的移动步数。如果不能到达，输出 -1。

Here 有一个博主写了很详细的分析

这题马上让人想到是最短路径，于是就刻了一个 Dijkstra，然后就会 TLE。

对于每个 vertex 我们都展开 4 * K 条边实在太多了，所幸我们可以剪枝。

当我们在 (r, c)，尝试用 dis[r][c] + 1 松弛 dis[r + k * dr][c + k * dc] 不成功时，我们不需要展开更大的 k，因为那些更远的点（即 k 更大）不可能透过目前的路径得到更佳的解。

写成程式码就是在展开边的地方加入剪枝：

  1. // omit
  2. for (int k = 1; k <= K; k++) {
  3.     // omit
  4.     if (dis[r + k * dr][c + k * dc] < dis[r][c] + 1) break;
  5.     // omit
  6. }

你就能 AC 了。官方題解我是沒有看懂，這題網路上的題解都是 BFS + 剪枝，我是覺得挺神奇的啦，最短路徑不是應該想到 Dijkstra 嗎？還有人說此剪枝方法不適用 Dijkstra，只能用在 BFS 上 (┛ಠ_ಠ)┛彡┻━┻

  1. using ti3 =  tuple<int, int, int>;
  2. const int inf = 0x3f3f3f3f;
  3. int main() {
  4.     cin.tie(nullptr)->sync_with_stdio(false);
  5.     int H, W, K;
  6.     cin >> H >> W >> K;
  7.     int sr, sc, tr, tc;
  8.     cin >> sr >> sc >> tr >> tc;
  9.     sr--, sc--, tr--, tc--;
  10.     vector<string> S(H);
  11.     for (int i = 0; i < H; ++i) cin >> S[i];
  13.     vector<ti3> nxt;
  14.     nxt.push_back({+1, 0, 1});
  15.     nxt.push_back({-1, 0, 1});
  16.     nxt.push_back({0, +1, 1});
  17.     nxt.push_back({0, -1, 1});
  19.     vector<vector<int>> dis(H, vector<int>(W, inf));
  20.     auto q = priority_queue<ti3, vector<ti3>, greater<ti3>>();
  22.     dis[sr][sc] = 0;
  23.     q.push({0, sr, sc});
  25.     while (!q.empty()) {
  26.         auto [d, r, c] = q.top(); q.pop();
  27.         if (d > dis[r][c]) continue;
  28.         for (auto &&[dr, dc, w] : nxt) {
  29.             for (int k = 1; k <= K; ++k) {
  30.                 int nr = r + k * dr;
  31.                 int nc = c + k * dc;
  32.                 if (nr < 0 || nr >= H) break;
  33.                 if (nc < 0 || nc >= W) break;
  34.                 if (S[nr][nc] == '@') break;
  35.                 if (dis[nr][nc] < d + w) break;
  36.                 if (dis[nr][nc] > d + w) {
  37.                     dis[nr][nc] = d + w;
  38.                     q.push({dis[nr][nc], nr, nc});
  39.                 }
  40.             }
  41.         }
  42.     }
  44.     cout << (dis[tr][tc] == inf ? -1 : dis[tr][tc]);
  45. }