算法竞赛入门经典(第二版)-刘汝佳-第十章 数学概念与方法 习题（12/51）

2024-04-02 01:48
文章标签 算法 方法 入门 概念 经典 51 竞赛 数学 第十章 第二 习题 刘汝佳

本文主要是介绍算法竞赛入门经典(第二版)-刘汝佳-第十章 数学概念与方法 习题（12/51），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 说明
  • 习题
    • 习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
    • 习10-30
    • 习10-31
    • 习10-32
    • 习10-33
    • 习10-34
    • 习10-35
    • 习10-36
    • 习10-37
    • 习10-38
    • 习10-39
    • 习10-40
    • 习10-41
    • 习10-42
    • 习10-43
    • 习10-44
    • 习10-45
    • 习10-46
    • 习10-47
    • 习10-48
    • 习10-49
    • 习10-50
    • 习10-51

说明

本文是我对第十章51道习题的练习总结，建议配合紫书——《算法竞赛入门经典（第2版）》阅读本文。
先贴代码，文字性题解回头再补充。

习题

习10-1

题意

思路

代码

#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 MAX = 100;int A[10][10];int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifint T;cin >> T;FOR1(t, 1, T) {FOR1(i, 0, 8) {if (i & 1) continue;FOR1(j, 0, i) {if (j & 1) continue;cin >> A[i][j];}}FOR1(i, 0, 6) {if (i & 1) continue;FOR1(j, 0, i) {if (j & 1) continue;A[i + 2][j + 1] = (A[i][j] - A[i + 2][j] - A[i + 2][j + 2]) / 2;A[i + 1][j] = A[i + 2][j] + A[i + 2][j + 1];A[i + 1][j + 1] = A[i + 2][j + 1] + A[i + 2][j + 2];}}FOR1(i, 0, 8) {FOR1(j, 0, i-1) {printf("%d ", A[i][j]);}printf("%d\n", A[i][i]);}}return 0;
}

习10-2

题意

思路

代码

习10-3

题意

思路

代码

习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 <= (int)(b); i++)
#define FOR2(i, a, b) for (int i = (a); i >= (int)(b); i--)const int MAX = 1299709+100000;//确保下一个素数被包含int n;
int isprime[MAX];
vector<int> prime;void process_prime() {memset(isprime, 0x3f, sizeof(isprime));isprime[1] = 0;FOR1(i, 2, MAX) {if (isprime[i]) {prime.push_back(i);for (int j = i * 2; j <= MAX; j += i) {isprime[j] = 0;}}}
}int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifprocess_prime();while (cin >> n && n) {if (isprime[n]) {printf("0\n", n);continue;}int s = prime.size();FOR1(i, 0, s - 1) {if (prime[i] > n) {printf("%d\n", prime[i] - prime[i - 1]);break;}}}return 0;
}

习10-5

题意

思路

代码

#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 = 1120;
const int MAXP = 187; //计算得出最多有187个素数
const int MAXK = 14; //计算得出最多有187个素数int n, k, ans;
int isprime[MAXN+1];
vector<int> prime;
//int dp[MAXP + 1][MAXK + 1][MAXN + 1]; //dp[i][j][m]表示前i个素数中挑出j个素数其值为m的可能数，实际上第一维可以省略
int dp[MAXK + 1][MAXN + 1]; //dp[j][m]表示前i个素数中挑出j个素数其值为m的可能数，第一维已经省略void process_prime() {memset(isprime, 0x3f, sizeof(isprime));isprime[1] = 0;FOR1(i, 2, MAXN) {if (isprime[i]) {prime.push_back(i);for (int j = i * 2; j <= MAXN; j += i) {isprime[j] = 0;}}}
}int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifprocess_prime();while (cin >> n >> k && n) {memset(dp, 0, sizeof(dp));dp[0][0] = 1;FOR1(i, 1, MAXP) {if (prime[i-1] > n) break;int pi = prime[i-1];FOR2(j, min(i, k), 1) {FOR2(m, n, pi) {dp[j][m] += dp[j - 1][m - pi];}}}printf("%d\n", dp[k][n]);}return 0;
}

习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 MAX = 10000;//确保下一个素数被包含int n, p; //p表示prime中素数个数
int isprime[MAX + 1];
vector<int> prime;void process_prime() {memset(isprime, 0x3f, sizeof(isprime));isprime[1] = 0;FOR1(i, 2, MAX) {if (isprime[i]) {prime.push_back(i);for (int j = i * 2; j <= MAX; j += i) {isprime[j] = 0;}}}p = prime.size();
}int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifprocess_prime();while (cin >> n && n) {int res = 0;int i = 0, j = 0;int s = prime[0];while (j < p) {if (s == n)	{res++;if (j == p - 1) break;s += prime[++j];}else if (s < n) {if (j == p - 1) break;s += prime[++j];}else {if (i == p - 1) break;s -= prime[i++];if (i > j)s += prime[++j];}}printf("%d\n", res);}return 0;
}

