A.动物的传染病
B.台阶问题
C.数的计算
D.数的划分
E.绝对值最小的和
F.区间和
G.二分查找
H.比k大的数
A.动物的传染病
Description
动物患传染病了。一个动物会每轮传染 x 个动物。试问 n 轮传染后有多少动物被传染？
Input
两个非负整数 x 和 n。
Output
一个整数，即被传染的动物数。
Sample Input
10 2
Sample Output
121
本题使用递推，一个循环结束。核心代码如下：
long long Solve(int x,int n)
{
long long sum=1;
for (int i=1;i<=n;i++)
{
sum=sum+sum*x;
}
return sum;
}B.台阶问题
Description
有 N 级的台阶，你一开始在底部，每次可以向上迈最多 K 级台阶（最少 1 级），问到达第 N 级台阶有多少种不同方式。
Input
两个正整数N，K。1 ≤ N ≤ 10 6, 1 ≤ K ≤ 20
Output
一个正整数，为不同方式数，由于答案可能很大，你需要输出 ans mod 100003 后的结果。
Sample Input
5 2
Sample Output
8
Hint
N级台阶的情况可以由 N-K ~ N-1 这些台阶的情况得到
根据提示我们可以得到这样的递推关系：a[n]=a[n-1]+a[n-2]+……+a[n-k] ，注意每次都要取模。
外层循环可以理解为计算走到第i阶台阶需要的步数，内层循环则计算递推公式，从i-1阶加到i-k阶。
代码借鉴了这位大佬的：走台阶（每次最多迈k级）C++_n层楼梯每次k步_!Polaris的博客-CSDN博客
#include <iostream>
using namespace std;
int n, k;
int ans[1111111];
const int mod = 100003;
int main() {
for (int i = 0; i < 1111111; i++)
ans[i] = 0;
ans[0] = 1;
while (cin >> n >> k)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= k; j++)
{
if (i - j >= 0)
{
ans[i] += ans[i - j];
ans[i] %= mod;
}
}
}
cout << ans[n] << endl;
}
return 0;
}C.数的计算
Description
给定一个初始序列，序列中仅包含一个元素 n(1≤ n≤1000)。重复以下步骤：
不做任何处理；
在序列的最左边插入一个正整数，但是这个正整数不能超过序列当前首元素的一半；
请问通过这样的规则，可以构造出多少个不同的序列。
Input
1 个正整数 n ( n ≤ 1000 )
Output
1 个整数，表示能够生成的序列个数。
Sample Input
6
Sample Output
6
Hint
当n=6，满足条件的序列为
{6},
{1, 6},
{2, 6},
{1, 2, 6},
{3, 6},
{1, 3, 6}
本题可以采取和B题类似的思路用双重循环去做（据题得递推公式：a[i]=1+a[1]+a[2]+...+a[i/2]），但是还有一种更简单的方法：首先我们根据题意列举出一些例子，如下表：
输入：n | 输出：a[n] |
1 | 1 |
2 | 2 |
3 | 2 |
4 | 4 |
5 | 4 |
6 | 6 |
7 | 6 |
8 | 10 |
9 | 10 |
根据上表我们可以发现，当n为奇数的时候，a[n]=a[n-1]，当n为偶数的时候，a[n]=a[n-1]+a[n/2]
直接一个循环即可结束此题。
#include <iostream>
using namespace std;
int n, ans[1005] = {1, 1, 2, 2};
int main() {
int n;
cin >> n;
for (int i = 3; i <= n; i++)
{
if (i % 2 == 1)
ans[i] = ans[i - 1];
else
ans[i] = ans[i - 1] + ans[i / 2];
}
cout << ans[n];
return 0;
}D.数的划分
Description
将整数 n 分成 k 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。
例如：n = 7，k = 3，下面三种分法被认为是相同的。
1 , 1 , 5
1 , 5 , 1
5 , 1 , 1
问有多少种不同的分法。
Input
n, k （6 < n ≤ 200，2 ≤ k ≤ 6）
Output
1 个整数，即不同的分法。
Sample Input
7 3
Sample Output
4
Hint
对于样例的输入输出
四种分法为：
1 , 1 , 5
1 , 2 , 4
1 , 3 , 3
2 , 2 , 3
这题主要考察对递推公式的理解，根据dp数组的定义可以得出这个递推公式：dp[i][j] 表示 i 分成 j 份。由于每份不为 0 ，则dp[i][j] = dp[i - j][j] + dp[i - 1][j - 1]。
这个博主（程序基本算法习题解析 动态规划-数的划分 将整数n分成k份，且每份不能为空，任意两种划分方案不能相同（不考虑顺序）。求整数n分为k份，共有多少种不同的分法。_将整数n分成k份,且每份不能为空_elma_tww的博客-CSDN博客）讲的特别详细，大家可以看一下，看过之后就很容易理解代码了。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int dp[220][11];
int main()
{
int n, k;
scanf("%d%d", &n, &k);
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= k; j++)
{
if (i >= j)
{
dp[i][j] = dp[i - j][j] + dp[i-1][j-1];
}
}
}
printf("%d\n", dp[n][k]);
return 0;
}E.绝对值最小的和
Description
给出一串由 N 个整数组成的数列 a 1, a 2, a 3, ..., a N 求问数列中哪两个不同元素的和的绝对值最小。
Input
输入共一组数据，共2行
第一行一个数字 N ，表示数列中元素的个数
第二行共 N 个数字，两两之间用空格分开，表示
a 1, a 2, a 3, ..., a N
输入保证 2 ≤ N ≤ 1 × 10 3, − 1 × 10 8 ≤ a i ≤ 1 × 10 8
Output
输出共1行，两个用空格隔开的数字 i 和 j ，表示 a i + a j 的绝对值最小。
若两对元素的之和的绝对值相同，且都比其它对元素之和的绝对值小，则取编号较小元素的编号较小的一对；若编号较小元素相同，则取编号较大元素的编号较小的一位。
例如，数列： − 1, 1, 1, − 1 中，有 | a 1 + a 2| = | a 1 + a 3| = | a 2 + a 4| = | a 3 + a 4| = 0
，它们的绝对值相等且最小。但应输出 1 2
Sample Input
5 5 4 3 2 1
Sample Output
4 5
简单的双重循环，代码如下：
（这里使用scanf是为了防止超时）
#include<stdio.h>
#include<math.h>
int main()
{
int n,i,j;
scanf("%d", &n);
long a[n + 1];
a[0] = 0;
for (i = 1; i <= n; i++)
scanf("%ld", &a[i]);
int min1 = 1, min2 = 2;
for (i = 1; i <= n; i++)
{
for (j = i + 1; j <= n; j++)
{
if (abs(a[i] + a[j]) < abs(a[min1] + a[min2]))
{
min1 = i; min2 = j;
}
}
}
printf("%d %d\n", min1, min2);
return 0;
}F.区间和
Description
给出一串由N个自然数组成的数列 a 1, a 2, a 3, ..., a n，之后给出M次询问，每次询问包含两个数字L和R。对于每次询问，求出L和R之间所有数（包括L和R本身）之和。
Input
输入仅有一组数据，共 M + 2行。
第一行有两个用空格隔开的自然数 N 和 M，表示数列中共有 N个数字，一共有 M 次询问。保证 1 ≤ N, M ≤ 1 × 10 6 第二行有 N 个用空格隔开的自然数 a 1、 a 2、 a 3、…… 、 a N，对于所有的 i，都有 1 ≤ a i ≤ 1 × 10 6
第三行到第 M+2行，每行有两个自然数 L 和 R ，表示要问数列中 a L到 a R之间的所有数之和（包括 a L和 a R）。保证 1 ≤ L ≤ R ≤ N
Output
输出共 M行，每行1个自然数，即数列中 a L到 a R之间的所有数之和（包括 a L和 a R）
Sample Input
5 8 1 2 3 4 5 1 3 2 5 2 3 1 1 5 5 1 5 3 4 4 5
Sample Output
6 14 5 1 5 15 7 9
本题使用循环求和会导致超时，换一种比较巧妙的思路，在输入的时候处理数据，把数组的每一项都转变为求和的形式，代码如下：
使用scanf是为了防止超时
#include <stdio.h>
int main()
{
long long int n, m, l, r, sum = 0;
scanf("%lld%lld", &n, &m);
long long a[n+1];
for (int i = 0; i < n+1; i++)
a[i] = 0;
for (int i = 1; i <= n; i++) {
scanf("%lld", &sum);
a[i] = a[i - 1] + sum; //注意
}
for (int i = 1; i <= m; i++) {
scanf("%lld%lld", &l, &r);
printf("%lld\n", a[r] - a[l - 1]);
}
}G.二分查找
Description
给出一串由N个自然数组成的非降数列 a 1, a 2, a 3, ..., a n，即数列中位置靠后的数一定大于或等于位置靠前的数。之后给出M次询问，每次询问包含一个数字Q。对于每次询问，求出数列中第一个大于或等于Q的数字的编号（数字在数列中的编号从1开始）
Input
输入仅有一组数据，共 M + 2行。
第一行有两个用空格隔开的自然数 N 和 M，表示数列中共有 N个数字，一共有 M 次询问。保证 1 ≤ N ≤ 10 7, 1 ≤ M ≤ 1 × 10 6 第二行有 N 个用空格隔开的自然数 a 1、 a 2、 a 3、…… 、 a N，分别表示 a i，都有 1 ≤ a i ≤ 10 9, a i ≤ a i + 1
第三行到第 M + 2行，每行一个数Q，表示要问数列中第一个大于或等于Q的元素的编号。保证 1 ≤ Q ≤ a N
Output
输出共 M行，每行1个自然数，即数列中第一个大于或等于Q的元素的编号
Sample Input
5 3 1 3 5 7 9 1 3 6
Sample Output
1 2 4
本题需要注意的是，在二分查找的基础上进行修改，如果遇到查找值和中间值相等的情况就不要让mid多移一步了，还有一点就是当数组只有一个元素的时候需要特判，具体代码如下，很容易看懂
#include<stdio.h>
int main()
{
long n, m;
long q;
scanf("%ld%ld", &n, &m);
long a[n + 1];
a[0] = 0;
for (int i = 1; i < n + 1; ++i)
scanf("%ld", &a[i]);
while (m--)
{
scanf("%ld", &q);
long low = 1, high = n;
long mid, pos = 0; //pos代表需要查找到的结果
if(n==1)
{
if(q<=a[1])
printf("1\n");
}
else
{
while (low < high)
{
mid = (low + high) / 2;
if (q > a[mid])
{
low = mid + 1; //非等于的情况直接和二分查找进行一致的操作即可
pos=low; //查找结果也要随之移动
}
else //当查找值小于等于中间值的时候，区间右端点移动到mid即可
{
high = mid;
pos = high;
}
}
printf("%ld\n", pos);
}
}
return 0;
}H.比k大的数
Description
给出一个由n个整数组成的数列 a 1, a 2, a 3, ..., a n
之后给出m个整数k。 问：对于每一个k，数列中有多少个数比k大？
Input
输入共包括三行
第一行是两个由空格隔开的正整数n和m
第二行是由n个整数组成的数列 a 1, a 2, a 3, ..., a n ，数与数之间由空格隔开。
第三行有m个整数k，数与数之间由空格隔开。
保证 0 < n ≤ 1 × 10 3; 0 < m ≤ 1 × 10 3; − 1 × 10 3 ≤ a 1, a 2, a 3, ..., a n ≤ 1 × 10 3; − 1 × 10 6 ≤ k ≤ 1 × 10 6;
Output
输出共包括m行，每行一个整数，表示数列中有多少个数比k大
Sample Input
5 5 1 2 3 4 5 3 5 4 6 -1
Sample Output
2 0 1 0 5
Hint
题目给的数据范围很小（-1000~1000），可以先统一映射到 0~2000，统计总数与前缀和
对于每个 k，超出范围可直接得结果，范围内就用总数减去前缀和。
本题不难，难的是按照题目提示去写(作者太菜了)，简单点双重循环直接求解即可。
#include<iostream>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
int* a = new int[n];
for (int i = 0; i < n; i++)
cin >> a[i];
while (m--)
{
int key,cnt=0;
//scanf("%d",&key);
cin >> key;
for (int i = 0; i < n; i++)
{
if (a[i] > key)
cnt++;
}
//printf("%d\n", cnt);
cout << cnt << endl;
}
return 0;
}版权声明：本文为m0_62886386原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。