21/29
题目都很基础，有很多题书上讲得比较详细，然后隔得时间有点久，所以具体什么trick都忘了，思路也懒得去回忆，所以将就着放上来了。。。。
例题10–1 Uva 11582
题意：输入a， b， n让你计算F[a^b]%n;其中这个F[i]是斐波那契数；
题解：
这题是快速幂+找循环节，用什么方法找循环节呢？因为第一个数是0和1，然后当再出现0和1的时候就是出现循环节的时候，然后假如找到了循环节T，然后就有F[n] = F[n % T]，预处理找循环节，O（一百万左右），快速幂logn * 10000组数据，复杂度并不高；最后一个注意：给佳哥坑了，f(0)= 0, f(1) = 1;书上写错了。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 typedef unsigned long long ull; 6 const int maxn = 1001; 7 int F[maxn][maxn * 6], len[maxn]; 8 9 void pre_slove() { 10 for (int n = 2; n <= 1000; n++) { 11 F[n][0] = 0; F[n][1] = 1; 12 for (int i = 2; ; i++) { 13 F[n][i] = (F[n][i - 1] + F[n][i - 2]) % n; 14 if (F[n][i - 1] == 0 && F[n][i] == 1) { 15 len[n] = i - 1; break; 16 } 17 } 18 } 19 } 20 21 int quick(ull a, ull b, ull mod) { 22 int ret = 1; 23 a %= mod; 24 while (b) { 25 if (b & 1) ret = ret * a % mod; 26 b = b / 2; 27 a = a * a % mod; 28 } 29 return ret; 30 } 31 32 int main() { 33 //freopen("case.in", "r", stdin); 34 pre_slove(); 35 int T; 36 scanf("%d", &T); 37 while (T--) { 38 ull a, b; 39 int n; 40 cin >> a >> b >> n; 41 if (n == 1) { puts("0"); continue; } 42 printf("%d\n", F[n][quick(a, b, ull(len[n]))]); 43 } 44 return 0; 45 } 代码君
例题10-2 uva12169
题意：给你n个数，这n个数是x1，x3，……，x2*n-1，是由递推式子xi = （xi-1 * a + b） % 10001得到的，现在让你输出一组可能的x2……x2n；
题解：先要确定的是a和b都可以是0~10001，有模运算可知，然后就是枚举a，然后根据式子：
x2 = (x1 * a + b) % n;
x3 = (x2 * a + b) % n;
化简可得：
b * (a + 1) - k * n = x3 - x1 * a ^ 2;
这个类似ax + by = c的形式，可以用扩展欧几里得算法求出b和k，b的范围可以化简到0~n-1，然后判定是不是可行解，然后输出即可。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 typedef long long ll; 6 const int maxn = 1e4 + 100; 7 const int mod = 1e4 + 1; 8 int v[maxn]; 9 10 void gcd(ll a, ll b, ll& d, ll& x, ll& y) { 11 if (!b) { d = a; x = 1; y = 0; } 12 else { 13 gcd(b, a % b, d, y, x); y -= x * (a / b); 14 } 15 } 16 17 int main() { 18 //freopen("case.in", "r", stdin); 19 int n; 20 while (scanf("%d", &n) == 1) { 21 for (int i = 0, j = 1; i < n; i++, j += 2) scanf("%d", v+ j); 22 bool f = true; 23 ll x, y, d, a, b, c; 24 for (a = 0; a < mod && f; a++) { 25 gcd(a + 1, mod, d, x, y); 26 c = v[3] - a * a * v[1]; 27 if (c % d) continue; 28 b = (x * c / d + mod * 10) % mod; 29 f = false; 30 for (int i = 3; i <= 2 * n - 1 && !f; i += 2) { 31 v[i - 1] = (v[i - 2] * a + b) % mod; 32 if (v[i] != (v[i - 1] * a + b) % mod) f = true; 33 } 34 if (!f) v[2 * n] = (v[2 * n - 1] * a + b) % mod; 35 } 36 for (int i = 2; i <= 2 * n; i += 2) printf("%d\n", v[i]); 37 } 38 return 0; 39 } 代码君
例题10-3 uva10375
题意：略
题解：唯一分解定理。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 const int maxn = 1e4 + 100; 6 bool vis[maxn]; 7 vector<int> primes; 8 int cnt[maxn]; 9 10 void pre_slove(int n) { 11 int m = sqrt(n + 0.5); 12 for (int i = 2; i <= m; i++) if (!vis[i]) 13 for (int j = i * i; j < maxn; j += i) vis[j] = true; 14 15 for (int i = 2; i < maxn; i++) if (!vis[i]) 16 primes.push_back(i); 17 } 18 19 void get_cnt(int n, int d) { 20 for (int i = 0; i < (int)primes.size() && primes[i] <= n; i++) { 21 while (n % primes[i] == 0) { 22 cnt[i] += d; 23 n /= primes[i]; 24 } 25 } 26 } 27 28 int main() { 29 //freopen("case.in","r", stdin); 30 pre_slove(maxn); 31 int p, q, r, s; 32 while (cin >> p >> q >> r >> s) { 33 memset(cnt, 0, sizeof cnt); 34 for (int i = 0; i < q; i++) { 35 get_cnt(p - i, 1); 36 get_cnt(i + 1, -1); 37 } 38 for (int i = 0; i < s; i++) { 39 get_cnt(r - i, -1); 40 get_cnt(i + 1, 1); 41 } 42 double ans = 1.0; 43 for (int i = 0; i < maxn; i++) if (cnt[i]) { 44 ans *= powl(primes[i] * 1.0, cnt[i] * 1.0); 45 } 46 printf("%.5lf\n", ans); 47 48 } 49 return 0; 50 } 代码君
例题10-4 uva 10791
题意：找几个数的公倍数为n的最小的和。
题解：唯一分解定理的各个项相加即是答案。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 typedef long long ll; 6 const int maxn = 1 << 16; 7 bool vis[maxn]; 8 vector<int> primes; 9 10 void pre_slove(int n) { 11 int m = sqrt(n + 0.5); 12 for (int i = 2; i <= m; i++) if (!vis[i]) 13 for (int j = i * i; j < n; j += i) vis[j] = true; 14 15 for (int i = 2; i < n; i++) if (!vis[i]) 16 primes.push_back(i); 17 } 18 19 ll get_ans(ll n) { 20 if (n == 1) return 2; 21 ll ret = 0; 22 int cnt = 0; 23 for (int i = 0; i < (int)primes.size() && n >= primes[i]; i++) 24 if (n % primes[i] == 0) { 25 ll x = 1; 26 while (n % primes[i] == 0) { 27 x *= primes[i]; n /= primes[i]; 28 } 29 cnt++; ret += x; 30 } 31 if (n > 1) { ret += n; cnt++; } 32 if (cnt == 1) ret++; 33 return ret; 34 } 35 36 int main() { 37 //freopen("case.in", "r", stdin); 38 pre_slove(maxn); 39 ll n; 40 int tcase = 0; 41 while (cin >> n, n) { 42 cout << "Case " << ++tcase << ": " << get_ans(n) << endl; 43 } 44 return 0; 45 } 代码君
例题10-5 uva12716
题意：略
题解：具体思路跟紫书说的一样：先枚举约数c和其中一个较大的数a，然后得到b，然后判定是否存在gcd(a, a ^ c) = c;这样的复杂度是O（nlognlogn）；
枚举a和c的代码如下：
for (int c = 1; c < maxn; c++)
for (int a = c + c; a < maxn; a += c)
就像素数筛法一样，对于c，2c，3c……都存在c这个约数。
最后发现有一个性质：满足a - c = b；所以就省去了一个log；
结合书和博客证明一下这个结论：
（1）首先前提是a - b <= a ^ b;
（2）设a - b = c;那么有a - b <= c;
（3）因为gcd(a, b) = c; 那么a = ca’, b = cb’，然后a - b = c(a’ - b’) >= c; 即c <= a - b <= c;
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 const int maxn = 3e7 + 1; 6 int cnt[maxn], sum[maxn]; 7 8 void pre_slove() { 9 for (int c = 1; c < maxn; c++) 10 for (int a = c + c; a < maxn; a += c) { 11 if (a - c == (a ^ c)) cnt[a]++; 12 } 13 for (int i = 1; i < maxn; i++) sum[i] = sum[i - 1] + cnt[i]; 14 } 15 16 int main() { 17 //freopen("case.in", "r", stdin); 18 pre_slove(); 19 int T, tcase = 0; 20 scanf("%d", &T); 21 while (T--) { 22 int n; 23 scanf("%d", &n); 24 printf("Case %d: %d\n", ++tcase, sum[n]); 25 } 26 return 0; 27 } 代码君
例题10-6 uva10820
题意：略
题解：书上很详细，就是找组合数C(0,n-1), C(1,n-1), ……,C(n-1,n-1)中有多少个能被m整除，方法是把m分解，找当前有没有全部覆盖它的所有因子即可。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 #define fi first 4 #define se second 5 using namespace std; 6 7 typedef pair<int,int> pii; 8 const int maxn = 1e5 + 10; 9 int mp1[maxn], mp2[maxn], cnt; 10 bool vis[maxn]; 11 vector<int> primes, ans; 12 vector<pii> PII[maxn]; 13 14 void pre_slove() { 15 int m = sqrt(maxn + 0.5); 16 for (int i = 2; i <= m; i++) if (!vis[i]) 17 for (int j = i * i; j < maxn; j += i) vis[j] = 1; 18 for (int i = 2; i < maxn; i++) if (!vis[i]) 19 primes.push_back(i); 20 21 for (int i = 2; i < maxn; i++) { 22 int x = i; 23 for (int j = 0; j < (int)primes.size() && x >= primes[j]; j++) if (x % primes[j] == 0) { 24 int t = 0; 25 while (x % primes[j] == 0) { 26 x /= primes[j]; 27 t++; 28 } 29 PII[i].push_back(make_pair(primes[j], t)); 30 } 31 } 32 } 33 34 void init() { 35 memset(mp1, 0, sizeof mp1); 36 memset(mp2, 0, sizeof mp2); 37 cnt = 0; 38 ans.clear(); 39 } 40 41 bool divide(int m, int n) { 42 if (m == 1) { 43 for (int i = 1; i <= n; i++) ans.push_back(i); 44 return false; 45 } 46 47 for (int i = 0; i < (int)primes.size() && m >= primes[i]; ++i) if (m % primes[i] == 0) { 48 ++cnt; 49 while (m % primes[i] == 0) { 50 m /= primes[i]; 51 mp2[primes[i]]++; 52 } 53 } 54 if (m > 1) return false; 55 return true; 56 } 57 58 void slove(int n) { 59 int now = 0, x; 60 for (int i = 1; i <= n; i++) { 61 x = n - i + 1; 62 for (int j = 0; j < (int)PII[x].size(); j++) { 63 pii& p = PII[x][j]; 64 if (mp2[p.fi] && mp1[p.fi] < mp2[p.fi] && mp1[p.fi] + p.se >= mp2[p.fi]) now++; 65 mp1[p.fi] += p.se; 66 } 67 x = i; 68 for (int j = 0; j < (int)PII[x].size(); j++) { 69 pii& p = PII[x][j]; 70 if (mp2[p.fi] && mp1[p.fi] >= mp2[p.fi] && mp1[p.fi] - p.se < mp2[p.fi]) now--; 71 mp1[p.fi] -= p.se; 72 } 73 if (now == cnt) ans.push_back(i + 1); 74 } 75 } 76 77 int main() { 78 //freopen("case.in", "r", stdin); 79 pre_slove(); 80 int n, m; 81 while (scanf("%d%d", &n, &m) == 2) { 82 init(); 83 84 if (divide(m, n)) slove(n - 1); 85 86 printf("%d\n", (int)ans.size()); 87 if (!ans.empty()) { 88 printf("%d", ans[0]); 89 for (int i = 1; i < (int)ans.size(); i++) printf(" %d", ans[i]); 90 } 91 printf("\n"); 92 } 93 return 0; 94 } 代码君
例题10-7 uva10820
题意：计算1 <= x,y <= n有多少个满足gcd（x，y） = 1？
题解：略
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 typedef long long ll; 6 const int maxn = 5e4 + 100; 7 int phi[maxn]; 8 9 void phi_table(int n) { 10 for (int i = 2; i <= n; i++) phi[i] = 0; 11 phi[1] = 1; 12 for (int i = 2; i <= n; i++) if (!phi[i]) 13 for (int j = i; j <= n; j += i) { 14 if (!phi[j]) phi[j] = j; 15 phi[j] = phi[j] / i * (i - 1); 16 } 17 for (int i = 3; i <= n; i++) phi[i] += phi[i - 1]; 18 } 19 20 int main() { 21 //freopen("case.in", "r", stdin); 22 phi_table(maxn - 1); 23 int n; 24 while (scanf("%d", &n) && n) { 25 ll ans = phi[n] * 2 + 1; 26 if (n == 1) ans = 1; 27 printf("%d\n", ans); 28 } 29 return 0; 30 } 代码君
例题 10-8
题意：找这两个表中每一列都一样的字符，然后顺序取每一列，然后找字典序第k小。
题解：两种方法：
1、直接暴力dfs枚举
2、递推来找（像拆排列一样）
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 const int maxn = 90; 6 int k, now; 7 char s[maxn]; 8 char M1[maxn][maxn], M2[maxn][maxn]; 9 10 bool dfs(int cur) { 11 if (cur == 5) { 12 if (++now == k) { 13 s[cur] = '\0'; 14 printf("%s\n", s); 15 return true; 16 } 17 return false; 18 } 19 20 bool vis1[30], vis2[30]; 21 memset(vis1, false, sizeof vis1); 22 memset(vis2, false, sizeof vis2); 23 24 for (int i = 0; i < 6; i++) vis1[M1[i][cur] - 'A'] = true; 25 for (int i = 0; i < 6; i++) vis2[M2[i][cur] - 'A'] = true; 26 27 for (int i = 0; i < 26; i++) if (vis1[i] && vis2[i]) { 28 s[cur] = 'A' + i; 29 if (dfs(cur + 1)) return true; 30 } 31 return false; 32 } 33 34 int main() { 35 //freopen("case.in", "r", stdin); 36 int T; 37 scanf("%d", &T); 38 while (T--) { 39 scanf("%d", &k); 40 for (int i = 0; i < 6; i++) scanf("%s", M1[i]); 41 for (int i = 0; i < 6; i++) scanf("%s", M2[i]); 42 43 now = 0; 44 if (!dfs(0)) printf("NO\n"); 45 } 46 return 0; 47 } 代码君（dfs）
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 const int maxn = 10; 6 char M1[maxn][maxn], M2[maxn][maxn], s[maxn]; 7 vector<char> V[maxn]; 8 bool vis1[26], vis2[26]; 9 10 int main() { 11 //freopen("case.in", "r", stdin); 12 int T, k; 13 scanf("%d", &T); 14 while (T--) { 15 scanf("%d", &k); 16 for (int i = 0; i < 6; i++) scanf("%s", M1[i]); 17 for (int i = 0; i < 6; i++) scanf("%s", M2[i]); 18 19 int tot = 1; 20 for (int j = 0; j < 5; j++) { 21 V[j].clear(); 22 memset(vis1, false, sizeof vis1); 23 memset(vis2, false, sizeof vis2); 24 25 for (int i = 0; i < 6; i++) vis1[M1[i][j] - 'A'] = true; 26 for (int i = 0; i < 6; i++) vis2[M2[i][j] - 'A'] = true; 27 for (int i = 0; i < 26; i++) if (vis1[i] && vis2[i]) 28 V[j].push_back(i + 'A'); 29 30 tot *= int(V[j].size()); 31 } 32 33 if (k > tot) { 34 puts("NO"); continue; 35 } 36 37 for (int j = 0; j < 5; j++) { 38 int i = 0, x = tot / V[j].size(), now = x; 39 while (now < k) now += x, i++; 40 k -= i * x; 41 tot = x; 42 s[j] = V[j][i]; 43 } 44 s[5] = '\0'; 45 printf("%s\n", s); 46 } 47 return 0; 48 } 代码君（递推）
例题 10-9 uva 1636
题意：略
题解：略
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 int slove(string s) { 6 int n = s.length(), t1 = 0, t2 = 0; 7 for (int i = 0; i < n; i++) 8 if (s[i] == '0') { 9 t1++; 10 if (s[(i + 1) % n] == '0') t2++; 11 } 12 return t2 * n - t1 * t1; 13 } 14 15 int main() { 16 //freopen("case.in", "r", stdin); 17 string s; 18 while (cin >> s) { 19 int ans = slove(s); 20 if (!ans) puts("EQUAL"); 21 else if (ans > 0) puts("SHOOT"); 22 else puts("ROTATE"); 23 } 24 return 0; 25 } 代码君
例题10-10 uva 10491
题意：略
题解：略
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 int main() { 6 //freopen("case.in", "r", stdin); 7 int a, b, c; 8 while (cin >> a >> b >> c) { 9 printf("%.5lf\n", double(a * b + b * (b - 1)) / (a + b) / (a + b - c - 1)); 10 } 11 return 0; 12 } 代码君
例题 10-11 uva 11181
题意：略
题解：按照书上的描述进行枚举
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 const int maxn = 21; 6 int n, r, v[maxn]; 7 double p[maxn], pos[maxn], tot; 8 9 void dfs(int cur, int sum) { 10 if (sum + n - cur < r) return; 11 if (sum > r) return; 12 if (cur == n) { 13 if (sum == r) { 14 double temp = 1.0; 15 for (int i = 0; i < n; i++) 16 temp *= (v[i] ? p[i] : 1 - p[i]); 17 tot += temp; 18 for (int i = 0; i < n; i++) 19 if (v[i]) pos[i] += temp; 20 } 21 return; 22 } 23 v[cur] = 0; 24 dfs(cur + 1, sum); 25 v[cur] = 1; 26 dfs(cur + 1, sum + 1); 27 } 28 29 int main() { 30 //freopen("case.in", "r", stdin); 31 int tcase = 0; 32 while (scanf("%d%d", &n, &r) == 2 && n | r) { 33 for (int i = 0; i < n; i++) scanf("%lf", p + i); 34 tot = 0; 35 memset(pos, 0, sizeof pos); 36 dfs(0, 0); 37 printf("Case %d:\n", ++tcase); 38 for (int i = 0; i < n; i++) printf("%.6lf\n", pos[i] / tot); 39 } 40 return 0; 41 } 代码君
例题10-12 uva1637
题意：略
题解：略
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 const int maxs = 1953125; 6 char s[10][5][3]; 7 int vis[maxs], sta[10], base[10], tcase; 8 double dp[maxs]; 9 10 int decode() { 11 int ret = 0; 12 for (int i = 8; i >= 0; i--) ret = ret * 5 + sta[i]; 13 return ret; 14 } 15 16 double d() { 17 int x = decode(); 18 if (x == 0) return 1.0; 19 if (vis[x] == tcase) return dp[x]; 20 vis[x] = tcase; 21 double& ans = dp[x]; ans = 0; 22 int cnt = 0; 23 for (int i = 0; i < 9; i++) 24 for (int j = i + 1; j < 9; j++) 25 if (sta[i] && sta[j] && s[i][sta[i]][0] == s[j][sta[j]][0]) { 26 sta[i]--; sta[j]--; 27 ans += d(); 28 cnt++; 29 sta[i]++; sta[j]++; 30 } 31 if (cnt) ans /= cnt; 32 return ans; 33 } 34 35 int main() { 36 //freopen("case.in", "r", stdin); 37 tcase = 0; 38 while (~scanf("%s", s[0][1])) { 39 ++tcase; 40 for (int i = 0; i < 9; i++) 41 for (int j = 1; j <= 4; j++) { 42 if (i == 0 && j == 1) continue; 43 scanf("%s", s[i][j]); 44 } 45 for (int i = 0; i < 9; i++) sta[i] = 4; 46 printf("%.6lf\n", d()); 47 } 48 return 0; 49 } 代码君
例题10-13 uva580
题意：略
题解：这里我觉得书上的方法太麻烦了，所以用了dp[i][j]表示以i为结尾j个危险物的方案数，然后总方案减去即可，很简单的递推题。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 typedef long long ll; 6 const int maxn = 40; 7 ll dp[maxn][3]; 8 9 void init() { 10 dp[2][0] = 2; 11 dp[2][1] = dp[2][2] = dp[1][0] = dp[1][1] = 1; 12 for (int i = 3; i < maxn; i++) { 13 for (int j = 0; j <= 2; j++) dp[i][0] += dp[i - 1][j]; 14 dp[i][1] = dp[i - 1][0]; 15 dp[i][2] = dp[i - 1][1]; 16 } 17 } 18 19 int main() { 20 // freopen("case.in", "r", stdin); 21 init(); 22 int n; 23 while (cin >> n, n) { 24 ll ans = 0; 25 for (int i = 0; i <= 2; i++) ans += dp[n][i]; 26 cout << (1LL << n) - ans << endl; 27 } 28 } 代码君
例题10-14 uva 12034
题意：略
题解：略
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 typedef long long ll; 6 const int maxn = 1100, mod = 10056; 7 int f[maxn], c[maxn][maxn]; 8 9 void init() { 10 for (int i = 0; i < maxn; i++) { 11 c[i][0] = 1; 12 for (int j = 1; j <= i; j++) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod; 13 } 14 15 f[0] = f[1] = 1; 16 for (int i = 2; i < maxn; i++) 17 for (int j = 1; j <= i; j++) 18 f[i] = (f[i] + f[i - j] * c[i][j] % mod) % mod; 19 } 20 21 int main() { 22 // freopen("case.in", "r", stdin); 23 int T, tcase = 0; 24 cin >> T; 25 init(); 26 while (T--) { 27 int n; 28 scanf("%d", &n); 29 printf("Case %d: %d\n", ++tcase, f[n]); 30 } 31 return 0; 32 } 代码君
例题 10-15 uva 1638
题意：略
题解：略
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 typedef long long ll; 6 const int maxn = 21; 7 ll dp[maxn][maxn][maxn]; 8 9 void init() { 10 dp[1][1][1] = 1; 11 for (int i = 2; i < maxn; i++) 12 for (int l = 1; l <= i; l++) 13 for (int r = 1; r <= i; r++) 14 dp[i][l][r] = dp[i - 1][l - 1][r] + dp[i - 1][l][r - 1] + dp[i - 1][l][r] * (i - 2); 15 } 16 17 int main() { 18 // freopen("case.in", "r", stdin); 19 init(); 20 int T; 21 cin >> T; 22 while (T--) { 23 int n, l, r; 24 cin >> n >> l >> r; 25 cout << dp[n][l][r] << endl; 26 } 27 return 0; 28 } 代码君
例题 10-16 uva 12230
题意：简单的概率题
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 #define lson l, m, rt*2 6 #define rson m + 1, r, rt*2+1 7 #define xx first 8 #define yy second 9 10 typedef pair<int,int> pii; 11 typedef long long ll; 12 typedef unsigned long long ull; 13 14 int main() { 15 // freopen("case.in", "r", stdin); 16 int n, D, tcase = 0; 17 while (scanf("%d%d", &n, &D) == 2 && n + D) { 18 double res = 0; 19 int tot = 0; 20 for (int i = 0; i < n; i++) { 21 int p, l, v; 22 scanf("%d%d%d", &p, &l, &v); 23 res += 2.0 * l / v; 24 tot += l; 25 } 26 res += D - tot; 27 printf("Case %d: %.3lf\n\n", ++tcase, res); 28 } 29 return 0; 30 } 代码君
例题10-17 uva 1639
题意：略
题解：这里组合数是要用log优化，C（n，m） = F（n） / F（m） / F（n - m），然后就是两边求一个ln，得ln（C（n，m）） = ln（F（n）） - ln（F（m）） - ln（F（n - m）），然后double精度不够，要用long double来处理这个log。还有一点要注意的是当p = 0或者p = 1的时候直接输出n。
/*zhen hao*/ #include <bits/stdc++.h> using namespace std; #define lson l, m, rt*2 #define rson m + 1, r, rt*2+1 #define xx first #define yy second typedef pair<int,int> pii; typedef long long ll; typedef unsigned long long ull; const int maxn = 4e5 + 100; long double F[maxn]; void init() { F[0] = 0; for (int i = 1; i < maxn; i++) { F[i] = F[i - 1] + log(1.0 * i); } // cout << exp(F[5] - F[3] - F[2]) << endl; } double get_res(int n, int i, double p, double q) { return F[2 * n - i] - F[n - i] - F[n] + double(n + 1) * log(p) + double(n - i) * log(q); } int main() { // freopen("case.in", "r", stdin); init(); int n, tcase = 0; double p; while (scanf("%d%lf", &n, &p) == 2) { double res = 0; for (int i = 1; i <= n; i++) { res += (exp(get_res(n, i, p, 1 - p)) + exp(get_res(n, i, 1 - p, p))) * i; } if (p == 1 || p == 0) res = n; printf("Case %d: %.6lf\n", ++tcase, res); } return 0; } 代码君
例题10-18 uva10288
题意：略
题解：这里复述一下那个化简公式的过程，实际上白书的期望题也有说到：
当t = 1， p = （1 - s）；
当t = 2， p = （1 - s） * s；
当t = 3， p = （1 - s） * s2；
然后设期望为E，则
E = （1 - s） * （1 + s + s2 + …… + sn） （1）
sE = （1 - s） * （s + s2 + s3 + …… + sn） （2）
（1） - （2） 得
E = 1 + s + s2 + …… + sn = 1 / （1 - s）；
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 #define lson l, m, rt*2 6 #define rson m + 1, r, rt*2+1 7 #define xx first 8 #define yy second 9 10 typedef pair<int,int> pii; 11 typedef long long ll; 12 typedef unsigned long long ull; 13 14 ll gcd(ll a, ll b) { 15 if (!b) return a; 16 else return gcd(b, a % b); 17 } 18 19 int cal(ll x) { 20 int ret = 0; 21 while (x) { 22 ret++; 23 x /= 10; 24 } 25 return ret; 26 } 27 28 int main() { 29 // freopen("case.in", "r", stdin); 30 int n; 31 while (~scanf("%d", &n)) { 32 ll res1, res2; 33 res1 = res2 = 0; 34 for (int k = 0; k < n; k++) { 35 ll a = n, b = n - k; 36 if (res1 == 0) { 37 res1 = a; res2 = b; 38 } else { 39 ll ta = res1, tb = res2, d; 40 res1 = a * tb + b * ta; 41 res2 = b * tb; 42 d = gcd(res1, res2); 43 res1 /= d; 44 res2 /= d; 45 } 46 } 47 if (res1 % res2 == 0) { 48 cout << res1 / res2 << endl; 49 } else { 50 ll x = res1 / res2, y = res1 - res2 * x, z = res2; 51 int c1 = cal(x), c2 = cal(z); 52 for (int i = 0; i <= c1; i++) putchar(' '); 53 cout << y << '\n' << x << ' '; 54 for (int i = 0; i < c2; i++) putchar('-'); 55 puts(""); 56 for (int i = 0; i <= c1; i++) putchar(' '); 57 cout << z << endl; 58 } 59 } 60 return 0; 61 } 代码君
例题 10-19 uva 10346
题意：略
题解：直接按照书上给的公式来码，然后注意如果这个s接近于的话，那就输出1，如果这个a * b < s，就直接输出0；
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 #define ld long double 6 7 const double eps = 1e-6; 8 9 int main() { 10 // freopen("case.in", "r", stdin); 11 int T; 12 cin >> T; 13 while (T--) { 14 double a, b, s, res; 15 scanf("%lf%lf%lf", &a, &b, &s); 16 if (a * b < s) res = 0; 17 else if (abs(s) < eps) res = 1.0; 18 else res = (a * b - s - s * log(a * b / s)) / (a * b); 19 printf("%.6f%%\n", res * 100); 20 } 21 return 0; 22 } 代码君
例题10-20 uva 10900
题意：略
题解：这题可以算是难题了，但是书上的分析也很透彻，也就是递推算出最有策略下的奖金期望，当i = n时，那么肯定直接答对的话就是拿2 ^ n，然后对于上一道题，分两种情况，给出一个临界概率p0，也就是t~p0就直接放弃，p0~1就直接答题，然后只有答对才有奖金，那么就还要再乘多一个平均能够答对的概率，也就是（p0 + 1） / 2；最终递推到第0题就是答案，代码很简单，但是思路很复杂，这也许是大部分数学题目的特点。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 const int maxn = 40; 6 int n; 7 double t; 8 9 double d(int x) { 10 if (x == n) return double(1 << x); 11 double temp = d(x + 1); 12 double p0 = max(t, (1 << x) / temp); 13 double p = (p0 - t) / (1 - t), q = 1 - p; 14 return p * (1 << x) + q * temp * (1 + p0) / 2; 15 } 16 17 int main() { 18 // freopen("case.in", "r", stdin); 19 while (cin >> n >> t, n) { 20 printf("%.3f\n", d(0)); 21 } 22 return 0; 23 } 代码君
例题10-21 uva 11971
题意：略
题解：略
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 typedef long long ll; 6 7 ll gcd(ll a, ll b) { 8 if (!b) return a; 9 else return gcd(b, a % b); 10 } 11 12 int main() { 13 // freopen("case.in", "r", stdin); 14 int T, tcase = 0; 15 cin >> T; 16 while (T--) { 17 ll n, k, a, b, d; 18 cin >> n >> k; 19 a = ((1LL << k) - k - 1); 20 b = 1LL << k; 21 if (a == 0) b = 1; 22 else { 23 d = gcd(a, b); 24 a /= d; 25 b /= d; 26 } 27 printf("Case #%d: %lld/%lld\n", ++tcase, a, b); 28 } 29 return 0; 30 } 代码君
转载于:https://www.cnblogs.com/zhenhao1/p/5548038.html
