Codeforces Round #703 (Div. 2)

博主： spirit
发布时间：2021 年 02 月 19 日
3613 次浏览
暂无评论
1885字数
分类： Codeforces

# [Codeforces Round #703 (Div. 2)](https://codeforces.com/contest/1486)

## [A - Shifting Stacks](https://codeforces.com/contest/1486/problem/A)

- 题意：有 $n$ 个堆栈，给出每个堆栈中的元素数量，你可以从第 $i$ 个堆栈的堆顶拿走一个元素放到第 $i + 1$ 个堆栈中去，问是否可以令堆栈的元素数量严格递增？
- 极限情况下，堆栈的元素分布应该为：$0, 1, 2, ···, n - 1$，对于前 $i$ 个堆栈，前缀和应该至少为 $\frac{i (i - 1)}{2}$ ，循环判断一遍即可。

## [B - Eastern Exhibition](https://codeforces.com/contest/1486/problem/B)

- 题意：在一个二维平面上有 $n$ 个房子，给出对应坐标，要求在平面上选择一个点使得该点到 $n$ 个房子的距离和最小。$(x1, y1)$ 和 $(x2, y2)$ 的距离为 $|x1 - x2| + |y1 - y2|$ 。问有多少个点可以选择。
- 思路：选取 $x$ 坐标的中位数和 $y$ 坐标的中位数即可，如果 $n$ 为偶数，则可选区域为一个矩形。
- 代码：
  
  ```cpp
  #include <bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  const int N = 1010;
  int x[N], y[N];
  
  int main(int argc, char const *argv[]) {
      int t, n;
      cin >> t;
      while (t--) {
          scanf("%d", &n);
          for (int i = 1; i <= n; i++) scanf("%d %d", &x[i], &y[i]);
          sort(x + 1, x + n + 1);
          sort(y + 1, y + n + 1);
          LL res;
          if (n & 1) {
              res = 1;
          } else {
              res = (x[n / 2 + 1] - x[n / 2] + 1) *
                    (LL)(y[n / 2 + 1] - y[n / 2] + 1);
          }
          printf("%lld\n", res);
      }
      return 0;
  }
  ```

## [C1 - Guessing the Greatest (easy version)](https://codeforces.com/contest/1486/problem/C1)

## [C2 - Guessing the Greatest (hard version)](https://codeforces.com/contest/1486/problem/C2)

- 题意：互动题目，存在一个大小为 $n$ 的序列，你可以进行询问操作：区间 $[l, r]$ 内第二大的元素位置 $pos$ 为多少，要求在不超过 $20$ 次询问后给出序列中最大值的位置。
- 思路：首先询问 $[1, n]$ 区间，得到 $pos$ ，通过询问区间 $[1, pos]$ ，判断是否有 $ask(1, pos) = pos$ ，如果是说明最大值在区间 $[1, pos]$ 内，否则在 $[pos + 1, r]$ 内。以右区间为例，令 $l = pos + 1$， 每次取 $mid = l + r >> 1$ ，判断最大值是否在区间 $[pos, mid]$ 内，最终可以找到可以使 $ask(pos, p) = pos$ 的 $p$ 的最小取值，此时 $p$ 的位置就是最大值。
- 代码：
  
  ```cpp
  #include <bits/stdc++.h>
  using namespace std;
  
  int ask(int l, int r) {
      int pos;
      cout << "? " << l << ' ' << r << endl;
      cin >> pos;
      return pos;
  }
  
  int main(int argc, char const *argv[]) {
      int n, l, r, pos;
      cin >> n;
      l = 1, r = n;
      pos = ask(l, r);
      if (pos == 1 || ask(l, pos) != pos) {
          l = pos + 1;
          while (l < r) {
              int mid = (l + r) / 2;
              if (ask(pos, mid) == pos)
                  r = mid;
              else
                  l = mid + 1;
          }
          cout << "! " << r << endl;
      } else {
          r = pos - 1;
          while (l < r) {
              int mid = (l + r + 1) / 2;
              if (ask(mid, pos) == pos)
                  l = mid;
              else
                  r = mid - 1;
          }
          cout << "! " << l << endl;
      }
      return 0;
  }
  ```

## [D - Max Median](https://codeforces.com/contest/1486/problem/D)

