SDUT 2021 Winter Individual Contest - E

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

## [E - Bonuses and Teleports](https://vjudge.net/problem/Gym-101341E)

- 题意：在一个数轴上有若干个奖品和传送门，给你它们的坐标，初始位置在第一个传送门处，传送门之间可以任意到达且不消耗时间。求拿到所有奖品再回到初始位置最少要走多少距离。
- 思路：可以用传送门将数轴划分为若干个区间，显然任意区间内的奖品一定都是由该区间的左传送门或右传送门拿到的（显然从一个更远的传送门跑过来太傻了）。那么我们可以将一个区间内的奖品划分为两个集合，一个都是由左传送门拿到的，另一个都是右传送门拿到的，容易想到正确的划分方式中这两个集合一定对应该区间由一个坐标分隔开后左半部分的奖品集合和右半部分的奖品集合。然后对每个区间暴力划分即可，时间复杂度 $O(n)$ 。

```cpp
  #include <bits/stdc++.h>
  #define lowbit(x) (x & -x)
  using namespace std;
  typedef long long LL;
  const int INF = 0x3f3f3f3f;
  const LL LINF = 0x3f3f3f3f3f3f3f3f;
  const double PI = acos(-1.0), eps = 1e-6;
  const int N = 2e5 + 10;
  LL t[N], b[N];
  int Max[N], Min[N];

int main(int argc, char const *argv[]) {
      memset(Max, -0x3f, sizeof Max);
      memset(Min, 0x3f, sizeof Min);
      int n, m;
      LL res = 0;
      cin >> n >> m;
      for (int i = 1; i <= n; i++) scanf("%lld", &t[i]);
      t[0] = -LINF;
      t[n + 1] = LINF;
      int cnt = 0;
      for (int i = 1; i <= m; i++) {
          scanf("%lld", &b[i]);
          while (b[i] >= t[cnt + 1]) {
              cnt++;
          }
          if (b[i] != t[cnt]) {
              Max[cnt] = max(Max[cnt], i);
              Min[cnt] = min(Min[cnt], i);
          }
      }
      if (b[1] < t[1]) res += 2 * (t[1] - b[1]);
      for (int i = 1; i < n; i++) {
          if (Min[i] == INF) continue;
          LL now = min(t[i + 1] - t[i],
                       2 * min(b[Max[i]] - t[i], t[i + 1] - b[Min[i]]));
          for (int j = Min[i]; j < Max[i]; j++) {
              now = min(now, 2 * (b[j] - t[i] + t[i + 1] - b[j + 1]));
          }
          res += now;
      }
      if (b[m] > t[n]) res += 2 * (b[m] - t[n]);
      cout << res << endl;
      return 0;
  }
  ```

## [H - Perfect Ban](https://vjudge.net/problem/Gym-101341H)

- 题意：$A$ 玩游戏，可以在 $n \times m$ 的矩阵中选择角色，每个角色都有一个权值评判强弱。$B$ 可以在 $A$ 选择角色之前 $ban$ 掉第 $x$ 行和第 $y$ 列。问：为了使 $A$ 选择到的角色最弱，$B$ 应该 $ban$ 哪一行和哪一列？
- 思路：当 $B$ $ban$ 掉 $(x, y)$ 时，显然 $A$ 会选择其他未被 $ban$ 掉的角色中最强的一个，这意味着每一对 $(x, y)$ 都对应着一个 $A$ 会选择的角色强度，只需要找到最小的那个值对应的 $(x, y)$ 就可以了。暴力寻找时间复杂度为 $O(n^2 m^2)$ ，显然超时。可以用二维前缀和预处理出要找的最大值，时间复杂度为 $O(n m)$ 。

