C/C++编程五级 题库
以下代码的输出是?( )
int f[10];
f[0] = 0;
f[1] = 1;
for (int i = 2; i<10; i++){
f[i] = f[i-1] + f[i-2];
}
cout << f[8];斐波那契序列,各项为:0 1 1 2 3 5 8 13 21 34,所以f[8]为21。
以下代码的时间复杂度为?( )
for(int step=1; step<n; step=step*2){
std::cout <<step<<"\n";
}循环变量 step 从 1 开始,每次乘以 2,直到不再小于 n。
循环停止条件:2^{k-1} < n,可以推出: k-1 < log n,因此时间复杂度是 O(log n)。
以下代码的输出是?( )
int f(int n) {
if(n == 0) return 2;
return n*f(n-1);
}
int main() {
cout << f(3);
}调用f(3)时,递归调用:3*f(2),f(2)=2*f(1),f(1)=1*f(0);
f(0)=2,所以f(1)=2,f(2)=2*2=4,f(3)=3*4=12。
若 pre[i] = a[1] + … + a[i],则能表示 a[3] 到 a[9] 的和公式是?( )
pre[9]为:a[1]+a[2]+……+a[9],a[3]前面是a[1]+a[2](即:pre[2]),则a[3]到a[9]是:pre[9]-pre[2]。
模运算中,(a-b) % m 必然等于(a % m) - (b % m)。( )
例如:(5 - 3) % 4 = 2,但(5 % 4) - (3 % 4)=1-3=-2。
漫漫回国路
2020年5月,国际航班机票难求。一位在美国华盛顿的中国留学生,因为一些原因必须在本周内回到北京。现在已知各个机场之间的航班情况,求问他回不回得来(不考虑转机次数和机票价格)。
时间限制:1000
内存限制:65536
输入
第一行为case个数n(n < 10)。 每一个case,第一行为机场个数N,N ≤ 10。 之后的N行,每一行包含N个整数。第i(1 ≤ i ≤ N)行的第j(1 ≤ j ≤ N)个整数代表从第i个机场出发到第j个机场的能买到的航班的最低票价t(0 < t < 10000)。如果不幸没有航班,那么用-1表示。第i行第i个整数为0。 起点华盛顿杜勒斯国际机场的编号为1,终点北京首都国际机场的编号为N。
输出
每一个case一行。 能够回国,输出字符串:YES。如果无法回国,输出字符串:NO
样例输入
2 3 0 100 -1 -1 0 200 -1 -1 0 4 0 1 5 -1 3 0 1 -1 2 4 0 -1 4 1 1 0
样例输出
YES NO
// 广搜
#include <bits/stdc++.h>
using namespace std;
int a[12][12], n;
bool v[12][12];
bool bfs(int p) {
queue<int> q;
q.push(p);
v[p][p] = true;
while (!q.empty()) {
int h = q.front();
q.pop();
for (int i = 1; i <= n; i++) {
if (!v[h][i] && a[h][i] > 0) {
if (i == n)
return true;
else {
q.push(i);
v[h][i] = true;
}
}
}
}
return false;
}
int main() {
int k;
cin >> k;
while (k--) {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
if (bfs(1))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}// 参考代码2
// 深度优先搜索
#include <stdbool.h>
#include <stdio.h>
#define MAX_N 10
#define INF 10000
int airports[MAX_N][MAX_N]; // 存储机场之间的航班票价
bool visited[MAX_N]; // 记录机场是否被访问过
int n; // 机场个数
bool found; // 是否找到回国路径
void dfs(int start, int end) {
if (start == end) {
found = true; // 找到回国路径
return;
}
visited[start] = true;
for (int i = 1; i <= n; i++) {
if (!visited[i] && airports[start][i] != -1) {
dfs(i, end);
}
}
}
bool canReturn() {
found = false;
for (int i = 1; i <= n; i++) {
visited[i] = false;
}
dfs(1, n);
return found;
}
int main() {
int cases;
scanf("%d", &cases);
while (cases--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &airports[i][j]);
}
}
if (canReturn()) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}打怪救公主
公主被魔王抓起来关在了迷宫的某处,骑士想要拯救公主,也进入了迷宫。
但是魔王不会轻易让骑士拯救公主,魔王在迷宫中安排了许多怪兽。
每个怪兽都有血量,骑士也有初始血量,骑士打败怪兽后血量的减少量为怪物的血量值,血量减到0,骑士会死去。
迷宫由m*n个方块组成,每个方块有墙或者路或者怪物,骑士在其中一个方块上,他每个时间单位可以四个方向(上、下、左、右)走到相邻方格,若遇到怪物,必须打败怪物才能继续前进。
请帮忙判断骑士能否成功拯救公主,如果能,给出骑士还剩的最大血量。
时间限制:1000
内存限制:65536
输入
第一行为三个整数m、n和t,t表示骑士的初始血量。(m,n <= 20, t <= 30) 第2至m+1行描述了迷宫,迷宫以m行n列的方格组成,若方格为"."则表示骑士可以通过,若方格为"#"则表示墙,骑士不能通过,若方格为数字则表示怪物,数字为怪物的血量,保证怪物的血量小于10(一位数)。"*"表示了骑士当前所在的位置,"+"表示公主被囚禁的位置。
输出
若骑士能成功拯救公主,则输出骑士走到公主所囚禁方格所剩最大血量,否则输出0。
样例输入
5 6 10 ..*... .#2### 5#..4# .##9.# .#+..#
样例输出
4
整理中……
算24
给出4个小于10个正整数,你可以使用加减乘除4种运算以及括号把这4个数连接起来得到一个表达式。现在的问题是,是否存在一种方式使得得到的表达式的结果等于24。 这里加减乘除以及括号的运算结果和运算的优先级跟我们平常的定义一致(这里的除法定义是实数除法)。 比如,对于5,5,5,1,我们知道5 * (5 – 1 / 5) = 24,因此可以得到24。又比如,对于1,1,4,2,我们怎么都不能得到24。
时间限制:6000
内存限制:65536
输入
输入数据包括多行,每行给出一组测试数据,包括4个小于10个正整数。最后一组测试数据中包括4个0,表示输入的结束,这组数据不用处理。
输出
对于每一组测试数据,输出一行,如果可以得到24,输出“YES”;否则,输出“NO”。
样例输入
5 5 5 1 1 1 4 2 0 0 0 0
样例输出
YES NO
//解法1
//青少年考级竞赛题库(tiku.scratchor.com)搜集整理,感谢网友提供代码!
#include <iostream>
#include<cmath>
#include<bits/stdc++.h>
#define EPS 1e-6
using namespace std;
bool iszero(double c){
if(fabs(c) <= EPS) return 1;
else return 0;
}
bool suan24(double* a,int k){
if(k==1 && iszero(a[0]-24)) return 1;
double b[5];
for(int i=0;i<k-1;i++)
for(int j=i+1;j<k;j++) {
int z = 0;
for (int xx = 0; xx < k; xx++)
if (xx != i && xx != j) b[z++] = a[xx];
b[z] = a[i] + a[j];
if (suan24(b, k - 1)) return 1;
b[z] = a[i] - a[j];
if (suan24(b, k - 1)) return 1;
b[z] = a[j] - a[i];
if (suan24(b, k - 1)) return 1;
b[z] = a[i] * a[j];
if (suan24(b, k - 1)) return 1;
if (a[j] != 0) {
b[z] = a[i] / a[j];
if (suan24(b, k - 1)) return 1;
}
if (!iszero(a[i])) {
b[z] = a[j] / a[i];
if (suan24(b, k - 1)) return 1;
}
}
return 0;
}
int main()
{
while(1)
{
double a[6];
int sum=0;
for(int i=0;i<4;++i)
{
cin>>a[i];
sum+=a[i];
}
if(sum==0)break;
bool flag=suan24(a,4);
if(flag==1)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
// cout<<flag<<endl;
}
return 0;
}//解法2 深搜
#include <bits/stdc++.h>
using namespace std;
double a[5];
bool fig(double a[],int n){
double b[5];
int i,j,k,m;
if(fabs(a[0]-24)<1e-6 && n==1) return 1;
if(n==1) return 0;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++){
m=0;
for(k=0;k<n;k++)
if(k!=i&&k!=j) b[++m]=a[k];
b[0]=a[i]+a[j];if(fig(b,n-1)) return 1;
b[0]=a[i]-a[j];if(fig(b,n-1)) return 1;
b[0]=a[j]-a[i];if(fig(b,n-1)) return 1;
b[0]=a[i]*a[j];if(fig(b,n-1)) return 1;
b[0]=a[i]/a[j];if(fig(b,n-1)) return 1;
b[0]=a[j]/a[i];if(fig(b,n-1)) return 1;
}
return 0;
}
int main() {
while(1){
for(int i=0;i<4;i++) cin>>a[i];
if(a[0]==0&&a[1]==0&&a[2]==0&&a[3]==0) break;
if(fig(a,4)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}忍者道具
忍者道具有很多种,苦无,飞镖,震爆弹。L君热衷于收集忍者道具,现在他有N个道具,每个道具的重量分别是C1、C2…CN。现在他想把这N个道具装到载重量为W的工具包里,请问他最少需要多少个工具包?
时间限制:1000
内存限制:65536
输入
第一行包含两个用空格隔开的整数,N和W。 接下来N行每行一个整数,其中第i+1行的整数表示第i个道具的重量Ci。
输出
输出一个整数,最少需要多少个工具包。
样例输入
5 1996 1 2 1994 12 29
样例输出
2
提示
对于100%的数据,1<=N<=18,1<=Ci<=W<=10^8。
//解法1
//青少年考级竞赛题库(tiku.scratchor.com)搜集整理,感谢网友提供代码!
#include <iostream>
using namespace std;
const int MAXN = 18;
int used[MAXN];
int W;
int m, n, ans = (1 << 30);
int item[MAXN];
int bag[MAXN];
void dfs(int x, int sum) {
if (sum >= ans) return;
if (x == n) {
ans = min(ans, sum);
return;
}
for (int i = 0; i < sum; ++i) {
if (bag[i] >= item[x]) {
bag[i] -= item[x];
dfs(x + 1, sum);
bag[i] += item[x];
}
}
bag[sum] -= item[x];
dfs(x + 1, sum + 1);
bag[sum] += item[x];
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> item[i];
bag[i] = m;
}
dfs (0, 1);
cout << ans << endl;
return 0;
}//解法2 深搜
#include <bits/stdc++.h>
using namespace std;
int n,w,ans=20;
int a[20],bag[20];
void dfs(int x,int sum){//放第x个物品,已使用sum个包
if(sum>=ans) return;//背包数量不够
if(x>n) {ans=min(ans,sum);return;}//所有物品已放完
for(int i=1;i<=sum;i++){//放入现有背包
if(bag[i]>=a[x]){
bag[i]-=a[x];
dfs(x+1,sum);
bag[i]+=a[x];//回溯
}
}
bag[sum+1]-=a[x];//放入新背包
dfs(x+1,sum+1);
bag[sum+1]+=a[x];//回溯
}
int main() {
cin>>n>>w;
for(int i=1;i<=n;i++) {
cin>>a[i];
bag[i]=w;//初始化n个背包的开始可用容量
}
dfs(1,1);
cout<<ans<<endl;
return 0;
}抓牛(2023.12)
农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点N(0<=N<=100000),牛位于点K(0<=K<=100000)。农夫有两种移动方式:
1、从X移动到X-1或X+1,每次移动花费一分钟
2、从X移动到2*X,每次移动花费一分钟
假设牛没有意识到农夫的行动,站在原地不动。农夫最少要花多少时间才能抓住牛?
时间限制:2000
内存限制:65536
输入
两个整数,N和K
输出
一个整数,农夫抓到牛所要花费的最小分钟数
样例输入
5 17
样例输出
4
// 参考代码1
#include <bits/stdc++.h>
using namespace std;
int b[200100];
int a[10];
queue<int> q;
int n, k;
void bfs(int x) {
q.push(x);
b[x] = 1;
while (!q.empty()) {
int s = q.front();
a[1] = s - 1;
a[2] = s + 1;
a[3] = 2 * s;
for (int i = 1; i < 4; i++) {
if (b[a[i]] == 0 && a[i] >= 0 && a[i] < 100100) {
b[a[i]] = b[s] + 1;
q.push(a[i]);
if (a[i] == k) {
cout << b[k] - 1 << endl;
}
}
}
q.pop();
}
}
int main() {
cin >> n >> k;
bfs(n);
return 0;
}// 参考代码2
#include <bits/stdc++.h>
using namespace std;
int n, k;
bool v[100005];
struct nod {
int x, dis;
};
int main() {
cin >> n >> k;
queue<nod> q;
if (n == k) {
cout << 0;
return 0;
}
v[n] = true;
q.push({n, 0});
while (!q.empty()) {
int l = q.size();
for (int i = 1; i <= l; i++) {
if (q.front().x + 1 == k || q.front().x - 1 == k ||
q.front().x * 2 == k) {
cout << q.front().dis + 1;
return 0;
}
if (q.front().x + 1 >= 0 && q.front().x + 1 <= 100000 &&
!v[q.front().x + 1]) {
v[q.front().x + 1] = true;
q.push({q.front().x + 1, q.front().dis + 1});
}
if (q.front().x - 1 >= 0 && q.front().x - 1 <= 100000 &&
!v[q.front().x - 1]) {
v[q.front().x - 1] = true;
q.push({q.front().x - 1, q.front().dis + 1});
}
if (q.front().x * 2 >= 0 && q.front().x * 2 <= 100000 &&
!v[q.front().x * 2]) {
v[q.front().x * 2] = true;
q.push({q.front().x * 2, q.front().dis + 1});
}
q.pop();
}
}
return 0;
}火车站的列车调度铁轨的结构如下图所示。

两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在图中有 9 趟列车,在入口处按照 { 8,4,2,5,3,9,1,6,7 } 的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开,则至少需要多少条平行铁轨用于调度?
时间限制:5000
内存限制:65536
输入
输入第一行给出一个整数 N (2 ≤ N ≤ 105),下一行给出从 1 到 N的整数序号的一个重排列。数字间以空格分隔。
输出
在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。
样例输入
9 8 4 2 5 3 9 1 6 7
样例输出
4
//参考代码1 // #include#include using namespace std; int main() { int n; cin >> n; int a[n] = {0}; int x;//每次输入的列车序号 int t = 0; for (int i = 0; i < n; i++) { cin >> x; if (t == 0 || a[t - 1] < x) //t-1是因为a[t]是0,a[t-1]才是真正的序号 //如果最后一个道路的最后一个元素都比x小, //说明前几条道路也没有能容下x的了 { a[t] = x; //第一个进去的,一定是这一列最大的 // printf("t=%d a[%d]=%d x=%d\n",t,i,a[i],x); t++; } int l = 0, r = t, mid; //t代表了当前开辟的道路的数量 while (l < r) { mid = (r - l) / 2 + l; if (x <= a[mid]) { r = mid; } else l = mid+1 ; } a[l] = x; //测试用: // for (int j = 0; j < t; j++) // { // cout << a[j] << ' '; // } // cout << endl; } cout << t; return 0; }
//参考代码2 #includeusing namespace std; int main(){ int n;cin>>n; int a[n];//a[i]存放的是这条道上的火车中最小的编号。 int max = 0; int k; while(n--){ cin>>k; if(max == 0 || a[max-1] < k){//当道为零或者或者所有道的最小号都小于新来的号码,需要加一条道来放这个号码 a[max++] = k; } else{//有道能放下新来的,找到比新来的大且和间距最小的那个道,用新来的覆盖它的号码 ,二分查找 int l=0;int r=max-1; while(l k) { r=mid-1; } else { l=mid+1; } } a[l]=k; } } cout< //参考代码3 #includeusing namespace std; const int N=100005; int a[N],cnt,n; int find(int x) { if(cnt==0)return 0; int l=0,r=cnt-1; while(l >1; if(a[mid]>x)r=mid; else l=mid+1; } if(a[r]>x)return r; return cnt; } int main() { cin>>n; for(int i=0;i >x; int t=find(x); if(t==cnt)a[cnt++]=x; else a[t]=x; } cout<
负载均衡
负载均衡是指在一组后端服务器上有效地分配传入的网络流量。负载均衡算法按照某种特定方法分配负载。
如果我们可以估算出最大的传入流量负载,则可以根据以下规则设计算法:
- 大小为S的传入流量负载将首先被分解为两块,并且每块可以再次被分解为两块,以此类推。
- 每轮只做一次分解。
- 在任何时候,最小负载的规模必须严格大于最大负载规模的一半。
- 所有的规模都是正整数。
- 这个分解过程会一直进行下去,直到不可能再进行任何分解。
例如,如果S=7,那么我们可以先将其分解为3+4,然后继续分为4=2+2。这个分解终止时,我们需要3台服务器,其负载分别为3、2、2。
本题要求此算法所需的后端服务器的最大数量。由于分解可能不是唯一的,因此请找到最佳解决方案 —— 即使最大和最小规模之间的差异最小化的解。
时间限制:9000
内存限制:65536
输入
输入给出一个正整数 S(2 ≤ S ≤ 200),为传入流量负载的规模。
输出
在一行中输出两个数字:M 为所需的后端服务器的最大数量;D 为使用了 M 个服务器的解决方案中,最大和最小规模之差的最小值。一行中的数字间必须以一个空格分隔,行的开头或结尾不能有多余的空格。
样例输入
22
样例输出
4 1
提示
样例解释: 分解负载的方法是不唯一的,例如可以做 22 = 8 + 14 = 8 + 7 + 7 = 4 + 4 + 7 + 7 或者 22 = 10 + 12 = 10 + 6 + 6 = 4 + 6 + 6 + 6 或者 22 = 10 + 12 = 10 + 6 + 6 = 5 + 5 + 6 + 6 所有上述分解都需要 4台服务器。最后一个解的差值最小,为 6-5=1,所以输出 1。
运行测试
#include<bits/stdc++.h>
using namespace std;
int main(){
int s;
cin>>s;
if(s=22){
cout<<4<<" "<<1;
}
}答案整理中……
狼人杀
以下文字摘自《灵机一动·好玩的数学》:“狼人杀”游戏分为狼人、好人两大阵营。在一局“狼人杀”游戏中,1号玩家说:“2号是狼人”,2号玩家说:“3号是好人”,3号玩家说:“4号是狼人”,4号玩家说:“5号是好人”,5号玩家说:“4号是好人”。已知这5名玩家中有2人扮演狼人角色,有2人说的不是实话,有狼人撒谎但并不是所有狼人都在撒谎。扮演狼人角色的是哪两号玩家?
本题是这个问题的升级版:已知 N 名玩家中有 M 人扮演狼人角色,有 L 人说的不是实话,有狼人撒谎但并不是所有狼人都在撒谎。要求你找出扮演狼人角色的是哪几号玩家?
时间限制:6000
内存限制:65536
输入
输入在第一行中给出三个正整数 N、M、L,其中 5 ≤ N ≤ 100,2 ≤ M,L ≤ N。随后 N 行,第 i 行给出第 i 号玩家说的话(1 ≤ i ≤ N),即一个玩家编号,用正号表示好人,负号表示狼人。
输出
如果有解,在一行中按递减顺序输出 M 个狼人的编号,其间以空格分隔,行首尾不得有多余空格。如果解不唯一,则输出最大序列解 —— 即对于两个序列 A = { a[1], … , a[M] } 和 B = { b[1], … , b[M] },若存在 0 ≤ k < M 使得 a[i]=b[i] (i ≤ k),且 a[k+1]>b[k+1],则称序列 A 大于序列 B。若无解则输出“No Solution”。
样例输入
样例1:
5 2 2 -2 +3 -4 +5 +4
样例2:
6 2 3 -2 +3 -4 +5 +4 -3
样例3:
6 2 5 -2 +3 -4 +5 +4 +6
样例输出
样例1:
4 1
样例2(解不唯一):
6 4
样例3:
No Solution
答案整理中……
卢卡斯数列
题目描述
卢卡斯数列规则如下:
(1)初始两个数字:A0 = 2,A1 = 1
(2)从 i ≥ 2 开始,每个新数字 Ai = A(i-1) + A(i - 2)。
现在给定一个整数 n,请你计算 An 的值。
输入格式
一个整数 n。
输出格式
一个整数,表示第 n 项卢卡斯数。
输入样例1
4
输出样例1
7
输入样例 #2
86
输出样例 #2
939587134549734843
说明提示
0 ≤ n ≤ 86, 保证 An < 10^18。
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long a[100] = {2, 1};
for(int i=2; i<=n; i++) {
a[i] = a[i-1]+a[i-2];
}
cout << a[n];
return 0;
}