首页 > 代码库 > # 7-17题解整理
# 7-17题解整理
# A - A Card Game
简单公式推导 > ( n - 1 ) ! * a [ 1 ] / n !
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 7 int a[105], n; 8 9 int main() { 10 int t; scanf("%d", &t); 11 int cnt = 0; 12 while (t--) { 13 scanf("%d", &n); 14 int sum = 0; 15 for(int i = 1;i <= n; ++i) { 16 scanf("%d", &a[i]); 17 sum += a[i]; 18 } 19 double ans = (double) a[1] / sum; 20 printf("Case %d: %.6lf\n", ++cnt, ans); 21 } 22 return 0; 23 }
# [F - Random Sequence]
暴力找规律+打表
// 打表
1 #include <cstdio> 2 #include <algorithm> 3 #include <cmath> 4 using namespace std; 5 6 int a[20]; 7 8 int main() { 9 for (int n = 1; n <= 15; ++n) { 10 double ans = 0; 11 for (int i = 0; i < (1 << n); ++i) { 12 for (int j = 0; j < n; ++j) { 13 if (i & (1 << j)) a[j] = 1; 14 else a[j] = -1; 15 } 16 int maxn = 0; 17 for (int len = 1; len <= n; ++len) 18 for (int j = 0; j + len - 1 < n; ++j) { 19 int sum = 0; 20 for (int k = j; k <= j + len - 1; ++k) { 21 sum += a[k]; 22 maxn = max(maxn, abs(sum)); 23 } 24 } 25 ans += maxn; 26 } 27 printf("%.6f\n", ans / pow(2, n)); 28 } 29 return 0; 30 }
找规律:
1 #include <cstdio> 2 3 double a[1505]; 4 5 void init() { 6 double d = 1.0 / 2; 7 a[1] = 1; 8 for (int i = 2; i <= 1500; ++i) { 9 if (i % 2 == 0 && i != 2) 10 d *= 1.0 * (i - 1) / i; 11 a[i] = a[i - 1] + d; 12 } 13 } 14 15 int main() { 16 init(); 17 int t; scanf("%d", &t); 18 int cas = 0, n; 19 while (t--) { 20 scanf("%d", &n); 21 printf("Case %d: %.6f\n", ++cas, a[n]); 22 } 23 return 0; 24 }
# [H - SanguoSHA]
6!*6!全排列暴力,注意全排列是从当前字典序开始的,用之前需要重新排序.
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <map> 6 #include <vector> 7 using namespace std; 8 9 vector <string> vec[7], ans; 10 string name[7]; 11 12 int main() { 13 int t; scanf("%d", &t); 14 int cnt = 0; 15 while (t--) { 16 int n; scanf("%d", &n); 17 ans.clear(); 18 for (int i = 0; i < 7; ++i) vec[i].clear(); 19 for (int i = 1; i <= n; ++i) cin >> name[i]; 20 for (int i = 1; i <= n; ++i) { 21 int y; scanf("%d", &y); 22 while (y--) { 23 string x; cin >> x; 24 vec[i].push_back(x); 25 } 26 } 27 int tmp[7]; 28 sort(name + 1, name + n + 1); 29 do { 30 for (int i = 1; i <= n; ++i) tmp[i] = i; 31 bool flag2 = 0; 32 do { 33 int p1 = 1, p2 = 1; 34 while (1) { 35 int flag = 1; 36 for (int i = 0; i < (int) vec[tmp[p1]].size(); ++i) 37 if (vec[tmp[p1]][i] == name[p2]) { 38 p2++; 39 flag = 0; 40 break; 41 } 42 if (flag) p1++; 43 if (p1 == n + 1 && p2 <= n) 44 break; 45 if (p2 == n + 1 && p1 <= n){ 46 flag2 = 1; 47 break; 48 } 49 } 50 if (flag2) break; 51 } while (next_permutation(tmp + 1, tmp + n + 1)); 52 if (flag2 == 0) { 53 string t; t.append(name[1]); 54 for (int i = 2; i <= n; ++i) 55 t.append(" " + name[i]); 56 ans.push_back(t); 57 } 58 } while (next_permutation(name + 1, name + n + 1)); 59 int f = ans.size(); 60 printf("Case %d: %s\n", ++cnt, f ? "Yes" : "No"); 61 if (f) cout << ans[0] << endl; 62 } 63 return 0; 64 }
# J - Phage War
是一道简单的贪心,让等待时间最长的最先来就行.
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 const int N = 1e5 + 5; 6 7 struct node { 8 int s, t; 9 } a[N]; 10 11 bool cmp(node a, node b) { 12 if (a.t == b.t) return a.s > b.s; 13 return a.t > b.t; 14 } 15 16 int main() { 17 int cnt = 0, n; 18 int t; scanf("%d", &t); 19 while (t--) { 20 scanf("%d", &n); 21 for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i].s, &a[i].t); 22 sort(a + 1, a + n + 1, cmp); 23 int t = 0, maxn = 0; 24 for (int i = 1; i <= n; ++i) { 25 t += a[i].s; 26 maxn = max(t + a[i].t, maxn); 27 } 28 printf("Case %d: %d\n", ++cnt, maxn); 29 } 30 return 0; 31 }
# 7-17题解整理
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。