|
? A. Got Any Grapes? 簽. 
1 #include <bits/stdc .h>
2 using namespace std;
3
4 int x, y, z, a, b, c;
5 bool solve()
6 {
7 if (a < x) return false;
8 a -= x;
9 b = a;
10 if (b < y) return false;
11 b -= y;
12 c = b;
13 if (c < z) return false;
14 return true;
15 }
16
17 int main()
18 {
19 while (scanf("%d%d%d", &x, &y, &z) != EOF)
20 {
21 scanf("%d%d%d", &a, &b, &c);
22 puts(solve() ? "YES" : "NO");
23 }
24 return 0;
25 }
View Code
? ? B. Yet Another Array Partitioning Task Solved. 題意： 有一個序列, 要求把這個序列分成$k段，每段最少m個$ 要求每一段中的前$m$大的數(shù)加起來的總和最大 輸出總和以及分配的方案 注意這里分的序列是連續(xù)的 思路： 我們考慮答案的總和就是所有數(shù)排序后的前$m * k大之和$ $我們考慮一個不屬于前m * k大的數(shù)$ $首先我們考慮每一段中都有m個數(shù)$ $并且這m個數(shù)屬于前m * k大的$ $那么剩下的數(shù)，無論分到哪個組，都不會被統(tǒng)計進答案$ $那么只要貪心選取，標記哪些數(shù)是前m * k大$ $每個組只要夠了m個這樣的數(shù)，就開啟下一組$
1 #include <bits/stdc .h>
2 using namespace std;
3
4 #define ll long long
5 #define N 200010
6 int n, m, k;
7 int vis[N];
8 struct node
9 {
10 int a, id;
11 void scan(int id)
12 {
13 this->id = id;
14 scanf("%d", &a);
15 }
16 bool operator < (const node &other) const
17 {
18 return a > other.a;
19 }
20 }a[N];
21
22 int main()
23 {
24 while (scanf("%d%d%d", &n, &m, &k) != EOF)
25 {
26 memset(vis, 0, sizeof vis);
27 for (int i = 1; i <= n; i) a[i].scan(i);
28 ll res = 0;
29 sort(a 1, a 1 n);
30 for (int i = 1; i <= m * k; i) res = a[i].a, vis[a[i].id] = 1;
31 vector <int> vec;
32 for (int i = 1, tmp = 0; i <= n; i)
33 {
34 tmp = vis[i];
35 if (tmp == m)
36 {
37 vec.push_back(i);
38 tmp = 0;
39 }
40 }
41 printf("%lld\n", res);
42 for (int i = 0; i < k - 1; i)
43 printf("%d%c", vec[i], " \n"[i == k - 2]);
44 }
45 return 0;
46 }
View Code
? ? C. Trailing Loves (or L'oeufs?) Solved. 題意： 求$n!在b進制下末尾的0的個數(shù)$ 思路： 我們考慮什么時候會產(chǎn)生$0$ 對于$b進制，我們知道滿b進1，末尾添一個0$ $那么我們只需要知道n!中所有數(shù)因數(shù)分解之后可以湊成多少個b末尾就是多少個0$ 我們令$b = p_1^{t_1} \cdot p_2^{t_2} \cdots p_n^{t_n}$ 那么求出$n!中有多少個 p_1^{t_1}, p_2^{t_2} \cdots p_n^{t_n} 取Min即可$
1 #include <bits/stdc .h>
2 using namespace std;
3
4 #define ll unsigned long long
5 #define pll pair <ll, ll>
6 ll n, b;
7
8 ll f()
9 {
10 ll res = (ll)1e18;
11 ll limit = sqrt(b);
12 vector <pll> vec;
13 for (ll i = 2; i <= limit; i) if (b % i == 0)
14 {
15 pll tmp = pll(i, 0);
16 while (b % i == 0)
17 {
18 tmp.second;
19 b /= i;
20 }
21 vec.push_back(tmp);
22 }
23 if (b != 1)
24 vec.push_back(pll(b, 1));
25 for (auto it : vec)
26 {
27 ll tmp = 0;
28 for (ll i = it.first; ; i *= it.first)
29 {
30 tmp = n / i;
31 if (i > n / it.first 10) break;
32 }
33 res = min(res, tmp / it.second);
34 }
35 return res;
36 }
37
38 int main()
39 {
40 while (scanf("%llu%llu", &n, &b) != EOF)
41 {
42 printf("%llu\n", f());
43 }
44 return 0;
45 }
View Code
? ? D. Flood Fill Upsolved. 題意： $有一行不同顏色的球$ $首先可以選擇一個主球，相同的球會合并$ $在接下來的每一步，我們都可以規(guī)定主球為任一顏色$ $和它相鄰的并且顏色和它相同的都會合并$ $求所有球合并完的最少步驟$ 思路： ? $DP解法$ $dp[l][r][0/1] 表示 l->r 這個區(qū)間合并完后狀態(tài)為0/1的最小步數(shù)$ $0表示合并后的顏色和c[l]相同，1表示合并后的顏色和c[1]相同$ $那么dp[l][r][0/1] 可以轉(zhuǎn)移到 dp[l - 1][r][0]$ $dp[l][r][0/1] 可以轉(zhuǎn)移到 dp[l][r 1][1]$
1 #include <bits/stdc .h>
2 using namespace std;
3
4 #define N 5010
5 int n, c[N];
6 int f[N][N][2];
7
8 int dp(int l, int r, int sta)
9 {
10 if (l >= r)
11 return 0;
12 if (f[l][r][sta] != -1)
13 return f[l][r][sta];
14 int res = (int)1e8;
15 if (sta == 0)
16 {
17 res = min(res, dp(l 1, r, 0) (c[l] != c[l 1]));
18 res = min(res, dp(l 1, r, 1) (c[l] != c[r]));
19 }
20 else
21 {
22 res = min(res, dp(l, r - 1, 0) (c[r] != c[l]));
23 res = min(res, dp(l, r - 1, 1) (c[r] != c[r - 1]));
24 }
25 return f[l][r][sta] = res;
26 }
27
28 int main()
29 {
30 while (scanf("%d", &n) != EOF)
31 {
32 for (int i = 1; i <= n; i) scanf("%d", c i);
33 memset(f, -1, sizeof f);
34 printf("%d\n", min(dp(1, n, 0), dp(1, n, 1)));
35 }
36 return 0;
37 }
View Code
? $LCS解法$ 我們假設$主球的位置在x$ $那么x把區(qū)間分成左右兩部分$ $每次可以選擇左邊一個合并或者右邊一個合并$ $但是更優(yōu)的是 左邊和右邊的相同，那么一步就可以將他們都合并$ $我們就是要找這樣相同的$ 假如這樣的東西 $abcxcba$ $x代表主球，相同字母代表相同數(shù)字$ $那么我們只需要三次就可以合并完$ $我們要找的就是這種相同的越多越好，并且是有順序可以接在一起的$ $那么把字符串翻轉(zhuǎn)求LCS就可以$ $要注意除2 ，因為多算了一次$
1 #include <bits/stdc .h>
2 using namespace std;
3
4 #define N 5010
5 int n, m, a[N], b[N];
6 int f[N][N];
7
8 int main()
9 {
10 while (scanf("%d", &n) != EOF)
11 {
12 a[0] = -1; m = 0;
13 for (int i = 1, x; i <= n; i)
14 {
15 scanf("%d", &x);
16 if (x != a[m]) a[ m] = x;
17 }
18 for (int i = 1; i <= m; i)
19 b[m - i 1] = a[i];
20 memset(f, 0, sizeof f);
21 for (int i = 1; i <= m; i)
22 for (int j = 1; j <= m; j)
23 {
24 f[i][j] = max(f[i][j - 1], f[i - 1][j]);
25 if (a[i] == b[j])
26 f[i][j] = max(f[i][j], f[i - 1][j - 1] 1);
27 }
28 printf("%d\n", m - 1 - f[m][m] / 2);
29 }
30 return 0;
31 }
View Code
? 下面這個線段樹版本本質(zhì)上和$LCS思想差不多$ 
1 #include <bits/stdc .h>
2 using namespace std;
3
4 #define N 10010
5 int n, m, c[N];
6 vector <int> vec[N];
7
8 namespace SEG
9 {
10 int Max[N << 2];
11 void init(){ memset(Max, 0, sizeof Max); }
12 void update(int id, int l, int r, int pos, int val)
13 {
14 if (l == r)
15 {
16 Max[id] = max(Max[id], val);
17 return;
18 }
19 int mid = (l r) >> 1;
20 if (pos <= mid) update(id << 1, l, mid, pos, val);
21 else update(id << 1 | 1, mid 1, r, pos, val);
22 Max[id] = max(Max[id << 1], Max[id << 1 | 1]);
23 }
24 int query(int id, int l, int r, int ql, int qr)
25 {
26 if (qr < ql) return 0;
27 if (l >= ql && r <= qr) return Max[id];
28 int res = 0;
29 int mid = (l r) >> 1;
30 if (ql <= mid) res = max(res, query(id << 1, l, mid, ql, qr));
31 if (qr > mid) res = max(res, query(id << 1 | 1, mid 1, r, ql, qr));
32 return res;
33 }
34 }
35
36 int main()
37 {
38 while (scanf("%d", &n) != EOF)
39 {
40 m = 0, c[0] = -1;
41 for (int i = 1, x; i <= n; i)
42 {
43 scanf("%d", &x);
44 if (x != c[m]) c[ m] = x;
45 }
46 for (int i = m 1; i <= 2 * m; i) c[i] = c[i - m];
47 for (int i = 1; i <= m; i) vec[i].clear();
48 for (int i = 2 * m; i >= m 1; --i) vec[c[i]].push_back(i);
49 int res = (int)1e8;
50 SEG::init();
51 for (int i = m; i >= 1; --i)
52 {
53 for (auto it : vec[c[i]])
54 {
55 int tmp = SEG::query(1, 1, 2 * m, m 1, it - 1);
56 SEG::update(1, 1, 2 * m, it, tmp 1);
57 }
58 }
59 for (int i = m; i <= 2 * m; i) res = min(res, m - 1 - SEG::query(1, 1, 2 * m, i, i) / 2);
60 printf("%d\n", res);
61 }
62 return 0;
63 }
View Code
? ? E. Arithmetic Progression Upsolved. 題意： 給出一個等差序列，但是不有序 $有兩種詢問方式$ $?\; i 表示詢問第i個位置上的數(shù)是多少$ $> x 表示詢問序列中存不存在嚴格大于x的數(shù)字$ 最后給出首項和公差 詢問次數(shù)最多60 思路： 首先可以用$30次詢問求出上界$ $接著如果搞定公差下界就有了$ $我們隨機詢問30個數(shù)，就得到900個差值$ $再求這個差值的gcd就是答案$ $為什么不會出現(xiàn)求的值的答案的倍數(shù)的情況?$ $概率很小，官方題解有證 (逃$ 注意隨機的時候要用大數(shù)隨機
1 #include <bits/stdc .h>
2 using namespace std;
3
4 #define ll long long
5 #define N 1000010
6 int n, cnt;
7
8 bool check(int x)
9 {
10 printf("> %d\n", x);
11 cnt;
12 fflush(stdout);
13 int tmp;
14 scanf("%d", &tmp);
15 return tmp == 0;
16 }
17
18 int vis[N];
19 int gcd(int a, int b)
20 {
21 return b ? gcd(b, a % b) : a;
22 }
23
24 int main()
25 {
26 while (scanf("%d", &n) != EOF)
27 {
28 if (n <= 60)
29 {
30 vector <int> vec;
31 for (int i = 1, x; i <= n; i)
32 {
33 printf("? %d\n", i);
34 fflush(stdout);
35 scanf("%d", &x);
36 vec.push_back(x);
37 }
38 sort(vec.begin(), vec.end());
39 printf("! %d %d\n", vec[0], vec[1] - vec[0]);
40 fflush(stdout);
41 continue;
42 }
43 cnt = 0;
44 int l = 0, r = (int)1e9, res = -1;
45 while (r - l >= 0)
46 {
47 int mid = (l r) >> 1;
48 if (check(mid))
49 {
50 res = mid;
51 r = mid - 1;
52 }
53 else
54 l = mid 1;
55 }
56 vector <int> vec, gap;
57 vec.push_back(res);
58 memset(vis, 0, sizeof vis);
59 for (int i = cnt 1, x; i <= 60; i)
60 {
61 do
62 {
63 x = ((rand() << 14) rand()) % n 1;
64 } while (vis[x]);
65 vis[x] = 1;
66 printf("? %d\n", x);
67 fflush(stdout);
68 scanf("%d", &x);
69 vec.push_back(x);
70 }
71 sort(vec.begin(), vec.end());
72 vec.erase(unique(vec.begin(), vec.end()), vec.end());
73 for (int i = 0, len = vec.size(); i < len; i)
74 for (int j = i 1; j < len; j)
75 gap.push_back(vec[j] - vec[i]);
76 int d = 0;
77 for (auto it : gap) d = gcd(d, it);
78 printf("! %d %d\n", res - (n - 1) * d, d);
79 fflush(stdout);
80 }
81 return 0;
82 }
View Code
? F. Please, another Queries on Array? Upsolved. 題意： 給出一個序列 有兩種操作 $M\; l, r, x 將[l, r]里面的數(shù)乘上x$ $q\; l, r? 詢問\phi(\prod_{i = l}^{r} a_i) mod 10^9 7$ 思路： 考慮$\phi(p^k) = p^{k - 1} \cdot (p - 1)$ 并且$\phi()是積性函數(shù)$ $有\(zhòng)phi(x \cdot y) = \phi(x) \cdot \phi(y)$ $那么令k = p_1^{t_1} \cdot p_2^{t_2} \cdots p_n^{t_n}$ 那么 $\phi(k) = \phi(p_1^{t_1}) \cdots$ $\phi(k) = p_1^{t_1 - 1} \cdot (p_1 - 1) \cdots$ $\phi(k) = p_1^{t_1} \cdot \frac{p_1 - 1}{p_1} \cdots$ ? 那么詢問的答案就是 $\phi(k) = k \cdot \prod_{p \in P} \frac{p - 1}{p}$ ? 前面那一段用乘積線段樹維護 考慮題目的數(shù)的值中涉及到的素數(shù)只有62個 $后面那一段用或線段樹維護是否存在即可$
1 #include <bits/stdc .h>
2 using namespace std;
3
4 #define ll long long
5 #define N 400010
6 const ll MOD = (ll)1e9 7;
7 int n, m, q, a[N];
8 int prime[110], pos[310];
9 ll inv[110], b[310];
10
11 void init()
12 {
13 m = 0;
14 memset(pos, 0, sizeof pos);
15 for (int i = 2; i <= 300; i)
16 {
17 if (!pos[i])
18 prime[ m] = i;
19 for (int j = i * i; j <= 300; j = i)
20 pos[j] = 1;
21 }
22 for (int i = 1; i <= 300; i)
23 {
24 b[i] = 0;
25 for (int j = 1; j <= 62; j)
26 if (i % prime[j] == 0)
27 b[i] |= (1ll << (j - 1));
28 }
29 }
30
31 ll qmod(ll base, ll n)
32 {
33 ll res = 1;
34 while (n)
35 {
36 if (n & 1) res = res * base % MOD;
37 base = base * base % MOD;
38 n >>= 1;
39 }
40 return res;
41 }
42
43 namespace SEG
44 {
45 struct node
46 {
47 int cnt;
48 ll sum, lazy;
49 ll S, W;
50 void init()
51 {
52 sum = 1;
53 lazy = 1;
54 S = 0, W = 0;
55 }
56 void add(ll val, ll SE)
57 {
58 sum = (sum * qmod(val, cnt)) % MOD;
59 lazy = (lazy * val) % MOD;
60 S |= SE;
61 W |= SE;
62 }
63 node operator (const node &other) const
64 {
65 node res; res.init();
66 res.sum = (sum * other.sum) % MOD;
67 res.S = S | other.S;
68 res.cnt = cnt other.cnt;
69 return res;
70 }
71 }a[N << 2], res;
72 void pushdown(int id)
73 {
74 if (a[id].lazy == 1 && a[id].W == 0) return;
75 a[id << 1].add(a[id].lazy, a[id].W);
76 a[id << 1 | 1].add(a[id].lazy, a[id].W);
77 a[id].lazy = 1;
78 a[id].W = 0;
79 }
80 void build(int id, int l, int r)
81 {
82 a[id].init();
83 a[id].cnt = (r - l 1);
84 if (l == r) return;
85 int mid = (l r) >> 1;
86 build(id << 1, l, mid);
87 build(id << 1 | 1, mid 1, r);
88 }
89 void update(int id, int l, int r, int ql, int qr, ll val, ll SE)
90 {
91 if (l >= ql && r <= qr)
92 {
93 a[id].add(val, SE);
94 return;
95 }
96 int mid = (l r) >> 1;
97 pushdown(id);
98 if (ql <= mid) update(id << 1, l, mid, ql, qr, val, SE);
99 if (qr > mid) update(id << 1 | 1, mid 1, r, ql, qr, val, SE);
100 a[id] = a[id << 1] a[id << 1 | 1];
101 }
102 void query(int id, int l, int r, int ql, int qr)
103 {
104 if (l >= ql && r <= qr)
105 {
106 res = res a[id];
107 return;
108 }
109 int mid = (l r) >> 1;
110 pushdown(id);
111 if (ql <= mid) query(id << 1, l, mid, ql, qr);
112 if (qr > mid) query(id << 1 | 1, mid 1, r, ql, qr);
113 }
114 }
115
116 int main()
117 {
118 init();
119 for (int i = 1; i <= 62; i)
120 inv[i] = qmod(prime[i], MOD - 2);
121 while (scanf("%d%d", &n, &q) != EOF)
122 {
123 for (int i = 1; i <= n; i) scanf("%d", a i);
124 SEG::build(1, 1, n);
125 for (int i = 1; i <= n; i)
126 SEG::update(1, 1, n, i, i, a[i], b[a[i]]);
127 char op[20]; int l, r, x;
128 for (int i = 1; i <= q; i)
129 {
130 scanf("%s%d%d", op, &l, &r);
131 if (op[0] == 'M')
132 {
133 scanf("%d", &x);
134 SEG::update(1, 1, n, l, r, x, b[x]);
135 }
136 else
137 {
138 SEG::res.init();
139 SEG::query(1, 1, n, l, r);
140 ll res = SEG::res.sum;
141 ll S = SEG::res.S;
142 for (int j = 1; j <= 62; j)
143 if ((S >> (j - 1)) & 1ll)
144 res = (res * (prime[j] - 1) % MOD * inv[j]) % MOD;
145 printf("%lld\n", res);
146 }
147 }
148 }
149 return 0;
150 }
View Code
? 來源：http://www./content-4-112351.html |
|
|