```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 = 1005;
  int a[N][N], s[N][N][4], n, m;

void init() {
      for (int i = 1; i <= n; i++)
          for (int j = 1; j <= m; j++)
              s[i][j][0] = max(a[i][j], max(s[i - 1][j][0], s[i][j - 1][0]));
      for (int i = 1; i <= n; i++)
          for (int j = m; j >= 1; j--)
              s[i][j][1] = max(a[i][j], max(s[i - 1][j][1], s[i][j + 1][1]));
      for (int i = n; i >= 1; i--)
          for (int j = m; j >= 1; j--)
              s[i][j][2] = max(a[i][j], max(s[i + 1][j][2], s[i][j + 1][2]));
      for (int i = n; i >= 1; i--)
          for (int j = 1; j <= m; j++)
              s[i][j][3] = max(a[i][j], max(s[i + 1][j][3], s[i][j - 1][3]));
  }

int get(int x, int y, int id) {
      if (x < 1 || x > n || y < 1 || y > m) return 0;
      return s[x][y][id];
  }

int main(int argc, char const *argv[]) {
      cin >> n >> m;
      int Min = INF, x, y;
      for (int i = 1; i <= n; i++)
          for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]);
      init();
      for (int i = 1; i <= n; i++)
          for (int j = 1; j <= m; j++) {
              int now = max(max(get(i - 1, j - 1, 0), get(i - 1, j + 1, 1)),
                            max(get(i + 1, j + 1, 2), get(i + 1, j - 1, 3)));
              if (now < Min) {
                  Min = now;
                  x = i, y = j;
              }
          }
      printf("%d %d\n", x, y);
      return 0;
  }
  ```

## [I - Matrix God](https://vjudge.net/problem/Gym-101341I)

- 题意：给三个矩阵 $A$ $B$ $C$ ，验证是否有 $A \times B = C$。
- 思路：暴力矩阵乘法时间复杂度为 $O(n^3)$ ，显然超时。引入一个 $n \times 1$ 的矩阵 $D$ ，原式可化为：$A \times (B \times D) = C \times D$。记 $B \times D = E$ ，$A \times E = F$ ，$C \times D = G$。只需要验证 $F = G$ 即可，单次验证的时间复杂度可以降到 $O(n^2)$ 。但是当 $F \neq G$ 时一定有 $A \times B \neq C$ ，当 $F = G$ 时不一定有 $A \times B = C$ ，所以需要多验证几次提高正确率。

```cpp
  #include <time.h>
  #include <bits/stdc++.h>
  #include <random>
  #define lowbit(x) (x & -x)
  using namespace std;
  typedef long long LL;
  typedef pair<int, int> PII;
  const int INF = 0x3f3f3f3f;
  const double PI = acos(-1.0), eps = 1e-6;
  const int N = 1e3 + 10, mod = 1e9 + 7;
  LL a[N][N], b[N][N], c[N][N], d[N], e[N], f[N], g[N];

void mul(LL a[][N], LL b[], LL c[], int n) {
      for (int i = 1; i <= n; i++) {
          c[i] = 0;
          for (int j = 1; j <= n; j++) c[i] = (c[i] + a[i][j] * b[j]) % mod;
      }
  }

bool judge(LL a[], LL b[], int n) {
      for (int i = 1; i <= n; i++)
          if (a[i] != b[i]) return false;
      return true;
  }

int main(int argc, char const *argv[]) {
      srand((unsigned long long)time(0));
      int n;
      cin >> n;
      for (int i = 1; i <= n; i++)
          for (int j = 1; j <= n; j++) scanf("%d", a[i] + j);
      for (int i = 1; i <= n; i++)
          for (int j = 1; j <= n; j++) scanf("%d", b[i] + j);
      for (int i = 1; i <= n; i++)
          for (int j = 1; j <= n; j++) scanf("%d", c[i] + j);
      bool flag = true;
      for (int k = 0; k < 10; k++) {
          for (int i = 1; i <= n; i++) d[i] = rand();
          mul(b, d, e, n);
          mul(a, e, f, n);
          mul(c, d, g, n);
          if (!judge(f, g, n)) {
              flag = false;
              break;
          }
      }
      if (flag)
          puts("YES");
      else
          puts("NO");
      return 0;
  }
  ```

## [K - Competitions](https://vjudge.net/problem/Gym-101341K)

- 题意：给出 $nn$ 场比赛的开始时间 $a_ia_i$ ，结束时间 $b_ib_i$ 和比赛权值 $c_ic_i$ 。设计一种参赛方案，使得参加的比赛权值和最大的同时花费时间最少。
- 思路：$dp_idp_i$ 表示 $[0, i][0, i]$ 时间内可以获得的最大权值和，$len_ilen_i$ 表示在上述权值和的情况下最小的时间花费。

状态转移：用结束时间恰好为 $ii$ 的比赛来更新 $dp_idp_i$ 和 $len_ilen_i$ 。$dp_i = max(dp_{i-1}, dp_{a_i} + c_i)dp_i = max(dp_{i-1}, dp_{a_i} + c_i)$，注意同时更新时间即可。

