Lyft Level 5 Challenge 2018

Lyft Level 5 Challenge 2018 - Final Round (Open Div. 2) (前三题题解）

这场比赛好毒瘤哇，看第四题好像是中国人出的，怕不是dllxl出的。

第四道什么鬼，互动题不说，花了四十五分钟看懂题目，都想砸电脑了。然后发现不会，互动题从来没做过。

不过这次新号上蓝名了（我才不告诉你我以前的号是灰名），还是挺高兴的，而且t神这场比赛又成第一了。

比赛传送门：http://codeforces.com/contest/1075

A. The King's Race

题意：有一黑一白两个旗子，白的在(1, 1)上，黑的在(n, n)上。每次可以将旗子移动到周围一圈这八个位置，给你三个数n, a, b(1 <= a, b <= n <= 10 ^ 18)，让你求那个旗子可以先到达(a, b)。注：先移动的是白棋。

只要求出黑棋到(a, b)和白棋到(a, b)的步数，如果白棋小于等于（因为白棋动下）黑棋的，那么就是白棋，否则就是黑棋。

至于求所需的步数，就是max(行 - a, 列 - b)。

代码如下

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <vector>
 6 #define rep(x, l, r) for(int x = (int)l; x <= (int)r; x++)
 7 #define repd(x, r, l) for(int x = (int)r; x >= (int)l; x--)
 8 #define clr(x,y) memset(x, y, sizeof(x))
 9 #define all(x) begin(x), end(x)
10 #define pb push_back
11 #define mp make_pair
12 #define MAXN    
13 #define fi first
14 #define se second
15 #define SZ(x) ((int)x.size())
16 using namespace std;
17 typedef long long LL;
18 typedef vector<int> vi;
19 typedef pair<int, int> pii;
20 const int INF = 1 << 30;
21 const int p = 10000007;
22 //head by DYH
23 
24 LL judge(LL X0, LL Y0, LL X1, LL Y1){
25     return max(abs(X0 - X1), abs(Y0 - Y1));
26 }
27 
28 int main(){
29     LL n, a, b;
30     scanf("%I64d%I64d%I64d", &n, &a, &b);
31     LL res1 = judge(1, 1, a, b), res2 = judge(n, n, a, b);
32     if(res1 <= res2) puts("White");
33     else puts("Black");
34     return 0;
35 }

View Code Problem-A

B. Taxi drivers and Lyft

题意：一条路上有n个乘客和m个出租车司机，给你他们的坐标（增序且保证没有坐标相同），每个乘客会向最近的一个司机发送订单，假如有两个最近的司机，发给坐标小的。求每个司机会收到多少个订单。

用数组res[i].first记录第i个人（乘客）最近的司机距离，res[i].second记录下标（因为有序，只要下标小坐标也一定小），即会收到订单的司机。

只要对于每个司机，向前后分别找所有的乘客j，更新res[j]，遇到别的司机就停止。最后再记录每个司机收到的订单。

代码如下

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <vector>
 6 #define rep(x, l, r) for(int x = (int)l; x <= (int)r; x++)
 7 #define repd(x, r, l) for(int x = (int)r; x >= (int)l; x--)
 8 #define clr(x,y) memset(x, y, sizeof(x))
 9 #define all(x) begin(x), end(x)
10 #define pb push_back
11 #define mp make_pair
12 #define MAXN 200005
13 #define fi first
14 #define se second
15 #define SZ(x) ((int)x.size())
16 using namespace std;
17 typedef long long LL;
18 typedef vector<int> vi;
19 typedef pair<int, int> pii;
20 const int INF = 1 << 30;
21 const int p = 10000007;
22 //head by DYH
23 
24 pii res[MAXN];
25 int a[MAXN], ans[MAXN];
26 bool flag[MAXN];
27 
28 int main(){
29     int n, m;
30     scanf("%d%d", &n, &m);
31     rep(i, 1, n + m){
32         scanf("%d", &a[i]);
33         res[i] = mp(INF, INF);
34     }
35     rep(i, 1, n + m) scanf("%d", &flag[i]);
36     rep(i, 1, n + m){
37         if(flag[i]){
38             repd(j, i - 1, 1){
39                 if(flag[j]) break;
40                 res[j] = min(res[j], mp(a[i] - a[j], i));
41             }
42             rep(j, i + 1, n + m){
43                 if(flag[j]) break;
44                 res[j] = min(res[j], mp(a[j] - a[i], i));
45             }
46         }
47     }
48     rep(i, 1, n + m)
49         if(!flag[i]) ans[res[i].se]++;
50     rep(i, 1, n + m)
51         if(flag[i]) printf("%d ", ans[i]);
52     puts("");
53     return 0;
54 }

View Code Problem-B

C. The Tower is Going Home

题意：在一个(10 ^ 9) * (10 ^ 9)棋盘的(1, 1)有一个车，需要走到最上面一行。现在有n个竖行障碍和m个横行障碍，竖行障碍会挡住所有从x[i]列到x[i] + 1列的路（两个竖行障碍不会在同一地方），横行障碍会挡住第x1[i]到x2[i]列从y[i]到y[i] + 1的路（两个横行障碍不会有任何接触），现在问你最少去掉多少障碍使得车能到达。

因为横行障碍不会相交，且竖行障碍都是整行禁止通行的，那么只要x1[i]不是1那么这个障碍i就一定不用删去，障碍i要删去仅当x2[i] >= x[j]都被删除（j为余下的最左边的竖行障碍。

因为竖行障碍是整行都禁止通行且起点再(1, 1)，那么如果删掉第i竖行障碍，所有x[j] < x[i] 的障碍j都要删掉，不然障碍i删掉和不删掉一样。

我们只要将a[i]排个序，记录所有x1[i] = 1的障碍i的右端x2[i]并排序。然后枚举i表示1～i的竖行障碍被删除，然后可以求得当前情况下要删掉的横行障碍（我用了二分）。

注：以上的最好手动模拟。

代码如下

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <vector>
 6 #define rep(x, l, r) for(int x = (int)l; x <= (int)r; x++)
 7 #define repd(x, r, l) for(int x = (int)r; x >= (int)l; x--)
 8 #define clr(x,y) memset(x, y, sizeof(x))
 9 #define all(x) begin(x), end(x)
10 #define pb push_back
11 #define mp make_pair
12 #define MAXN 100005
13 #define fi first
14 #define se second
15 #define SZ(x) ((int)x.size())
16 using namespace std;
17 typedef long long LL;
18 typedef vector<int> vi;
19 typedef pair<int, int> pii;
20 const int INF = 1e9;
21 const int p = 10000007;
22 //head by DYH
23 
24 int a[MAXN], b[MAXN];
25 
26 int main(){
27     int n, m;
28     scanf("%d%d", &n, &m);
29     rep(i, 1, n) scanf("%d", &a[i]);
30     sort(a + 1, a + n + 1);
31     a[n + 1] = INF;
32     int cnt = 0;
33     rep(i, 1, m){
34         int X0, X1, y;
35         scanf("%d%d%d", &X0, &X1, &y);
36         if(X0 == 1) b[++cnt] = X1;
37     }
38     sort(b + 1, b + cnt + 1);
39     int ans = INF;
40     rep(i, 1, n + 1){
41         int id = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
42         ans = min(ans, i + cnt - id);
43     }
44     printf("%d
", ans);
45     return 0;
46 }

View Code Problem-C

嗯，写完了。才三道，主要是互动题不大会做。完成时间：2018-11-05 14:27:01