跳转至

2020 ICPC ECfinal

排名 当场过题数 至今过题数 总题数
185/527 4 8 13

A

solved by JJLeo 2sozx

题意

题解

B

upsolved by 2sozx

题意

题解

C

upsolved by 2sozx

题意

给一份代码，告诉 \(n\) 以及输出的数列，问随机输入的种子 \(x\) 是多少。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
  uint64_t x;//uint64_t represents 64-bit unsigned integer
  int n;
  uint64_t rand() {//this is a xor-shift random generator
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    return x;
  }
  int main() {
    cin >> n;
    cin >> x;
    for (int i = 1; i <= n; i++) {//random shuffle [1, 2,..., n]
      a[i] = i;
      swap(a[i], a[rand() % i + 1]);
    }
    for (int i = 1; i <= n; i++) {//print the result
      cout << a[i] << (i == n ? ’\n’ : ’ ’);
    }
  }

\(50 \le n \le 10^5, 0 \le x \le 2^{64} - 1\)

题解

观察这个随机，我们会发现从后往前推我们可以知道每一次 \(\text{rand() \% i}\) 为多少，考虑我们通过这个值会得到什么。

考虑 \(\text{rand() \% i}\)，我们可以确定这次 \(\text{rand()}\) 后 \(\text{i \& -i}\) 位置为多少。考虑单独的每一位在这个 \(\text{rand()}\) 后由最开始的哪几位得到，这样我们可以得到很多个方程。在题中 \(n\ge 50\) 的情况下没有确定的位置不超过 \(17\) 个，因此我们可以枚举剩余位置的值，再 \(O(n)\) 判断这个 \(x\) 是否合法。

注意这个复杂度是不可能满的，因为 \(n\) 大的时候没确定的位置就会变少，并且不合法的 \(x\) 走很少的步数就可以 \(\text{break}\) 掉。

D

upsolved by 2sozx

题意

\(n\) 个点，\(m\) 条边的无向图，每条边长度为 \(1\)，初始速度为 \(1\)。每次可以花 \(1\)元钱增加每条边的速度。现在有两对起点和终点，共有 \(k\) 元钱，问两个起点分别到对应终点花费的时间和最小值是多少。

\(k \le 10^9, n, m \le 5000\)

题解

对于这两条路径我们可以分为公共边和单独边。

一个结论：两条路径的公共边一定是连续的。

首先预处理出所有点对之间的最短距离。考虑枚举公共边的起点和终点，这样我们就可以得到这种情况下单独边的条数最少是多少。由于我们公共边条数最大不超过 \(n\)，因此最后我们只有 \(O(n)\) 种状态。对于每种状态我们可以三分在公共边上花的费用得到这个状态下的最小时间，所有状态取 \(\min\) 即可。

注意可以两条路径直接走，没有公共边。

E

upsolved by

题意

题解

G

upsolved by

题意

题解

H

upsolved by

题意

题解

I

upsolved by 2sozx

题意

PvZ！

一维数轴，\(n\) 个僵尸在 \(t_i\) 时刻从 \(x = 0\) 出发，共有 \(h_i\) 的生命值，每秒钟僵尸移动 \(V\)。

植物有 \(m\) 个地刺和豌豆射手： - 第 \(i\) 个地刺在 \(p_i\) 可以造成 \(a_i\) 的伤害。如果僵尸某个时刻从 \(P\) 移动到 \(P + V\)，则会受到所有位置在 \((P, P + V]\) 地刺的伤害。

  • 豌豆射手在无穷远处，每秒会发射 \(K\) 个豌豆，每个豌豆伤害为 \(D\)。豌豆会攻击走的最远的僵尸，如果多个僵尸位置相同则会攻击序号最小的僵尸。

每个时刻的移动如下： - 僵尸移动

  • 踩地刺

  • 被豌豆打

问所有僵尸的死亡时间。

\(1\le n, m \le 10^5, 1 \le V, K, D \le 10^9\)

题解

考虑先将所有僵尸排序，按顺序考虑，对于每个僵尸我们可以二分他的死亡时间。有个很显然的性质就是被豌豆攻击过的僵尸死亡时间是递增的。因此考虑记录已经攻击过僵尸的豌豆个数，通过这个也可以计算出豌豆攻击了多少时间。

考虑二分的死亡时间，计算这段时间收到了多少伤害，地刺伤害显然是好算的，豌豆伤害也是好算的，通过之前攻击的豌豆个数以及这个僵尸的出现时间和此时二分的时间也可以算出。得到这个僵尸死亡时间后更新使用的豌豆次数即可。

此题需要开 __int128 并且答案巨大，二分范围最好为 \(1\sim 10^{18}\)。

J

upsolved by

题意

题解

K

upsolved by 2sozx Bazoka13 JJLeo

题意

小模拟，爬

题解

小模拟，爬

L

upsolved by JJLeo 2sozx

题意

题解

记录

0h：F是个签到，ZYF写了过了。看L好像也是个签到，MJX喂了个做法ZYF开写，写完WA了，发现统计个数时候判断写错了，改了过了。MJX看A感觉很可做，开始想A，CSK看J感觉有点想法，MJX感觉没啥毛病。

1h：MJX给ZYF喂了A的想法，ZYF YY了A的做法，感觉很对就开冲，两次WA5，不知道哪错了开始对拍，CSK说K是个德扑模拟，先冲J了。

2h：嘛也不会，MJX看ZYF A有个地方没必要这么写，不过MJX和ZYF俩人觉得也没错（就离谱）

3h：MJX说瞅瞅暴力和对拍，ZYF发现对拍写的是 "fc a.out a.out"，可不拍不出来，改了一下就拍出来了，瞅了下就是那个没必要那么写的地方写错了，改了过了，离谱。CSK J还没调出来，MJX想先把K写了，CSK概述了一下题意，ZYF想了想有用的状态只有同花顺，MJX开写，写了过了。

4h：调J，寄！

总结

Dirt