SDUT 2021 Winter Individual Contest - D

博主： spirit
发布时间：2021 年 01 月 18 日
1608 次浏览
暂无评论
1055字数
分类： VJ训练赛

## [A - City of Lights](https://vjudge.net/problem/Gym-102465A)

- 题意：给 $n$ 个灯（按照 $1$ ~ $n$ 编号）和 $k$ 次操作，每次操作给出一个整数 $i$ ，编号能被 $i$ 整数的灯状态翻转（所有灯初始状态都是亮着的）。问整个过程中最多有多少灯是同时灭着的。
- 思路：$n$ 最多 $1e6$ ，$k$ 最多 $100$ ，暴力即可。

## [B - Blurred Pictures](https://vjudge.net/problem/Gym-102465B)

- 题意：有一个 $n \times n$  像素的图片，图片的边缘有一些模糊。输入共 $n$ 行，第 $i$ 行给出图片第 $i$ 行上清晰部分的起始坐标 $l_i$ 和终止坐标 $r_i$ 。要从图片上裁剪下一个正方形，不能斜着剪（正方形和原图的长宽平行）。任意水平或垂直的清晰像素之间都是清晰像素，即清晰部分是一个凸包。问最大可以裁剪的正方形边长。
- 思路：读题的时候没读到凸包那句话。。。所以想的比较麻烦。容易知道答案具有单调性，所以使用二分答案的思路。重点是 $check$ 函数怎么写，要判断能否裁剪出 $k \times k$ 的正方形，可以遍历 $x$ 坐标，然后判断 $[i, i + k - 1]$ 这个区间内的 $y$ 坐标是否满足条件：$r_{min} - l_{max} + 1 \geq k$，只要有一个满足这个条件的区间就可以。用线段树维护下最大值最小值，时间复杂度 $O(nlog^{2}_{n})$ 。这个写法应该是能解决一般情况的（无论是不是凸包）。由凸包的性质还有一个 $O(n)$ 的写法，因为比较简单就不写了。
  
  ```cpp
  #include <bits/stdc++.h>
  #define lowbit(x) (x & -x)
  using namespace std;
  typedef long long LL;
  const int INF = 0x3f3f3f3f;
  const double PI = acos(-1.0), eps = 1e-6;
  const int N = 1e5 + 10;
  struct Segment {
      int l, r, min, max;
  } tr[N << 2];
  int a[N], b[N];
  
  void build(int p, int l, int r) {
      tr[p].l = l;
      tr[p].r = r;
      if (l == r) {
          tr[p].min = b[l];
          tr[p].max = a[l];
      } else {
          int mid = l + r >> 1;
          build(p << 1, l, mid);
          build(p << 1 | 1, mid + 1, r);
          tr[p].max = max(tr[p << 1].max, tr[p << 1 | 1].max);
          tr[p].min = min(tr[p << 1].min, tr[p << 1 | 1].min);
      }
  }
  
  void query(int p, int l, int r, int &Max, int &Min) {
      if (l > tr[p].r || tr[p].l > r) return;
      if (l <= tr[p].l && tr[p].r <= r) {
          Max = max(Max, tr[p].max);
          Min = min(Min, tr[p].min);
      } else {
          query(p << 1, l, r, Max, Min);
          query(p << 1 | 1, l, r, Max, Min);
      }
  }
  
  bool judge(int n, int len) {
      int l = 1, r = len;
      while (r <= n) {
          int Max = 0, Min = 1e9;
          query(1, l, r, Max, Min);
          if (Min - Max + 1 >= len) return true;
          l++, r++;
      }
      return false;
  }
  
  int main(int argc, char const *argv[]) {
      int n, res = 1;
      cin >> n;
      for (int i = 1; i <= n; i++) scanf("%d %d", &a[i], &b[i]);
      build(1, 1, n);
      int l = 1, r = n;
      while (l <= r) {
          int mid = l + r >> 1;
          if (judge(n, mid)) {
              res = mid;
              l = mid + 1;
          } else {
              r = mid - 1;
          }
      }
      cout << res << endl;
      return 0;
  }
  ```

## [D - Monument Tour](https://vjudge.net/problem/Gym-102465D)

