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

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

[A - Average Rank](https://open.kattis.com/problems/averagerank)

- 题意：共有 $n$ 个选手和 $w$ 周，每周有 $k$ 个选手的积分加一，相同积分的选手排名并列，计算每个选手所有星期的排名均值。
- 思路：若 $x$ 选手的积分为 $p[x]$ ，加一后使得积分为 $p[x]$ 的人数减一，积分为 $p[x] + 1$ 的人数加一，同时积分为 $p[x]$ 的人排名加一。如果暴力统计排名和时间复杂度为 $O(nw)$ ，显然不能满足要求。由于每周需要更新的人数和分数其实很少，所以可以采用懒标记的方法记录每个积分对应的排名与排名和上一次发生变化是什么时候。这样做的时间复杂度为 输入时间 $+$ $O(n)$ 。

```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 = 3e5 + 10;
  //分别为：选手当前积分，积分对应排名，积分对应排名和，选手积分变动时对应排名和，选手排名和，积分排名变化懒标记
  LL p[N], rk[N], num[N], pre[N], sum[N], lazy[N];

int main(int argc, char const *argv[]) {
      int n, w, k, x;
      cin >> n >> w;
      for (int i = 0; i < w; i++) {
          scanf("%d", &k);
          while (k --) {
              scanf("%d", &x);
              num[p[x]] += rk[p[x]] * (i - lazy[p[x]]);
              ++rk[p[x]];
              lazy[p[x]] = i;
              sum[x] += num[p[x]] - pre[x];

++p[x];
              num[p[x]] += rk[p[x]] * (i - lazy[p[x]]);
              lazy[p[x]] = i;
              pre[x] = num[p[x]];
          }
      }
      for (int i = 1; i <= n; i++) {
          num[p[i]] += rk[p[i]] * (w - lazy[p[i]]);
          lazy[p[i]] = w;
          sum[i] += num[p[i]] - pre[i];
          printf("%.6lf\n", 1.0 + (double)sum[i] / w);
      }
      return 0;
  }

```

## [G - Gnoll Hypothesis](https://open.kattis.com/problems/gnollhypothesis)

- 题意：怪物池中有 $n$ 只怪物，每只怪物的生成概率为 $p_i$  。现在怪物池中的怪物只有 $k$ 只会生成（任意 $k$ 只），不生成的怪物原本的生成概率将会向后转移给下一只会可能生成的怪物（如果最后的怪物不会生成，那么概率会转移给第一只可能生成的）。求所有怪物现在的生成概率。
- 思路：核心在于概率的合并，对于第 $i$ 只怪物，如果 $p_{i-j}$ 要合并到 $p_i$ ，那么区间 $[i-j, i]$ 之间一定是不能生成的怪物，即需要在剩余的 $n - j - 1$ 个怪物中选择 $k-1$ 个怪物。因此计算 $p_i^{'}$ 的公式为： $p_i^{'} = \sum_{j=0}^{n-k} p_{i-j}·\frac{C_{n-j-1}^{k-1}}{C_n^k}$ 。

```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 = 1005;
  long double dp[N][N];//事实上刚做这道题的时候我和队友认为n = 500时的组合数太大会爆long long，但其实double 和 long double 可以存1e4000+ 和 1e300+，且这道题求的不是精确的整数，所以用long double是可以做这道题的
  double a[N], sum[N];

void init(int n) {
      for (int i = 0; i <= n; i++) dp[i][0] = dp[i][i] = 1;
      for (int i = 1; i <= n; i++) {
          for (int j = 1; j < i; j++) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
      }
  }

int main(int argc, char const *argv[]) {
      int n, k;
      cin >> n >> k;
      init(n);
      for (int i = 1; i <= n; i++) {
          scanf("%lf", &a[i]);
          a[i + n] = a[i];
      }
      int m = n - k;
      for (int i = 1; i <= n; i++) {
          for (int j = 0; j <= m; j++)
              sum[i] += dp[n - j - 1][k - 1] * a[i + n - j] / dp[n][k];
          printf("%.7lf%c", sum[i], i == n ? '\n' : ' ');
      }
      return 0;
  }
  ```

## [A - Average Rank](https://open.kattis.com/problems/averagerank)

* 题意：共有  个选手和  周，每周有  个选手的积分加一，相同积分的选手排名并列，计算每个选手所有星期的排名均值。
* 思路：若  选手的积分为  ，加一后使得积分为  的人数减一，积分为  的人数加一，同时积分为  的人排名加一。如果暴力统计排名和时间复杂度为  ，显然不能满足要求。由于每周需要更新的人数和分数其实很少，所以可以采用懒标记的方法记录每个积分对应的排名与排名和上一次发生变化是什么时候。这样做的时间复杂度为 输入时间   。
  ```
  #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 = 3e5 + 10;
  //分别为：选手当前积分，积分对应排名，积分对应排名和，选手积分变动时对应排名和，选手排名和，积分排名变化懒标记
  LL p[N], rk[N], num[N], pre[N], sum[N], lazy[N];

int main(int argc, char const *argv[]) {
      int n, w, k, x;
      cin >> n >> w;
      for (int i = 0; i < w; i++) {
          scanf("%d", &k);
          while (k --) {
              scanf("%d", &x);
              num[p[x]] += rk[p[x]] * (i - lazy[p[x]]);
              ++rk[p[x]];
              lazy[p[x]] = i;
              sum[x] += num[p[x]] - pre[x];

++p[x];
              num[p[x]] += rk[p[x]] * (i - lazy[p[x]]);
              lazy[p[x]] = i;
              pre[x] = num[p[x]];
          }
      }
      for (int i = 1; i <= n; i++) {
          num[p[i]] += rk[p[i]] * (w - lazy[p[i]]);
          lazy[p[i]] = w;
          sum[i] += num[p[i]] - pre[i];
          printf("%.6lf\n", 1.0 + (double)sum[i] / w);
      }
      return 0;
  }

```

## [G - Gnoll Hypothesis](https://open.kattis.com/problems/gnollhypothesis)

* 题意：怪物池中有  只怪物，每只怪物的生成概率为   。现在怪物池中的怪物只有  只会生成（任意  只），不生成的怪物原本的生成概率将会向后转移给下一只会可能生成的怪物（如果最后的怪物不会生成，那么概率会转移给第一只可能生成的）。求所有怪物现在的生成概率。
* 思路：核心在于概率的合并，对于第  只怪物，如果  要合并到  ，那么区间  之间一定是不能生成的怪物，即需要在剩余的  个怪物中选择  个怪物。因此计算  的公式为：  。
  ```
  #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 = 1005;
  long double dp[N][N];//事实上刚做这道题的时候我和队友认为n = 500时的组合数太大会爆long long，但其实double 和 long double 可以存1e4000+ 和 1e300+，且这道题求的不是精确的整数，所以用long double是可以做这道题的
  double a[N], sum[N];

void init(int n) {
      for (int i = 0; i <= n; i++) dp[i][0] = dp[i][i] = 1;
      for (int i = 1; i <= n; i++) {
          for (int j = 1; j < i; j++) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
      }
  }

int main(int argc, char const *argv[]) {
      int n, k;
      cin >> n >> k;
      init(n);
      for (int i = 1; i <= n; i++) {
          scanf("%lf", &a[i]);
          a[i + n] = a[i];
      }
      int m = n - k;
      for (int i = 1; i <= n; i++) {
          for (int j = 0; j <= m; j++)
              sum[i] += dp[n - j - 1][k - 1] * a[i + n - j] / dp[n][k];
          printf("%.7lf%c", sum[i], i == n ? '\n' : ' ');
      }
      return 0;
  }
  ```

最后修改：2021 年 02 月 09 日

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

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

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

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

spirit • 2020 年 12 月 14 日

[A - Average Rank](https://open.kattis.com/problems/averagerank)

```

## [G - Gnoll Hypothesis](https://open.kattis.com/problems/gnollhypothesis)

```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 = 1005;
  long double dp[N][N];//事实上刚做这道题的时候我和队友认为n = 500时的组合数太大会爆long long，但其实double 和 long double 可以存1e4000+ 和 1e300+，且这道题求的不是精确的整数，所以用long double是可以做这道题的
  double a[N], sum[N];

## [A - Average Rank](https://open.kattis.com/problems/averagerank)

int main(int argc, char const *argv[]) {
      int n, w, k, x;
      cin >> n >> w;
      for (int i = 0; i < w; i++) {
          scanf("%d", &k);
          while (k --) {
              scanf("%d", &x);
              num[p[x]] += rk[p[x]] * (i - lazy[p[x]]);
              ++rk[p[x]];
              lazy[p[x]] = i;
              sum[x] += num[p[x]] - pre[x];

++p[x];
              num[p[x]] += rk[p[x]] * (i - lazy[p[x]]);
              lazy[p[x]] = i;
              pre[x] = num[p[x]];
          }
      }
      for (int i = 1; i <= n; i++) {
          num[p[i]] += rk[p[i]] * (w - lazy[p[i]]);
          lazy[p[i]] = w;
          sum[i] += num[p[i]] - pre[i];
          printf("%.6lf\n", 1.0 + (double)sum[i] / w);
      }
      return 0;
  }

```

## [G - Gnoll Hypothesis](https://open.kattis.com/problems/gnollhypothesis)

void init(int n) {
      for (int i = 0; i <= n; i++) dp[i][0] = dp[i][i] = 1;
      for (int i = 1; i <= n; i++) {
          for (int j = 1; j < i; j++) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
      }
  }

int main(int argc, char const *argv[]) {
      int n, k;
      cin >> n >> k;
      init(n);
      for (int i = 1; i <= n; i++) {
          scanf("%lf", &a[i]);
          a[i + n] = a[i];
      }
      int m = n - k;
      for (int i = 1; i <= n; i++) {
          for (int j = 0; j <= m; j++)
              sum[i] += dp[n - j - 1][k - 1] * a[i + n - j] / dp[n][k];
          printf("%.7lf%c", sum[i], i == n ? '\n' : ' ');
      }
      return 0;
  }
  ```

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

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

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

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

Codeforces Round #703 (Div. 2)

SDUT 2021 Winter Individual Contest - E

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

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

SDUT 2021 Winter Individual Contest - M

SDUT 2021 Winter Individual Contest - D

堆的实现

SDUT 2021 Winter Individual Contest - E

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

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

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

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