跃迁引擎启动

Grakn Forces 2020 题解

发表于 更新于 分类于 阅读次数：

A Circle Coloring

每个点有 $3$ 种选择，一个点需要与前后不同，显然遍历一遍即可。

B Arrays Sum

注意到，每种数有多个并没有用，假设一共有 $n$ 种数。

考虑 $k=2$ 的时候情况，如果 $n \le 2$，那么一次操作就能完成，否则之后每次前面一部分填 $0$，然后构造下一个数。

因此 $k>2$ 也是类似的，第一步制造 $k$ 个，然后每次制造 $k-1$。

C Discrete Acceleration

直接对着题意模拟即可。

D Searchlights

注意到，被控制的区域呈现一种下降台阶的形状。于是，每个人，要么往上走，要么往右走，要么走到某个拐角处。

于是，每个人有很多种选择 $(x_j,y_j)$，表示他两个方向需要的步数。

按 $x$ 从小到大枚举，如果所有人都满足过了，在所有人 $y$ 的最小值，取最大值。

E Avoid Rainbow Cycles

注意到，对于每个集合，不需要真的搞出最大团，只要按顺序连成一条链，如果这个图有环，那么原图必有环。

因此题目要求的是，删除最小的边，使得原图没有环，也就是加入最多的树边。

做一个类似 MST 的过程即可。

F Two Different

考虑 $n=2^k$，我们可以每次将数组对半分，如果左右半边都分别被弄成了同样的数，那么我们通过左右两边一一对应，就能将整个区间弄成同一个数。

进一步，考虑 $n$ 的最高位，类似 ST 表，做两次即可。

G Clusterization Counting

给定一个无向带权完全图，每条边边权不同，求有多少种点集的划分方案，使得每个团内的所有边权小于该团所有向外的出边。

观察 Kruskal 建最小生成树的过程，每次合并两个连通块，新加入那条边的权值一定大于两个连通块内的所有边，于是我们可以合并两个连通块的 dp 值。

合并 dp 值只需要做一个类似卷积的过程即可。

特别地，如果某个连通块本身就是 $1$ 个团，那么其分成 $1$ 块的方案数 $+1$。

具体实现可以构造一棵 Kruskal 重构树，做树形背包的 dp。

代码

A

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
#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <cmath>
#include <functional>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <map>
#include <set>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
using ll = long long;
using PII = pair<int,int>;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 200000 + 5;
 
int n, a[maxn], b[maxn], c[maxn];
 
bool ok = false;
vector<int> ans, res;
void dfs(int i) {
  if (ok) return ;
  if (i == n + 1) {
    if (ans.back() != ans.front()) {
      ok = true;
      res = ans;
    }
    return ;
  }
  if (ans.empty() || a[i] != ans.back()) {
    ans.push_back(a[i]);
    dfs(i + 1);
    ans.pop_back();
  }
  if (ans.empty() || b[i] != ans.back()) {
    ans.push_back(b[i]);
    dfs(i + 1);
    ans.pop_back();
  }
  if (ans.empty() || c[i] != ans.back()) {
    ans.push_back(c[i]);
    dfs(i + 1);
    ans.pop_back();
  }
}
 
int main() {
  int T; scanf("%d", &T);
  while (T--) {
    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);
    }
    for (int i = 1; i <= n; i++) {
      scanf("%d", c + i);
    }
    ans.clear();
    res.clear();
    ok = false;
    dfs(1);
    assert(ok);
    for (int x: res) printf("%d ", x);
    puts("");
  }
  return 0;
}

B

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 <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <cmath>
#include <functional>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <map>
#include <set>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
using ll = long long;
using PII = pair<int,int>;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 200000 + 5;
 
int n, k, a[maxn];
 
int ceil(int x, int y) {
  return (x + y - 1) / y;
}
 
int main() {
  int T; scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &n, &k);
    set<int> st;
    for (int i = 1; i <= n; i++) {
      scanf("%d", a + i);
      st.insert(a[i]);
    }
    int sz = st.size();
    if (k == 1) {
      puts(sz == 1 ? "1" : "-1");
    } else {
      if (sz <= k) {
        puts("1");
      } else {
        int ans = 1 + ceil(sz - k, k - 1);
        printf("%d\n", ans);
      }
    }
  }
  return 0;
}

C

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
#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <cmath>
#include <functional>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <map>
#include <set>
#ifdef XLor
  #define dbg(args...) cout << "\033[32;1m" << #args << " -> ", err(args)
  void err() { std::cout << "\033[39;0m" << std::endl; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
  #define dbg(...)
#endif
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
using ll = long long;
using PII = pair<int,int>;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 200000 + 5;
 
int n, L, a[maxn];
 
int main() {
  int T; scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &n, &L);
    a[n + 1] = L;
    for (int i = 1; i <= n; i++) {
      scanf("%d", a + i);
    }
    int px = 0, py = n + 1;
    int vx = 1, vy = 1;
    double ans = 0, lx = 0, ly = L;
    while (true) {
      if (px + 1 == py) {
        ans += (ly - lx) / (vx + vy);
        break;
      } else {
        double dx = (a[px + 1] - lx) / vx;
        double dy = (ly - a[py - 1]) / vy;
        if (dx < dy) {
          ans += dx;
          lx = a[px + 1];
          ly -= vy * dx;
          px++;
          vx++;
        } else {
          ans += dy;
          lx += vx * dy;
          ly = a[py - 1];
          py--;
          vy++;
        }
      }
    }
    printf("%.8lf\n", ans);
  }
  return 0;
}

