训练

2019 ICPC Asia-East Continent Final

A B C D E F G H I J K L M
O x O x O x Ø O x x x x O
  • O 在比赛中通过
  • Ø 赛后通过
  • ! 尝试了但是失败了
  • x 没有尝试

A. City

全程队友做的，说是签到。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int n,m;
  scanf("%d%d",&n,&m);
  ll A=1LL*(m-m/2)*(m/2);
  ll B=1LL*(n-n/2)*(n/2);
  ll ans=2LL*A*B+A*(n+1)+B*(m+1);
  printf("%lld\n",ans);
  return 0;
}

C. Dirichlet $k$-th root

给出 \(g = f^k\) ，“乘法”定义为狄利克雷卷积，其中 \(g(1) = f(1) = 1\) 。

容易发现 \[ g(n) = \sum \prod_{\prod a_i = n, 1 \le i \le k} f(a_i) = \sum_{m = 1}^{k} {k \choose m} \prod_{\prod a_i = n , 1 \le i \le m, a_i \ge 2} f(a_i) \] 由于$a_i ≥ 2, n ≤ 10^5$，所以$m ≤ min(k, 19)$。定义$C = min(k, 19)$，有 \[ f(n) = \frac{g(n) - \sum_{m = 2}^{k} {k \choose m} \prod_{\prod a_i = n , 1 \le i \le m, a_i \ge 2} f(a_i)}{k} \] 定义 \(h_{n, m} = \prod_{\prod a_i = n , 1 \le i \le m, a_i \ge 2} f(a_i)\) ，我们就可以推导出$f(n)$了。

学弟还发现了 \(f = g^{k^{-1}}\) 在模意义下成立，但是菜鸡 cycleke 不会证明 😭️。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

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

const int MAXN = 1e5 + 3;
const int MOD = 998244353;

int mpow(int a, int b = MOD - 2) {
  int r = 1;
  for (; b; b >>= 1, a = 1ll * a * a % MOD)
    (b & 1) && (r = 1ll * r * a % MOD);
  return r;
}

int factor[MAXN];
bitset<MAXN> vis;
vector<int> prime, factors;

int p[18], e[18], tot;

void dfs(int step, int cur) {
  if (step == 0) {
    if (cur > 1) factors.push_back(cur);
  } else {
    for (int i = 0; i <= e[step]; ++i, cur *= p[step])
      dfs(step - 1, cur);
  }
}

void find_factors(int x) {
  factors.clear();
  tot = 0;
  while (x > 1) {
    ++tot;
    int f = p[tot] = factor[x];
    for (e[tot] = 0; factor[x] == f; x /= f) ++e[tot];
  }
  dfs(tot, 1);
}

int f[MAXN], g[MAXN], h[MAXN][18];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);

  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) cin >> g[i];

  for (int i = 2; i < MAXN; ++i) {
    if (!vis[i]) {
      factor[i] = i;
      prime.push_back(i);
    }
    for (int p : prime) {
      int t = i * p;
      if (t >= MAXN) break;
      vis[t] = 1;
      factor[t] = p;
      if (i % p == 0) break;
    }
  }

  int inv_k = mpow(k);
  f[1] = 1;
  cout << 1;
  for (int i = 2; i <= n; ++i) {
    int bound = min(17, k);
    find_factors(i);
    for (int d : factors) {
      for (int m = 2; m <= bound; ++m) {
        h[i][m] = (h[i][m] + 1ll * h[d][1] * h[i / d][m - 1]) % MOD;
      }
    }
    int C = k;
    int sum = 0;
    for (int m = 2; m <= bound; ++m) {
      C = 1ll * C * (k + 1 - m) % MOD * mpow(m) % MOD;
      sum = (sum + 1ll * C * h[i][m]) % MOD;
    }
    f[i] = g[i] - sum;
    if (f[i] < 0) f[i] += MOD;
    h[i][1] = f[i] = 1ll * f[i] * inv_k % MOD;
    cout << " " << f[i];
  }
  cout << "\n";
  return 0;
}

E. Flow

显然最大流为 \(\lceil \frac{\sum z}{dist_{1, n}} \rceil\) ，为了获得最大流，我们的策略就是依次为小边扩流。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

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

const int MAXN = 1e5 + 3;
const int MAXM = 2e5 + 3;