- 题意：给出一张城市地图和 $n$ 个博物馆的坐标，要求选取一个 $y$ 坐标，从城市西边进去，每访问完一个 $x$ 坐标上的博物馆以后，必须再回到选定的 $y$ 坐标上继续向东走，最终从城市东边出城。求最短路径。
- 思路：队友说这个直接用中位数就行了，我用了前缀差分（问题复杂化大师）。先选中一个 $x$ 坐标，那么对于这条线上来说每个 $y$ 坐标访问博物馆的消耗是很容易算出来的，然后遍历 $x$ 坐标算总消耗就可以了。但是这种做法显然会超时，用差分优化一下就可以了，时间复杂度 $O(n)$。
  
  ```cpp
  #include <bits/stdc++.h>
  #define lowbit(x) (x & -x)
  using namespace std;
  typedef long long LL;
  const int INF = 0x3f3f3f3f;
  const double PI = acos(-1.0), eps = 1e-6;
  const int N = 1e5 + 10;
  int Max[N], Min[N];
  LL a[N], b[N];
  
  int main(int argc, char const *argv[]) {
      int x, y, n, u, v;
      LL res, now = 1e18;
      memset(Max, 0, sizeof Max);
      memset(Min, 0x3f, sizeof Min);
      cin >> x >> y >> n;
      res = x - 1;
      for (int i = 1; i <= n; i++) {
          scanf("%d %d", &u, &v);
          u++, v++;
          Max[u] = max(Max[u], v);
          Min[u] = min(Min[u], v);
      }
      for (int i = 1; i <= x; i++) {
          if (Max[i] == 0) continue;
          res += 2 * (Max[i] - Min[i]);
          a[Max[i] + 1] += 2;
          b[Min[i] - 1] += 2;
      }
      for (int i = 1; i <= y; i++) a[i] += a[i - 1];
      for (int i = 1; i <= y; i++) a[i] += a[i - 1];
      for (int i = y; i; i--) b[i] += b[i + 1];
      for (int i = y; i; i--) b[i] += b[i + 1];
      for (int i = 1; i <= y; i++) now = min(now, a[i] + b[i]);
      cout << res + now << endl;
      return 0;
  }
  ```

## [E - Rounding](https://vjudge.net/problem/Gym-102465E)

- 题意：有一家机构调查 $10000$ 个人最喜欢的地方，给出每个地点受喜爱的百分比，真实数值应该精确到小数点后两位，但是该机构对数据四舍五入到个位。给你舍入后的数据，求每个地点真实数据的取值范围，或者输出不可能。
- 思路：设题目输入的舍入值为 $round_i$ ，真实值为 $origin_i$ ，那么有 ：
  
  $$
  origin_i \geq min_i ，其中 min_i = max(0, round_i - 0.50)
  $$
  
  $$
  origin_i \leq max_i ，其中 max_i = min(100.0, round_i + 0.49)
  $$
  
  那么容易推导出：
  
  $$
  若minSum = \sum_i min_i ， maxSum = \sum_i max_i
  $$
  
  $$
  则 minSum \leq 100 \leq maxSum
  $$
  
  $$
  如果不满足该条件则输出 impossible 。
  $$
  
  对于第 $i$ 个地点的取值范围应为：
  
  $$
  realMin_i = max(min_i, 100 - (maxSum - max_i))
  $$
  
  $$
  realMax_i = min(max_i, 100 - (minSum - min_i))
  $$
  
  ```cpp
  #include <bits/stdc++.h>
  #define lowbit(x) (x & -x)
  using namespace std;
  typedef long long LL;
  const int INF = 0x3f3f3f3f;
  const double PI = acos(-1.0), eps = 1e-6;
  const int N = 1e4 + 10;
  char str[N][25];
  double Max[N], Min[N];
  
  int main(int argc, char const *argv[]) {
      int n, x;
      double s1 = 0, s2 = 0;
      cin >> n;
      for (int i = 1; i <= n; i++) {
          scanf("%s %d", str[i], &x);
          Max[i] = min(100.0, x + 0.49);
          Min[i] = max(0.0, x - 0.50);
          s1 += Max[i];
          s2 += Min[i];
      }
      bool flag = (s1 >= 100 && s2 <= 100);
      for (int i = 1; i <= n && flag; i++) {
          Max[i] = min(Max[i], 100.0 - s2 + Min[i]);
          Min[i] = max(Min[i], 100.0 - s1 + Max[i]);
      }
      if (flag) {
          for (int i = 1; i <= n; i++)
              printf("%s %.2f %.2f\n", str[i], Min[i], Max[i]);
      } else {
          puts("IMPOSSIBLE");
      }
      return 0;
  }
  ```

## [I - Mason's Mark](https://vjudge.net/problem/Gym-102465I)

