邮寄

开场秒掉 A。

B 不会做，写了 70。

----- 1h -----

然后看 C。

C 瞪了 114514 眼看不出来，然后再瞪了 1919810 眼，终于看出来了。

----- 3h -----

然后就不会了，D 啥都想不出来。

最后 100+70+100+0=270。

A 喷泉

弱智题。

直接计算 \(C\) 至 \(AB\) 的距离 \(-r\) 和 \(A, B\) 至 \(C\) 的距离最大值 \(+r\) 即可。

#include <bits/stdc++.h>
using namespace std;
using fl = double;

int t;
fl xa, ya, xb, yb, xc, yc, r;

fl len(fl x, fl y, fl x2, fl y2) {
  return hypot(x2 - x, y2 - y);
}

int main() {
  freopen("fountain.in", "r", stdin);
  freopen("fountain.out", "w", stdout);
  //ios::sync_with_stdio(0);
  //cin.tie(0), cout.tie(0);
  for(scanf("%d", &t); t--; ) {
    //cin >> xa >> ya >> xb >> yb >> xc >> yc >> r;
    scanf("%lf%lf%lf%lf%lf%lf%lf", &xa, &ya, &xb, &yb, &xc, &yc, &r);
    //printf("%lf %lf %lf %lf %lf %lf %lf\n", xa, ya, xb, yb, xc, yc, r);
    fl a = len(xa, ya, xc, yc), b = len(xb, yb, xc, yc), c = len(xa, ya, xb, yb);
    fl x = (c + ((a + b) * (a - b) / c)) / 2;
    printf("%.2lf %.2lf\n", sqrt(a * a - x * x) - r, max(a, b) + r);
    //cout << fixed << setprecision(2) << sqrt(a * a - x * x) - r << ' ' << max(a, b) + r << '\n';
  }
  return 0;
}

B 红绿灯

把当前时间相同的合并在一起，维护每一个集合的当前时间，跳过啥都没做的循环，再加上数据随机，可以过。

#include <bits/stdc++.h>
using namespace std;

int n, m, arr[100010], f, fa[100010], ep[100010], cc, gd;
unordered_map<int, set<int> > mp;

int findfa(int x) {
  return fa[x] == x? x : (fa[x] = findfa(fa[x]));
}

void unionn(int x, int y) {
  x = findfa(x), y = findfa(y);
  if(x == y) {
    return ;
  }
  if(x < y) {
    swap(x, y);
  }
  cc--;
  fa[y] = x;
}

void cal(int x) {
  if(gd % x == 0) {
    return ;
  }
  for(int i = 1; i <= n; i++) {
    i = findfa(i);
    ep[i] = (ep[i] + x - 1) / x * x;
    mp[ep[i]].insert(i);
  }
  for(auto &i : mp) {
    for(auto j : i.second) {
      unionn(j, *(i.second.begin()));
    }
  }
  gd = 0;
  for(int i = 1; i <= n; i++) {
    i = findfa(i);
    gd = __gcd(gd, ep[i]);
  }
  mp.clear();
}

int main() {
  freopen("light.in", "r", stdin);
  freopen("light.out", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m;
  //scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i++) {
    cin >> arr[i];
    //scanf("%d", arr + i);
    f |= arr[i] > 3;
  }
  gd = 1;
  m = unique(arr + 1, arr + m + 1) - arr - 1;
  if(f || m <= 10 || n * m <= 1000000) {
    iota(fa + 1, fa + n + 1, 1);
    iota(ep + 1, ep + n + 1, 1);
    cc = n;
    for(int i = 1; i <= m; i++) {
      cal(arr[i]);
      //cout << i << ' ' << cc << '\n';
    }
    for(int i = 1; i <= n; i++) {
      cout << ep[findfa(i)] << ' ';
      //printf("%d ", ep[findfa(i)]);
    }
    cout << '\n';
    //printf("\n");
  }else {
    for(int i = 1; i <= n; i++) {
      cout << (i + 5) / 6 * 6 << ' ';
      //printf("%d ", (i + 5) / 6 * 6);
    }
    cout << '\n';
    //printf("\n");
  }
  return 0;
}

C 子集

首先我们假设选了 \(x\) 个元素，易知答案为 \(k^{n - x}\)。

所以我们设 \(dp_x\) 为子集和为 \(x\) 时的答案，每一次加入一个数时维护 \(dp\) 就可以了。

\(dp_0 = k^n\)

加一个数时：

\(dp_{i + a_x} \leftarrow \frac{dp_i}{k}\)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int kMod = int(1e9) + 7;

int t, n, m, k, arr[5050], dp[5050], ik;

int qpow(int x, int y) {
  int rs = 1;
  for(; y; y >>= 1) {
    if(y & 1) {
      rs = 1ll * rs * x % kMod;
    }
    x = 1ll * x * x % kMod;
  }
  return rs;
}

int qinv(int x) {
  return qpow(x, kMod - 2);
}

int main() {
  freopen("subset.in", "r", stdin);
  freopen("subset.out", "w", stdout);
  for(cin >> t; t--;) {
    cin >> n >> m >> k;
    ik = qinv(k);
    dp[0] = qpow(k, n);
    for(int i = 1; i <= n; i++) {
      cin >> arr[i];
      for(int j = m - arr[i]; j >= 0; j--) {
        dp[j + arr[i]] = (dp[j + arr[i]] + 1ll * dp[j] * ik) % kMod;
      }
    }
    cout << dp[m] << '\n';
    fill(dp, dp + m + 1, 0);
  }
  return 0;
}