习10-7

题意

思路

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;typedef long long LL;#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 LL MAX = 1000000;
const LL LMAX = MAX*MAX;LL a[2];
int p; //p表示oneprime中素数个数
int isprime[MAX + 1];
vector<LL> oneprime;void process_prime() {memset(isprime, 0x3f, sizeof(isprime));isprime[1] = 0;FOR1(i, 2, MAX) {if (isprime[i]) {for (LL j = (LL)i * i; j <= LMAX; j *= i)oneprime.push_back(j);for (int j = i * 2; j <= MAX; j += i) {isprime[j] = 0;}}}sort(oneprime.begin(), oneprime.end());p = oneprime.size();
}int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifprocess_prime();int T;cin >> T;FOR1(t, 1, T) {cin >> a[0] >> a[1];a[1]++;int res[2];FOR1(j, 0, 1) {FOR1(i, 0, p - 1) {if (oneprime[i] >= a[j]) {res[j] = i;break;}}}printf("%d\n", res[1] - res[0]);}return 0;
}

习10-8

题意

思路

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;typedef long long LL;#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 LL MAX = 500000;
const LL LMAX = MAX*MAX;int n, n0;
map<LL, int> oneprime;void process_prime() {FOR1(i, 2, MAX) {if (!oneprime.count(i)) {int k = 2;for (LL j = (LL)i * i; j <= LMAX; j *= i, k++)if (!oneprime.count(j)) oneprime[j] = k;}}
}int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifprocess_prime();while (cin >> n && n) {if (n == (-(1<<30) - (1<<30))) {printf("31\n");continue;}n0 = abs(n);if (oneprime.count(n0)) {int ans = oneprime[n0];if (n < 0) {while (ans % 2 == 0) ans >>= 1;}printf("%d\n", ans);}elseprintf("1\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--)//const int MAXN2 = 1e9;
const int MAXN = 40000;int L, U;
int isprime[MAXN+1];
vector<int> prime;
int resn, resi;void process_prime() {memset(isprime, 0x3f, sizeof(isprime));isprime[1] = 0;FOR1(i, 2, MAXN) {if (isprime[i]) {prime.push_back(i);for (int j = i * 2; j <= MAXN; j += i) {isprime[j] = 0;}}}
}int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifprocess_prime();int T;cin >> T;FOR1(t, 1, T) {cin >> L >> U;resn = L, resi = 0;FOR1(k, L, U) {int k1 = k;int ik = k1 - L;int res = 1;int k2 = sqrt(k1) + 1;int pcnt = prime.size();FOR1(j, 0, pcnt-1) {int mult = 1;int pj = prime[j];if (k1 == 1) break;while (k1 % pj == 0) {k1 /= pj;mult++;}res *= mult;}if (k1 > 1) //说明还有约数res *= 2;if (res > resi) {resn = k;resi = res;}}printf("Between %d and %d, %d has a maximum of %d divisors.\n", L, U, resn, resi);}return 0;
}

习10-10

题意

思路

代码

习10-11

题意

思路

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
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 = 10000;int n;
string s[3];string add(string s1, string s2) {string sum;int up = 0;int l1 = s1.size(), l2 = s2.size();FOR1(i, 0, MAXN) {if (i >= l1 && i >= l2) {if (up) sum += (char)(up + 48);break;}int a1 = (i < l1) ? s1[i]-48 : 0;int a2 = (i < l2) ? s2[i]-48 : 0;up = up + a1 + a2;sum += (char)(up % 10 + 48);up /= 10;}return sum;
}int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifwhile (cin >> n) {s[1] = "1";s[2] = "2";FOR1(i, 0, n - 3) {s[0] = s[1];s[1] = s[2];s[2] = add(s[0], s[1]);}s[1] = add(s[0], s[2]);int scnt = s[1].size();FOR2(i, scnt - 1, 0)printf("%c", s[1][i]);printf("\n");}return 0;
}

习10-12

题意

思路

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
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;
double F[MAXN + 1];void pre_process() {F[1] = 1;F[2] = 0.5;FOR1(i, 2, MAXN - 1)F[i + 1] = F[i] * (2 * i - 1) / 2 / i;
}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("%.4lf\n", 1 - F[n / 2]);}return 0;
}

习10-13

题意

思路

代码

习10-14

题意

思路

代码

习10-15

题意

思路

代码

习10-16

题意

