KEYENCE Programming Contest 2019 Solution

A - Beginning

签到.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int a[4];
 7     while (scanf("%d", a) != EOF)
 8     {
 9         for (int i = 1; i < 4; ++i) scanf("%d", a + i);
10         sort(a, a + 4);
11         int res = 0;
12         for (int i = 0; i < 4; ++i) res = res * 10 + a[i];
13         puts(res == 1479 ? "YES" : "NO");
14     }
15     return 0;
16 }

View Code

B - KEYENCE String

签

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 string s;
 5 
 6 string get(int pos)
 7 {
 8     string res = "";
 9     for (int i = 0; i <= pos; ++i) res += s[i];
10     int len = s.size();
11     for (int i = len - (7 - pos - 1); i < len; ++i) res += s[i];
12     return res;
13 }
14 
15 bool work()
16 {
17     for (int i = 0; i < 7; ++i)
18     {
19         string tmp = get(i);
20         if (tmp == "keyence") return 1;
21     }
22     return 0;
23 }
24 
25 int main()
26 {
27     while (cin >> s) puts(work() ? "YES" : "NO");
28     return 0;
29 }

View Code

C - Exam and Wizard

Solved.

题意：

给出些个数字$A_i, 和 B_i$

要求构造$C_i 使得 C_i >= B_i 并且 sum A_i = sum C_i$

并且使得变动的数字个数最少

思路：