- 题意：给出一个长度为 $n$ 的序列，要求你选择一个长度至少为 $k$ 的子段 $[l, r]$ ，令这段序列的中位数最大，输出这个数字。
- 思路：二分答案，$check(x)$ 函数判断是否存在存在一个长度不小于为 $k$ 的子段，其中位数不小于 $x$ 。如果我们把序列中小于 $x$ 的数字记为 $-1$ ，其他数字为 $1$ ，那么区间 $[l, r]$ 的中位数大于等于 $x$ 的充分必要条件为 $sum[l, r] > 0$ 。可以通过前缀和快速找到以 $i$ 结尾的子段中和最大的一个，只需要在 $pre_1, pre_2, ···, pre_{i - k}$ 中找到最小的一个，令 $pre_i - pre_{min}$ 即可。
- 代码：
  
  ```cpp
  #include <bits/stdc++.h>
  using namespace std;
  const int N = 2e5 + 10;
  int a[N], b[N];
  
  bool check(int m, int n, int k) {
      for (int i = 1; i <= n; i++) {
          if (a[i] >= m) b[i] = 1;
          else b[i] = -1;
          b[i] += b[i - 1];
      }
      int mx = b[k], mn = 0;
      for (int i = k + 1; i <= n; i++) {
          mn = min(mn, b[i - k]);
          mx = max(mx, b[i] - mn);
      }
      if (mx > 0) return true;
      return false;
  }
  
  int main(int argc, char const *argv[]) {
      int n, k, l, r, res;
      cin >> n >> k;
      for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
      l = 1, r = n;
      while (l <= r) {
          int mid = l + r >> 1;
          if (check(mid, n, k)) {
              res = mid;
              l = mid + 1;
          } else {
              r = mid - 1;
          }
      }
      cout << res << endl;
      return 0;
  }
  ```

## [E - Paired Payment](https://codeforces.com/contest/1486/problem/E)

- 题意：给出一个带权无向图（不保证连通），起点为 $1$ ，每次必须连续走两条边，即从 $a$ 到 $c$ 需要走 $a -> b -> c$ ，记 $w1 = w(a, b)$ $w2 = w(b, c)$ ，则由 $a$ 到 $c$ 的花费为 $(w1 + w2)^2$ ，且在该过程中点 $b$ 不视为可到达。求点 $1$ 到其他点的最短路。
- 思路一：既然 $a - b - c$ 的过程中 $b$ 视为未到达，那么我们虚构一个点 $(b, w1)$ 。上述过程变为 $a - (b, w1) - c$ ，其中 $a - (b, w1)$ 边权为 $0$ ，$(b, w1) - c$ 边权为 $(w1 + w2)^2$ ，如果能将整张图建成上述的虚构图，那么就可以直接跑最短路算法了。重点就在于建图这一步，注意到题目中 $1 \leq w_i \leq 50$，我们可以将节点 $b$ 的编号在虚构图中设为 $b \cdot 51$ ，对于节点 $(b, w1)$ ，编号为 $b \cdot 51 + w1$ ，这样可以保证所有可能出现的虚构点与原图中的点都在虚构图中。对于任意一条边 $(u, v, w)$ 而言，我们考虑这条边可能是第一条边还是第二条边：如果对应的是 $a - b$ 这一步，那么直接在点 $u$ 和点 $(v, w)$ 之间建边即可；如果对应的是 $b - c$ 这一步，需要在点 $(u, was)$ 和点 $v$ 之间建边，$1 \leq was \leq 50$ 。可以发现虚构图的规模是原图的 $50$ 倍，直接跑一遍 $Dijkstra$ 算法即可。
- 思路一代码：
  
  ```cpp
  #include <bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  typedef pair<int, int> PII;
  const int INF = 0x3f3f3f3f;
  
  int main(int argc, char const *argv[]) {
      int n, m;
      cin >> n >> m;
      vector<vector<pair<int, int>>> G((n + 1) * 51);
      auto addedge = [&](int u, int v, int w) {
          G[u * 51].push_back({v * 51 + w, 0});
          for (int was = 1; was <= 50; ++was) {
              G[u * 51 + was].push_back({v * 51, (w + was) * (w + was)});
          }
      };
      for (int i = 0; i < m; i++) {
          int u, v, w;
          scanf("%d %d %d", &u, &v, &w);
          addedge(u, v, w);
          addedge(v, u, w);
      }
      set<pair<int, int>> se;
      vector<int> d(G.size(), INF);
      d[51] = 0;
      se.insert({d[51], 51});
      while (se.size()) {
          auto p = *se.begin();
          se.erase(se.begin());
          for (auto it : G[p.second]) {
              if (d[it.first] > d[p.second] + it.second) {
                  se.erase({d[it.first], it.first});
                  d[it.first] = d[p.second] + it.second;
                  se.insert({d[it.first], it.first});
              }
          }
      }
      for (int i = 1; i <= n; i++) {
          int ans = d[i * 51];
          if (ans == INF)
              printf("-1 ");
          else
              printf("%d ", ans);
      }
      return 0;
  }
  ```
