SDUT 2021 Winter Individual Contest - G

博主： spirit
发布时间：2021 年 01 月 27 日
1675 次浏览
1 条评论
3881字数
分类： VJ训练赛

# [2019 ICPC Mid-Central Regional](https://open.kattis.com/problem-sources/2019%20ICPC%20Mid-Central%20Regional)

## [A - Basketball One-on-One](https://vjudge.net/problem/Kattis-basketballoneonone)

- 题意：$A$ $B$ 两人打球，得分在 $11$ 分及以上且领先对手两分即可获胜，按顺序给出得分情况，问胜者是谁。
- 思路：暴力统计判断谁大即可。
- 代码：
  
  ```cpp
  #include <bits/stdc++.h>
  
  using namespace std;
  
  void read(int &a, int &b) {
      a = b = 0;
      char x, y;
      while (~(x = getchar())) {
          if (x == '\n') break;
          y = getchar();
          if (x == 'A')
              a += y - '0';
          else
              b += y - '0';
      }
  }
  
  int main() {
      int a, b;
      read(a, b);
      if (a - b >= 2)
          puts("A");
      else
          puts("B");
      return 0;
  }
  ```

## [C - Convoy](https://vjudge.net/problem/Kattis-convoy)

- 题意：共有 $n$ 个人要从相同地点到体育场，共有 $k$ 辆车。任何一个人都可以驾驶任意一辆车，除司机外每辆车还可以再载 $4$ 个人。每个人开车到达体育场的时间为 $t_i$ ，从体育场返回的时间与之相等。给出每个人的 $t_i$ ，求最少需要花费多少时间让 $n$ 个人都到达体育场？
- 思路：假设 $i$ 开车，一共发车了 $w_i$ 次，那么花费时间为 $(2w_i - 1) \cdot t_i$ ，可载人数为 $4w_i + 1$ 。同时注意到答案显然具有单调性，那么可以考虑用二分答案处理。 $check$ 的时候按照 $t_i$ 升序尝试让 $i$ 开车即可。
- 代码：
  
  ```cpp
  #include <bits/stdc++.h>
  
  using namespace std;
  typedef long long LL;
  const int N = 2e4 + 10;
  LL t[N];
  int n, k;
  
  bool judge(LL limit) {
      LL sum = 0;
      int m = min(n, k);
      for (int i = 1; i <= m; i++) {
          //已经没有人能开车时数量依然不够说明不可行
          if (limit < t[i]) return false;
          LL w = (limit / t[i] + 1) / 2;
          sum += 4 * w + 1;
          if (sum >= n) return true;
      }
      return false;
  }
  
  LL solve(LL l, LL r) {
      LL res = r;
      while (l <= r) {
          LL mid = l + r >> 1;
          if (judge(mid)) {
              res = mid;
              r = mid - 1;
          } else {
              l = mid + 1;
          }
      }
      return res;
  }
  
  int main() {
      cin >> n >> k;
      for (int i = 1; i <= n; i++) scanf("%lld", &t[i]);
      sort(t + 1, t + n + 1);
      LL res = solve(1, 1e18);
      printf("%lld\n", res);
      return 0;
  }
  ```

## [F - Dragon Ball I](https://vjudge.net/problem/Kattis-dragonball1)

