Codeforces Round #570 (Div. 3)

题目链接：https://codeforces.com/contest/1183

A：

太傻不说。

B：

最大最小值之差跟2k比较一下就好了，也不说。

C：

算一下就好了，注意开long long。

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson (curpos<<1)
15 #define rson (curpos<<1|1)
16 #define mid (curl+curr>>1)
17 /* namespace */
18 using namespace std;
19 /* header end */
20 
21 int q;
22 
23 int main() {
24     cin >> q;
25     while (q--) {
26         ll k, n, a, b; cin >> k >> n >> a >> b;
27         if (n * b >= k) puts("-1");
28         else printf("%lld
", min(n, (k - b * n - 1) / (a - b)));
29     }
30     return 0;
31 }

View Code

D：

倒着贪心就完事了。

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson (curpos<<1)
15 #define rson (curpos<<1|1)
16 #define mid (curl+curr>>1)
17 /* namespace */
18 using namespace std;
19 /* header end */
20 
21 const int maxn = 2e5 + 10;
22 int q;
23 
24 int main() {
25     scanf("%d", &q);
26     while (q--) {
27         int n, cnt[maxn] = {0}, maxx = 0; scanf("%d", &n);
28         rep1(i, 1, n) {
29             int x; scanf("%d", &x); maxx = max(maxx, x);
30             cnt[x]++;
31         }
32         sot(cnt, maxx);
33         ll ans = cnt[maxx]; int last = cnt[maxx];
34         for (int i = maxx - 1; i; i--) {
35             if (!last || !cnt[i]) break;
36             if (cnt[i] >= last) ans += last - 1, last--;
37             else ans += cnt[i], last = cnt[i];
38         }
39         printf("%lld
", ans);
40     }
41     return 0;
42 }

View Code

E：

bfs。

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson (curpos<<1)
15 #define rson (curpos<<1|1)
16 #define mid (curl+curr>>1)
17 /* namespace */
18 using namespace std;
19 /* header end */
20 
21 int n, k;
22 ll ans = 0;
23 string s;
24 queue<string>q;
25 set<string>ss;
26 
27 int main() {
28     cin >> n >> k >> s;
29     q.push(s); ss.insert(s);
30     while (!q.empty() && (int)ss.size() < k) {
31         auto curr = q.front();
32         q.pop();
33         rep1(i, 0, (int)curr.size()) {
34             string tmp = curr;
35             tmp.erase(i, 1);
36             if (ss.find(tmp) == ss.end() && ss.size() < k) {
37                 q.push(tmp); ss.insert(tmp); ans += n - tmp.size();
38             }
39         }
40     }
41     if ((int)ss.size() < k) puts("-1");
42     else printf("%lld
", ans);
43     return 0;
44 }

View Code

F：

给定n个数，选出尽量多的数，在满足两两不能互相整除的情况下，和最大。

从大到小sort，然后O(n)扫一遍，选出最大的三个不能互质的数，再把和跟最大的数a/30*31取最大值即可。

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson (curpos<<1)
15 #define rson (curpos<<1|1)
16 #define mid (curl+curr>>1)
17 /* namespace */
18 using namespace std;
19 /* header end */
20 
21 const int maxn = 2e5 + 10;
22 int q, a[maxn];
23 
24 int cmp(int a, int b) {
25     return a > b;
26 }
27 
28 int main() {
29     scanf("%d", &q);
30     while (q--) {
31         int n; scanf("%d", &n);
32         rep1(i, 1, n) scanf("%d", &a[i]);
33         sort(a + 1, a + 1 + n, cmp);
34         ll ans = a[1], sec = 0, thir = 0;
35         int f1 = 0, f2 = 0, f3 = 0;
36         for (int i = 2; i <= n && !thir; i++) {
37             if (a[1] % a[i]) {
38                 if (sec) {
39                     if (sec % a[i]) {
40                         thir = a[i];
41                         ans += a[i];
42                     }
43                 } else {
44                     sec = a[i];
45                     ans += a[i];
46                 }
47             }
48             if (a[i] * 2 == a[1]) f1 = 1;
49             else if (a[i] * 3 == a[1]) f2 = 1;
50             else if (a[i] * 5 == a[1]) f3 = 1;
51         }
52         if (f1 && f2 && f3) ans = max(ans, (ll)a[1] / 30 * 31);
53         printf("%lld
", ans);
54     }
55     return 0;
56 }

View Code

G && H：

摸了(