long long sum[MAXN];
vector<pair<int, int>> adj[MAXN];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);

  int n, m;
  long long flow = 0;
  cin >> n >> m;
  for (int u, v, w; m; --m) {
    cin >> u >> v >> w;
    adj[u].emplace_back(v, w);
    flow += w;
  }

  int len = 0;
  for (auto e : adj[1]) {
    static vector<int> path;

    path.clear();
    path.push_back(e.second);
    for (int x = e.first; x != n; x = adj[x][0].first)
      path.push_back(adj[x][0].second);

    sort(path.begin(), path.end());

    len = path.size();
    for (int i = 0; i < len; ++i) sum[i] += path[i];
  }

  // for (int i = 0; i < len; ++i) cout << sum[i] << " ";

  flow -= sum[0] * len;
  long long ans = 0;
  for (int i = 1; i < len; ++i) {
    long long temp = min(flow / len, sum[i] - sum[i - 1]);
    ans += temp * i, flow -= temp * len;
  }
  cout << ans << "\n";

  return 0;
}

G. Happiness

大模拟，队友没来得及写完。。。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112

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

const int MAXN = 300 + 3;
const int PROBLEMS = 10;
const int PENALTY = 20;
const int GOLD_MEDAL = 1200;
const int SILVER_MEDAL = 800;
const int BRONZE_MEDAL = 400;
const int PROBLEM_FIRST_BLOOD = 800;
const int ALL_FIRST_BLOOD = 700;
const int ALL_LAST_BLOOD = 500;
const int CONTEST_TIME = 300;
const int HAPPINESS_RATE = 5000;

int getInt() {
  char ch = getchar();
  while (ch != '-' && !isdigit(ch)) ch = getchar();
  if (ch == '-') return -1;
  int x = ch - '0';
  while (isdigit(ch = getchar())) x = x * 10 + ch - '0';
  return x;
}

int n, team_rank[MAXN], all_first_time, all_last_time, first_time[PROBLEMS];

struct Team {
  int id, solved, total_time, solved_time[PROBLEMS];

  void read(int id) {
    this->id = id;
    solved = total_time = 0;
    for (int i = 0; i < PROBLEMS; ++i) {
      int done_time = getInt();
      if (done_time == -1) continue;
      int wrong_time = getInt();
      solved_time[solved++] = done_time;
      total_time += done_time + PENALTY * wrong_time;
      first_time[i] = min(first_time[i], done_time);
    }
    sort(solved_time, solved_time + solved, greater<int>());
    if (solved) {
      all_last_time = max(all_last_time, solved_time[0]);
      all_first_time = min(all_first_time, solved_time[solved - 1]);
    }
  }

  bool operator<(const Team &other) const {
    if (solved ^ other.solved) return solved > other.solved;
    if (total_time ^ other.total_time) return total_time < other.total_time;
    for (int i = 0; i < solved; ++i)
      if (solved_time[i] ^ other.solved_time[i])
        return solved_time[i] < other.solved_time[i];
    return id < other.id;
  }
} teams[MAXN], pang;

int need_time[PROBLEMS], need_wrong_time[PROBLEMS], can_solve, permu[PROBLEMS];

int main(int argc, char *argv[]) {
  n = getInt();

  fill(first_time, first_time + PROBLEMS, INT_MAX);
  all_first_time = INT_MAX, all_last_time = INT_MIN;
  for (int i = 1; i < n; ++i) {
    teams[i].read(i);
    team_rank[i] = i;
  }
  sort(team_rank + 1, team_rank + n,
       [&](int a, int b) { return teams[a] < teams[b]; });

  for (int i = 0; i < PROBLEMS; ++i) {
    need_time[i] = getInt();
    if (need_time[i] < 0) continue;
    permu[can_solve++] = i;
    need_wrong_time[i] = getInt();
  }

  int ans = 0;
  do {
    int happiness = 0, now = 0;
    pang.solved = pang.total_time = 0;
    for (int i = 0; i < can_solve; ++i) {
      int j = permu[i];
      if (now + need_time[j] > CONTEST_TIME) break;
      now += need_time[j];
      pang.solved_time[pang.solved++] = now;
      pang.total_time += now + need_wrong_time[j] * PENALTY;
      if (now <= first_time[j]) happiness += PROBLEM_FIRST_BLOOD;
      if (!i && now <= all_first_time) happiness += ALL_FIRST_BLOOD;
    }
    if (pang.solved && now >= all_last_time) happiness += ALL_LAST_BLOOD;
    reverse(pang.solved_time, pang.solved_time + pang.solved);
    int l = 1, r = n - 1;
    while (l <= r) {
      int mid = (l + r) / 2;
      (pang < teams[team_rank[mid]]) ? r = mid - 1 : l = mid + 1;
    }
    happiness += HAPPINESS_RATE / l;
    if (l <= n / 10) {
      happiness += GOLD_MEDAL;
    } else if (l <= 3 * n / 10) {
      happiness += SILVER_MEDAL;
    } else if (l <= 6 * n / 10) {
      happiness += BRONZE_MEDAL;
    }
    ans = max(ans, happiness);
  } while (next_permutation(permu, permu + can_solve));

  cout << ans << "\n";
  return 0;
}