- 思路二：队友在原图上直接进行 $Dijkstra$ 算法，通过二重 $for$ 循环查找点 $a$ 可以到达的所有点 $c$ 。剪枝：为中间点 $b$ 记录一个值 $first_b$ ，该值存放已经搜索过的 $a - b$ 边权的最小值。若在外层循环处发现 $first_b \leq w(a, b)$ ，直接 `continue` 即可。由 $Dijkstra$ 算法本身升序寻找最短路的特性可以推导出该剪枝的正确性：记已经搜索过的点为 $u$ ，那么有 $dist_a >= dist_u$ ，如果同时 $w(a, b)$ 比之前搜索过的边权大，显然这样得到的 $dist_a + (w1 + w2)^2$ 不可能更新任何一个点 $c$ 。同时由于 $1 \leq w_i \leq 50$ ，该剪枝可以保证算法运行效率最差是普通 $Dijkstra$ 算法的 $50$ 倍，时间复杂度上比思路一还要好。
- 思路二代码：
  
  ```cpp
  #include <bits/stdc++.h>
  
  using namespace std;
  const int N = 2e5 + 10;
  const int INF = 0x3f3f3f3f;
  struct edge{
      int u,v,w,next;
  }e[N<<1];
  int h[N],idx;
  void addd(int u,int v,int w){
      e[++idx].v = v;
      e[idx].w = w;
      e[idx].next = h[u];
      h[u] = idx;
  }
  
  struct node{
      int u,v,w,next;
  }a[N<<1];
  int f[N],cnt;
  inline void add(int u,int v,int w){
      a[++cnt].v = v;
      a[cnt].w = w;
      a[cnt].next = f[u];
      f[u] = cnt;
  }
  int dis[N];
  int vis[N];
  int first[N];
  void dijkstra(){
      memset(dis,0x3f,sizeof dis);
      memset(first,0x3f,sizeof first);
      dis[1] = 0;
      priority_queue<pair<int,int>> q;
      q.push({0,1});
      while(!q.empty()){
          int u = q.top().second;
          q.pop();
          if(vis[u])  continue;
          vis[u] = 1;
          for(int i = f[u];i;i = a[i].next){
              int v1 = a[i].v,w1 = a[i].w;
              if(w1>=first[v1])    continue;//这个剪枝是重点
              first[v1] = w1;
              for(int j = f[v1];j;j = a[j].next){
                  int v2 = a[j].v,w2 = a[j].w;
                  int dist = (w1+w2)*(w1+w2) + dis[u];
                  if(dis[v2] > dist){
                      dis[v2] = dist;
                      q.push({-dist,v2});
                  }
              }
          }
      }
  }
  
  int main() {
      int n,m;
      cin>>n>>m;
      for(int i = 1;i<=m;i++){
          int u,v,w;
          scanf("%d%d%d",&u,&v,&w);
          add(u,v,w);
          add(v,u,w);
      }
      dijkstra();
      for(int i = 1;i<=n;i++){
          if(dis[i]==INF) printf("-1 ");
          else    printf("%d ",dis[i]);
      }
      return 0;
  }
  ```

最后修改：2021 年 02 月 19 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

Codeforces Round #703 (Div. 2)

spirit • 2021 年 02 月 19 日

# [Codeforces Round #703 (Div. 2)](https://codeforces.com/contest/1486)

## [A - Shifting Stacks](https://codeforces.com/contest/1486/problem/A)

## [B - Eastern Exhibition](https://codeforces.com/contest/1486/problem/B)

## [C1 - Guessing the Greatest (easy version)](https://codeforces.com/contest/1486/problem/C1)

## [C2 - Guessing the Greatest (hard version)](https://codeforces.com/contest/1486/problem/C2)

## [D - Max Median](https://codeforces.com/contest/1486/problem/D)

## [E - Paired Payment](https://codeforces.com/contest/1486/problem/E)

Codeforces Round #703 (Div. 2)

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

Kattis Message （状态机模型 + 矩阵快速幂）

数论进阶——莫比乌斯反演

Codeforces Round #703 (Div. 2)

SDUT 2021 Winter Individual Contest - E

Kattis Fruit Slicer （计算几何 + 扫描线）

Windows Terminal & PowerShell 美化记录

2020 ICPC EC-Final A题

SDUT 2021 Winter Individual Contest - E

Kattis Message （状态机模型 + 矩阵快速幂）

Gym 101147 A-The game of Osho

Codeforces Round #703 (Div. 2)

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

Codeforces Round #703 (Div. 2)

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款