D

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
#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <cmath>
#include <functional>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <map>
#include <set>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
using ll = long long;
using PII = pair<int,int>;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 200000 + 5;
 
int n, m;
PII a[maxn], b[maxn];
 
struct Info {
  int x, y, id;
  bool operator<(const Info& b) const {
    return x < b.x;
  }
};
 
namespace SegT {
  #define lson l, m, rt << 1
  #define rson m + 1, r, rt << 1 | 1
 
  int a[maxn << 2];
  void build(int l = 1, int r = n, int rt = 1) {
    a[rt] = inf;
    if (l == r) return ;
    int m = (l + r) / 2;
    build(lson);
    build(rson);
  }
  void update(int i, int x, int l = 1, int r = n, int rt = 1) {
    if (l == r) {
      a[rt] = min(a[rt], x);
      return ;
    }
    int m = (l + r) / 2;
    if (i <= m) update(i, x, lson);
    else update(i, x, rson);
    a[rt] = max(a[rt << 1], a[rt << 1 | 1]);
  }
  int ans() {
    return a[1];
  }
}
 
int main() {
  scanf("%d%d", &n, &m);
  SegT::build();
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &a[i].first, &a[i].second);
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &b[i].first, &b[i].second);
  }
  sort(b + 1, b + 1 + m, [&](PII x, PII y) {
    if (x.first != y.first) {
      return x.first < y.first;
    } else {
      return x.second > y.second;
    }
  });
  vector<PII> stk;
  for (int i = 1; i <= m; i++) {
    while (!stk.empty() && b[i].second >= stk.back().second) {
      stk.pop_back();
    }
    stk.push_back(b[i]);
  }
  vector<Info> evs;
  for (int i = 1; i <= n; i++) {
    {
      int dy = stk.front().second + 1 - a[i].second;
      evs.push_back({ 0, max(dy, 0), i });
    }
    {
      int dx = stk.back().first + 1 - a[i].first;
      evs.push_back({ max(dx, 0), 0, i });
    }
    for (int j = 1; j < stk.size(); j++) {
      int tx = stk[j - 1].first + 1;
      int ty = stk[j].second + 1;
      evs.push_back({ max(tx - a[i].first, 0), max(ty - a[i].second, 0), i });
    }
  }
  sort(begin(evs), end(evs));
  int ans = inf;
  for (auto ev: evs) {
    SegT::update(ev.id, ev.y);
    int Y = SegT::ans();
    if (Y < inf) {
      ans = min(ans, ev.x + Y);
    }
  }
  printf("%d\n", ans);
  return 0;
}

