2019 HDOJ Multi-University Training Contest Stage 10(杭电多校)

最后一场多校打得一般般。

题目链接：http://acm.hdu.edu.cn/contests/contest_show.php?cid=857

C：

递推概率水题。

 1 /* Codeforces Contest 2019_mutc_10
 2  * Problem C
 3  * Au: SJoshua
 4  */
 5 #include <cstdio>
 6 #include <vector>
 7 #include <string>
 8 #include <iostream>
 9 #include <algorithm>
10 #include <functional>
11 
12 using namespace std;
13 
14 const double eps = 1e-9;
15 
16 int main(void) {
17     int T;
18     scanf("%d", &T);
19     while (T--) {
20         int n;
21         scanf("%d", &n);
22         vector <double> p(n);
23         for (int i = 0; i < n; i++)
24             scanf("%lf", &p[i]);
25         sort(p.begin(), p.end(), greater <double> ());
26         double a = 1.0, b = 0.0, c = 0.0;
27         for (int i = 0; i < n; i++) {
28             double nxt = b * (1 - p[i]) + a * p[i]; // P of pick current gift
29             if (nxt - b > eps) {
30                 a = a * (1 - p[i]);
31                 b = nxt;
32             }
33         }
34         printf("%.9f
", b);
35     }
36     return 0;
37 }

View Code

E：

对每个数对以x为关键字从小到大排序。枚举所有x，对于x_i，找出最近的y_i。用数据结构维护即可。复杂度O(nlogn)。

 1 /* Codeforces Contest 2019_mutc_10
 2  * Problem E
 3  * Au: SJoshua
 4  */
 5 #include <set>
 6 #include <map>
 7 #include <cstdio>
 8 #include <vector>
 9 #include <string>
10 #include <climits>
11 #include <iostream>
12 #include <algorithm>
13 
14 using namespace std;
15 
16 struct info {
17     long long int x, y;
18 };
19 
20 int main(void) {
21     int T;
22     scanf("%d", &T);
23     while (T--) {
24         int n;
25         scanf("%d", &n);
26         vector <info> data(n);
27         map <long long int, int> cnt; // counter of y
28         set <long long int> usedY;
29         for (int i = 0; i < n; i++) {
30             scanf("%lld %lld", &data[i].x, &data[i].y);
31             cnt[data[i].y]++;
32         }
33         sort(data.begin(), data.end(), [](info & a, info & b) -> bool {
34             return a.x < b.x; // sort by x
35         });
36         long long int ans = LONG_LONG_MAX;
37         for (int i = 0; i < n; i++) { // enum each number pair
38             if (!(--cnt[data[i].y])) { // if y remain one time
39                 cnt.erase(data[i].y);
40             }
41             long long int top = 0;
42             if (!cnt.empty()) { // top is the largest y
43                 top = cnt.rbegin()->first;
44                 ans = min(ans, abs(top - data[i].x)); // ans up limit
45             }
46             auto it = usedY.lower_bound(data[i].x);
47             if (it != usedY.end()) {
48                 ans = min(ans, abs(max(top, *it) - data[i].x));
49             }
50             if (it != usedY.begin()) {
51                 advance(it, -1);
52                 ans = min(ans, abs(max(top, *it) - data[i].x));
53             }
54             usedY.insert(data[i].y);
55         }
56         printf("%lld
", ans);
57     }
58     return 0;
59 }

View Code

I：

BFS水题。

 1 /* Codeforces Contest 2019_mutc_10
 2  * Problem I
 3  * Au: SJoshua
 4  */
 5 #include <queue>
 6 #include <cstdio>
 7 #include <vector>
 8 #include <string>
 9 #include <iostream>
10 
11 using namespace std;
12 
13 bool board[2002][2002];
14 int n, m, q;
15 
16 const int movement[4][2] = {
17     {0, 1}, {0, -1}, {1, 0}, {-1, 0}
18 };
19 
20 struct pos {
21     int x, y;
22 };
23 
24 int solve(int x, int y) {
25     int ans = 0;
26     if (board[x][y]) {
27         queue <pos> q;
28         q.push({x, y});
29         while (!q.empty()) {
30             auto t = q.front();
31             q.pop();
32             if (!board[t.x][t.y]) {
33                 continue;
34             }
35             ans++;
36             board[t.x][t.y] = 0;
37             for (int i = 0; i < 4; i++) {
38                 int nx = t.x + movement[i][0], ny = t.y + movement[i][1];
39                 if (1 <= nx && nx <= n && 1 <= ny && ny <= m && board[nx][ny]) {
40                     if ((!board[nx + 1][ny] || !board[nx - 1][ny]) && (!board[nx][ny - 1] || !board[nx][ny + 1])) {
41                         q.push({nx, ny});
42                     }
43                 }
44             }
45         }
46     }
47     return ans;
48 }
49 
50 int main(void) {
51     int T;
52     scanf("%d", &T);
53     while (T--) {
54         scanf("%d %d %d", &n, &m, &q);
55         for (int i = 0; i <= n + 1; i++) {
56             for (int j = 0; j <= m + 1; j++) {
57                 board[i][j] = true;
58             }
59         }
60         while (q--) {
61             int x, y;
62             scanf("%d %d", &x, &y);
63             printf("%d
", solve(x, y));
64         }
65     }
66     return 0;
67 }

View Code

K：

做法略像之前牛客多校第四场C。对于每个a[i]，计算出在满足区间内元素unique的前提下，往左往右能到的最大区间。

考虑启发式分治，对于当前区间，找到最大值所在位置并记为mid并看mid是更靠左还是靠右。若更靠左，则枚举左区间内的值作为端点，计算对右区间的贡献；反之同理。

  1 // 数符合条件的区间个数，满足区间max-k<=区间长度
  2 /* basic header */
  3 #include <bits/stdc++.h>
  4 /* define */
  5 #define ll long long
  6 #define dou double
  7 #define pb emplace_back
  8 #define mp make_pair
  9 #define sot(a,b) sort(a+1,a+1+b)
 10 #define rep1(i,a,b) for(int i=a;i<=b;++i)
 11 #define rep0(i,a,b) for(int i=a;i<b;++i)
 12 #define eps 1e-8
 13 #define int_inf 0x3f3f3f3f
 14 #define ll_inf 0x7f7f7f7f7f7f7f7f
 15 #define lson (curpos<<1)
 16 #define rson (curpos<<1|1)
 17 /* namespace */
 18 using namespace std;
 19 /* header end */
 20 
 21 const int maxn = 3e5 + 10;
 22 
 23 struct Node {
 24     int maxx, pos;
 25 } segt[maxn << 2];
 26 int n, k, a[maxn], vis[maxn], pre[maxn], suf[maxn];
 27 
 28 void maintain(int curpos) {
 29     segt[curpos].maxx = max(segt[lson].maxx, segt[rson].maxx);
 30     segt[curpos].pos = segt[lson].maxx > segt[rson].maxx ? segt[lson].pos : segt[rson].pos;
 31 }
 32 
 33 void build(int curpos, int curl, int curr) {
 34     if (curl == curr) {
 35         segt[curpos].maxx = a[curl];
 36         segt[curpos].pos = curl;
 37         return;
 38     }
 39     int mid = curl + curr >> 1;
 40     build(lson, curl, mid); build(rson, mid + 1, curr);
 41     maintain(curpos);
 42 }
 43 
 44 int query(int curpos, int curl, int curr, int ql, int qr) {
 45     if (ql <= curl && curr <= qr)
 46         return segt[curpos].pos;
 47     int mid = curl + curr >> 1, lpos = -1, rpos = -1;
 48     if (ql <= mid) lpos = query(lson, curl, mid, ql, qr);
 49     if (mid < qr) rpos = query(rson, mid + 1, curr, ql, qr);
 50     if (lpos == -1) return rpos;
 51     else if (rpos == -1) return lpos;
 52     else return a[lpos] > a[rpos] ? lpos : rpos;
 53 }
 54 
 55 void query(int l, int r, ll &ans) {
 56     if (l > r) return;
 57     int mid = query(1, 1, n, l, r), len = max(1, a[mid] - k); // mid是区间[l,r]最大值的位置，len是最小长度
 58     if (mid - l <= r - mid) { // 最大值位置更靠左时，枚举最大值左侧元素作为区间左端点
 59         for (int i = l; i <= mid; i++) { // 枚举左端点到mid的每个位置，暴力计算对右区间的贡献
 60             int L = max(mid, i + len - 1), R = min(pre[i], r);
 61             ans += max(0, R - L + 1);
 62         }
 63     } else {
 64         for (int i = mid; i <= r; i++) {
 65             int L = max(suf[i], l), R = min(mid, i - len + 1);
 66             ans += max(0, R - L + 1);
 67         }
 68     }
 69     query(l, mid - 1, ans); query(mid + 1, r, ans);
 70 }
 71 
 72 int main() {
 73     int t; scanf("%d", &t);
 74     while (t--) {
 75         scanf("%d%d", &n, &k);
 76         for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
 77         build(1, 1, n);
 78         int pos = 0;
 79         for (int i = 1; i <= n; i++) { // 计算从当前位置开始，向右延伸最远到什么位置，区间内的元素依然unique
 80             while (pos < n && !vis[a[pos + 1]]) { // 不用set可以少一个log
 81                 pos++;
 82                 vis[a[pos]] = true;
 83             }
 84             pre[i] = pos;
 85             vis[a[i]] = false;
 86         }
 87         pos = n + 1;
 88         for (int i = n; i >= 1; i--) {
 89             while (pos > 1 && !vis[a[pos - 1]]) {
 90                 pos--;
 91                 vis[a[pos]] = true;
 92             }
 93             suf[i] = pos;
 94             vis[a[i]] = false;
 95         }
 96         ll ans = 0;
 97         query(1, n, ans);
 98         printf("%lld
", ans);
 99     }
100     return 0;
101 }

View Code