ZOJ Monthly, March 2018 Solution
分类:
IT文章
•
2025-01-09 09:00:56
A - Easy Number Game
水。
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define ll long long
5 #define N 100010
6 ll arr[N];
7 int n, m;
8
9 int main()
10 {
11 int t; scanf("%d", &t);
12 while (t--)
13 {
14 scanf("%d%d", &n, &m);
15 for (int i = 1; i <= n; ++i) scanf("%lld", arr + i);
16 sort(arr + 1, arr + 1 + n);
17 ll res = 0;
18 for (int i = 1; i <= m; ++i)
19 res += arr[i] * arr[2 * m - i + 1];
20 printf("%lld
", res);
21 }
22 return 0;
23 }
View Code
B - Lucky Man
题意：判断大数开根后的奇偶性
思路：牛顿迭代法
![]()
1 import java.io.BufferedInputStream;
2 import java.util.Scanner;
3 import java.math.*;
4
5 public class Main {
6
7 public static void main(String[] args) {
8 Scanner in = new Scanner(new BufferedInputStream(System.in));
9 int t = in.nextInt();
10 BigInteger a, x, two; String n;
11 two = BigInteger.valueOf(2);
12 while (t-- != 0)
13 {
14 n = in.next();
15 a = new BigInteger(n);
16 x = new BigInteger(n.substring(0, n.length() / 2 + 1));
17 while (a.compareTo(x.multiply(x)) < 0)
18 x = x.add(a.divide(x)).divide(two);
19 if (x.mod(two).compareTo(BigInteger.ZERO) == 0) System.out.println(0);
20 else System.out.println(1);
21 }
22 in.close();
23 }
24 }
View Code
C - Travel along the Line
题意：一维坐标系中，刚开始位于原点，有$frac{1}{4}$的概率 坐标 +1 和 -1 有$frac {1}{2} 的概率 不动$ 求在第n秒的时候恰好到达第m个位置的概率
思路：考虑把一个0拆成两个0，变成四种操作，这样四种操作是等概率的，那么所有的可能性就是 $4^n$ 再考虑符合条件的方案数
可以考虑将m通过坐标变换转化成正的，那么一个满足题意的操作序列肯定是 1 的个数 减去 -1的 个数 恰好为m
那么我们只需要枚举1的个数，排列组合一下即可
16说 假如用a 表示 1 的个数 b 表示 -1 的个数 c 表示 0的个数
那么有$frac {n!} {a! cdot b! cdot c!}$ 但是这里要考虑 多乘上$2^c$ 因为每个0都有两种选择 ，可以是$0_1 或者 是 0_2$
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define ll long long
5 #define N 100010
6 ll MOD = (ll)1e9 +7;
7
8 ll fac[N], Bit[N];
9 ll qmod(ll base, ll n)
10 {
11 ll res = 1;
12 while (n)
13 {
14 if (n & 1) res = res * base % MOD;
15 base = base * base % MOD;
16 n >>= 1;
17 }
18 return res;
19 }
20
21 void Init()
22 {
23 fac[0] = 1;
24 Bit[0] = 1;
25 for (int i = 1; i < N; ++i) fac[i] = fac[i - 1] * i % MOD;
26 for (int i = 1; i < N; ++i) Bit[i] = Bit[i - 1] * 2 % MOD;
27 }
28
29 int n, m;
30
31 int main()
32 {
33 Init();
34 int t; scanf("%d", &t);
35 while (t--)
36 {
37 scanf("%d%d", &n, &m);
38 if (m < 0) m = -m;
39 ll p = 0, q = qmod(4, n);
40 for (int i = 0; 2 * i + m <= n; ++i)
41 p = (p + (fac[n] * qmod(fac[i], MOD - 2) %MOD * qmod(fac[i + m], MOD - 2) % MOD * qmod(fac[n - 2 * i - m], MOD - 2) % MOD * Bit[n - 2 * i - m] % MOD)) % MOD;
42 ll res = p * qmod(q, MOD - 2) % MOD;
43 printf("%lld
", res);
44 }
45 return 0;
46 }
View Code
D - Machine Learning on a Tree
留坑。
E - Yet Another Tree Query Problem
题意：每次询问$[l, r]$ 区间内所有点所在的连通块个数
思路：先预处理l 为 1 r 为 1 ->n 的答案 考虑删去一个点对后面答案的影响
将一个点的所有孩子和父亲中，按编号排序
比如说 点1 连出去的边有 4, 10, 20
那么 对于右界为 2-3 的 连通块个数少一
右界为5 - 9 的 连通块个数不变
右界为 11 - 19 的 连通块个数加1
BIT区间更新即可
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define N 200010
5 #define pii pair <int, int>
6 int t, n, q;
7 vector <int> G[N];
8 vector <pii> que[N];
9 int base[N], ans[N];
10
11 struct BIT
12 {
13 int a[N];
14 void init() { memset(a, 0, sizeof a); }
15 void update(int x, int val) { for (; x <= n; x += x & -x) a[x] += val; }
16 void update(int l, int r, int val)
17 {
18 if (r < l) return;
19 update(l, val);
20 update(r + 1, -val);
21 }
22 int query(int x)
23 {
24 int res = 0;
25 for (; x; x -= x & -x)
26 res += a[x];
27 return res;
28 }
29
30 }bit;
31
32 void Run()
33 {
34 scanf("%d", &t);
35 while (t--)
36 {
37 for (int i = 1; i <= n; ++i) G[i].clear(), que[i].clear();
38 bit.init();
39 scanf("%d%d", &n, &q);
40 for (int i = 1, u, v; i < n; ++i)
41 {
42 scanf("%d%d", &u, &v);
43 G[u].push_back(v);
44 G[v].push_back(u);
45 }
46 for (int i = 1, l, r; i <= q; ++i)
47 {
48 scanf("%d%d", &l, &r);
49 que[l].emplace_back(r, i);
50 }
51 for (int i = 1; i <= n; ++i)
52 {
53 int tmp = 1;
54 sort(G[i].begin(), G[i].end());
55 for (auto v : G[i]) if (v < i)
56 --tmp;
57 base[i] = base[i - 1] + tmp;
58 }
59 for (int i = 1; i <= n; ++i)
60 {
61 for (auto it : que[i])
62 ans[it.second] = base[it.first] + bit.query(it.first);
63 G[i].push_back(n + 1);
64 int pre = i + 1;
65 for (int j = 0, len = G[i].size(), add = -1; j < len; ++j)
66 {
67 int v = G[i][j];
68 if (v < i) continue;
69 bit.update(pre, v - 1, add);
70 pre = v; ++add;
71 }
72 }
73 for (int i = 1; i <= q; ++i) printf("%d
", ans[i]);
74 }
75 }
76
77 int main()
78 {
79 #ifdef LOCAL
80 freopen("Test.in", "r", stdin);
81 #endif
82
83 Run();
84 return 0;
85
86 }
View Code
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define N 100010
5 #define ll long long
6 const ll MOD = 99971;
7 int t, n, q;
8 ll arr[N];
9
10 struct SEG
11 {
12 ll a[N << 2][49], tmp[49];
13 int lazy[N << 2];
14 void init() { memset(a, 0, sizeof a); }
15 void pushup(int id)
16 {
17 for (int i = 0; i < 48; ++i)
18 a[id][i] = (a[id << 1][(i + lazy[id << 1]) % 48] + a[id << 1 | 1][(i + lazy[id << 1 | 1]) % 48]) % MOD;
19 }
20 void pushdown(int id)
21 {
22 if (!lazy[id]) return;
23 lazy[id << 1] = (lazy[id << 1] + lazy[id]) % 48;
24 lazy[id << 1 | 1] = (lazy[id << 1 | 1] + lazy[id]) % 48;
25 for (int i = 0; i < 48; ++i) tmp[i] = a[id][(i + lazy[id]) % 48];
26 memcpy(a[id], tmp, sizeof tmp);
27 lazy[id] = 0;
28 }
29 void build(int id, int l, int r)
30 {
31 lazy[id] = 0;
32 if (l == r)
33 {
34 a[id][0] = arr[l];
35 for (int i = 1; i < 48; ++i)
36 a[id][i] = a[id][i - 1] * a[id][i - 1] % MOD * a[id][i - 1] % MOD;
37 return;
38 }
39 int mid = (l + r) >> 1;
40 build(id << 1, l, mid);
41 build(id << 1 | 1, mid + 1, r);
42 pushup(id);
43 }
44 void update(int id, int l, int r, int ql, int qr, int val)
45 {
46 if (l >= ql && r <= qr)
47 {
48 lazy[id] = (lazy[id] + val) % 48;
49 return;
50 }
51 pushdown(id);
52 int mid = (l + r) >> 1;
53 if (ql <= mid) update(id << 1, l, mid, ql, qr, val);
54 if (qr > mid) update(id << 1 | 1, mid + 1, r, ql, qr, val);
55 pushup(id);
56 }
57 ll query(int id, int l, int r, int ql, int qr)
58 {
59 if (l >= ql && r <= qr) return a[id][lazy[id]];
60 pushdown(id);
61 int mid = (l + r) >> 1;
62 ll res = 0;
63 if (ql <= mid) res = (res + query(id << 1, l, mid, ql, qr)) % MOD;
64 if (qr > mid) res = (res + query(id << 1 | 1, mid + 1, r, ql, qr)) % MOD;
65 //pushup(id);
66 return res;
67 }
68 }seg;
69
70 void Run()
71 {
72 scanf("%d", &t);
73 while (t--)
74 {
75 scanf("%d%d", &n, &q);
76 for (int i = 1; i <= n; ++i) scanf("%lld", arr + i), arr[i] %= MOD;
77 seg.build(1, 1, n);
78 for (int i = 1, op, l, r; i <= q; ++i)
79 {
80 scanf("%d%d%d", &op, &l, &r);
81 if (op == 1) seg.update(1, 1, n, l, r, 1);
82 else printf("%lld
", seg.query(1, 1, n, l, r));
83 }
84 }
85 }
86
87 int main()
88 {
89 #ifdef LOCAL
90 freopen("Test.in", "r", stdin);
91 #endif
92
93 Run();
94 return 0;
95
96 }