先弄出不足的部分，然后取差值最大的$A_i > B_i$ 的部分用堆维护，每次取最大的贡献出来补充

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 100010
 5 #define ll long long
 6 int n, a[N], b[N];
 7 
 8 int main()
 9 {
10     while (scanf("%d", &n) != EOF)
11     {
12         for (int i = 1; i <= n; ++i) scanf("%d", a + i);
13         for (int i = 1; i <= n; ++i) scanf("%d", b + i);
14         ll need = 0;
15         priority_queue <int, vector <int>, less <int> > pq;
16         int res = 0; 
17         for (int i = 1; i <= n; ++i) 
18         {
19             if (b[i] > a[i]) need += b[i] - a[i], ++res;
20             else if (b[i] < a[i]) pq.push(a[i] - b[i]);
21         }
22         while (!pq.empty() && need > 0)
23         {
24             int top = pq.top(); pq.pop();
25             need -= top; ++res;    
26         }
27         if (need > 0) puts("-1");
28         else printf("%d
", res);
29     }
30     return 0;
31 }

View Code

D - Double Landscape

Upsolved.

题意：

在$n * m的矩阵中填数，每行中最大的数为a_i, 每列中最大的数为b_i$

求填数方案

思路：

对于某个数$x$

如果它存在于多个$a_i 中或者多个 b_i 中 $

那么无解

再考虑

它既存在于$a_i 也存在于 b_i 中

那么它的位置是确定的$

它只存在于某个$a_i或者某个b_i中$

那么它的方案数就是那一列或者那一行的$a_i$比它大的数的个数

它不存在于某个$a_i或者某个b_i中$

那么它的方案数是 $a_i > a_x 的个数 cdot b_i > b_x的个数$

但是要减去比它大的数的个数

因为它能填的位置，比它大的数都能填，而且是子集关系

所以要让出一位

但是对于第二种情况不用考虑，因为第二种情况的那个数肯定是当前行或者当前列最大的

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 #define N 1100
 6 const ll MOD = (ll)1e9 + 7;
 7 int n, m, a[N], b[N];
 8 
 9 bool check()
10 {
11     for (int i = 1; i <= n; ++i) for (int j = i + 1; j <= n; ++j)
12         if (a[i] == a[j]) return false;
13     for (int i = 1; i <= m; ++i) for (int j = i + 1; j <= m; ++j)
14         if (b[i] == b[j]) return false; 
15     return true; 
16 }
17 
18 int main()
19 {
20     while (scanf("%d%d", &n, &m) != EOF)
21     {
22         for (int i = 1; i <= n; ++i) scanf("%d", a + i);
23         for (int i = 1; i <= m; ++i) scanf("%d", b + i);
24         sort(a + 1, a + 1 + n);
25         sort(b + 1, b + 1 + m);
26         if (!check()) puts("0");  
27         else
28         {
29             a[n + 1] = n + 1;
30             b[m + 1] = m + 1;
31             int l[2] = {0, 0};
32             ll res = 1; 
33             for (int i = 1; i <= n * m; ++i)
34             {
35                 while (l[0] <= n && a[l[0]] < i) ++l[0]; 
36                 while (l[1] <= m && b[l[1]] < i) ++l[1];
37                 ll d = 0;
38                 if (a[l[0]] == i && b[l[1]] == i)
39                     d = 1;
40                 else if (a[l[0]] == i && b[l[1]] != i)
41                     d = m - l[1] + 1;
42                 else if (b[l[1]] == i && a[l[0]] != i)
43                     d = n - l[0] + 1;
44                 else
45                     d = (m - l[1] + 1) * (n - l[0] + 1) - (n * m - i);
46                 res = (res * d) % MOD; 
47             } 
48             printf("%lld
", res);
49         }
50     }
51     return 0;
52 }

View Code

E - Connecting Cities

Upsolved.

题意：

$n个城市，两个城市之间的边权是 |i - j| cdot D + A_i + A_j$

求最小生成树

思路：

考虑将区间分成两部分

分别为$[l, mid] 和 [mid +1, r]$

考虑

左区间为$f[i] = a[i] - d * i$

右区间为$g[i] = a[i] + d * j$

令$f[0] 和 g[0] 为 Min(f[i]), g[0] 为 Min(g[i])$

那么我们将$(i, j_0), (i_0, j), (i_0, j_0) 连边$

我么考虑$(i, j)这种边一定比上面三种边的边权要大$

那么假设我们需要$(i, j)这种边来增加连通性，那么上面那三种边必定能满足$

所以分治建边一共有$NlogN级别的边数 $

再做MST

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 #define N 200010
 6 #define INFLL 0x3f3f3f3f3f3f3f3f
 7 int n, m;
 8 ll d, a[N];
 9 struct Edge
10 {
11     int u, v; ll w;
12     Edge() {}
13     Edge(int u, int v, ll w) : u(u), v(v), w(w) {}
14     bool operator < (const Edge &other) const { return w < other.w; }
15 }edge[N * 30];
16 
17 void add(int l, int r)
18 {
19     if (l == r) return;
20     int mid = (l + r) >> 1;
21     ll Min = INFLL; int pos = -1; 
22     for (int i = l; i <= mid; ++i) 
23     {
24         ll f = a[i] - d * i;
25         if (f < Min)
26         {
27             Min = f;
28             pos = i;
29         }
30     }
31     for (int i = mid + 1; i <= r; ++i)
32         edge[++m] = Edge(pos, i, a[pos] + a[i] + d * (i - pos));
33     Min = INFLL; pos = -1;
34     for (int i = mid + 1; i <= r; ++i)
35     {
36         ll f = a[i] + d * i;
37         if (f < Min)
38         {
39             Min = f;
40             pos = i;
41         }
42     }
43     for (int i = l; i <= mid; ++i) 
44         edge[++m] = Edge(pos, i, a[pos] + a[i] + d * (pos - i));
45     add(l, mid);
46     add(mid + 1, r);
47 }
48 
49 int pre[N];
50 int find(int x) { return pre[x] == 0 ? x : pre[x] = find(pre[x]); }
51 ll Kruskal()
52 {
53     memset(pre, 0, sizeof pre);
54     sort(edge + 1, edge + 1 + m);
55     int cnt = 1;
56     ll res = 0;
57     for (int i = 1; i <= m; ++i)
58     {
59         int u = edge[i].u, v = edge[i].v; ll w = edge[i].w;
60         int fu = find(u), fv = find(v);
61         if (fu == fv) continue;
62         pre[fu] = fv;
63         res += w;
64         ++cnt;
65         if (cnt == n) return res;
66     }
67     return res;
68 }
69 
70 int main()
71 {
72     while (scanf("%d%lld", &n, &d) != EOF)
73     {
74         m = 0;
75         for (int i = 1; i <= n; ++i) scanf("%lld", a + i);
76         add(1, n);
77         printf("%lld
", Kruskal());
78     }
79     return 0;
80 }

View Code

法二：

按$a_i大小排序$

每次对于当前$x, 在所有a_j <= a_x的城市当中，对于在它两侧的，各选出一条最短边连边$

为什么这样贪心是对的

我们考虑假如存在一个城市$z; a_z < a_i, 并且假设最短边的城市是y$

那么$(x, y) 和 (y, z) 都小于 (x, z)$

所以$(x, z)这条边一定不在MST中$

考虑这样证明

$dist(x, y) < dist(x, z) 非常显然$

考虑$dist(y, z) < dist(x, z)$

首先假设$z < y < x$

$dist(y, z) = a_y +a_z + d * (y - z)$

$dist(x, z) = a_x + a_z + d * (x - z)$

$dist(x, z) - dist(y, z) = a_x - a_y + d * (x - y) >= 0$

得证

再考虑$y < z < x$

$dist(x, y) = a_x + a_y + d * (x - y)$

$dist(z, y) = a_z + a_y + d * (z - y)$

$dist(x, y) - dist(z, y) = a_x - a_z + d * (x - z) >= 0$

又因为 $dist(x, y) <= dist(x, z)$

所以$dist(x, z) >= dist(x, y) >= dist(z, y)$

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 #define ll long long
  5 #define N 200010
  6 #define INFLL 0x3f3f3f3f3f3f3f3f
  7 int n, m;
  8 ll d;
  9 struct node
 10 {
 11     int id; ll v;
 12     void scan(int id)
 13     {
 14         this->id = id;
 15         scanf("%lld", &v);
 16     }
 17     bool operator < (const node &other) const { return v < other.v; }
 18 }a[N];
 19 struct Edge
 20 {
 21     int u, v; ll w;
 22     Edge () {}
 23     Edge (int u, int v, ll w) : u(u), v(v), w(w) {}
 24     bool operator < (const Edge &other) const { return w < other.w; }
 25 }edge[N << 2];
 26 
 27 struct SEG
 28 {
 29     struct node
 30     {
 31         ll Min; int pos;
 32         node () {}
 33         node (ll Min, int pos) : Min(Min), pos(pos) {}
 34         void init() { Min = INFLL, pos = -1; }
 35         node operator + (const node &other) const
 36         {
 37             node res; res.init();
 38             if (Min < other.Min)
 39             {
 40                 res.Min = Min;
 41                 res.pos = pos;
 42             }
 43             else
 44             {
 45                 res.Min = other.Min;
 46                 res.pos = other.pos;
 47             }
 48             return res;
 49         }
 50     }a[N << 2], res;
 51     void build(int id, int l, int r)
 52     {
 53         a[id].init(); 
 54         if (l == r) return;
 55         int mid = (l + r) >> 1;
 56         build(id << 1, l, mid);
 57         build(id << 1 | 1, mid + 1, r);
 58     }
 59     void update(int id, int l, int r, int pos, ll v)
 60     {
 61         if (l == r) 
 62         {
 63             a[id] = node(v, pos);
 64             return;
 65         }
 66         int mid = (l + r) >> 1;
 67         if (pos <= mid) update(id << 1, l, mid, pos, v);
 68         else update(id << 1 | 1, mid + 1, r, pos, v);
 69         a[id] = a[id << 1] + a[id << 1 | 1];
 70     }
 71     void query(int id, int l, int r, int ql, int qr)
 72     {
 73         if (qr < ql) return;
 74         if (l >= ql && r <= qr)
 75         {
 76             res = res + a[id];
 77             return;
 78         }
 79         int mid = (l + r) >> 1;
 80         if (ql <= mid) query(id << 1, l, mid, ql, qr);
 81         if (qr > mid) query(id << 1 | 1, mid + 1, r, ql, qr);
 82     }
 83 }seg[2];
 84 
 85 int pre[N];
 86 int find(int x) { return pre[x] == 0 ? x : pre[x] = find(pre[x]); }
 87 ll Kruskal()
 88 {
 89     memset(pre, 0, sizeof pre);
 90     sort(edge + 1, edge + 1 + m);
 91     int cnt = 1;
 92     ll res = 0;
 93     for (int i = 1; i <= m; ++i)
 94     {
 95         int u = edge[i].u, v = edge[i].v; ll w = edge[i].w;
 96         int fu = find(u), fv = find(v);
 97         if (fu == fv) continue;
 98         pre[fu] = fv;
 99         ++cnt;
100         res += w;
101         if (cnt == n) return res;
102     }
103     return res;
104 }
105 
106 int main()
107 {
108     while (scanf("%d%lld", &n, &d) != EOF)
109     {    
110         m = 0;
111         for (int i = 1; i <= n; ++i) a[i].scan(i);
112         for (int i = 0; i < 2; ++i) seg[i].build(1, 1, n);
113         sort(a + 1, a + 1 + n);
114         for (int i = 1; i <= n; ++i)
115         {
116             int u = a[i].id, v;
117             for (int j = 0; j < 2; ++j)
118                 seg[j].res.init();
119             seg[0].query(1, 1, n, 1, u - 1);
120             seg[1].query(1, 1, n, u + 1, n);
121             for (int j = 0; j < 2; ++j) if (seg[j].res.pos != -1)
122             {
123                 v = seg[j].res.pos;
124                 edge[++m] = Edge(u, v, a[i].v + 1ll * (j ? -1 : 1) * d * u + seg[j].res.Min);
125             }
126             seg[0].update(1, 1, n, u, a[i].v - d * u);
127             seg[1].update(1, 1, n, u, a[i].v + d * u);
128         }
129         printf("%lld
", Kruskal());
130     }
131     return 0;
132 }

View Code