SDUT 2020 Autumn Team Contest---44

博主： spirit
发布时间：2020 年 12 月 16 日
1213 次浏览
暂无评论
1420字数
分类： VJ训练赛

[gym链接](https://codeforces.com/gym/102860)

## A - Jumping Machine

- 题意：现在有一个机器停在 $(0, 0)$ 点上，它有 $n$ 根弹簧，第 $i$ 根弹簧可以使机器前进 $l_i$ 距离，它只能向上或向右前进。换言之，假如机器现在处于 $(x, y)$ 点，那么它可以使用长度为 $l_i$ 的弹簧到达 $(x + l_i, y)$ 点或者 $(x, y + l_i)$ 点。问机器前进路径上所有可能到达的点的总数是多少。机器所处的方格是无限大的。
- 思路：队友的思路是假设机器先把所有向上走的路径走完，统计机器所能到达的所有 $y$ 轴坐标，记这些坐标的总数量为 $m$ 。那么对应的 $x$ 轴坐标就是 $\sum_1^n l_i - y$ ，同时机器也可以选择先在 $x$ 轴上走 $y$ 长度，这样就形成了一个矩形（除了所有弹簧均向上或向右走的情况）。可以发现所有这些矩形就是机器可以走出的所有轨迹的合集，因此只需要统计所有的矩形共占据了多少个点。由题目中给出的样图可以看出，每个矩形必然有一条长边和一条短边是和 $y$ 轴最长边与 $x$ 轴最长边重合，所以这一部分不需要统计。倘若我们把每一个矩形与 $x$ 轴平行的边长度记为 $v_i$ 并按照递增排序，那么第 $i$ 个矩形需要统计的就是横边长度 $v_i$ 以及纵边长度 $\sum_1^n l_i - v_i$ 减去重合点，重合点的数量为 $m - i$ （即所有横轴长度比 $v_i$ 更长的矩形）。

```cpp
  #include <algorithm>
  #include <bitset>
  #include <cmath>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <deque>
  #include <functional>
  #include <iostream>
  #include <map>
  #include <queue>
  #include <set>
  #include <stack>
  #include <string>
  #include <vector>
  #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 = 1e6 + 10;
  vector<int> v;
  bool book[N];

int main(int argc, char const *argv[]) {
      int n, a, m;
      LL res = 0;
      cin >> n;
      v.push_back(0);
      for (int i = 1; i <= n; i++) {
          scanf("%d", &a);
          m = v.size();
          for (int j = 0; j < m; j++) {
              if (!book[v[j] + a]) {
                  book[v[j] + a] = true;
                  v.push_back(v[j] + a);
              }
          }
      }
      sort(v.begin(), v.end());
      m = v.size() - 1;
      res += v[m] + 1;
      for (int i = 1; i <= m; i++) {
          res += v[m] - m + i;
      }
      cout << res << '\n';
      return 0;
  }
  ```

## B - Triangles and a Circle

- 题意：给定一个圆的周长 $L$ 和 $n$ 个圆上点的相对位置。要求任取 $n$ 个点中的三个点作为顶点构成一个三角形，三角形要包含圆心（圆心位于边长也可以）。求满足条件的三角形个数。
- 思路：首先只考虑所有选点的方法显然为：$C_n^3 = n · (n - 1) · (n - 2) / 6$ ，然后从中删去所有不符合条件的三角形。假设选择的第一个点为 $a$ 点，顺时针依次将另外两个点命名为 $b$ 点和 $c$ 点。以通过$a$ 点的直径将圆分为两个部分，显然当 $b$ 点和 $c$ 点位于同一侧时三角形不符合题意，这里我们只统计顺时针来看的第一部分。因为当 $b$ 和 $c$ 点都处于第二部分时，$a$ 点和 $c$ 点都位于 $b$ 点的第一侧，在遍历至 $b$ 点时会被统计到，这样刚好可以不重不漏地统计数量。

int main(int argc, char const *argv[]) {
      int n, L, m, l;
      cin >> n >> L;
      LL x = L;
      L *= 2;//所有的数据均乘2是因为L为奇数时L/2是个浮点数，不方便写代码
      LL res = (LL)n * (n - 1) * (n - 2) / 6;
      for (int i = 1; i <= n; i++) {
          scanf("%d", &a[i]);
          a[i] *= 2;
      }
      sort(a + 1, a + n + 1);
      for (int i = 1; i <= n; i++) a[i + n] = a[i] + L;
      for (int i = 1; i <= n; i++) {
          LL p = lower_bound(a + i + 1, a + 2 * n + 1, a[i] + x) - a - 1;
          res -= (p - i) * (p - i - 1) / 2;
      }
      cout << res << '\n';
      return 0;
  }
  ```

## E - Flag with Stars

- 题意：给 $n$ 颗星星，做一面旗帜，要求上下两排星星数量的差距不能超过 $1$ ，而且如果你有两排的数量是有差异的，那么整张图每两排之间都必须遵循这个差异，即此时图必须是 长-短-长-短 或者 短-长-短-长 这样排列。问行数和每一排最多的星星数量差的绝对值最小为多少。
- 思路：设行数为 $a$ ，此时如果 $n \bmod a = 0$ ，那么每一行星星的数量 $b = n / a$ ；如果 $n \bmod a = a / 2$ 或 $n \bmod a = (a + 1) / 2$ ，则最多单行星星数量 $b = a / 2 + 1$ 。显然最终的答案行数会在 $\sqrt{n}$ 左右，因此以 $\sqrt{n}$ 为中心左右开一个长度 $1e6$ 左右的区间，循环行数 $a$ 即可。

int main(int argc, char const *argv[]) {
      LL n, res = 9e18;
      cin >> n;
      int r = sqrt(n) + 5e5;
      for (int a = 1; a <= r; a++) {
          int r = n % a;
          if (r == 0)
              res = min(res, abs(a - n / a));
          else if (r == (a + 1) / 2 || r == a / 2)
              res = min(res, abs(a - n / a - 1));
      }
      cout << res << '\n';
      return 0;
  }
  ```

## F - String Art

- 题意：给定一张图，要求你给出一个染了色的树，这个树中所有颜色相同的点钉在一起后形成的图和题目给出的图相同。
- 思路：逆向来看这道题其实是想让你把一张图拆成一棵树。拆的方法形象一些来说，把图中的每一条边做成一个纸条，把纸条用钉子钉在一起形成图，你需要把一些钉子拔开把某些纸条的其中一端拿下来形成一棵树。所以可以先把每一个点的颜色编号为点编号，然后遍历图中的每一条边，如果加上这条边会使已有的树出现环，就把这条边的一端拿下来用一个新的点编号表示，颜色与原来的节点相同，否则直接把这条边加入到树中就可以了。用并查集维护这个过程。

void init(int n) {
      for (int i = 1; i <= n; i++) s[i] = col[i] = i;
  }

int Find(int u) {
      if (u == s[u]) return u;
      return s[u] = Find(s[u]);
  }

int main(int argc, char const *argv[]) {
      int n, m, a, b;
      cin >> n >> m;
      init(n);
      idx = n;
      for (int i = 1; i <= m; i++) {
          scanf("%d %d", &e[i].x, &e[i].y);
          a = Find(e[i].x);
          b = Find(e[i].y);
          if (a != b) {
              v.push_back(Edge(e[i].x, e[i].y));
              s[a] = b;
          } else {
              col[++idx] = e[i].y;
              v.push_back(Edge(e[i].x, idx));
          }
      }
      printf("%d\n", idx);
      for (int i = 1; i <= idx; i++)
          printf("%d%c", col[i], i == idx ? '\n' : ' ');
      for (auto it : v) printf("%d %d\n", it.x, it.y);
      return 0;
  }
  ```

## G - Ice Cream

- 题意：给出 $nn$ 个冰激凌，所有冰激凌都在以速度 $vv$ 融化，每个冰激凌有一个体积 $a_ia_i$ ，而 $MakarMakar$ 同一时刻只能以 $uu$ 的速度吃其中一个冰激凌，问 $MakarMakar$ 能吃到的最少冰激凌体积。
- 思路：为了让同一时刻融化掉的冰激凌体积尽可能的多（即保持冰激凌数量尽可能多），$MakarMakar$ 会先吃体积较大的冰激凌，当出现两个冰激凌体积相同的时候，$MakarMakar$ 会 ”同时” 吃他们（可以理解为吃一下这个冰激凌立马换另一个），当然他吃的相对速度会变为 $u / numu / num$ ，$numnum$ 为相同体积冰激凌的数量，直至 $MakarMakar$ 把所有冰激凌吃完或者冰激凌融化完，模拟这个过程即可。

int main(int argc, char const *argv[]) {
      int n;
      double u, v, u2, res = 0, t, sum = 0;
      cin >> n >> v >> u;
      for (int i = 1; i <= n; i++) scanf("%lf", &a[i]);
      sort(a + 1, a + n + 1, greater<double>());
      int i;
      for (i = 1; i < n; i++) {
          a[i + 1] -= sum;
          if (a[i + 1] <= 0) break;//后面的已经被融化完了
          if (a[i] == a[i + 1]) continue;
          u2 = u / i;
          t = (a[i] - a[i + 1]) / u2;
          if (a[i + 1] <= v * t) {//当最大值与次大值相同时已经为负数的话应该退出
              break;
          }
          res += u * t;
          a[i + 1] -= v * t;
          sum += v * t;
      }
      u2 = u / i;
      res += a[i] * u / (u2 + v);
      printf("%.7lf\n", res);
      return 0;
  }
  ```

最后修改：2021 年 02 月 09 日

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

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

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

SDUT 2020 Autumn Team Contest---44

spirit • 2020 年 12 月 16 日

[gym链接](https://codeforces.com/gym/102860)

## A - Jumping Machine

## B - Triangles and a Circle

## E - Flag with Stars

## F - String Art

void init(int n) {
      for (int i = 1; i <= n; i++) s[i] = col[i] = i;
  }

int Find(int u) {
      if (u == s[u]) return u;
      return s[u] = Find(s[u]);
  }

## G - Ice Cream

SDUT 2020 Autumn Team Contest---44

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

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

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

Codeforces Round #703 (Div. 2)

SDUT 2021 Winter Individual Contest - E

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

SDUT 2021 Winter Individual Contest - E

SDUT 2021 Winter Individual Contest - M

计算几何基础知识

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

Kattis Terraced fields （数位DP）

SDUT 2020 Autumn Team Contest---44

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

SDUT 2020 Autumn Team Contest---44

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