- 题意：给出一张带权图和七颗龙珠所在的位置，你的初始位置是 $1$ 点，求收集七颗龙珠的最少花费，如果无法收集则输出 $-1$。
- 思路：先用 $dijkstra$ 求出带有龙珠的几个城市之间的最短路，然后从 $1$ 点开始 $dfs$ 即可，注意会爆 $int$ 。
- 代码：
  
  ```cpp
  #include <bits/stdc++.h>
  
  using namespace std;
  typedef long long LL;
  const int N = 2e5 + 10;
  const LL INF = 0x3f3f3f3f3f3f3f3f;
  int h[N], ne[N * 2], ver[N * 2], w[N * 2], idx;
  int st[8], cnt;
  LL dist[8][N], res = INF;
  bool vis[N], book[N];
  
  inline void add(int a, int b, int c) {
      ver[++idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx;
  }
  
  void dijkstra(int id) {
      memset(vis, false, sizeof vis);
      memset(dist[id], 0x3f, sizeof dist[id]);
      dist[id][st[id]] = 0;
      priority_queue <pair<LL, int>> q;
      q.push({dist[id][st[id]], st[id]});
      while (!q.empty()) {
          auto p = q.top();
          q.pop();
          int u = p.second;
          if (vis[u]) continue;
          vis[u] = true;
          for (int i = h[u]; i; i = ne[i]) {
              if (!vis[ver[i]] && dist[id][ver[i]] > dist[id][u] + w[i]) {
                  dist[id][ver[i]] = dist[id][u] + w[i];
                  q.push({-dist[id][ver[i]], ver[i]});
              }
          }
      }
  }
  
  void dfs(int u, int num, LL sum) {
      if (num == cnt) {
          if (sum < res) res = sum;
          return ;
      }
      vis[u] = true;
      for (int i = 0; i < cnt; i++) {
          if (u == i || vis[i] || dist[u][st[i]] == INF) continue;
          dfs(i, num + 1, sum + dist[u][st[i]]);
      }
      vis[u] = false;
  }
  
  int main() {
      int n, m, a, b, c;
      cin >> n >> m;
      while (m--) {
          scanf("%d %d %d", &a, &b, &c);
          add(a, b, c);
          add(b, a, c);
      }
      st[cnt++] = 1;
      book[1] = true;
      for (int i = 1; i <= 7; i++) {
          scanf("%d", &c);
          if (book[c]) continue;
          book[c] = true;
          st[cnt++] = c;
      }
      for (int i = 0; i < cnt; i++) dijkstra(i);
      memset(vis, false, sizeof vis);
      dfs(0, 1, 0);
      if (res == INF)
          puts("-1");
      else
          printf("%d\n", res);
      return 0;
  }
  ```

## [H - Farming Mars](https://vjudge.net/problem/Kattis-farmingmars)

- 题意：给出一个序列，询问区间 $[l, r]$ 之间出现次数最多的一个数字出现次数是否大于等于 $(r - l + 1) / 2 + 1$ 。
- 思路：其实用数组开桶暴力就可以过了，但是做的时候错把 $1e7$ 级别的桶当成了 $1e8$ 级别的桶，以为不能这样做。折腾了半天想到的方法是：用 $map + vector$ 记录每个数字出现的位置，查询的时候按照出现次数降序查找每一个数字，利用二分查找快速检测该数字在指定区间内的出现次数。没想到居然只跑了 $10ms$ ……
- 代码：
  
  ```cpp
  #include <bits/stdc++.h>
  
  using namespace std;
  const double eps = 1e-6;
  const int N = 1e4 + 10;
  map<int, vector<int>> mp;
  int a[N], cnt;
  pair<int, int> b[N];
  
  inline bool judge(int l, int r) {
      int len = r - l + 1;
      int L = len / 2 + 1;
      for (int i = cnt; i; i--) {
          if (b[i].first < L) break;
          vector<int> &v = mp[b[i].second];
          auto ll = lower_bound(v.begin(), v.end(), l);
          auto rr = upper_bound(v.begin(), v.end(), r);
          if (rr - ll >= L) return true;
      }
      return false;
  }
  
  int main() {
      int n, m, l, r;
      double x;
      cin >> n >> m;
      for (int i = 1; i <= n; i++) {
          scanf("%lf", &x);
          a[i] = x * 1000000;
          mp[a[i]].push_back(i);
      }
      cnt = 0;
      for (auto it : mp) {
          b[++cnt] = {it.second.size(), it.first};
      }
      sort(b + 1, b + cnt + 1);
      while (m--) {
          scanf("%d %d", &l, &r);
          if (judge(l, r))
              puts("usable");
          else
              puts("unusable");
      }
      return 0;
  }
  ```

## [I - Soft Passwords](https://vjudge.net/problem/Kattis-softpasswords)

