NCD2019

比较水的一场，智力不足差一题AK。

A：

solver：czq

树状数组+二分

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define pb emplace_back
 6 #define mp make_pair
 7 #define eps 1e-8
 8 #define lson (curpos<<1)
 9 #define rson (curpos<<1|1)
10 /* namespace */
11 using namespace std;
12 /* header end */
13 
14 const int maxn = 2e5 + 10;
15 
16 struct Segment {
17     int st, ed, len;
18 } seg[maxn];
19 
20 struct Info {
21     int isHori, len, slen, sign;
22 } cross[maxn];
23 
24 int t, n, m, tree[maxn], pos[maxn];
25 
26 int lowbit(int x) {
27     return x & -x;
28 }
29 
30 void init() {
31     for (int i = 0; i < 100001; i++) tree[i] = 0;
32 }
33 
34 void add(int x, int k) {
35     for (; x < maxn; x += lowbit(x)) tree[x] += k;
36 }
37 
38 int query(int x) {
39     int ret = 0;
40     for (; x; x -= lowbit(x)) ret += tree[x];
41     return ret;
42 }
43 
44 int cmp(int u, int v) {
45     return mp(cross[u].len, cross[u].isHori) < mp(cross[v].len, cross[v].isHori);
46 }
47 
48 bool check(int len) {
49     init();
50     int cnt = 0;
51     for (int i = 1; i <= n; i++) {
52         if (seg[i].ed - seg[i].st < len * 2) continue;
53         cross[++cnt].slen = seg[i].len, cross[cnt].sign = 1, cross[cnt].isHori = 0, cross[cnt].len = seg[i].st + len;
54         cross[++cnt].slen = seg[i].len, cross[cnt].sign = -1, cross[cnt].isHori = 0, cross[cnt].len = seg[i].ed - len + 1;
55     }
56     for (int i = n + 1; i <= n + m; i++) {
57         if (seg[i].ed - seg[i].st < len * 2) continue;
58         cross[++cnt].slen = seg[i].st + len, cross[cnt].sign = seg[i].ed - len, cross[cnt].isHori = 1, cross[cnt].len = seg[i].len;
59     }
60     for (int i = 1; i <= cnt; i++) pos[i] = i;
61     sort(pos + 1, pos + cnt + 1, cmp);
62     for (int l = 1, r = 1; l <= cnt; l = r) {
63         for (; r <= cnt && cross[pos[l]].len == cross[pos[r]].len; r++) {
64             if (!cross[pos[r]].isHori) add(cross[pos[r]].slen, cross[pos[r]].sign);
65             else if (query(cross[pos[r]].slen - 1) < query(cross[pos[r]].sign)) return true;
66         }
67     }
68     return false;
69 }
70 
71 int main() {
72     scanf("%d", &t);
73     while (t--) {
74         scanf("%d%d", &n, &m);
75         for (int i = 1; i <= n; i++) scanf("%d%d%d", &seg[i].st, &seg[i].ed, &seg[i].len);
76         for (int i = n + 1; i <= n + m; i++) scanf("%d%d%d", &seg[i].st, &seg[i].ed, &seg[i].len);
77         int l = 0, r = 5e4, ans;
78         while (l < r) {
79             int mid = (l + r + 1) / 2;
80             if (check(mid)) l = mid; else r = mid - 1;
81         }
82         ans = l;
83         printf("%d
", ans);
84     }
85     return 0;
86 }

View Code

B：

solver：zyh、czq

tarjan求强连通分量和割边数量，缩点，求树的直径，ans=割边数量-直径

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int SIZE = 100010;
 5 int head[SIZE], ver[SIZE * 2], Next[SIZE * 2];
 6 int dfn[SIZE], low[SIZE];
 7 int n, m, tot, num;
 8 int color[SIZE];
 9 int cnum = 0;
10 stack<int> st;
11 unordered_set<int> rds[SIZE];
12 void add(int x, int y) {
13     ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
14 }
15 
16 void tarjan(int x, int in_edge) {
17     dfn[x] = low[x] = ++num;
18     st.push(x);
19     for (int i = head[x]; i; i = Next[i]) {
20         int y = ver[i];
21         if (!dfn[y]) {
22             tarjan(y, i);
23             low[x] = min(low[x], low[y]);
24         } else if (i != (in_edge ^ 1)) low[x] = min(low[x], dfn[y]);
25     }
26     if (low[x] == dfn[x]) {
27         cnum++;
28         while (!st.empty() && st.top() != x) {
29             color[st.top()] = x;
30             st.pop();
31         }
32         st.pop();
33         color[x] = x;
34     }
35 }
36 int furthest = 0;
37 int furthest_u = 0;
38 void dfs(int u, int f, int d) {
39     if (d > furthest) {
40         furthest_u = u;
41         furthest = d;
42     }
43     for (auto v : rds[u]) {
44         if (v == f) continue;
45         dfs(v, u, d + 1);
46     }
47 }
48 
49 int main() {
50     int T;
51     scanf("%d", &T);
52     while (T--) {
53         scanf("%d%d", &n, &m);
54         memset(head, 0, sizeof(head));
55         memset(dfn, 0, sizeof(dfn));
56         for (int i = 1; i <= n; ++i) rds[i].clear();
57         tot = 1;
58         cnum = 0;
59         num = 0;
60         for (int i = 1; i <= m; i++) {
61             int x, y;
62             scanf("%d%d", &x, &y);
63             add(x, y), add(y, x);
64         }
65         for (int i = 1; i <= n; i++)
66             if (!dfn[i]) tarjan(i, 0);
67         for (int i = 2; i < tot; i += 2) {
68             int u = color[ver[i]];
69             int v = color[ver[i ^ 1]];
70             if (u != v) {
71                 rds[u].insert(v);
72                 rds[v].insert(u);
73             }
74         }
75         furthest = 0;
76         furthest_u = 0;
77         dfs(color[1], 0, 1);
78         dfs(furthest_u, 0, 1);
79         printf("%d
", cnum - furthest);
80     }
81 }

View Code

C：

solver：czq

求LIS长度和个数

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define pb emplace_back
 6 #define mp make_pair
 7 #define eps 1e-8
 8 #define lson (curpos<<1)
 9 #define rson (curpos<<1|1)
10 /* namespace */
11 using namespace std;
12 /* header end */
13 
14 const int maxn = 1010, mod = 1e9 + 7;
15 int t, n, a[maxn], f[maxn], g[maxn];
16 
17 int main() {
18     scanf("%d", &t);
19     while (t--) {
20         int maxx = 0, num = 0;
21         scanf("%d", &n);
22         for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
23         for (int i = 1; i <= n; i++) {
24             f[i] = 1, g[i] = 1;
25             for (int j = 1; j < i; j++)
26                 if (a[j] < a[i]) {
27                     if (f[i] < f[j] + 1) f[i] = f[j] + 1, g[i] = g[j];
28                     else if (f[i] == f[j] + 1) g[i] = (g[i] + g[j]) % mod;
29                 }
30         }
31         for (int i = 1; i <= n; i++)
32             if (maxx < f[i]) maxx = f[i], num = g[i];
33             else if (maxx == f[i]) num = (num + g[i]) % mod;
34         printf("%d %d
", maxx, num);
35     }
36     return 0;
37 }

View Code

D：

solver：czq

白给

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define pb emplace_back
 6 #define mp make_pair
 7 #define eps 1e-8
 8 #define lson (curpos<<1)
 9 #define rson (curpos<<1|1)
10 /* namespace */
11 using namespace std;
12 /* header end */
13 
14 int t;
15 
16 int main() {
17     scanf("%d", &t);
18     while (t--) {
19         int x, y; scanf("%d%d", &x, &y);
20         if (x > y) puts("Bashar");
21         else if (x < y) puts("Hamada");
22         else puts("Iskandar");
23     }
24     return 0;
25 }

View Code

E：

看上去像是数据结构，待补

F：

solver：lzh

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ff first
 4 #define ss second
 5 typedef long long ll;
 6 typedef pair<int, int> pii;
 7 
 8 int main() {
 9     int t;
10     scanf("%d", &t);
11     while (t--) {
12         ll a, b;
13         scanf("%lld%lld", &a, &b);
14         a -= b;
15         ll ans = a / 6;
16         if (a % 6)
17             ans++;
18         printf("%lld
", ans);
19     }
20 }

View Code

G：

solver：lzh

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ff first
 4 #define ss second
 5 typedef long long ll;
 6 typedef pair<int, int> pii;
 7 
 8 const double g = 10.0;
 9 const double pi = acos(-1.0);
10 
11 long double ansl, ansr;
12 int n, v, l, r;
13 void solve45(double x, double y) {
14     ansl = ansr = -1;
15     if (l > 45)
16         return;
17     long double L = l * pi / 180.0, R = min(45, r) * pi / 180.0;
18     long double st = (long double)v * v / g * sin(2.0 * L),
19                 end = (long double)v * v / g * sin(2.0 * R);
20     if (l == 0)
21         st = 0;
22     x = max((long double)x, st), y = min((long double)y, end);
23     if (x > y)
24         return;
25 
26     long double res1 = asin((long double)g * x / v / v);
27     res1 /= 2.0;
28 
29     long double res2 = asin((long double)g * y / v / v);
30     res2 /= 2.0;
31 
32     ansl = max(L, res1), ansr = min(R, res2);
33 }
34 void solve90(double x, double y) {
35     ansl = ansr = -1;
36     if (r < 45)
37         return;
38     long double L = max(45, l) * pi / 180.0, R = r * pi / 180.0;
39     long double st = (long double)v * v / g * sin(2.0 * R),
40                 end = (long double)v * v / g * sin(2.0 * L);
41     if (r == 90)
42         st = 0;
43     x = max((long double)x, st), y = min((long double)y, end);
44     //printf("%lf %lf
", x, y);
45     if (x > y)
46         return;
47 
48     long double res1 = asin((long double)g * y / v / v);
49     res1 = (pi - res1) / 2.0;
50 
51     long double res2 = asin((long double)g * x / v / v);
52     res2 = (pi - res2) / 2.0;
53 
54     ansl = max(L, res1), ansr = min(R, res2);
55 }
56 
57 int main() {
58     int t;
59     scanf("%d", &t);
60     while (t--) {
61         scanf("%d%d%d%d", &n, &v, &l, &r);
62         if (l == r) {
63             long double should = (long double)v * v / g * sin(2.0 * l * pi / 180.0);
64             while (n--) {
65                 double x, y;
66                 scanf("%lf%lf", &x, &y);
67                 if (should - x >= -1e-6 && y - should >= -1e-6)
68                     printf("1.0000
");
69                 else
70                     printf("0.0000
");
71             }
72         } else
73             while (n--) {
74                 double x, y;
75                 scanf("%lf%lf", &x, &y);
76                 double ans = 0;
77 
78                 solve45(x, y);
79                 if (ansl != -1)
80                     ans += ansr - ansl;
81 
82                 solve90(x, y);
83                 if (ansl != -1)
84                     ans += ansr - ansl;
85 
86                 printf("%.4lf
", abs(ans / (pi * (r - l) / 180.0)));
87             }
88     }
89 }

View Code

H：

solver：lzh

并查集

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ff first
 4 #define ss second
 5 typedef long long ll;
 6 typedef pair<int, int> pii;
 7 
 8 int f[100010];
 9 int find(int x) {
10     return f[x] != x ? f[x] = find(f[x]) : f[x];
11 }
12 void add(int x, int y) {
13     int fx = find(x), fy = find(y);
14     if (fx != fy)
15         f[fx] = fy;
16 }
17 int main() {
18     int t;
19     scanf("%d", &t);
20     while (t--) {
21         int n, m, q;
22         scanf("%d%d%d", &n, &m, &q);
23         for (int i = 1; i <= n; i++)
24             f[i] = i;
25         while (m--) {
26             int x, y;
27             scanf("%d%d", &x, &y);
28             add(x, y);
29         }
30         while (q--) {
31             int x, y;
32             scanf("%d%d", &x, &y);
33             if (find(x) == find(y))
34                 printf("1");
35             else
36                 printf("0");
37         }
38         printf("
");
39     }
40 }

View Code

J：

solver：lzh

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ff first
 4 #define ss second
 5 typedef long long ll;
 6 typedef pair<ll, ll> pii;
 7 
 8 ll a[300010], ans[300010];
 9 pii p[100010];
10 int main() {
11     int t;
12     scanf("%d", &t);
13     while (t--) {
14         int n, m;
15         scanf("%d%d", &n, &m);
16         for (int i = 0; i <= 3 * n; i++)
17             a[i] = ans[i] = 0;
18         for (int i = 1; i <= m; i++)
19             scanf("%lld", &p[i].ff), p[i].ff += n - 1;
20         for (int i = 1; i <= m; i++)
21             scanf("%lld", &p[i].ss);
22         for (int i = 1; i <= m; i++) {
23             int l = p[i].ff, r = p[i].ff + p[i].ss;
24             if (l > r)
25                 swap(l, r);
26             r++;
27             a[l]++, a[r]--;
28         }
29         for (int i = 1; i < 3 * n; i++)
30             a[i] += a[i - 1];
31         for (int i = 0; i < 3 * n; i++)
32             ans[i % n] += a[i];
33         pii ansn = { 0, 0 };
34         for (int i = 0; i < n; i++) {
35             if (ans[i] > ansn.ff)
36                 ansn = { ans[i], i };
37         }
38         ansn.ss++;
39         printf("%lld %lld
", ansn.ss, ansn.ff);
40     }
41 }

View Code

K：

solver：lzh

upper_bound一下就行

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ff first
 4 #define ss second
 5 typedef long long ll;
 6 typedef pair<int, int> pii;
 7 
 8 ll a[100010];
 9 int main() {
10     int t;
11     scanf("%d", &t);
12     while (t--) {
13         int n, x;
14         scanf("%d%d", &n, &x);
15         for (int i = 1; i <= n; i++)
16             scanf("%lld", &a[i]), a[i] += a[i - 1];
17         ll ans = 0;
18         for (int i = 1; i <= n; i++) {
19             int r = upper_bound(a + 1, a + 1 + n, a[i - 1] + x - 1) - a - 1;
20             ans += r - i + 1;
21         }
22         printf("%lld
", ans);
23     }
24 }

View Code

L：
solver：czq

白给

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define pb emplace_back
 6 #define mp make_pair
 7 #define eps 1e-8
 8 #define lson (curpos<<1)
 9 #define rson (curpos<<1|1)
10 /* namespace */
11 using namespace std;
12 /* header end */
13 
14 int t, n;
15 
16 int main() {
17     scanf("%d", &t);
18     while (t--) {
19         scanf("%d", &n);
20         vector<int>ans;
21         while (n--) {
22             int x, cnt = 0; scanf("%d", &x);
23             while (x) {
24                 cnt += x & 1;
25                 x >>= 1;
26             }
27             ans.pb(cnt);
28         }
29         for (int i = 0; i < (int)ans.size() - 1; i++) printf("%d ", ans[i]);
30         printf("%d
", ans[(int)ans.size() - 1]);
31     }
32     return 0;
33 }

View Code

M：
solver：lzh

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ff first
 4 #define ss second
 5 typedef long long ll;
 6 typedef pair<int, int> pii;
 7 
 8 ll mod = 1e9 + 7;
 9 ll qp(ll base, ll b) {
10     ll res = 1;
11     while (b) {
12         if (b & 1)
13             res = res * base % mod;
14         base = base * base % mod;
15         b >>= 1;
16     }
17     return res;
18 }
19 
20 int main() {
21     int t;
22     scanf("%d", &t);
23     while (t--) {
24         int b1, p1, b2, p2;
25         scanf("%d%d%d%d", &b1, &p1, &b2, &p2);
26         double tmp = p1 * log(b1) - p2 * log(b2);
27         int l = -1, r = -1;
28         if (!b1)
29             l = 0;
30         else if (!p1)
31             l = 1;
32         if (!b2)
33             r = 0;
34         else if (!p2)
35             r = 1;
36         if (l != -1 && r != -1) {
37             if (l == r)
38                 printf("Lazy
");
39             else if (l < r)
40                 printf("Congrats
");
41             else
42                 printf("HaHa
");
43             continue;
44         }
45 
46         if (fabs(tmp) < 1e-8 && qp(b1, p1) == qp(b2, p2))
47             printf("Lazy
");
48         else if (tmp < 1e-8)
49             printf("Congrats
");
50         else
51             printf("HaHa
");
52     }
53 }

View Code