- 题意：给出一张图，图中有若干块石头，每一块石头上都有且只有一个标记 $A B C$ ，标记用黑色涂色，图中也可能存在污点，每个污点都是由 $8$ 个白点包围的黑点，同时在石头周围的区域也是黑色的，不过这些区域都是连通的（斜着相邻也是连通）。问三种标记的石头各有多少个。
- 思路：首先可以通过 $BFS$ 或者 $DFS$ 把石头周围的区域消掉，然后遍历图中的黑色连通块，如果只有一个点说明是污点可以忽视，否则判断是 $ABC$ 中哪种类型。我是看了题解后通过关键点判断类型。代码如下：
  
  ```cpp
  #include <bits/stdc++.h>
  #define lowbit(x) (x & -x)
  using namespace std;
  typedef long long LL;
  const int INF = 0x3f3f3f3f;
  const double PI = acos(-1.0), eps = 1e-6;
  const int N = 1e3 + 10;
  int dx[10] = {-1, -1, -1, 0, 0, 1, 1, 1};
  int dy[10] = {-1, 0, 1, -1, 1, -1, 0, 1};
  int n, m, ans[5];
  char g[N][N];
  
  void Clear(int sx, int sy) {
      queue<pair<int, int>> q;
      g[sx][sy] = '.';
      q.push({sx, sy});
      while (!q.empty()) {
          int x = q.front().first;
          int y = q.front().second;
          q.pop();
          for (int i = 0; i < 8; i++) {
              int u = x + dx[i];
              int v = y + dy[i];
              if (u >= 1 && u <= n && v >= 1 && v <= m && g[u][v] == '#') {
                  g[u][v] = '.';
                  q.push({u, v});
              }
          }
      }
  }
  
  int Type(int sx, int sy, int lx, int ly) {
      if (g[sx + lx][sy + 2 * lx + ly - 1] != '#')
          return 3;
      else if (g[sx + 2 * lx + 2 * ly][sy + lx] != '#')
          return 1;
      return 2;
  }
  
  void Solve(int sx, int sy) {
      int lx, ly, ey;
      for (int i = sy; i <= m; i++)
          if (g[sx][i] == '#')
              ey = i;
          else
              break;
      for (lx = 1; g[sx + lx][sy + lx] == '#'; lx++)
          ;
      ly = ey - sy + 1 - 2 * lx;
      if (ly <= 0) return;
      ans[Type(sx, sy, lx, ly)]++;
      Clear(sx, sy);
  }
  
  int main(int argc, char const *argv[]) {
      cin >> m >> n;
      for (int i = 1; i <= n; i++) scanf("%s", g[i] + 1);
      Clear(1, 1);
      for (int i = 1; i <= n; i++)
          for (int j = 1; j <= m; j++)
              if (g[i][j] == '#') Solve(i, j);
      printf("%d %d %d\n", ans[1], ans[2], ans[3]);
      return 0;
  }
  ```
  
  队友的思路是从每个图形的连通性上考虑的。如图：
  
  ![](https://i.loli.net/2021/01/18/jLpBZNM9xVS5ArY.png)

## [K - Dishonest Driver](https://vjudge.net/problem/Gym-102465K)

- 题意：对于相连的两个相同字符串，如 $ss$ ，可以缩写为：$(s)^2$ 。给你一个字符串，问该字符串最短压缩形式的大小。
- 思路：由于任意区间都有可能发生压缩，因此想到了区间DP，比较棘手的是处理任意区间能否压缩的问题。最开始的几次提交都不对，因为时间给了 $6s$ ，索性用 $KMP$ 跑循环节，结果最后只跑了300ms+。
  
  ```cpp
  #include <bits/stdc++.h>
  #define lowbit(x) (x & -x)
  using namespace std;
  typedef long long LL;
  const int INF = 0x3f3f3f3f;
  const double PI = acos(-1.0), eps = 1e-6;
  const int N = 705;
  int dp[N][N], Next[N];
  char str[N];
  
  void getNext(int n, int p) {
      Next[0] = -1;
      int i = 0, j = -1;
      while (i < n) {
          if (j == -1 || str[i + p] == str[j + p]) {
              Next[++i] = ++j;
          } else {
              j = Next[j];
          }
      }
  }
  
  int main(int argc, char const *argv[]) {
      int n;
      cin >> n >> str;
      for (int len = 1; len <= n; len++) {
          for (int i = 0; i + len - 1 < n; i++) {
              int e = i + len - 1;
              dp[i][e] = len;
              getNext(len, i);
              int L = len - Next[len];
              if (len % L == 0) dp[i][e] = min(dp[i][e], dp[i][i + L - 1]);
              for (int j = i; j < e; j++) {
                  dp[i][e] = min(dp[i][e], dp[i][j] + dp[j + 1][e]);
              }
          }
      }
      cout << dp[0][n - 1] << endl;
      return 0;
  }
  ```

最后修改：2021 年 02 月 11 日

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

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

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

SDUT 2021 Winter Individual Contest - D

spirit • 2021 年 01 月 18 日

## [A - City of Lights](https://vjudge.net/problem/Gym-102465A)

## [B - Blurred Pictures](https://vjudge.net/problem/Gym-102465B)

## [D - Monument Tour](https://vjudge.net/problem/Gym-102465D)

## [E - Rounding](https://vjudge.net/problem/Gym-102465E)

## [I - Mason's Mark](https://vjudge.net/problem/Gym-102465I)

## [K - Dishonest Driver](https://vjudge.net/problem/Gym-102465K)

SDUT 2021 Winter Individual Contest - D

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

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

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

Codeforces Round #703 (Div. 2)

SDUT 2021 Winter Individual Contest - E

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

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

SDUT 2021 Winter Individual Contest - E

SDUT 2021 Winter Individual Contest - F

Kattis Terraced fields （数位DP）

Gym102896 C - Color the Tree

SDUT 2021 Winter Individual Contest - D

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

SDUT 2021 Winter Individual Contest - D

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