但是题目给出的时间范围太大，需要离散化。题目要求给出方案，还需要用一个数组 $which_iwhich_i$ 记录 $dp_idp_i$ 是选择哪个比赛得到的。

```cpp
  #include <bits/stdc++.h>
  #define lowbit(x) (x & -x)
  using namespace std;
  typedef long long LL;
  typedef pair<int, int> PII;
  const int INF = 0x3f3f3f3f;
  const double PI = acos(-1.0), eps = 1e-6;
  const int N = 2e5 + 10;
  vector<int> ls, pv[N * 2];
  LL a[N], b[N], c[N], t[N];
  int ans[N], cnt, which[N * 2];
  LL dp[N * 2], len[N * 2];

int get(int x) { return lower_bound(ls.begin(), ls.end(), x) - ls.begin() + 1; }

int main(int argc, char const *argv[]) {
      int n, m;
      cin >> n;
      for (int i = 1; i <= n; i++) {
          scanf("%lld %lld %lld", &a[i], &b[i], &c[i]);
          ls.push_back(a[i]);
          ls.push_back(b[i]);
          t[i] = b[i] - a[i];
      }
      sort(ls.begin(), ls.end());
      ls.erase(unique(ls.begin(), ls.end()), ls.end());
      for (int i = 1; i <= n; i++) {
          a[i] = get(a[i]);
          b[i] = get(b[i]);
          pv[b[i]].push_back(i);
      }
      m = ls.size();
      for (int i = 1; i <= m; i++) {
          dp[i] = dp[i - 1];
          len[i] = len[i - 1];
          which[i] = which[i - 1];
          for (auto id : pv[i]) {
              if (dp[i] < dp[a[id]] + c[id]) {
                  dp[i] = dp[a[id]] + c[id];
                  len[i] = len[a[id]] + t[id];
                  which[i] = id;
              } else if (dp[i] == dp[a[id]] + c[id] &&
                         len[i] > len[a[id]] + t[id]) {
                  len[i] = len[a[id]] + t[id];
                  which[i] = id;
              }
          }
      }
      LL val = dp[m], Time = len[m];
      int  x = which[m];
      while (x) {
          ans[++cnt] = x;
          x = which[a[x]];
      }
      sort(ans + 1, ans + cnt + 1);
      printf("%d %lld %lld\n", cnt, val, Time);
      for (int i = 1; i <= cnt; i++)
          printf("%d%c", ans[i], i == cnt ? '\n' : ' ');
      return 0;
  }
  ```

最后修改：2021 年 02 月 09 日

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

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

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

SDUT 2021 Winter Individual Contest - E

spirit • 2021 年 01 月 20 日

## [E - Bonuses and Teleports](https://vjudge.net/problem/Gym-101341E)

## [H - Perfect Ban](https://vjudge.net/problem/Gym-101341H)

int get(int x, int y, int id) {
      if (x < 1 || x > n || y < 1 || y > m) return 0;
      return s[x][y][id];
  }

## [I - Matrix God](https://vjudge.net/problem/Gym-101341I)

void mul(LL a[][N], LL b[], LL c[], int n) {
      for (int i = 1; i <= n; i++) {
          c[i] = 0;
          for (int j = 1; j <= n; j++) c[i] = (c[i] + a[i][j] * b[j]) % mod;
      }
  }

bool judge(LL a[], LL b[], int n) {
      for (int i = 1; i <= n; i++)
          if (a[i] != b[i]) return false;
      return true;
  }

## [K - Competitions](https://vjudge.net/problem/Gym-101341K)

但是题目给出的时间范围太大，需要离散化。题目要求给出方案，还需要用一个数组 $which_iwhich_i$ 记录 $dp_idp_i$ 是选择哪个比赛得到的。

int get(int x) { return lower_bound(ls.begin(), ls.end(), x) - ls.begin() + 1; }

SDUT 2021 Winter Individual Contest - E

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

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

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

Codeforces Round #703 (Div. 2)

SDUT 2021 Winter Individual Contest - E

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

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

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

Kattis Terraced fields （数位DP）

SDUT 2020 Autumn Team Contest---43(for 19)

Gym 101147 A-The game of Osho

SDUT 2021 Winter Individual Contest - E

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

SDUT 2021 Winter Individual Contest - E

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