本文主要是介绍算法竞赛入门经典(第二版)-刘汝佳-第十章 数学概念与方法 例题（16/29），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 说明
- 例题
- 例10-1
- 例10-2
- 例10-3
- 例10-4
- 例10-5 （未尝试）
- 例10-6
- 例10-7
- 例10-8
- 例10-9
- 例10-10
- 例10-11
- 例10-12
- 例10-13
- 例10-14
- 例10-15
- 例10-16 （未尝试）
- 例10-17 （未尝试）
- 例10-18 （未尝试）
- 例10-19 （未尝试）
- 例10-20 （未尝试）
- 例10-21 （未尝试）
- 例10-22
- 例10-23 （未尝试）
- 例10-24
- 例10-25 （其后皆未尝试）
- 例10-26
- 例10-27
- 例10-28
- 例10-29
说明
本文是我对第十章29道例题的练习总结，建议配合紫书——《算法竞赛入门经典（第2版）》阅读本文。
先把通过的代码贴上，文字性说明以后再补。
例题
例10-1
题意
思路
代码
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;typedef unsigned long long ULL;#define FOR1(i, a, b) for (int i = (a); i <= (b); i++)
#define FOR2(i, a, b) for (int i = (a); i >= (b); i--)const int MAXN = 1005;ULL a, b;
int n, n2;
//int firsti;
int F[MAXN][6*MAXN], C[MAXN * MAXN], P[MAXN];int fast_mod(int a1, ULL b1, int p) {if (b1 == 0) return 1;int res = fast_mod(a1, b1 / 2, p);res = res * res % p;if (b1 & 1) res *= a1;return res % p;
}int Quick_pow_mod(int x, ULL y, int mod){int ans = 1;while (y){if (y & 1) ans = (int)((ans * x) % mod);x = (x * x) % mod;y >>= 1;}return ans;
}void pre_process()
{FOR1(n, 2, 1000) {F[n][0] = 0; F[n][1] = 1;memset(C, 0, sizeof(C));C[0 + 1*MAXN] = 1;FOR1(i, 2, MAXN*MAXN) {F[n][i] = (F[n][i - 1] + F[n][i - 2]) % n;int &c = C[F[n][i - 1] + F[n][i] * MAXN];if (c) {P[n] = i - c;break;}c = i;}if (n == 1000)n = 1000;}
}int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifpre_process();int T;scanf("%d", &T);FOR1(t, 1, T) {scanf("%llu %llu %d", &a, &b, &n);int ans = 0;if (n > 1 && a > 0) {//int k = fast_mod(a%P[n], b, P[n]);int k = Quick_pow_mod(a%P[n], b, P[n]);//if (k < firsti) k += p;ans = F[n][k];}printf("%d\n", ans);}return 0;
}
例10-2
题意
思路
代码
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;typedef unsigned long long ULL;#define FOR1(i, a, b) for (int i = (a); i <= (b); i++)
#define FOR2(i, a, b) for (int i = (a); i >= (b); i--)const int MAXN = 101;int T;
int X[2*MAXN];
int a0, b0;
vector<int> B, C;int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifscanf("%d", &T);FOR1(t, 1, T)scanf("%d", &X[t]);a0 = 0;b0 = 0;FOR1(a, 0, 10000) {B.clear();FOR1(b, 0, 10000)B.push_back(b);FOR1(t, 1, T - 1) {int a2x = ((a * a) % 10001 * X[t]) % 10001;FOR2(j, B.size() - 1, 0) {if ((a2x + B[j] * (a + 1)) % 10001 != X[t + 1]) {B[j] = B[B.size() - 1];B.pop_back();int count = B.size();}}/*//vector是连续存储空间,只提供高效的尾部删除方法pop_back() ,在中间删除的效率很低，因此该代码不行for (vector<int>::iterator it = B.begin(); it != B.end(); ) {if ((ax2 + (*it) * (X[t] + 1)) % 10001 != X[t + 1])it = B.erase(it); else++it;}*/if (B.empty()) break;}if (!B.empty()) {a0 = a;b0 = B[0];break;}}//printf("%d %d\n", a0, b0);FOR1(t, 1, T)printf("%d\n", (a0 * X[t] + b0) % 10001);return 0;
}
例10-3
题意
思路
代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;typedef unsigned long long ULL;#define FOR1(i, a, b) for (int i = (a); i <= (b); i++)
#define FOR2(i, a, b) for (int i = (a); i >= (b); i--)int p, q, r, s;int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifwhile (cin >> p >> q >> r >> s) {if (q > p - q) q = p - q;if (s > r - s) s = r - s;double res = 1;while (q > 0 || s > 0) {if (s == 0 || q > 0 && res < 1) {res = res * p / q;p--;q--;}else {res = res / r * s;r--;s--;}}printf("%.5lf\n", res);} return 0;
}
例10-4
题意
思路
代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;#define FOR1(i, a, b) for (int i = (a); i <= (b); i++)
#define FOR2(i, a, b) for (int i = (a); i >= (b); i--)const int MAXP = 60000;int n;
//int isprime[MAXP]; //并不需要
vector<int> yinshu;/*
void pre_process_sushu() {memset(isprime, 0x3f, sizeof(isprime));FOR1(i, 2, MAXP) {if (isprime[i]) {for (int j = i * 2; j <= MAXP; j += i)isprime[j] = 0;}}
}*/int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifint t = 0;while (cin >> n && n) {long long res = 0;int count = 0;int n2 = sqrt(n) + 1;FOR1(i, 2, n2) {if (n == 1) break;if (n % i == 0) {int add = 1;while (n % i == 0) {n /= i;add *= i;}res += add;count++;}}if (n != 1) {res += n;count++;}if (count == 0) res = 2;if (count == 1) res += 1;printf("Case %d: %lld\n", ++t, res);}return 0;
}
例10-5 （未尝试）
题意
思路
代码
例10-6
题意
思路
代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;#define FOR1(i, a, b) for (int i = (a); i <= (int)(b); i++)
#define FOR2(i, a, b) for (int i = (a); i >= (int)(b); i--)const int MAXN = 100000;int n, m;
vector<int> prime, e;
int neg_count;void process_prime(int m) {neg_count = 0;prime.clear();e.clear();int m2 = sqrt(m) + 1;FOR1(i, 2, m2) {int k = 0;while (m % i == 0) {m /= i;k++;}if (k) {prime.push_back(i);e.push_back(-k);neg_count++;}}if (m > 1) {prime.push_back(m);e.push_back(-1);neg_count++;}
}void add_exp(int x, int d) {//for (int j = 0; j <= ((int)prime.size() - 1); j++) {FOR1(j, 0, prime.size() - 1) {int p = prime[j];if (x < p) break;while (x % p == 0) {x /= p;e[j] += d;if (e[j] == -1 && d == -1) neg_count++;if (e[j] == 0 && d == 1) neg_count--;}}
}int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifwhile (cin >> n >> m) {process_prime(m);vector<int> res;n--;FOR1(i, 0, n) {if (i) {add_exp(n - i + 1, 1);add_exp(i, -1);}if (neg_count == 0)res.push_back(i + 1);}printf("%d\n", res.size());if (res.size() == 0) printf("\n");else {FOR1(i, 0, res.size() - 1)printf("%d%c", res[i], (i == res.size() - 1) ? '\n' : ' ');}}return 0;
}
例10-7
题意
思路
代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;#define FOR1(i, a, b) for (int i = (a); i <= (int)(b); i++)
#define FOR2(i, a, b) for (int i = (a); i >= (int)(b); i--)const int MAXN = 50000;int n;
int phi[MAXN + 1], res[MAXN + 1];void pre_process() {FOR1(i, 1, MAXN)phi[i] = i;int prime[MAXN + 1];memset(prime, 0x3f, sizeof(prime));FOR1(i, 2, MAXN) {if (prime[i]) {for (int j = i; j <= MAXN; j += i) {if (j > i) prime[j] = 0;phi[j] = phi[j] /i * (i - 1);}}}res[1] = 1;FOR1(i, 2, MAXN)res[i] = res[i-1] + phi[i] * 2;
}//1、预先计算好所有的n。2、求每个数的所有素因子，用欧拉公式，筛法作为程序主框架。
int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifpre_process();while (cin >> n && n) {printf("%d\n", res[n]);}return 0;
}
例10-8
题意
思路
代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;#define FOR1(i, a, b) for (int i = (a); i <= (int)(b); i++)
#define FOR2(i, a, b) for (int i = (a); i >= (int)(b); i--)int k;
char s1[7][7], s2[7][7];
vector<char> same[5];
int cnt[5], mult[5];int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifint T;cin >> T;FOR1(t, 1, T) {scanf("%d", &k);char st[7];FOR1(i, 0, 5) {scanf("%s", st);FOR1(j, 0, 4) s1[j][i] = st[j];}FOR1(i, 0, 5) {scanf("%s", st);FOR1(j, 0, 4) s2[j][i] = st[j];}FOR1(j, 0, 4) {same[j].clear();sort(s1[j], s1[j] + 6);sort(s2[j], s2[j] + 6);int i1 = 0, i2 = 0;while (i1 < 6 && i2 < 6) {if (s1[j][i1] == s2[j][i2]) {if (same[j].size() == 0 || same[j][same[j].size() - 1] != s1[j][i1])same[j].push_back(s1[j][i1]);i1++; i2++;}else if (s1[j][i1] < s2[j][i2])i1++;elsei2++;}cnt[j] = same[j].size();}mult[4] = 1;FOR2(j, 3, 0)mult[j] = mult[j + 1] * cnt[j + 1];int res[5];k--;bool ok = true;if (mult[0] == 0 || cnt[0] == 0) ok = false;if (ok == true) {FOR1(j, 0, 4) {res[j] = k / mult[j];k %= mult[j];}}if (ok == false || res[0] >= cnt[0])printf("NO");else {FOR1(j, 0, 4)printf("%c", same[j][res[j]]);}printf("\n");}return 0;
}
例10-9
题意
思路
代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;#define FOR1(i, a, b) for (int i = (a); i <= (int)(b); i++)
#define FOR2(i, a, b) for (int i = (a); i >= (int)(b); i--)int n;
char s[101];int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifwhile (scanf("%s", s) != EOF) {n = strlen(s);int p1 = 0, p2 = 0;FOR1(i, 0, n - 1) {if (s[i] == '0' && s[(i + 1) % n] == '0')p1++;if (s[i] == '0')p2++;}int res = p1 * n - p2 * p2;if (res > 0)printf("SHOOT\n");else if (res < 0)printf("ROTATE\n");elseprintf("EQUAL\n");}return 0;
}
例10-10
题意
思路
代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;#define FOR1(i, a, b) for (int i = (a); i <= (b); i++)
#define FOR2(i, a, b) for (int i = (a); i >= (b); i--)int a, b, c;int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifwhile (cin >> a >> b >> c) {double p = ((double)a * b + b * (b - 1)) / ((a + b) * (a + b - c - 1));printf("%.5lf\n", p);}return 0;
}
例10-11
题意
思路
代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;#define FOR1(i, a, b) for (int i = (a); i <= (b); i++)
#define FOR2(i, a, b) for (int i = (a); i >= (b); i--)int n, r;
double p[21];
double res[21];double solve(int m, int m1, int k) { //q表示当前概率，m表示计算到第几步，m1表示这m个人中有m1个已经买了，k表示第k个人确定会买，k=0表示没有确定if (m1 > r) return 0;m++;if (m == k) return p[m] * solve(m, m1 + 1, k);if (m > n) {if (m1 == r) return 1;else return 0;}if (m1 == r) //已经有r人买了，后面的人不会再买return (1 - p[m]) * solve(m, m1, k);return p[m] * solve(m, m1 + 1, k) + (1 - p[m]) * solve(m, m1, k);
}int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifint t = 0;while (cin >> n >> r && n) {FOR1(i, 1, n)cin >> p[i];FOR1(i, 0, n)res[i] = solve(0, 0, i);printf("Case %d:\n", ++t); FOR1(i, 1, n)printf("%.6lf\n", res[i] / res[0]);}return 0;
}
例10-12
题意
思路
代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;#define FOR1(i, a, b) for (int i = (a); i <= (b); i++)
#define FOR2(i, a, b) for (int i = (a); i >= (b); i--)const int MAXD = 1953126; //5^9 = 1953125char s[9][5];
int e[9];
int state[9];
double dp[MAXD];void pre_process5() {FOR2(i, 8, 0) {if (i == 8) e[i] = 1;else e[i] = e[i+1] * 5;}
}double solve(int code) {if (dp[code] < 1.5) //表示已访问过return dp[code];vector<int> left;FOR1(i, 0, 8)if (state[i]) left.push_back(i);int cnt = left.size();if (cnt == 0) return dp[code] = 1;dp[code] = 0;int tot = 0;FOR1(i, 0, cnt-1) {int &si = state[left[i]];FOR1(j, i + 1, cnt-1) {int &sj = state[left[j]];if (s[left[i]][si-1] == s[left[j]][sj-1]) {si--; sj--;dp[code] += solve(code - e[left[i]] - e[left[j]]);si++; sj++;tot++;}}}if (tot) dp[code] = dp[code] / tot;return dp[code];
}int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifpre_process5();char s0[3];while (scanf("%s", s0) != EOF) {FOR1(i, 0, 8) {state[i] = 4;FOR1(j, 0, 3) {if (i || j) scanf("%s", s0);s[i][j] = s0[0];}}FOR1(i, 1, MAXD)dp[i] = 10; //表示未访问，因为概率不可能大于1dp[0] = 1;printf("%.6lf\n", solve(e[0] * 5 - 1));}return 0;
}
例10-13
题意
思路
代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;#define FOR1(i, a, b) for (int i = (a); i <= (b); i++)
#define FOR2(i, a, b) for (int i = (a); i >= (b); i--)int n;
int f[31];void pre_process() {memset(f, 0, sizeof(f));f[3] = 1;FOR1(i, 4, 30)f[i] = f[i - 1] * 2 + (1 << (i - 4)) - f[i - 4];
}int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifpre_process();while (scanf("%d", &n) && n) { printf("%d\n", f[n]);}return 0;
}
例10-14
题意
思路
代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;#define FOR1(i, a, b) for (int i = (a); i <= (int)(b); i++)
#define FOR2(i, a, b) for (int i = (a); i >= (int)(b); i--)const int MOD = 10056;
const int MAXN = 1000;int n;
int C[MAXN + 1][MAXN + 1], F[MAXN + 1];// 注意不能用乘除来推，而要用这个公式：C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
void pre_process() {C[0][0] = 1;FOR1(n, 1, MAXN) {C[n][0] = 1;FOR1(i, 1, n) {C[n][i] = (C[n - 1][i] + C[n - 1][i - 1]) % MOD;}}F[0] = 1;FOR1(n, 1, MAXN) {F[n] = 0;FOR1(i, 1, n) {F[n] = (F[n] + C[n][i] * F[n - i]) % MOD;}}
}int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifpre_process();int T;cin >> T;FOR1(t, 1, T) {cin >> n;printf("Case %d: %d\n", t, F[n]);}return 0;
}
例10-15
题意
思路
代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;#define FOR1(i, a, b) for (int i = (a); i <= (int)(b); i++)
#define FOR2(i, a, b) for (int i = (a); i >= (int)(b); i--)int n, L, R;long long solve(int k, int l, int r) {if (l <= 0 || r <= 0 || k < l+r-1) return 0;if (k == 1) {if (l == 1 && r == 1) return 1;return 0;}if (k == 2 && l == 1 && r == 1)k = k;long long res = solve(k - 1, l - 1, r) + (k-2) * solve(k - 1, l, r) + solve(k - 1, l, r - 1);//printf("%d %d %d : %d\n", k, l, r, res);return res;
}int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifint T;cin >> T;FOR1(t, 1, T) {cin >> n >> L >> R;printf("%lld\n", solve(n, L, R)); //从长到短安排，第一个参数表示已经安排好的数量，后两个参数表示左看和右看能看到的数量}return 0;
}
例10-16 （未尝试）
题意
思路
代码
例10-17 （未尝试）
题意
思路
代码
例10-18 （未尝试）
题意
思路
代码
例10-19 （未尝试）
题意
思路
代码
例10-20 （未尝试）
题意
思路
代码
例10-21 （未尝试）
题意
思路
代码
例10-22
题意
思路
代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;typedef vector<int> VINT;#define FOR1(i, a, b) for (int i = (a); i <= (int)(b); i++)
#define FOR2(i, a, b) for (int i = (a); i >= (int)(b); i--)int a, b;VINT solve(int x) {x++; //因为算法统计的是小于该数的所有数VINT vx;FOR1(j, 0, 9) vx.push_back(0);int k = 1, e = 0, k10;FOR1(i, 1, 8) {k10 = k * 10;if (x < k10) break;FOR1(j, 0, 9) //算低位vx[j] += (k-k/10) * (i-1);FOR1(j, 1, 9) //算当前位vx[j] += k;k *= 10; e++;}VINT vt;FOR1(j, 0, 9) vt.push_back(0);bool first = true;while (k) {int t = x / k;if (first) {FOR1(j, 0, 9) //算低位vx[j] += k / 10 * e * (t-1);FOR1(j, 1, t - 1) //算当前位vx[j] += k;first = false;}else {FOR1(j, 0, 9) //算低位vx[j] += k / 10 * e * t;t = t;FOR1(j, 0, t - 1) //算当前位vx[j] += k;t = t;FOR1(j, 0, 9) //算高位vx[j] += k * vt[j] * t;t = t;}vt[x / k]++;x %= k;k /= 10;e--;}return vx;
}int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifwhile (cin >> a >> b && (a || b)) {if (a < b) swap(a, b);b--;VINT va = solve(a);VINT vb = solve(b);FOR1(i, 0, 9)printf("%d%c", va[i] - vb[i], i < 9 ? ' ' : '\n');}return 0;
}
例10-23 （未尝试）
题意
思路
代码
例10-24
题意
思路
说明：代码是汝佳写的。
我之前用另外的方法做，虽然能通过题目中测试用例，但提交后WA了。汝佳的代码极其简单，我也就没有再自己重复写，直接拿过来了。
代码
#include<cstdio>
int main() {int h, w;char s[999];while(scanf("%d%d", &h, &w) == 2) {int ans = 0, c = 0;while(h--) {scanf("%s", s);int in = 0;for(int i = 0; i < w; i++) {if(s[i] == '/' || s[i] == '\\') { c++; in = !in; }else if(in) ans++;}}printf("%d\n", ans + c/2);}return 0;
}
例10-25 （其后皆未尝试）
题意
思路
代码
例10-26
题意
思路
代码
例10-27
题意
思路
代码
例10-28
题意
思路
代码
例10-29
题意
思路
代码
这篇关于算法竞赛入门经典(第二版)-刘汝佳-第十章 数学概念与方法 例题（16/29）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