E

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
#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <cmath>
#include <functional>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <map>
#include <set>
#ifdef XLor
  #define dbg(args...) cout << "\033[32;1m" << #args << " -> ", err(args)
  void err() { std::cout << "\033[39;0m" << std::endl; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
  #define dbg(...)
#endif
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
using ll = long long;
using PII = pair<int,int>;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 100000 + 5;
 
int m, n, a[maxn], b[maxn];
int pre[maxn];
set<int> A[maxn];
 
int find(int x) {
  return x == pre[x] ? x : pre[x] = find(pre[x]);
}
void join(int x, int y) {
  x = find(x);
  y = find(y);
  if (x != y) {
    pre[x] = y;
  }
}
 
int main() {
  scanf("%d%d", &m, &n);
  for (int i = 1; i <= m; i++) {
    scanf("%d", a + i);
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d", b + i);
    pre[i] = i;
  }
  ll ans = 0;
  set<tuple<ll,int,int> > st;
  for (int i = 1; i <= m; i++) {
    int k, x;
    scanf("%d", &k);
    while (k--) {
      scanf("%d", &x);
      ans -= a[i] + b[x];
      // A[i].insert(x);
      st.emplace(a[i] + b[x], i, x);
    }
  }
  while (!st.empty()) {
    auto mx = *st.rbegin();
    ll tot = get<0>(mx);
    int aid = get<1>(mx);
    int val = get<2>(mx);
    st.erase(--st.end());
 
    bool flag = true;
    int L = -1, R = -1;
    auto it = A[aid].upper_bound(val);
    if (it != A[aid].end()) {
      if (find(val) == find(*it)) {
        flag = false;
      } else {
        R = *it;
      }
    }
    if (it != A[aid].begin()) {
      it--;
      if (find(val) == find(*it)) {
        flag = false;
      } else {
        L = *it;
      }
    }
 
    if (flag) {
      A[aid].insert(val);
      ans += tot;
      if (L != -1) join(L, val);
      if (R != -1) join(val, R);
    }
  }
 
  printf("%I64d\n", -ans);
  return 0;
}

F

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
#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <cmath>
#include <functional>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <map>
#include <set>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
using ll = long long;
using PII = pair<int,int>;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 200000 + 5;
 
int n;
 
bool check(int x) {
  return x == (x & -x);
}
 
vector<PII> get(vector<int>& a) {
  vector<PII> ans;
  int sz = a.size();
  function<void(int,int)> dfs = [&](int l, int r) {
    if (l == r) return ;
    int m = (l + r) / 2;
    dfs(l, m);
    dfs(m + 1, r);
    assert(m - l + 1 == r - m);
    for (int i = l, j = m + 1; i <= m; i++, j++) {
      ans.emplace_back(a[i], a[j]);
    }
  };
  dfs(0, sz - 1);
  return ans;
}
 
int main() {
  scanf("%d", &n);
  vector<PII> ans;
  vector<int> Lhalf, Rhalf;
  for (int i = 20, j = 0; i >= 0; i--) {
    if (n >> i & 1) {
      int k = 1 << i;
      vector<int> vec;
      while (k--) {
        vec.push_back(++j);
      }
      if (Lhalf.empty()) {
        for (int x: vec) {
          Lhalf.push_back(x);
        }
      } else {
        for (int x: vec) {
          Rhalf.push_back(x);
        }
      }
      for (auto x: get(vec)) {
        ans.push_back(x);
      }
    }
  }
  if (!Rhalf.empty()) {
    while (!check(Rhalf.size())) {
      Rhalf.push_back(Lhalf.back());
      Lhalf.pop_back();
    }
    for (auto x: get(Rhalf)) {
      ans.push_back(x);
    }
  }
  printf("%d\n", ans.size());
  for (auto x: ans) {
    printf("%d %d\n", x.first, x.second);
  }
  return 0;
}

G

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <cmath>
#include <functional>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <map>
#include <set>
#ifdef XLor
  #define dbg(args...) cout << "\033[32;1m" << #args << " -> ", err(args)
  void err() { std::cout << "\033[39;0m" << std::endl; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
  #define dbg(...)
#endif
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
using ll = long long;
using PII = pair<int,int>;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 3000 + 5;
 
inline int add(int x, int y) {
  x += y;
  return x >= mod ? x -= mod : x;
}
inline int sub(int x, int y) {
  x -= y;
  return x < 0 ? x += mod : x;
}
inline int mul(int x, int y) {
  return 1ll * x * y % mod;
}
inline int qpow(int x, ll n) {
  int r = 1;
  while (n > 0) {
    if (n & 1) r = 1ll * r * x % mod;
    n >>= 1; x = 1ll * x * x % mod;
  }
  return r;
}
inline int inv(int x) {
  return qpow(x, mod - 2);
}
 
int n, ch[maxn][2];
bool isClique[maxn];
 
int pre[maxn], siz[maxn], cnt[maxn];
int find(int x) {
  return x == pre[x] ? x : pre[x] = find(pre[x]);
}
bool join(int x, int y) {
  x = find(x);
  y = find(y);
  if (x == y) return false;
  pre[x] = y;
  siz[y] += siz[x];
  cnt[y] += cnt[x];
  return true;
}
 
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    pre[i] = i;
    siz[i] = 1;
  }
  vector<tuple<int,int,int> > egs;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      int w;
      scanf("%d", &w);
      if (j < i) {
        egs.emplace_back(w, j, i);
      }
    }
  }
  sort(begin(egs), end(egs));
  int vsz = n;
  for (auto [w, u, v]: egs) {
    int x = find(u), y = find(v);
    if (x != y) {
      vsz++;
      pre[vsz] = vsz;
      join(x, vsz);
      join(y, vsz);
      siz[vsz] = siz[x] + siz[y];
      cnt[vsz] = cnt[x] + cnt[y];
      ch[vsz][0] = x;
      ch[vsz][1] = y;
    }
    int rt = find(u);
    cnt[rt]++;
    if (cnt[rt] == siz[rt] * (siz[rt] - 1) / 2) {
      isClique[rt] = true;
    }
  }
  function<vector<int>(int)> dfs = [&](int u) {
    vector<int> f(n + 1, 0);
    if (u <= n) {
      f[1] = 1;
      return f;
    }
    if (isClique[u]) {
      f[1] = 1;
    }
    auto g = dfs(ch[u][0]);
    auto h = dfs(ch[u][1]);
    for (int i = 1; i <= siz[ch[u][0]]; i++) {
      for (int j = 1; i + j <= siz[u]; j++) {
        int val = mul(g[i], h[j]);
        f[i + j] = add(f[i + j], val);
      }
    }
    return f;
  };
 
  vector<int> ans;
  for (int i = 1; i <= vsz; i++) {
    if (i == find(i)) {
      ans = dfs(i);
      break;
    }
  }
 
  for (int i = 1; i <= n; i++) {
    printf("%d ", ans[i]);
  }
  return 0;
}