C/C++编程三级 题库
vector 是动态数组,可以自动扩展容量。( )
正确,vector 是 C++ 标准库中的动态数组,可以根据元素的增加自动分配内存空间来扩展容量,无需手动管理内存。
vector 的 clear() 会释放所有内存。( )
错误,vector::clear() 的作用是删除所有元素,但不会释放数组底层的内存。
string 的 find()函数在找不到子串时返回 -1。( )
在 C++ 中,string::find() 返回类型是 size_t(无符号整数),当找不到子串时,返回 string::npos,该值并不是-1。
substr() 函数的参数可以只有一个参数。( )
在 C++ 中,string::substr() 有两种重载形式:
substr(pos):从 pos 开始一直取到字符串末尾;
substr(pos, count):从 pos 开始取 count 个字符;
本题答案为正确。
田忌赛马
在田忌赛马的故事中,孙膑用自己的下等马对战对手的上等马,自己上等马对阵对手的中等马,自己的中等马对阵对手的下等马,从而赢得了胜利。现在即将进行的是N匹马的赛马比赛。双方队伍的马各分为N等。已知只有当我方马的等级比对方马等级高X等以上(包含X)时,我方才可以取得这场比赛的胜利。如果在N场比赛中我方的胜场数大于对方,则我方取得最终的胜利。现在已知对方这N场比赛的出战方案,请计算所有令我方最终获胜的出战方案。
时间限制:1000
内存限制:65536
输入
第一行两个整数,N和X。N≤9, 0 ≤ X < N。 第二行N个正整数,A(1)....A(N)。A(i)表示第i场比赛对方马的等级,1≤i≤N。等级越高越强
输出
按字典序输出所有我方最终获胜的方案,每个方案一行。每行是N个正整数,第i个数表示我方第i场比赛马的等级。
样例输入
样例1输入
3 1 3 2 1
样例2输入
3 0 3 1 2
样例输出
样例1输出
1 3 2
样例2输出
1 2 3 1 3 2 2 1 3 3 1 2 3 2 1
#include <bits/stdc++.h>
using namespace std;
int A[12];
int N, X, xy;
int x[12];
#include <algorithm>
#include <iostream>
using namespace std;
void prt(int arr[], int end) {
int i;
int sum = 0;
for (i = 0; i <= end; i++)
if (arr[i] >= A[i] + X)
sum++;
if (sum >= xy) {
for (i = 0; i <= end; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
}
}
void perm(int arr[], int len) {
if (len < 2)
return;
int i, j, temp;
do {
// 输出当前序列
prt(arr, len - 1);
i = j = len - 1;
// 向前查找第一个变小的元素
while (i > 0 && arr[i] < arr[i - 1])
--i;
temp = i;
if (i == 0)
break;
// 先后查找第一个比arr[i-1]大的元素
while (temp + 1 < len && arr[temp + 1] > arr[i - 1])
++temp;
swap(arr[i - 1], arr[temp]); // 交换两个值
reverse(arr + i, arr + len); // 逆序
} while (true);
}
int main() {
int i, j, k;
scanf("%d%d", &N, &X);
for (i = 0; i < N; i++)
scanf("%d", &A[i]);
if (N % 2 == 0)
xy = N / 2 + 1;
else
xy = (N + 1) / 2;
for (i = 1; i <= N; i++)
x[i] = i;
perm(x + 1, N);
return 0;
}
爬楼(2023.3)
已知楼梯的数量,可以每次走2级或者3级,求不同的走法数
例如:楼梯一共有7级,一共3种方法:2 2 3或者 2 3 2 或者 3 2 2。
时间限制:1000
内存限制:65536
输入
输入包含若干行,每行包含一个正整数N,代表楼梯级数,1 <= N <= 50。 最后一行为0,表示测试结束。
输出
不同的走法数,每一行输入对应一行输出
样例输入
7 0
样例输出
3
#include <iostream>
using namespace std;
#define maxn 55
long long dp[maxn];
void init() {
dp[1] = 0, dp[2] = 1, dp[3] = 1, dp[4] = 1;
for (int i = 5; i <= maxn; i++)
dp[i] = dp[i - 3] + dp[i - 2];
}
int main() {
init();
int n;
while (cin >> n) {
if (n == 0) {
return 0;
}
cout << dp[n] << endl;
}
return 0;
}分解因数
给出一个正整数a,要求分解成若干个正整数的乘积,即a = a1 * a2 * a3 * ... * an,并且1 < a1 <= a2 <= a3 <= ... <= an,问这样的分解的种数有多少。注意到a = a也是一种分解。
时间限制:1000
内存限制:65536
输入
第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数a (1 < a < 32768)
输出
n行,每行输出对应一个输入。输出应是一个正整数,指明满足要求的分解的种数
样例输入
2 2 20
样例输出
1 4
//解法1
#include <iostream>
using namespace std;
int find(int n,int k){
int ans=1;if(n==1){return 1;}
for(int i=k;i*i<=n;i++){
if(n%i==0){
ans+=find(n/i,i);
}
}
return ans;
}
int main(){
int a;cin>>a;
int b[a];
for(int i=0;i<a;i++){
cin>>b[i];
}
for(int i=0;i<a;i++){
cout<<find(b[i],2)<<endl;
}
return 0;
}//解法2 递归
#include<bits/stdc++.h>
using namespace std;
int n,a,ans;
void f(int a,int b){
if(a<=b) return;
for(int i=b;i*i<=a;i++){
if(a%i==0){
ans++;
f(a/i,i);
}
}
}
int main()
{
cin>>n;
while(n--){
cin>>a;
ans=1;
f(a,2);
cout<<ans<<endl;
}
return 0;
}苹果消消乐
有100个苹果和香蕉排成一条直线,其中有N个香蕉,你可以使用至多M次魔法道具将香蕉变成苹果,最后“最长的连续苹果数量”即为你本次苹果消消乐的得分,给定苹果和香蕉的排列,求你能获得的最大得分。
时间限制:1000
内存限制:65536
输入
第一行是一个整数T(1 <= T <= 10),代表测试数据的组数。 每个测试数据第一行是2个整数N和M(0 <= N, M <= 100)。第二行包含N个整数a1, a2, ... aN(1 <= a1 < a2 < ... < aN <= 100),表示第a1, a2, ... aN个位置上摆放的是香蕉。
输出
对于每组数据,输出通过使用魔法道具后你能获得的最大得分。
样例输入
3 5 1 34 77 82 83 84 5 2 10 30 55 56 90 5 10 10 30 55 56 90
样例输出
76 59 100
提示
这是个枚举题
//解法1
#include<bits/stdc++.h>
using namespace std;
//计算最大长度
void fun(int n,int m,int a[]){
int ma=0;
if(m>=n)ma=100;//如果道具次数大于香蕉的个数,能把香蕉全变成苹果,不用算,直接得100
else {
int s;
for(int i=m+1;i<=n+1;i++){//3 2 10 50 90
s=a[i]-1-a[i-m-1];
if(s>ma)ma=s;
}
}
cout<<ma<<endl;
}
int main(){
int t,n,m,i,j;//n个香蕉,m个道具,t组数据
cin>>t;
for(i=1;i<=t;i++){
cin>>n>>m;
int a[102]={0};
for(j=1;j<=n;j++)cin>>a[j];//香蕉的位置
a[0]=0;//在最前面和最后面添加一个香蕉
a[n+1]=101;
fun(n,m,a);
}
return 0;
}//解法2 模拟+尺取
#include <iostream>
#include <cstring>
using namespace std;
int a[102];
int main(){
int t,n,m,maxn;
cin>>t;
while(t--){
memset(a,0,sizeof(a)); maxn=0;
cin>>n>>m;
if(m>=n) {cout<<100<<endl;continue;}
for(int i=1;i<=n;i++) cin>>a[i];
a[n+1]=101;
for(int i=1;i+m-1<=n;i++)
maxn=max(maxn,a[i+m]-a[i-1]-1);
cout<<maxn<<endl;
}
return 0;
}数列
用以下方式构造数列: 数列的第一个和第二个数都为1,接下来每个数都等于前面2个数之和。
给出一个正整数a,要求数列中第a个数对1000取模的结果是多少。
时间限制:1000
内存限制:65536
输入
第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数a(1 <= a <= 1000000)。
输出
n行,每行输出对应一个输入。输出应是一个正整数,为数列中第a个数对1000取模得到的结果。
样例输入
4 5 2 19 1
样例输出
5 1 181 1
//解法1
#include <iostream>
using namespace std;
int a[1000000];
void sl(){
a[0]=1;a[1]=1;
for(int i=2;i<1000000;i++){
a[i]=a[i-1]+a[i-2];a[i]=a[i]%1000;
}
}
int main(){
sl();
int b;cin>>b;
for(int i=0;i<b;i++){
int c;cin>>c;
cout<<a[c-1]<<endl;
}
return 0;
}//解法2 斐波那契额数列
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N]={0,1,1},k=2,n;
int fibo(int x){
if(x<=k) return a[x];
for(int i=k+1;i<=x;i++)
a[i]=(a[i-1]+a[i-2])%1000;
k=x;
return a[x];
}
int main()
{
cin>>n;
for(int i=1,m;i<=n;i++){
cin>>m;
cout<<fibo(m)<<endl;
}
return 0;
}波兰表达式(2023.12)
波兰表达式是一种把运算符前置的算术表达式,例如普通的表达式2 + 3的波兰表示法为+ 2 3。波兰表达式的优点是运算符之间不必有优先级关系,也不必用括号改变运算次序,例如(2 + 3) * 4的波兰表示法为* + 2 3 4。本题求解波兰表达式的值,其中运算符包括+ - * /四个。
时间限制:1000
内存限制:65536
输入
输入为一行,其中运算符和运算数之间都用空格分隔,运算数是浮点数。
输出
输出为一行,表达式的值。 可直接用printf("%f\n", v)输出表达式的值v。
样例输入
* + 11.0 12.0 + 24.0 35.0
样例输出
1357.000000
// C++参考代码1
#include <bits/stdc++.h>
using namespace std;
double do_ans() {
string s;
cin >> s;
if (s == "+")
return do_ans() + do_ans();
else if (s == "-")
return do_ans() - do_ans();
else if (s == "*")
return do_ans() * do_ans();
else if (s == "/")
return do_ans() / do_ans();
else {
return atof(s.c_str());
}
}
int main() {
printf("%f", do_ans());
return 0;
}// C++参考代码2
#include <bits/stdc++.h>
using namespace std;
void Pre_notation(vector<string> exp) {
stack<double> num;
string ops = "+-*/";
int ln = exp.size();
for (int i = ln - 1; i >= 0; i--) {
if (ops.find(exp[i]) != string::npos) {
double a = num.top();
num.pop();
double b = num.top();
num.pop();
if (exp[i] == "+")
num.push(a + b);
else if (exp[i] == "-")
num.push(a - b);
else if (exp[i] == "*")
num.push(b * a);
else if (exp[i] == "/")
num.push(a / b);
} else
num.push(atof(exp[i].c_str()));
}
printf("%f\n", num.top());
}
int main() {
string s;
vector<string> v;
while (cin >> s) {
v.push_back(s);
}
Pre_notation(v);
return 0;
}// C++参考代码3
#include <iostream>
#include <cstdlib>
double exp() {
char s[20];
std::cin >> s;
switch (s[0]) {
case '+':
return exp() + exp();
case '-':
return exp() - exp();
case '*':
return exp() * exp();
case '/':
return exp() / exp();
default:
return std::atof(s);
}
}
int main() {
std::cout << std::fixed;
std::cout.precision(6);
std::cout << exp() << std::endl;
return 0;
}流感传染(2023.12)
有一批易感人群住在网格状的宿舍区内,宿舍区为n*n的矩阵,每个格点为一个房间,房间里可能住人,也可能空着。在第一天,有些房间里的人得了流感,以后每天,得流感的人会使其邻居传染上流感,(已经得病的不变),空房间不会传染。请输出第m天得流感的人数。
时间限制:1000
内存限制:65536
输入
第一行一个数字n,n不超过100,表示有n*n的宿舍房间。 接下来的n行,每行n个字符,’.’表示第一天该房间住着健康的人,’#’表示该房间空着,’@’表示第一天该房间住着得流感的人。 接下来的一行是一个整数m,m不超过100.
输出
输出第m天,得流感的人数
样例输入
5 ....# .#.@. .#@.. #.... ..... 4
样例输出
16
// C++参考代码1
#include <bits/stdc++.h>
using namespace std;
char a[102][102];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int ans = 0, n, m;
void infect(int x) {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if (a[i][j] == '0' + x) {
for (int k = 0; k < 4; k++) {
if (i + dx[k] >= 1 && i + dx[k] <= n && j + dy[k] >= 1 &&
j + dy[k] <= n && a[i + dx[k]][j + dy[k]] == '.') {
a[i + dx[k]][j + dy[k]] = '0' + x + 1;
ans++;
}
}
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
if (a[i][j] == '@') {
a[i][j] = '1';
ans++;
}
}
cin >> m;
for (int i = 1; i < m; i++) {
infect(i);
}
cout << ans;
return 0;
}// C++参考代码2
#include <iostream>
char a[101][101], b[101][101];
int main() {
int n, m, ans = 0;
std::cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
std::cin >> a[i][j];
}
}
std::cin >> m;
for (int k = 2; k <= m; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
b[i][j] = a[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (a[i][j] == '.' && (b[i - 1][j] == '@' || b[i + 1][j] == '@' ||
b[i][j - 1] == '@' || b[i][j + 1] == '@')) {
a[i][j] = '@';
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (a[i][j] == '@') {
ans++;
}
}
}
std::cout << ans << std::endl;
return 0;
}// C语言参考代码
#include <stdio.h>
char a[101][101], b[101][101];
int main() {
int n, m, ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf(" %c", &a[i][j]);
}
}
scanf("%d", &m);
for (int k = 2; k <= m; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
b[i][j] = a[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (a[i][j] == '.' &&
(b[i - 1][j] == '@' || b[i + 1][j] == '@' || b[i][j - 1] == '@' || b[i][j + 1] == '@')) {
a[i][j] = '@';
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (a[i][j] == '@') {
ans++;
}
}
}
printf("%d\n", ans);
return 0;
}课程冲突
小 A 修了 n 门课程, 第 i 门课程是从第 ai 天一直上到第 bi 天。
定义两门课程的冲突程度为 : 有几天是这两门课程都要上的。
例如 a1=1,b1=3,a2=2,b2=4 时, 这两门课的冲突程度为 2。
现在你需要求的是这 n 门课中冲突程度最大的两门课的冲突程度。
时间限制:1000
内存限制:65536
输入
第一行一个正整数 n 表示课程数量。 接下来 n 行,每行两个正整数 ai,bi。 2 ≤ n≤ 1000, 1 ≤ ai ≤ bi ≤ 1000。
输出
输出一个整数表示最大的冲突程度
样例输入
3 1 3 2 4 5 5
样例输出
2
//参考答案1
#include <bits/stdc++.h>
using namespace std;
//#define PPYDEBUG
struct lesson{
int no; //课程编号
int a; //课程开始a天
int b; //课程结束b天
};
int max_chongtu(lesson x, lesson y){
int r = min(x.b, y.b) - max(x.a, y.a) + 1;
if(r < 0){
r = 0;
}
#ifdef PPYDEBUG
printf("%d = x[%d,%d] - y[%d,%d]\n", r, x.a, x.b, y.a, y.b);
#endif
return r;
}
int main() {
#ifdef LOCAL
freopen("202209_3_1.in", "r", stdin);
#endif
int n;
scanf("%d", &n);
lesson le[1010];
for(int i = 0; i < n; i++){
le[i].no = i + 1;
scanf("%d%d", &le[i].a, &le[i].b);
}
int r = 0;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
r = max(r, max_chongtu(le[i], le[j]));
}
}
printf("%d", r);
return 0;
}//参考答案2
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct project {
int start;
int end;
project(int a,int b):start(a),end(b){}
bool operator <(const project A)const {
if (start == A.start)
return end < A.end;
else
return start < A.start;
}
};
int main() {
int n;
cin >> n;
vector<project>alls;
for (int i = 0; i < n; i++)
{
int a, b;
cin >> a >> b;
alls.push_back(project(a, b));
}
sort(alls.begin(), alls.end());
int result = 0;
for (int i = 0; i < n; i++) {
if (alls[i].end - alls[i].start < result)//剪枝
continue;
for (int j = i + 1; j < n; j++) {
if (alls[j].start > alls[i].end)
break;
int t = min(alls[i].end, alls[j].end) - alls[j].start + 1;
result = max(t, result);
}
}
cout << result << endl;
return 0;
}