A. Minimum Integer
签到。
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define ll long long
5 ll l, r, d;
6
7 int main()
8 {
9 int t; scanf("%d", &t);
10 while (t--)
11 {
12 scanf("%lld%lld%lld", &l, &r, &d);
13 if (d < l) printf("%lld\n", d);
14 else printf("%lld\n", ((r / d) + 1) * d);
15 }
16 return 0;
17 }
View Code
B. Accordion
签到。
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define N 5000010
5 char s[N];
6
7 int work()
8 {
9 int l, r, flag, len = strlen(s + 1);
10 flag = false;
11 for (int i = 1; i <= len; ++i)
12 {
13 if (s[i] == '[') flag = true;
14 else if (s[i] == ':' && flag)
15 {
16 l = i;
17 break;
18 }
19 }
20 flag = false;
21 for (int i = len; i >= 1; --i)
22 {
23 if (s[i] == ']') flag = true;
24 else if (s[i] == ':' && flag)
25 {
26 r = i;
27 break;
28 }
29 }
30 if (r <= l) return -1;
31 int res = 4;
32 for (int i = l + 1; i < r; ++i) if (s[i] == '|')
33 ++res;
34 return res;
35 }
36
37 int main()
38 {
39 while (scanf("%s", s + 1) != EOF)
40 printf("%d\n", work());
41 return 0;
42 }
View Code
C. Division and Union
Solved.
题意：
有n个区间，将它分成两个集合，使得每个集合任意出一个区间组成的一对，这对没有交
思路：
按左端点排序，如果存在这样的划分，那么必定一个界限使得当前区间与之前的那个区间没有交，这样的话，后面的区间和之前的区间都不会有交
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define N 100010
5 int t, n, ans[N];
6 struct node
7 {
8 int l, r, id;
9 void scan(int id) { scanf("%d%d", &l, &r); this->id = id; }
10 bool operator < (const node &other) const { return l < other.l || (l == other.l && r < other.r); }
11 }a[N];
12
13 int main()
14 {
15 scanf("%d", &t);
16 while (t--)
17 {
18 scanf("%d", &n);
19 for (int i = 1; i <= n; ++i) a[i].scan(i);
20 sort(a + 1, a + 1 + n);
21 int pos = -1; int maxr = a[1].r;
22 for (int i = 2; i <= n; ++i)
23 {
24 if (a[i].l > maxr)
25 {
26 pos = i;
27 break;
28 }
29 maxr = max(maxr, a[i].r);
30 }
31 if (pos == -1) puts("-1");
32 else
33 {
34 for (int i = 1; i <= n; ++i) ans[a[i].id] = i < pos ? 2 : 1;
35 for (int i = 1; i <= n; ++i) printf("%d%c", ans[i], " \n"[i == n]);
36 }
37 }
38 return 0;
39 }
View Code
D. GCD Counting
Upsolved.
题意：
一棵树中，每个点有权值，找出一条最长的简单路径，使得这个路劲上所有点的点权的gcd > 1
思路：
枚举质因子，再在虚树上dp
质因子很多，有1w多个，但是我们考虑每个质因子对应的集合的总和不会太多，
因为一个数的质因子个数不会太多，2e5一下也就十几个，那么一个数的贡献也就十几个
最后的总和就是O(nlogn)级别的
其实不用建虚树，直接在dfs序上dp就可以了
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define N 200010
5 int n, a[N], res;
6 vector <int> G[N];
7 vector <int> fac[N];
8
9 int fa[N], p[N], pos[N], cnt; int f[2][N];
10 void pre(int u)
11 {
12 p[u] = ++cnt;
13 for (auto v : G[u]) if (v != fa[u])
14 {
15 fa[v] = u;
16 pre(v);
17 }
18 }
19
20 void init()
21 {
22 for (int i = 1; i <= n; ++i) G[i].clear();
23 for (int i = 2; i < N; ++i) fac[i].clear();
24 memset(pos, -1, sizeof pos);
25 res = 0; cnt = 0;
26 }
27
28 int main()
29 {
30 while (scanf("%d", &n) != EOF)
31 {
32 init();
33 for (int i = 1; i <= n; ++i) scanf("%d", a + i);
34 for (int i = 1, u, v; i < n; ++i)
35 {
36 scanf("%d%d", &u, &v);
37 G[u].push_back(v);
38 G[v].push_back(u);
39 }
40 pre(1);
41 for (int i = 1; i <= n; ++i)
42 {
43 int tmp = a[i];
44 int limit = sqrt(tmp);
45 for (int j = 2; j <= limit; ++j)
46 {
47 if (tmp % j == 0)
48 {
49 fac[j].push_back(i);
50 while (tmp % j == 0) tmp /= j;
51 }
52 }
53 if (tmp != 1) fac[tmp].push_back(i);
54 }
55 for (int i = 2; i < N; ++i) if (fac[i].size() >= 1)
56 {
57 sort(fac[i].begin(), fac[i].end(), [](int x, int y) { return p[x] > p[y]; });
58 int len = fac[i].size();
59 for (int j = 0; j < len; ++j) for (int o = 0; o < 2; ++o) f[o][j] = 0;
60 for (int j = 0; j < len; ++j) pos[fac[i][j]] = j;
61 for (int j = 0, u, v; j < len; ++j)
62 {
63 v = fac[i][j];
64 res = max(res, f[0][j] + f[1][j] + 1);
65 if (pos[fa[v]] != -1)
66 {
67 int id = pos[fa[v]];
68 if (f[0][j] + 1 >= f[0][id])
69 {
70 f[1][id] = f[0][id];
71 f[0][id] = f[0][j] + 1;
72 }
73 else if (f[0][j] + 1 >= f[1][id])
74 {
75 f[1][id] = f[0][j] + 1;
76 }
77 }
78 }
79 for (int j = 0; j < len; ++j) pos[fac[i][j]] = -1;
80 }
81 printf("%d\n", res);
82 }
83 return 0;
84 }
View Code
E. Polycarp's New Job
签到.
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define N 500010
5 int n, x, y, l, r; char op[10];
6
7 int main()
8 {
9 l = 0, r = 0;
10 scanf("%d", &n);
11 while (n--)
12 {
13 scanf("%s%d%d", op, &x, &y);
14 if (x > y) swap(x, y);
15 if (op[0] == '+')
16 {
17 l = max(l, x);
18 r = max(r, y);
19 }
20 else
21 {
22 puts(l <= x && r <= y ? "YES" : "NO");
23 }
24 }
25 return 0;
26 }
View Code