C/C++编程二级 题库
为 i 做 e
“为 i 做 e”是最近新出的流行梗。这里的 i 和 e 指 MBTI 人格测试中的不同性格,i 是社恐,e 是外向。“为 i 做 e”就是在一群内向的人中促使自己变成外向(奇奇怪怪无用的知识又增加了)。
给定某次大型活动中的餐桌安排,请你判断一下哪几桌的客人需要“为 i 做 e”了。
时间限制:6000
内存限制:65536
输入
输入第一行首先给出正整数 n(≤ 105),随后 n 行,每行给出一个人的代号和其性格,其中代号由 8 位数字组成,性格是单个字母 i 或 e,其间以空格分隔。 接下来是餐桌安排。首先给出正整数 m(≤ 103),为餐桌数量,随后 m 行,每行给出一个正整数 k(≤ 10)以及该桌 k 位客人的代号,用空格分隔。第 i 行对应的是第 i 桌的信息(1 ≤ i ≤ m)。题目保证没有人在餐桌安排中重复出现,且餐桌上每个人的性格都已给出。
输出
如果一桌客人全是 i 人,则意味着有人要“为 i 做 e”了。请在一行中按递增序输出这些桌的桌号。数字间以 1 个空格分隔,行首尾不得有多余空格。如果这样的餐桌不存在,则在一行中输出 None。
样例输入
样例1:
10 00000000 i 12345678 e 23468270 i 78827341 e 67476289 i 35748108 e 99999999 i 40926483 i 88472901 i 55032849 i 3 3 00000000 67476289 99999999 4 12345678 78827341 35748108 55032849 3 23468270 40926483 88472901
样例2:
10 00000000 i 12345678 e 23468270 i 78827341 e 67476289 i 35748108 e 99999999 i 40926483 i 88472901 i 55032849 i 2 4 78827341 35748108 55032849 00000000 6 12345678 67476289 99999999 23468270 40926483 88472901
样例输出
样例1:
1 3
样例2:
None
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
string id,ie;
map<string,string>mp;
vector<int>v;
int main()
{
cin>>n;
while(n--)
{
cin>>id>>ie;
mp[id]=ie;
}
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>k;
int cnt=0;
for(int j=0;j<k;j++)
{
cin>>id;
if(mp[id]=="i")cnt++;
}
if(cnt==k)v.push_back(i);
}
if(v.size())
{
for(int i=0;i<v.size();i++)
{
if(i)cout<<" ";
cout<<v[i];
}
}
else cout<<"None";
return 0;
}吃火锅
本题要求你实现一个程序,自动检查你朋友给你发来的信息里有没有 `chi1 huo3 guo1`。
时间限制:1000
内存限制:65536
输入
输入每行给出一句不超过 80 个字符的、以回车结尾的朋友信息,信息为非空字符串,仅包括字母、数字、空格、可见的半角标点符号。当读到某一行只有一个英文句点 . 时,输入结束,此行不算在朋友信息里。
输出
首先在一行中输出朋友信息的总条数。然后对朋友的每一行信息,检查其中是否包含 chi1 huo3 guo1,并且统计这样厉害的信息有多少条。在第二行中首先输出第一次出现 chi1 huo3 guo1 的信息是第几条(从 1 开始计数),然后输出这类信息的总条数,其间以一个空格分隔。题目保证输出的所有数字不超过 100。 如果朋友从头到尾都没提 chi1 huo3 guo1 这个关键词,则在第二行输出一个表情 `-_-#`。
样例输入
样例1:
Hello! are you there? wantta chi1 huo3 guo1? that's so li hai le our story begins from chi1 huo3 guo1 le .
样例2:
Hello! are you there? wantta qi huo3 guo1 chi1huo3guo1? that's so li hai le our story begins from ci1 huo4 guo2 le .
样例输出
样例1:
5 3 2
样例2:
5 -_-#
#include <bits/stdc++.h>
using namespace std;
int sum, cnt, first;
string s;
int main() {
while (getline(cin, s)) {
if (s == ".") break;
sum++;
if (s.find("chi1 huo3 guo1") != -1) {
if (!first) first = sum;
cnt++;
}
}
cout << sum << '\n';
if (!cnt) cout << "-_-#";
else cout << first << ' ' << cnt;
return 0;
}排课
排课是个世界难题。
假设每个学期有 N 个教学班的课需要排,每周有 M 个时间段可以上课,全校共有 K 间教室,不同排课组合方案的个数可能会超过整个宇宙的质子数。更为复杂的是,每个学期排课前,学校还会收集每个教学班任课老师不能上课的时间段,还要保证排课不与老师的时间安排起冲突。
当然,本题不是要求你实现一个排课算法,而是要求你实现一个排课方案检查算法。即给定每个教学班上课的时间和地点,你需要检查这个时间段和地点是否只有这一个班上课,并且这个上课时间不会正好是任课老师不能上课的时间。
时间限制:5000
内存限制:65536
输入
输入在第一行中给出三个正整数:N(≤ 104)为教学班总数;M(≤ 40)为一周内上课时间段的个数;K(≤ 103)为教室总数。数字间以空格分隔。以下我们就将教学班、时间段、教室分别从 1 开始顺序编号。 随后 N 行,每行给出一个教学班的任课教师时间限制和排课的信息。格式如下: L T[1] ... T[L] Time Room 其中 L 是任课教师的时间限制数量(< M),后面给出 L 个该老师不能上课的时间段编号;Time 是该教学班安排的上课时间段编号,Room 是上课教室编号。
输出
如果给定的课表安排是完全无冲突的,则在一行内输出:Perfect Arrangement for N classes! 其中 N 是教学班数量。 如果课表有冲突,则需要输出冲突原因。我们首先假设教学班是按照编号递增序进行排课的,教学资源先到先得。如果后面安排的教学班 A 跟前面的教学班 B 排在了同一个时间和地点,则在一行中输出 ERROR: Conflict between A and B.;如果教学班 A 的上课时间跟任课教师有冲突,则在一行中输出 ERROR: Conflict with instructor for A.。当两种冲突都发生时,分两行输出,先输出教学班冲突的信息。发生冲突的教学班暂不安排。
样例输入
样例1:
5 20 10 2 1 5 10 7 0 10 3 5 2 4 6 8 10 3 3 3 10 3 18 15 1 1 20 19 10
样例2:
5 20 10 2 1 5 10 7 0 10 7 5 2 4 6 8 10 6 3 3 10 3 18 6 3 2 20 10 10 7
样例输出
样例1:
Perfect Arrangement for 5 classes!
样例2:
ERROR: Conflict between 2 and 1. ERROR: Conflict with instructor for 3. ERROR: Conflict between 5 and 1. ERROR: Conflict with instructor for 5.
//C语言参考题解
#include <stdio.h>
#include <stdlib.h>
//存储教师信息
struct kb {
int L, T[50], time, room;
} k[10001];
int cmp(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}
int main() {
int N, M, K,all=0;
scanf("%d %d %d", &N, &M, &K);
for (int i = 0; i < N; i++) {
scanf("%d", &k[i].L);
int flag=0,flagg=0;
for (int j = 0; j < k[i].L; j++)
scanf("%d", &k[i].T[j]);
scanf("%d %d", &k[i].time, &k[i].room);
qsort(k[i].T, k[i].L, sizeof(k[0].T[0]), cmp);//每次读入一个教师的不能上课时间段数组之后就排个序,方便用bsearch查找
if (i) {
for (int m = 0; m < i; m++) {
if (k[i].room == k[m].room && k[m].time == k[i].time) {//校验是否存在教室冲突
printf("ERROR: Conflict between %d and %d.\n", i+1, m+1);
flag=1;
all=1;
}
}
}
if(bsearch(&k[i].time,k[i].T,k[i].L,sizeof(k[0].T[0]),cmp)){//校验是否存在时间冲突
printf("ERROR: Conflict with instructor for %d.\n",i+1);
flagg=1;
all=1;
}
if(flag || flagg){//必须先将两个条件都检验一遍才能初始化
k[i].time=-1*i;
k[i].room=-1*i;
}
}
if(!all)
printf("Perfect Arrangement for %d classes!",N);
}垃圾分类
据香港《南华早报》7月15日文章,上海严格的垃圾分类新规令不少居民抓狂。这催生出大量帮助找出正确分类答案的App和小程序。目前仅微信上就至少有280种与垃圾处理有关的App,在苹果应用商店也达130种。支付宝表示,已有60多家独立App开发商申请为该平台提供类似服务。
本题就请你现场实现一个简单的垃圾分类小助手。
时间限制:1000
内存限制:65536
输入
输入首先给出官方分类指南中每种物品的归属。在一行中给出一个正整数 N(≤ 100000),即物品数量;随后 N 行,每行给出一个物品名称(长度不超过 10 的、由小写英文字母和下划线组成的字符串)和该物品所属的分类(1 代表干垃圾、2 代表湿垃圾、3 代表可回收物、4 代表有害垃圾)。题目保证所有物品名称无重复。 随后每行给出一个查询物品的名称(格式与指南物品名称相同)。最后一行给出结束符 `#`,表示查询终止,这一行不需要查询。(查询的数量 ≤ 100000个)
输出
对每个查询的物品,在一行中给出其所属分类:`Gan laji` 代表干垃圾;`Shi laji` 代表湿垃圾;`Ke Hui Shou` 代表可回收物;`You Hai laji` 代表有害垃圾。如果查询的物品不在指南中,则输出 `?` 表示不知道。
样例输入
4 bao_zhi 3 dian_chi 4 dan_ke 2 bei_ke 1 dan_ke dian_chi ren_zha bao_zhi bei_ke
样例输出
Shi laji You Hai laji ? Ke Hui Shou Gan laji
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
int main() {
// 定义一个unordered_map来存储物品名称和分类的映射关系
unordered_map<string, int> garbageMap;
// 读取物品数量和每个物品的名称及其分类
int N;
cin >> N;
for (int i = 0; i < N; ++i) {
string name;
int type;
cin >> name >> type;
garbageMap[name] = type;
}
// 读取查询物品的名称并输出其分类
string query;
while (cin >> query && query != "#") {
// 查找物品名称在unordered_map中的分类
auto it = garbageMap.find(query);
if (it != garbageMap.end()) {
// 根据分类输出对应的中文描述
switch (it->second) {
case 1:
cout << "Gan laji" << endl;
break;
case 2:
cout << "Shi laji" << endl;
break;
case 3:
cout << "Ke Hui Shou" << endl;
break;
case 4:
cout << "You Hai laji" << endl;
break;
}
} else {
// 如果查询的物品不在指南中,则输出?表示不知道
cout << "?" << endl;
}
}
return 0;
}生成字母串
英语老师要求学生按照如下规则写一串字母:
- 如果写了某个大写字母,下一个就必须写同个字母的小写,或者写字母表中下一个字母的大写;
- 如果写了某个小写字母,下一个就必须写同个字母的大写,或者写字母表中前一个字母的小写。
例如 `aAaABCDdcbBC` 就是一个合法的字母串;而 `dEFfeFGhI` 就是非法的。
本题就请你编写程序,自动生成一个合法的字母串。
时间限制:1000
内存限制:65536
输入
输入在第一行给出一个不超过 10000 的正整数 N 和第一个字母。 随后一行给出一个由 `0` 和 `1` 组成的长度为 N 的字符串。这个串给出了字母串的生成规则:从第一个字母开始,如果对应的规则串字符是 `0`,则下一个字母应该生成当前字母的大/小写;如果是 `1` 则下一个字母应该生成当前字母的前/后一个字母。 注意:因为字母表中 `a` 没有前一个字母,`Z` 没有后一个字母,所以如果此时遇到 `1` 就忽略之。
输出
在一行中输出按规则生成的字母串。
样例输入
12 a 001011101101
样例输出
aAaABCDdcbBC
#include <iostream>
#include <string>
using namespace std;
char getNextChar(char current, char rule) {
if (islower(current)) {
if (rule == '0') {
return toupper(current);
} else if (rule == '1' && current != 'a') {
return tolower(current - 1);
} else {
return current;
}
} else if (isupper(current)) {
if (rule == '0') {
return tolower(current);
} else if (rule == '1' && current != 'Z') {
return toupper(current + 1);
} else {
return current;
}
} else {
return ' ';
}
}
int main() {
int N;
char firstChar;
string ruleString;
cin >> N >> firstChar;
cin >> ruleString;
string result = string(1, firstChar);
for (int i = 0; i < N; ++i) {
char currentChar = result.back();
char nextChar = getNextChar(currentChar, ruleString[i]);
result += nextChar;
}
cout << result << endl;
return 0;
}机器人拼图
给定一块由 n × m 个格子组成的矩形拼图板,本题要求你根据给定的机械手移动指令集,将拼图中的碎片逐一放到指定位置。
机械手每次抓取一块碎片,都会在拼图板的左上角位置等待指令。一个指令集是由 0-4 这五个数字组成的字符串,每个数字代表的意义如下:
- 1:向右移动一格;
- 2:向下移动一格;
- 3:向左移动一格;
- 4:向上移动一格;
- 0:将碎片放置在当前位置,并结束这次任务。
如果指令要求机械手移动到拼图板边界外,机械手会无视这个指令。如果接收到指令 0 时,当前位置上已经有一块碎片放好了,机械手会扔掉手里的碎片,结束这次任务。
时间限制:5000
内存限制:65536
输入
输入第一行给出 2 个正整数 n 和 m(1 ≤ n,m ≤ 100),随后一共有 n × m 行,第 i 行给出编号为 i(i=1,... n×m)的碎片对应的指令集,每条指令集一定以唯一的 0 结尾。(总的指令操作步数不超超过107)
输出
输出 n 行,每行 m 个整数,为放置在对应位置上的碎片编号。如果该位置上没有碎片,则输出 0。一行中的数字间以 1 个空格分隔,行首位不得有多余空格。
样例输入
2 3 1120 21140 34120 0 110 21111340
样例输出
4 6 2
//参考代码1
#include<bits/stdc++.h>
using namespace std;
int n,m;
int note[105][105];
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for (int i = 0; i < n * m; ++i) {
string s;cin>>s;
int x = 0,y = 0;
for (int j = 0; j < s.length(); ++j) {
switch (s[j]) {
case '1':
y += 1;y = min(y,m-1);break;
case '2':
x += 1;x = min(x,n-1);break;
case '3':
y -= 1;y = max(0,y);break;
case '4':
x -= 1;x = max(0,x);break;
default:
if (!note[x][y])
// cout<<x<<"*"<<y<<endl;
note[x][y] = i+1;
break;
}
}
}
for (int i = 0; i < n; ++i) {
cout<<note[i][0];
for (int j = 1; j < m; ++j) {
cout<<" "<<note[i][j];
}
cout<<"\n";
}
return 0;
}//参考代码2
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
// 初始化拼图板,所有位置为0,表示没有碎片
vector<vector<int>> puzzle(n, vector<int>(m, 0));
// 读取每个碎片的指令集
for (int i = 0; i < n * m; ++i) {
int x = 0, y = 0; // 机械手的初始位置(左上角)
string instructions;
cin >> instructions;
for (char ch : instructions) {
if (ch == '1') {
// 向右移动一格
if (y + 1 < m) {
++y;
}
} else if (ch == '2') {
// 向下移动一格
if (x + 1 < n) {
++x;
}
} else if (ch == '3') {
// 向左移动一格
if (y - 1 >= 0) {
--y;
}
} else if (ch == '4') {
// 向上移动一格
if (x - 1 >= 0) {
--x;
}
} else if (ch == '0') {
// 将碎片放置在当前位置,并结束这次任务
if (puzzle[x][y] == 0) {
puzzle[x][y] = i + 1; // 碎片编号为i+1
}
break; // 结束这次任务的指令集
}
}
}
// 输出拼图板上每个位置上的碎片编号
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cout << puzzle[i][j];
if (j < m - 1) {
cout << " ";
}
}
cout << endl;
}
return 0;
}查找特定值