- 题意：给出真实密码 $S$ 和输入密码 $P$ 。如果满足以下条件之一，就输出 $Yes$ ： $P$ 和 $S$ 相同；$P$ 在头部或者尾部添加一个数字后和 $S$ 相同；$P$ 中全部字母大小写翻转后和 $S$ 相同。
- 思路：暴力
- 代码：
  
  ```cpp
  #include <bits/stdc++.h>
  
  using namespace std;
  const int N = 110;
  char s1[N], s2[N];
  
  bool cmp(char s1[], char s2[], int p1, int p2, int len) {
      for (int i = 0; i < len; i++)
          if (s1[p1 + i] != s2[p2 + i]) return false;
      return true;
  }
  
  bool judge(char s1[], char s2[], int n, int m) {
      if (n == m) {
          if (cmp(s1, s2, 1, 1, n)) return true;
          for (int i = 1; i <= n; i++)
              if (s1[i] <= 'z' && s1[i] >= 'a')
                  s1[i] = s1[i] - 'a' + 'A';
              else if (s1[i] <= 'Z' && s1[i] >= 'A')
                  s1[i] = s1[i] - 'A' + 'a';
          if (cmp(s1, s2, 1, 1, n)) return true;
      } else if (n == m + 1) {
          if (s1[1] <= '9' && s1[1] >= '0' && cmp(s1, s2, 2, 1, m)) return true;
          if (s1[n] <= '9' && s1[n] >= '0' && cmp(s1, s2, 1, 1, m)) return true;
      }
      return false;
  }
  
  int main() {
      int n, m;
      cin >> s1 + 1 >> s2 + 1;
      n = strlen(s1 + 1);
      m = strlen(s2 + 1);
      if (judge(s1, s2, n, m))
          puts("Yes");
      else
          puts("No");
      return 0;
  }
  ```

## [L - Umm Code](https://vjudge.net/problem/Kattis-ummcode)

- 题意：将一个字符串的 $ASCII$ 码的二进制形式用 $u$ 和 $m$ 代替后以多个单词的形式给出，含有其他字母或数字的单词直接忽视。
- 思路：暴力
- 代码：
  
  ```cpp
  #include <bits/stdc++.h>
  
  using namespace std;
  string s, str;
  
  bool check() {
      for (auto c : s) {
          if (c <= '9' && c >= '0') return false;
          if (c <= 'Z' && c >= 'A') return false;
          if (c <= 'z' && c >= 'a' && c != 'u' && c != 'm') return false;
      }
      return true;
  }
  
  int main() {
      ios::sync_with_stdio(false);
      int num = 0, cnt = 0;
      while (cin >> s) {
          if (!check()) continue;
          for (auto c : s) {
              if (c == 'u') {
                  num = num * 2 + 1;
                  cnt++;
              } else if (c == 'm') {
                  num *= 2;
                  cnt++;
              }
              if (cnt == 7) {
                  str.push_back((char)num);
                  num = cnt = 0;
              }
          }
      }
      cout << str << '\n';
      return 0;
  }
  ```

最后修改：2021 年 02 月 11 日

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

1 条评论

spirit
February 14th, 2021 at 06:19 pm

测试

回复

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

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

SDUT 2021 Winter Individual Contest - G

spirit • 2021 年 01 月 27 日

# [2019 ICPC Mid-Central Regional](https://open.kattis.com/problem-sources/2019%20ICPC%20Mid-Central%20Regional)

## [A - Basketball One-on-One](https://vjudge.net/problem/Kattis-basketballoneonone)

## [C - Convoy](https://vjudge.net/problem/Kattis-convoy)

## [F - Dragon Ball I](https://vjudge.net/problem/Kattis-dragonball1)

## [H - Farming Mars](https://vjudge.net/problem/Kattis-farmingmars)

## [I - Soft Passwords](https://vjudge.net/problem/Kattis-softpasswords)

## [L - Umm Code](https://vjudge.net/problem/Kattis-ummcode)

SDUT 2021 Winter Individual Contest - G

1 条评论

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

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

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

Codeforces Round #703 (Div. 2)

SDUT 2021 Winter Individual Contest - E

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

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

线性DP入门

Kattis Terraced fields （数位DP）

Windows Terminal & PowerShell 美化记录

计算几何基础知识

SDUT 2021 Winter Individual Contest - G

1 条评论

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

SDUT 2021 Winter Individual Contest - G

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