题目链接：https://www.jisuanke.com/contest/3007?view=challenges B： 并查集sb题。 1 /* Contest shenyang_2019_online 2 * Problem B 3 * Team: Make One For Us 4 */ 5 #include bits/stdc++.h 6 7 using namespace std; 8 9 int read( void
题目链接：https://www.jisuanke.com/contest/3007?view=challenges
B：
并查集sb题。
1 /* Contest shenyang_2019_online 2 * Problem B 3 * Team: Make One For Us 4 */ 5 #include <bits/stdc++.h> 6 7 using namespace std; 8 9 int read(void) { 10 char ch; 11 do { 12 ch = getchar(); 13 } while (!isdigit(ch)); 14 int ret = 0; 15 while (isdigit(ch)) { 16 ret *= 10; 17 ret += ch - ‘0‘; 18 ch = getchar(); 19 } 20 return ret; 21 } 22 23 int fa[100001], cnt[100001]; 24 25 int findSet(int u) { 26 return u == fa[u] ? u : fa[u] = findSet(fa[u]); 27 } 28 29 void search(int p, vector <vector <int>> &graph, vector <int> &conn, vector <int> &monster, vector <int> &visit) { 30 if (visit[p]) { 31 return; 32 } 33 visit[p] = true; 34 if (monster[p]) { 35 conn.emplace_back(p); 36 return; 37 } 38 for (auto e : graph[p]) { 39 search(e, graph, conn, monster, visit); 40 } 41 } 42 43 int main(void) { 44 int t = read(); 45 while (t--) { 46 int n = read(), m = read(), k = read(); 47 vector <int> monster(n + 1), vis(n + 1); 48 vector <vector <int>> graph(n + 1); 49 for (int i = 0; i < m; i++) { 50 int u, v; 51 scanf("%d %d", &u, &v); 52 graph[u].emplace_back(v); 53 graph[v].emplace_back(u); 54 } 55 for (int i = 1; i <= n; i++) { 56 fa[i] = i; 57 cnt[i] = 1; 58 } 59 for (int i = 0; i < k; i++) { 60 int x; 61 scanf("%d", &x); 62 monster[x] = 1; 63 } 64 for (int i = 1; i <= n; i++) { 65 if (!monster[i] && !vis[i]) { 66 queue <int> q; 67 q.push(i); 68 int index = findSet(i); 69 while (!q.empty()) { 70 int t = q.front(); 71 q.pop(); 72 if (vis[t]) { 73 continue; 74 } 75 vis[t] = true; 76 int ft = findSet(t); 77 if (ft != index) { 78 fa[ft] = index; 79 cnt[index]++; 80 } 81 for (auto e : graph[t]) { 82 if (!monster[e]) { 83 q.push(e); 84 } 85 } 86 } 87 } 88 } 89 vector <int> conn; 90 vector <int> visit(n + 1); 91 search(1, graph, conn, monster, visit); 92 double maxi = 0.0; 93 for (auto p : conn) { 94 double cur = 0.0; 95 for (auto l : graph[p]) { 96 int tar = findSet(l); 97 if (tar != 1 && !monster[tar]) { 98 cur += (double) cnt[tar] / graph[p].size(); 99 } 100 } 101 maxi = max(maxi, cur); 102 } 103 printf("%.9f\n", maxi + cnt[1]); 104 } 105 return 0; 106 }View Code
C：
背包。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 struct info { 6 long long int price, weight; 7 }; 8 9 int main(void) { 10 int n, m; 11 while (scanf("%d %d", &n, &m) != EOF) { 12 vector <info> water(n); 13 for (int i = 0; i < n; i++) { 14 scanf("%lld %lld", &water[i].price, &water[i].weight); 15 } 16 for (int i = 0; i < n; i++) { 17 for (int j = 1; j < 32; j++) { 18 water.emplace_back((info) { 19 water[i].price * (1 << j), water[i].weight * (1 << j) 20 }); 21 if (water.back().weight > m) { 22 break; 23 } 24 } 25 } 26 unordered_map <int, long long int> obj(20001); 27 for (auto e : water) { 28 if (!obj.count(e.weight) || obj[e.weight] > e.price) { 29 obj[e.weight] = e.price; 30 } 31 } 32 long long int ans = 10000000000000000LL; 33 int rec = 0; 34 vector <long long int> f(20001, 10000000000000000LL); 35 f[0] = 0; 36 for (auto e : obj) { 37 int weight = e.first; 38 long long int price = e.second; 39 for (int j = m + 10000; j >= 0; j--) { 40 if (j >= weight) { 41 f[j] = min(f[j - weight] + price, f[j]); 42 } 43 if (j >= m) { 44 if (ans > f[j]) { 45 ans = f[j]; 46 rec = j; 47 } else if (ans == f[j]) { 48 rec = max(rec, j); 49 } 50 } 51 } 52 } 53 printf("%lld %d\n", ans, rec); 54 } 55 return 0; 56 }View Code
F：
模拟。
1 /* Contest shenyang_2019_online 2 * Problem F 3 * Team: Make One For Us 4 */ 5 #include <bits/stdc++.h> 6 7 using namespace std; 8 9 int main(void) { 10 long long int n, k; 11 while (scanf("%lld %lld", &n, &k) != EOF) { 12 vector <long long int> arr(n); 13 map <long long int, int> cnt; 14 long long int sum = 0; 15 for (int i = 0; i < n; i++) { 16 scanf("%lld", &arr[i]); 17 cnt[arr[i]]++; 18 sum += arr[i]; 19 } 20 vector <pair <long long int, int>> vec; 21 for (auto e : cnt) { 22 vec.emplace_back(make_pair(e.first, e.second)); 23 // cerr << e.first << ", " << e.second << endl; 24 } 25 // array: less to more 26 long long int n_min = vec.front().first, n_max = vec.back().first, rem = k; 27 int cur = 0; 28 for (unsigned int i = 0; i < vec.size() - 1; i++) { 29 cur += vec[i].second; 30 auto delta = (vec[i + 1].first - vec[i].first) * cur; 31 if (rem >= delta) { 32 rem -= delta; 33 n_min = vec[i + 1].first; 34 } else { 35 n_min = vec[i].first + rem / cur; 36 break; 37 } 38 } 39 cur = 0; 40 rem = k; 41 for (unsigned int i = vec.size() - 1; i > 0; i--) { 42 cur += vec[i].second; 43 auto delta = (vec[i].first - vec[i - 1].first) * cur; 44 if (rem >= delta) { 45 rem -= delta; 46 n_max = vec[i - 1].first; 47 } else { 48 n_max = vec[i].first - rem / cur; 49 break; 50 } 51 } 52 printf("%lld\n", n_min < n_max ? n_max - n_min : ((sum % n) ? 1 : 0)); 53 } 54 return 0; 55 }View Code
H：
模拟。
1 /* Contest shenyang_2019_online 2 * Problem H 3 * Team: Make One For Us 4 */ 5 #include <bits/stdc++.h> 6 7 using namespace std; 8 9 struct info { 10 string name, deck; 11 int value(void) const { 12 vector <int> cards; 13 for (auto ch : deck) { 14 if (ch == ‘1‘) { 15 cards.emplace_back(10); 16 } else if (ch == ‘J‘) { 17 cards.emplace_back(11); 18 } else if (ch == ‘Q‘) { 19 cards.emplace_back(12); 20 } else if (ch == ‘K‘) { 21 cards.emplace_back(13); 22 } else if (ch == ‘A‘) { 23 cards.emplace_back(1); 24 } else if (ch != ‘0‘) { 25 cards.emplace_back(ch - ‘0‘); 26 } 27 } 28 sort(cards.begin(), cards.end()); 29 30 int sum = 0; 31 for (int i = 0; i < 5; i++) { 32 sum += cards[i]; 33 } 34 35 bool flag = cards[0] == 1; 36 for (int i = 1; i <= 4; i++) { 37 if (cards[i] != 9 + i) { 38 flag = false; 39 } 40 } 41 if (flag) { 42 return 900000000; 43 } 44 45 flag = true; 46 for (int i = 0; i < 4; i++) { 47 if (cards[i] + 1 != cards[i + 1]) { 48 flag = false; 49 } 50 } 51 if (flag) { 52 return 800000000 + cards[4]; 53 } 54 55 if (cards[0] == cards[3] || cards[1] == cards[4]) { 56 return 700000000 + cards[2] * 100 + (sum - 4 * cards[2]); 57 } 58 59 if ((cards[0] == cards[2] && cards[3] == cards[4]) || (cards[0] == cards[1] && cards[2] == cards[4])) { 60 return 600000000 + cards[2] * 10000 + (cards[0] ^ cards[2] ^ cards[4]); 61 } 62 63 if (cards[0] == cards[2] || cards[1] == cards[3] || cards[2] == cards[4]) { 64 return 500000000 + cards[2] * 10000 + (sum - cards[2] * 3); 65 } 66 67 vector <int> pairs; 68 69 for (int i = 0; i < 4; i++) { 70 if (cards[i] == cards[i + 1]) { 71 pairs.emplace_back(cards[i]); 72 } 73 } 74 // Two pairs 75 if (pairs.size() == 2) { 76 return 400000000 + pairs[1] * 10000 + pairs[0] * 100 + (sum - 2 * pairs[1] - 2 * pairs[0]); 77 } 78 79 // Pair 80 if (pairs.size() == 1) { 81 return 300000000 + pairs[0] * 10000 + (sum - 2 * pairs[0]); 82 } 83 84 // High Card 85 return sum; 86 } 87 }; 88 89 int main(void) { 90 ios::sync_with_stdio(false); 91 cin.tie(nullptr); 92 int n; 93 cin >> n; 94 vector <info> data(n); 95 for (int i = 0; i < n; i++) { 96 cin >> data[i].name >> data[i].deck; 97 } 98 sort(data.begin(), data.end(), [&] (const info & a, const info & b) { 99 int va = a.value(), vb = b.value(); 100 return va == vb ? a.name < b.name : va > vb; 101 }); 102 for (auto e : data) { 103 cout << e.name << endl; 104 } 105 return 0; 106 }View Code