思路

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
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 = 1000;int n;
string S[1001];string add(string s1, string s2) {string sum;int up = 0;int l1 = s1.size(), l2 = s2.size();FOR1(i, 0, MAXN) {if (i >= l1 && i >= l2) {if (up) sum += (char)(up + 48);break;}int a1 = (i < l1) ? s1[i] - 48 : 0;int a2 = (i < l2) ? s2[i] - 48 : 0;up = up + a1 + a2;sum += (char)(up % 10 + 48);up /= 10;}return sum;
}void pre_process() {S[1] = "0";S[2] = "1";S[3] = "1";FOR1(i, 4, MAXN)S[i] = add(S[i-2], add(S[i-1], S[i-2]));
}int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifpre_process();while (cin >> n) {int scnt = S[n].size();FOR2(i, scnt - 1, 0)printf("%c", S[n][i]);printf("\n");}return 0;
}

习10-17

题意

思路

代码


#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;const int N = 1000001;bool isPrime[N+1];
bool isSemi[N+1];
int countSemi[N/4+1];void initPrime()
{   int i;for (i = 0; i <= N; i ++)isPrime[i] = true;isPrime[0] = isPrime[1] = false;for (i = 5; i <= N; i += 4) {if (isPrime[i]) {if (i > (int)sqrt((double)N)) continue;for (int j = i*i; j <= N; j += 4*i)isPrime[j] = false;}}
}void initSemi()
{int i, j;for (i = 1; i <= N; i += 4) {isSemi[i] = false;countSemi[i/4] = 0;}for (i = 5; i <= N; i += 4) {if (i > (int)sqrt((double)N)) break;for (j = i; j <= N; j += 4) {if (i * j > N) break;if (isPrime[i] && isPrime[j])isSemi[i * j] = true;}}for (i = 5; i <= N; i += 4) {countSemi[i/4] = countSemi[i/4-1];if (isSemi[i])countSemi[i/4] ++;}
}int main(void)
{int n;initPrime();initSemi();while (cin >> n && n) {printf("%d %d\n", n, countSemi[n/4]);}return 0;
}

习10-18

题意

思路

代码

习10-19

题意

思路

代码

习10-20

题意

思路

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
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 MAXM = 2000;int n, m;
int u[MAXM], d[MAXM];int main() {
#ifdef CODE_LIANGfreopen("datain.txt", "r", stdin);freopen("dataout.txt", "w", stdout);
#endifwhile (cin >> n >> m) {int ans = -1, minfloor = 0x3f3f3f3f;FOR1(i, 0, m - 1) {cin >> u[i] >> d[i];int floor = (n*u[i]) - (n*u[i] - 1) / (u[i] + d[i]) * (u[i] + d[i]);if (floor < minfloor) {ans = i;minfloor = floor;}}printf("%d\n", minfloor);}return 0;
}

习10-21

题意

思路

代码

习10-22

题意

思路

代码

习10-23

题意

思路

代码

习10-24

题意

思路

代码

习10-25

题意

思路

代码

习10-26

题意

思路

代码

习10-27

题意

思路

代码

习10-28

题意

思路

代码

习10-29

题意

思路

代码

习10-30

题意

思路

代码

习10-31

题意

思路

代码

习10-32

题意

思路

代码

习10-33

题意

思路

代码

习10-34

题意

思路

代码

习10-35

题意

思路

代码

习10-36

题意

思路

代码

习10-37

题意

思路

代码

习10-38

题意

思路

代码

习10-39

题意

思路

代码

习10-40

题意

思路

代码

习10-41

题意

思路

代码

习10-42

题意

思路

代码

习10-43

题意

思路

代码

习10-44

题意

思路

代码

习10-45

题意

思路

代码

习10-46

题意

思路

代码

习10-47

题意

思路

代码

习10-48

题意

思路

代码

习10-49

题意

思路

代码

习10-50

题意

思路

代码

习10-51

题意

思路

代码

这篇关于算法竞赛入门经典(第二版)-刘汝佳-第十章 数学概念与方法 习题（12/51）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/868667。

相关文章

闲置电脑也能活出第二春？鲁大师AiNAS让你动动手指就能轻松部署

闲置电脑也能活出第二春？鲁大师AiNAS让你动动手指就能轻松部署

对于大多数人而言，在这个“数据爆炸”的时代或多或少都遇到过存储告急的情况，这使得“存储焦虑”不再是个别现象，而将会是随着软件的不断臃肿而越来越普遍的情况。从不少手机厂商都开始将存储上限提升至1TB可以见得，我们似乎正处在互联网信息飞速增长的阶段，对于存储的需求也将会不断扩大。对于苹果用户而言，这一问题愈发严峻，毕竟512GB和1TB版本的iPhone可不是人人都消费得起的，因此成熟的外置存储方案开
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
浅谈主机加固，六种有效的主机加固方法

浅谈主机加固，六种有效的主机加固方法

在数字化时代，数据的价值不言而喻，但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露，企业的数据安全面临着前所未有的挑战。为了应对这些挑战，一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案，采用先进的安全容器中间件技术，构建起一套内核级的纵深立体防护体系。这一体系突破了传统安全防护的局限，即使在管理员权限被恶意利用的情况下，也能确保服务器的安全稳定运行。 普适主机加固措施：
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2