H. King

由于我们只需要输出超过 \(\frac{n}{2}\) 的答案，所以统计所以相邻和间隔一的比例，只需要对于出现次数大于 \(\frac{n}{8}\) 的进行所有的统计。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

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

const int MAXN = 2e5 + 3;

int mpow(int a, int b, int m) {
  int r = 1;
  for (; b; b >>= 1, a = 1ll * a * a % m)
    (b & 1) && (r = 1ll * r * a % m);
  return r;
}

int inv(int x, int m) { return mpow(x, m - 2, m); }

int a[MAXN], n, p;

void solve() {
  cin >> n >> p;
  for (int i = 0; i < n; ++i) cin >> a[i];

  static vector<int> qs;
  static map<int, int> f;

  f.clear();
  ++f[1ll * a[1] * inv(a[0], p) % p];
  for (int i = 2; i < n; ++i) {
    ++f[1ll * a[i] * inv(a[i - 1], p) % p];
    ++f[1ll * a[i] * inv(a[i - 2], p) % p];
  }

  int bound = n / 8;
  qs.clear();
  for (auto &p : f)
    if (p.second >= bound) qs.push_back(p.first);

  static auto gao = [&](int q) {
    f.clear();
    int res = 0;
    for (int i = n - 1; ~i; --i) {
      f[a[i]] = max(f[a[i]], f[1ll * a[i] * q % p] + 1);
      res = max(res, f[a[i]]);
    }
    return res;
  };

  int ans = 0;
  for (int q : qs) ans = max(ans, gao(q));
  cout << (ans * 2 < n ? -1 : ans) << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);

  int o_o;
  for (cin >> o_o; o_o; --o_o) solve();

  return 0;
}

M. Value

全程队友做的，按幂独立搜索即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

# include <bits/stdc++.h>
# define LL long long
# define N 100010

using namespace std;

int n,a[N],b[N],cnt,num[N];
bool v[N],it[N];
LL ans,nowans;

void dfs(int id){
  if (id == cnt+1)
  {
    LL now = 0;
    for (int i=1; i<=cnt; ++i) if (it[i]) now += a[num[i]];
    for (int i=1; i<=cnt; ++i)
    {
      if (!it[i]) continue;
      for (int j=i+1; j<=cnt; ++j)
      {
        if (!it[j]) continue;
        if (j%i) continue;
        now -= b[num[j]];
      }
    }
    nowans = max(nowans,now);
    return;
  }
  it[id] = 1;
  dfs(id+1);
  it[id] = 0;
  dfs(id+1);
}

int main()
{
//	freopen("data.txt","r",stdin);
  scanf("%d",&n);
  for (int i=1; i<=n; ++i) scanf("%d",&a[i]);
  for (int i=1; i<=n; ++i) scanf("%d",&b[i]);
  ans += a[1];
  for (int i=2; i<=n; ++i)
  {
    if (v[i]) continue;
//		printf("%d ",i);
    LL now = i;
    cnt = 0;
    while (now <= 1LL*n)
    {
      num[++cnt] = now;
      v[now] = 1;
      now *= i;
    }
    nowans = 0;
    dfs(1);
//		printf("%d -- ",nowans);
    ans += nowans;
  }
  printf("%lld",ans);
}
comments powered by Disqus