#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int arr[10005];
for (int i = 1; i <= n; ++i)
{
cin >> arr[i];
}
int t;
cin >> t;
int res = -1;
for (int i = 1; i <= n; ++i)
{
if (arr[i] == t)
{
res = i;
break;
}
}
cout << res;
return 0;
}闯关得分
题目描述
每一名选手有三次挑战机会,每次挑战会获得一个得分。最终得分规则为:取三次挑战中得分最高的两次,将这两次的得分相加,作为该选手的最终得分。
现给定该选手三次挑战的得分,请计算并输出其最终得分。
输入
一行包含三个整数,分别表示三次挑战的得分,整数之间用空格分隔。
输出
一个整数,表示选手的最终得分。
数据范围
每次挑战的得分均为 0 到 100 之间的整数(包含 0 和 100)。
输入样例1
80 90 70
输出样例1
170
输入样例2
100 50 100
输出样例2
200
#include <bits/stdc++.h>
using namespace std;
int main() {
int a,b,c,m;
cin >> a >> b >> c;
m=a;
if(b<m)
m=b;
if(c<m)
m=c;
cout << a+b+c-m;
return 0;
}计算天数
题目描述
以 年-月-日 的形式给定一个日期,计算给定的日期是当年第几天。注意闰年二月有 29 天。
输入
输入格式为 yyyy-mm-dd,其中:
yyyy 表示给定的年份,mm 表示给定的月份,dd 表示给定的日期。
如果这些数字不足四位或二位,以 0 补足。
输出
单个整数:表示输入的日期是当年的第几天。
数据范围
保证月份与日期都是合理的。
输入样例1
2021-12-31
输出样例1
365
输入样例2
2022-01-01
输出样例2
1
#include <iostream>
using namespace std;
int main() {
int y,m,d,ans=0;
int days[]= {31,28,31,30,31,30,31,31,30,31,30,31};
scanf("%d-%d-%d",&y,&m,&d);
for(int i=0; i<m-1; i++) { //m月份之前的天数
ans+=days[i];
}
ans+=d; //当月的天数
if(m > 2 && (y % 400 ==0 || (y%100!=0 && y%4==0))) //闰年二月 +1天
ans+=1;
cout << ans;
return 0;
}一半
题目描述
给定一个长度为 4 的大写字母字符串 S,请判断它是否满足以下两个条件: 字符串中恰好包含两种不同字母;这两种字母都恰好出现两次。
输入格式
一个字符串 S。
输出格式
如果满足条件,输出 Yes,否则输出 No。
输入样例#1
MAMA
输出样例#1
Yes
输入样例#2
DEED
输出样例#2
Yes
输入样例#3
PEER
输出样例#3
No
说明提示
S一定是长度为4的大写字符串。
限制
时间限制:1000ms
内存限制:256MiB
#include<iostream>
int main()
{
char a, b, c, d;
std::cin >> a >> b >> c >> d;
if (a == b && b == c && c == d)
std::cout << "No\n";
else if (a == b && c == d)
std::cout << "Yes\n";
else if (a == c && b == d)
std::cout << "Yes\n";
else if (a == d && c == b)
std::cout << "Yes\n";
else
std::cout << "No\n";
}充电宝
题目描述
有一块电量为n的充电宝,她计划给若干块电池充电,每次充电时会有一定电量的损失,使用电量ai时,其损失电量为f(ai),f(x)表示除x以外最大因子。注意:若只充电1点,其损失电量也为1。
应该如何分配用光电量,使得损失总量最小。
输入格式
输入一个正数表示总电量n
输出格式
输出最小损失电量
输入样例#1
4
输出样例#1
2
输入样例#2
9
输出样例#2
2
说明提示
2≤n≤2×109
限制
时间限制:1000ms
内存限制:256MiB
#include <iostream>
#include <cmath>
using namespace std;
// 判断一个数是否为质数(高效试除法,适合大数)
bool is_prime(long long x) {
if (x <= 1) return false;
if (x == 2) return true;
if (x % 2 == 0) return false;
// 只需检查到sqrt(x),且只检查奇数
for (long long i = 3; i <= sqrt(x); i += 2) {
if (x % i == 0) return false;
}
return true;
}
int main() {
long long n;
cin >> n;
int min_loss;
if (is_prime(n)) {
// 情况1:n本身是质数,直接用1块,损失1
min_loss = 1;
} else if (n % 2 == 0) {
// 情况2:n是偶数(≥4),拆为两个质数,损失2
min_loss = 2;
} else {
// 情况3:n是奇数
if (is_prime(n - 2)) {
// 拆为2 + (n-2)(两个质数),损失2
min_loss = 2;
} else {
// n-2是合数,n必为3的倍数且≥9,拆为3+3+(n-6),损失3
min_loss = 3;
}
}
cout << min_loss << endl;
return 0;
}漫画书
题目描述
一套漫画书共有 N册,第 i册包含 Ai个章节。 已知全书总章节数是奇数。
如果把第 1 册第 1 章算作第 1 章,那么这套书正中间的那一章位于第几册第几章?
输入格式
第一行:一个整数 N
第二行:N个整数 A1,A2,…,AN,用空格隔开
输出格式
两个整数 a b,表示正中间那一章在第 a册第 b章
输入样例#1
1 1
输出样例#1
1 1
输入样例#2
12 28 31 31 30 31 30 31 31 30 31 31 30
输出样例#2
7 2
说明提示
1≤N≤100
1≤Ai≤100
保证书的章节总数为奇数
限制
时间限制:1000ms
内存限制:256MiB
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N;
cin >> N;
vector<int> A(N);
int total = 0;
// 读取每册的章节数,并计算总章节数
for (int i = 0; i < N; ++i) {
cin >> A[i];
total += A[i];
}
// 计算正中间章节的位置(总章节数为奇数,无需处理小数)
int mid = (total + 1) / 2;
int current_sum = 0; // 累加的章节数
int book_num = 0; // 所在册数
int chapter_num = 0; // 册内章节数
// 遍历每一册,找到中间章节所在位置
for (int i = 0; i < N; ++i) {
current_sum += A[i];
// 当累加和≥mid时,说明中间章节在当前册
if (current_sum >= mid) {
book_num = i + 1; // 册数从1开始计数
chapter_num = mid - (current_sum - A[i]); // 前i册累加和是current_sum - A[i]
break;
}
}
// 输出结果
cout << book_num << " " << chapter_num << endl;
return 0;
}实心正方形
题目描述
给定一个整数 n,请打印一个实心的正方形,它的边界由星号 * 构成,内部由 · 填充,每条边都恰好有 n个星号。
输入格式
单个整数:表示 n。
输出格式
输出一个边界为星号、内部为点的正方形。
输入样例#1
5
输出样例#1
***** *...* *...* *...* *****
输入样例#2
3
输出样例#2
*** *.* ***
说明提示
3≤n≤1000。
限制
时间限制:1000ms
内存限制:256MiB
#include<iostream>
int main()
{
int n;
std::cin >> n;
for(int i = 1; i <= n ; ++i){
for(int j = 1 ;j <= n ;++j){
if(i!=1&&j!=1&&i!=n&&j!=n)
std::cout << '.';
else
std::cout << '*';
}
std::cout << "\n";
}
}不同的数字
给定 n个正整数 a1、a2、……、an,请统计出这个数列中含有多少个不同的整数。
时间限制:1000ms,内存限制:256MB
输入格式
第一行:一个整数 n;
第二行:n 个整数 a1、a2、……、an。
输出格式
一个整数,数列中含有多少个不同的整数。
输入样例#1
6 1 6 5 6 3 1
输出样例#1
4
输入样例#2
10 1 2 3 4 5 6 7 8 9 10
输出样例#2
10
数据范围:
1≤n、ai≤105。
//C语言参考代码
#include <stdio.h>
int state[100001] = {0};
int main() {
int n, i;
scanf("%d", &n); // 读取数字的个数
for (i = 0; i < n; i++) {
int num;
scanf("%d", &num);
state[num] = 1; // 标记该数字出现过
}
// 统计出现过的数字个数
int count = 0;
for (i = 1; i <= 100000; i++) {
if (state[i]) {
count++;
}
}
printf("%d\n", count);
return 0;
}//C++参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> vt;
for (int i = 0; i < n; i++) {
int num;
cin >> num;
if(find(vt.begin(), vt.end(), num) == vt.end())
vt.push_back(num);
}
cout << vt.size() << endl;
return 0;
}丢失的数字
述给定整数 n 和一个包含 n - 1 个整数的序列,该序列由区间 [1, n] 内的 n - 1 个互异整数组成。请找出该区间内缺失的唯一整数。
时间限制:1000ms,内存限制:256MB
输入格式
第一行:一个整数 n;
第二行:n - 1 个整数。
输出格式
一个整数,表示丢失的数字。
输入样例#1
6 1 2 5 6 3
输出样例#1
4
输入样例#2
10 7 2 3 9 4 8 1 6 10
输出样例#2
5
数据范围:
1≤n≤2×104 ,输入序列保证合法。
//C语言参考代码
#include <stdio.h>
int a[20001];
int main() {
int i, j, n, min = -1; // 最小数字
scanf("%d", &n);
for (i = 0; i < n - 1; i++) {
int num;
scanf("%d", &num);
if(min == -1)
min = num;
else if(num < min)
min = num;
a[i] = num;
}
for(i=0; i< n - 1; i++) {
bool flag = false;
for(j=0; j<n-1; j++) { // 寻找对应的数字即:min + i
if(min + i == a[j]) {
flag = true;
break;
}
}
if(!flag) {
printf("%d\n", min + i);
break;
}
}
return 0;
}//C++参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> vt;
for (int i = 0; i < n - 1; i++) {
int num;
cin >> num;
vt.push_back(num);
}
sort(vt.begin(), vt.end());
int beg = vt[0];
for(int i=0; i<vt.size(); i++, beg++) {
if(vt[i] != beg) {
cout << beg << endl;
break;
}
}
return 0;
}维修任务
在一条商业街上,有 100个店铺,店铺从左到右编号为 1 到 100。工人从店铺 x 移动到 y 发生的移动距离为 ∣y - x∣。
现在需要完成 n 个修理任务。其中第 i 个任务要求工人移动到店铺 ai,报修任务分两类,用 L 表示任务分配给小李,用 R 表示任务分配给小任。必须按照报修的顺序来完成这些任务。
请计算,完成所有修理任务后,两位工人的总移动的总距离。工人最开始的位置可以按照最理想的情况安排。
时间限制:1000ms,内存限制:256MB
输入格式
第一行:一个整数 n,表示搬运次数;
接下来 n 行,每行一个整数 ai 表示商店位置,一个字符 Si 表示哪位工人完成。
输出格式
输出所有任务完成时的最小总距离。
输入样例#1
4 3 L 6 R 9 L 2 R
输出样例#1
10
输入样例#2
3 2 L 2 L 99 L
输出样例#2
97
输入样例#3
8 22 L 75 L 26 R 45 R 72 R 81 R 47 L 29 L
输出样例#3
154
数据范围:
1≤N≤100,1≤ai≤100,si∈{L, R}。
#include <stdio.h>
#include <math.h>
int main() {
int i, n, ls = -1, rs = -1, dist = 0;
//ls, rs 为-1表示L,R开始的位置
scanf("%d", &n);
for (i = 0; i < n; i++) {
int d;
char c;
scanf("%d %c", &d, &c);
if(c == 'L') {
if(ls != -1)
dist += abs(d - ls);
ls = d;
} else if(c == 'R') {
if(rs != -1)
dist += abs(d - rs);
rs = d;
}
}
printf("%d\n", dist);
return 0;
}硬币
可以使用任意数量的 a元硬币、b 元硬币和 c 元硬币。请找出恰好凑出 n 元所需的最小硬币总数。若无法凑出,则输出 -1。
时间限制:1000ms,内存限制:256MB
输入格式
第一行,整数 n;
第二行,三个整数表示 a、b、c。
输出格式
输出最小硬币总数(若无法凑出则输出 -1)。
输入样例#1
100 20 40 50
输出样例#1
2
输入样例#2
99 1 5 10
输出样例#2
14
数据范围:
1≤N≤109;1≤A≤B≤C≤109。保证最终最小硬币总数不超过104。
#include <stdio.h>
#include <limits.h> // 用于INT_MAX
int main() {
long long n, a, b, c;
scanf("%lld", &n);
scanf("%lld %lld %lld", &a, &b, &c);
int min_count = INT_MAX; // 初始化最小硬币数为最大整数
// 枚举c硬币的数量,最多不超过10000个
for (int x = 0; x * c <= n && x <= 10000; x++) {
long long rem1 = n - x * c; // 使用x个c后剩余的金额
if (rem1 < 0) {
break;
}
// 枚举b硬币的数量,最多不超过10000个
for (int y = 0; y * b <= rem1 && y <= 10000; y++) {
long long rem2 = rem1 - y * b; // 使用y个b后剩余的金额
if (rem2 < 0) {
break;
}
// 检查剩余金额是否能被a整除
if (rem2 % a == 0) {
int z = rem2 / a; // a硬币的数量
int total = x + y + z; // 总硬币数
// 更新最小硬币数
if (total < min_count) {
min_count = total;
}
}
}
}
// 若仍为初始值,说明无法凑出,否则输出最小硬币数
if (min_count == INT_MAX) {
printf("-1\n");
} else {
printf("%d\n", min_count);
}
return 0;
}游戏
游戏中有 N 个敌人,第 i 个敌人有 hi 的血量,当敌人血量降至 0 或以下时该敌人被消灭。
按照顺序从第 1 个敌人开始打,时间 T 从 0 开始,每次攻击前,先将 T 增加 1,若此时 T 为 3 的倍数,当前敌人掉 3 滴血,否则掉 1 滴血。求消灭全部敌人所需时间。
时间限制:1000ms,内存限制:256MB
输入格式
第一行输入一个正整数 N;
第二行输入 N 个 正整数 H1、H2、……、Hn。
输出格式
输出一行答案 T。
输入样例#1
3 3 1 4
输出样例#1
6
输入样例#2
6 3 14 15 9 2 6
输出样例#2
33
数据范围:
1≤ N≤ 2×105;1≤ Hi ≤109。
#include <stdio.h>
long long n, a[200005];
bool check() {
for (int i = 0; i < n; i++) {
if(a[i] > 0)
return false;
}
return true;
}
int main() {
int t = 0, cur = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%lld", &a[i]);
}
while(true) {
t++;
if(t % 3 == 0)
a[cur] -= 3;
else
a[cur] -= 1;
if(check())
break;
while(a[cur] <= 0) // 下一个
cur = (cur + 1) % n;
}
printf("%lld\n", t);
return 0;
}区间的交
题目描述
一个区间可以由两个整数描述,表示为 [a,b], 意思是所有大于等于 a 且小于等于 b 的数字。
给定两个区间,第一个是 [a,b],第二个是 [p,q],请判断这两个区间的关系。
· 如果这两个区间没有公共的交集,输出 Disjoint
· 否则,如果一个区间完全包含另一个区间,输出 Nested
· 否则,如果两个区间有一部分内容重叠,输出 Overlap
输入格式
· 第一行:两个整数 a 与 b
· 第二行:两个整数 p 与 q
输出格式
根据区间的相交关系输出 Disjoint、Nested 或 Overlap
输入样例1
1 10 2 20
输出样例1
Overlap
输入样例2
-1 1 10 20
输出样例2
Disjoint
输入样例3
-100 100 -10 10
输出样例3
Nested
说明提示
-1,000,000,000≤a≤b≤1,000,000,000
-1,000,000,000≤p≤q≤1,000,000,000
#include <iostream>
using namespace std;
int main() {
int a, b, p, q;
cin >> a >> b >> p >> q;
// 判断是否无交集
if (b < p || q < a) {
cout << "Disjoint" << endl;
}
// 判断包含关系
else if ((a <= p && q <= b) || (p <= a && b <= q)) {
cout << "Nested" << endl;
}
// 部分重叠情况
else {
cout << "Overlap" << endl;
}
return 0;
}亲和数
题目描述
古希腊数学家毕达哥拉斯发现,某些正整数的真因子之和等于另一个数,而另一个数的真因子之和恰好就等于前者。
例如,220 的所有真因子之和为:
1+2+4+5+10+11+20+22+44+55+110=284
而 284 的所有真因子为:
1+2+4+71+142=220
人们对这样的数感到很惊奇,并称之为亲和数。一般地讲,如果两个数中任何一个数都是另一个数的真约数之和,则这两个数就是亲和数。
输入格式
输入数据第一行包含一个数 M,接下有 M 行,每行一个实例,包含两个整数 A,B。
输出格式
对于每个测试实例,如果 A 和 B 是亲和数的话输出 YES,否则输出 NO。
输入样例
2 220 284 100 200
输出样例
YES NO
说明提示
0≤M≤30
0≤A,B≤100000
//C代码
#include <stdio.h>
// 函数:计算一个数的真因子之和
int sumOfProperDivisors(int num) {
if (num <= 1) {
return 0;
}
int sum = 1; // 1是所有大于1的数的真因子
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
sum += i;
if (i != num / i) { // 避免重复添加平方数的情况
sum += num / i;
}
}
}
return sum;
}
// 函数:判断两个数是否为亲和数
int areAmicableNumbers(int a, int b) {
return (sumOfProperDivisors(a) == b) && (sumOfProperDivisors(b) == a);
}
int main() {
int M;
scanf("%d", &M); // 读取测试实例的数量
for (int i = 0; i < M; i++) {
int A, B;
scanf("%d %d", &A, &B); // 读取每对数字
if (areAmicableNumbers(A, B)) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}//C++代码
#include <iostream>
#include <cmath>
// 计算一个数的真因子之和(不包括自身)
int getSumOfProperDivisors(int n) {
if (n <= 1) return 0; // 0和1没有真因子
int sum = 1; // 1是所有大于1的数的真因子
// 从2遍历到平方根,找出所有因子对
for (int i = 2; i <= std::sqrt(n); i++) {
if (n % i == 0) {
sum += i;
if (i != n / i) { // 避免平方根重复计算
sum += n / i;
}
}
}
return sum;
}
int main() {
int M;
std::cin >> M; // 读取测试用例数量
while (M--) {
int A, B;
std::cin >> A >> B; // 读取一对数
// 计算两数的真因子和
int sumA = getSumOfProperDivisors(A);
int sumB = getSumOfProperDivisors(B);
// 检查是否为亲和数
if (sumA == B && sumB == A) {
std::cout << "YES" << std::endl;
} else {
std::cout << "NO" << std::endl;
}
}
return 0;
}