C/C++编程四级 题库
有几个PAT
字符串 APPAPT 中包含了两个单词 PAT,其中第一个 PAT 是第 2 位(P),第 4 位(A),第 6 位(T);第二个 PAT 是第 3 位(P),第 4 位(A),第 6 位(T)。
现给定字符串,问一共可以形成多少个 PAT?
时间限制:1000
内存限制:262144
输入
输入只有一行,包含一个字符串,长度不超过105,只包含 P、A、T 三种字母。
输出
在一行中输出给定字符串中包含多少个 PAT。由于结果可能比较大,只输出对 1000000007 取余数的结果。
样例输入
APPAPT
样例输出
2
#include<iostream>
#include<string>
using namespace std;
int main()
{
long long sum = 0;
string list;
getline(cin, list);
for (int i = 0,p=0,a=0; i < list.size(); ++i)
{
if (list[i] == 'P')
{
++p;
}
if (list[i] == 'A')
{
a += p;
}
if (list[i] == 'T')
{
sum += a;
}
}
sum %= 1000000007;
cout << sum << endl;
system("pause");
return 0;
}彩带
织女要织一条自己最爱的彩带,方法是从一条现成的彩带上按照她喜欢的颜色顺序保留她最爱的几种颜色,裁掉不要的部分,把留下的缝制在一起,就制成了她最喜欢的彩带。
一般肉眼能分辨的颜色不超过 200 种,所以织女的彩带颜色是有限的。但原始的彩带可是非常长,并且织女想最后形成的彩带也尽可能长,所以她需要你的帮助来得到一个最佳的结果。
注意到解可能是不唯一的,但你只需要告诉她结果的长度即可。例如,给定原始的彩带为 { 2 2 4 1 5 5 6 3 1 1 5 6 },其中数字代表颜色的编号。如果织女喜欢的颜色和顺序是 { 2 3 1 5 6 },则她可以得到 4 个不同的最优解:{ 2 2 1 1 1 5 6 }、{ 2 2 1 5 5 5 6 }、{ 2 2 1 5 5 6 6 } 和 { 2 2 3 1 1 5 6 },长度都是 7。
时间限制:1000
内存限制:262144
输入
输入第一行给出一个正整数 N(≤ 200),为颜色种类的数量(即颜色从 1 到 N 编号)。下一行先给出一个正整数 M(≤ 200),随后是织女喜欢的 M个颜色,按她喜欢的顺序给出。第三行也是先给出一个正整数 L(≤ 104),即原始彩带的长度,随后是 L 个颜色值。一行中的所有数字以空格分隔。
输出
只需要输出织女最喜欢的彩带的最大长度值。
样例输入
6 5 2 3 1 5 6 12 2 2 4 1 5 5 6 3 1 1 5 6
样例输出
7
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main() {
int N, M, L;
cin >> N; // 颜色总数,此处可忽略
// 读取织女喜欢的颜色序列
cin >> M;
vector<int> favorite(M);
for (int i = 0; i < M; ++i) {
cin >> favorite[i];
}
// 建立颜色到位置的映射,记录每个颜色最后出现的位置
unordered_map<int, int> colorToPos;
for (int i = 0; i < M; ++i) {
colorToPos[favorite[i]] = i + 1; // 位置从1开始
}
// 读取原始彩带并转换为有效的位置列表
cin >> L;
vector<int> positions;
for (int i = 0; i < L; ++i) {
int color;
cin >> color;
if (colorToPos.count(color)) {
positions.push_back(colorToPos[color]);
}
}
// 动态规划处理
vector<int> currentMax(M + 1, 0); // currentMax[i]表示以位置i结尾的最长子序列长度
vector<int> prefixMax(M + 1, 0); // prefixMax[i]表示前i个位置的最大长度
for (int p : positions) {
int newLen = prefixMax[p] + 1;
if (newLen > currentMax[p]) {
currentMax[p] = newLen;
// 更新prefixMax数组
for (int i = 1; i <= M; ++i) {
if (i == 1) {
prefixMax[i] = currentMax[i];
} else {
prefixMax[i] = max(prefixMax[i - 1], currentMax[i]);
}
}
}
}
cout << prefixMax[M] << endl;
return 0;
}方法思路:
预处理织女喜欢的颜色序列:建立一个颜色到位置的映射,记录每个颜色在织女喜欢的序列中最后出现的位置。
过滤原始彩带:将原始彩带中的颜色转换为对应的位置,过滤掉不在织女喜欢的颜色序列中的颜色。
动态规划:维护两个数组,current_max 和 prefix_max。current_max 数组记录以每个位置结尾的最长子序列长度,prefix_max 数组记录前缀最大值。遍历处理后的位置列表,更新这两个数组,最终得到最长子序列的长度。
最长峰形线
在科学研究中,很多时候需要从一大堆原始数据中找出一条最好的“峰形线”。所谓长度为 L 的“峰形线”,是指 L 个数字组成的有序序列 { D1, …, DL },满足条件:存在下标 i(1 < i < L)使得 D1 < … < Di-1 < Di > Di+1 > … > DL。
顺次给出 n 个数字,你可以从中删掉部分数字,使得剩下的数字能构成峰形线。要求构造出来的峰形线是最长的。当最长峰形线不唯一时,你要输出最对称(即升序和降序两部分长度之差为最小)的那条。
时间限制:7000
内存限制:262144
输入
输入第一行给出一个正个整数 n (3 ≤ n ≤ 104),随后一行给出 n 个在区间 [-10000, 10000] 内的整数,以空格分隔。
输出
首先在一行中输出最长峰形线的长度、峰顶数字的序号(从 1 开始)和它的值,数字间以 1 个空格分隔。如果解不存在,则在一行中输出 `No peak shape`。裁判数据保证输出是唯一的。
样例输入
样例#1:
20
1 3 0 8 5 -2 29 20 20 4 10 4 7 25 18 6 17 16 2 -1
样例#2:
5
-1 3 8 10 20
样例输出
样例#1:
10 14 25
样例#2:
No peak shape
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
if (n < 3) {
cout << "No peak shape" << endl;
return 0;
}
// LIS dp (Longest Increasing Subsequence from the left)
vector<int> lis(n, 1); // lis[i] 表示以 arr[i] 为结尾的最长上升子序列长度
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j]) {
lis[i] = max(lis[i], lis[j] + 1);
}
}
}
// LDS dp (Longest Decreasing Subsequence from the right)
vector<int> lds(n, 1); // lds[i] 表示以 arr[i] 为开始的最长下降子序列长度
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j > i; j--) {
if (arr[i] > arr[j]) {
lds[i] = max(lds[i], lds[j] + 1);
}
}
}
int maxLength = 0;
int bestIndex = -1;
int bestValue = INT_MIN;
int bestDiff = INT_MAX;
// 查找峰形线
for (int i = 1; i < n - 1; i++) {
// 如果 arr[i] 是峰顶
if (lis[i] > 1 && lds[i] > 1) {
int length = lis[i] + lds[i] - 1; // 总长度
int diff = abs(lis[i] - lds[i]); // 升降长度差
if (length > maxLength || (length == maxLength && diff < bestDiff)) {
maxLength = length;
bestIndex = i;
bestValue = arr[i];
bestDiff = diff;
}
}
}
// 输出结果
if (maxLength == 0) {
cout << "No peak shape" << endl;
} else {
cout << maxLength << " " << bestIndex + 1 << " " << bestValue << endl;
}
return 0;
}红蓝串
小红有两条珠串,一条有 A 只红色珠子,另一条有 B 只蓝色珠子。她想用下列步骤做一条红蓝珠子的串:
- 她会从两条珠串上一步一步地取下珠子。
- 第 i 步时,她会从一条珠串上取下 i 颗珠子,穿到结果串上。
- 她最后要得到一条有 n 颗珠子的串。
小红有可能得到多少种不同的结果呢?
如果小红在至少某一步中选择了不同颜色的串来取珠子,那么两条结果串就被认为是不同的。
时间限制:6000
内存限制:262144
输入
输入在一行中给出 3 个整数:n (0 < n ≤ 2 × 105)、A、B (0≤ A, B ≤ 105),其定义如题面所述。
输出
在一行中输出小红有可能得到多少条有 n 颗珠子的串。因为结果可能是很大的数字,所以你要输出对 1000000007 (109 + 7) 取模后的结果。
样例输入
10 4 7
样例输出
4
提示
小红能得到的 4 种不同的结果如下图所示。

#include#include #include using namespace std; const int MOD = 1000000007; int main() { long long n, A, B; cin >> n >> A >> B; long long D = 8 * n + 1; long long m = sqrt(D); if (m * m != D || m % 2 == 0) { cout << 0 << endl; return 0; } long long k = (m - 1) / 2; long long low = max(n - B, 0LL); long long high = min(A, n); if (low > high) { cout << 0 << endl; return 0; } vector dp(n + 1, 0); dp[0] = 1; for (int i = 1; i <= k; ++i) { for (int s = n; s >= i; --s) { dp[s] = (dp[s] + dp[s - i]) % MOD; } } long long ans = 0; for (int s = low; s <= high; ++s) { ans = (ans + dp[s]) % MOD; } cout << ans << endl; return 0; }
总异或和


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
ll ans = 0;
// 遍历每一位 0~30
for (int k = 0; k <= 30; ++k)
{
ll mod = 1LL << (k + 1);
ll half = 1LL << k;
vector<ll> rem;
for (ll x : a)
rem.push_back(x % mod);
sort(rem.begin(), rem.end());
ll cnt = 0;
int l = 0, r = n - 1;
// 统计 r_i + r_j >= half 且 < mod
for (; r >= 0; --r)
{
while (l < n && rem[l] + rem[r] < half)
l++;
cnt += n - max(l, r + 1);
}
// 统计 r_i + r_j >= mod + half
l = 0, r = n - 1;
for (; r >= 0; --r)
{
while (l < n && rem[l] + rem[r] < mod + half)
l++;
cnt += n - max(l, r + 1);
}
if (cnt % 2 == 1)
ans |= half;
}
cout << ans << endl;
return 0;
}三数之和


#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
// 两个字符串大数相加
string add(string s1, string s2)
{
vector<int> res;
int i = s1.size() - 1, j = s2.size() - 1, carry = 0;
while (i >= 0 || j >= 0 || carry)
{
int a = i >= 0 ? s1[i--] - '0' : 0;
int b = j >= 0 ? s2[j--] - '0' : 0;
int sum = a + b + carry;
carry = sum / 10;
res.push_back(sum % 10);
}
string ans;
reverse(res.begin(), res.end());
for (int num : res) ans += (char)('0' + num);
return ans;
}
int main()
{
string a, b, c;
cin >> a >> b >> c;
string total = add(add(a, b), c);
cout << total << endl;
return 0;
}计算不同位
题目描述
给你两个正整数 m、n,请问它们二进制位上有多少位是不同的。
输入
两个正整数 n、m。
输出
一个整数,表示答案。
数据范围:
1≤n、m≤10^9。
输入样例1
2 1
输出样例1
2
输入样例2
3 17
输出样例2
2
输入样例3
233 233
输出样例3
0
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, ans = 0;
unsigned int mask = 1;
cin >> n >> m;
for(int i=0; i<32; i++) {
if((n & mask) != (m & mask))
ans++;
mask<<=1; //左移一位
}
cout << ans;
return 0;
}四方定理
题目描述
给定一个自然数 n,请输出 n 的所有四平方拆分方案。
输入
单个整数:表示 n。
输出
若干行:每行四个由小到大排列的自然数,表示一种拆分方案。
如果有多种方案,先输出首项较小的方案,对于首项相同的方案,先输出第二项较小的方案,其他情况以此类推。
数据范围:
0≤n≤50,000。
输入样例1
25
输出样例1
0 0 0 5 0 0 3 4 1 2 2 4
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
for(int a=0; a*a<=n; a++) { //使用三重循环避免超时
for(int b=a; a*a+b*b<=n; b++) {
for(int c=b; a*a+b*b+c*c<=n; c++) {
int left=n-a*a-b*b-c*c; //剩余数
int d=sqrt(left);
if(d*d==left && d>=c) //判断d是整数即可
cout << a << " " << b << " " << c << " " << d << endl;
}
}
}
return 0;
}进制数位
题目描述
给定一个十进制正整数 n,请计算 n 在 2 进制到 16 进制下,各有多少位数字。
输入
一个正整数n。
输出
输出一行,表示在各种进制下各有多少数位。
数据范围
1≤n≤2×10^9。
输入样例1
3
输出样例1
2 2 1 1 1 1 1 1 1 1 1 1 1 1 1
输入样例2
31415926
输出样例2
25 16 13 11 10 9 9 8 8 8 7 7 7 7 7
#include<iostream>
using namespace std;
int calNum(int n, int base) {
int num = 0;
while(n!=0) {
num++;
n /= base;
}
return num;
}
int main() {
int n;
cin >> n;
for(int i=2; i<=16; i++) {
cout << calNum(n, i) << " ";
}
return 0;
}缺失的档案
题目描述
你有一套连续编号的绝密档案,共 n+1 份。它们被整齐地归档在档案柜中。然而,一场意外之后,你发现其中一份档案不翼而飞。
现在,你手上是剩下的 n 份档案的编号 a1, a2, …, an 。请你找出那份丢失的档案编号。
档案的编号是连续的,因此丢失的那一份是唯一确定的,即丢失的肯定不是第一份或最后一份。
输入
第一行:一个整数 n。
第二行:n 个整数 a1, a2, …, an,用空格隔开。
输出
一个整数,表示丢失的贴纸编号。
数据范围
2≤n≤100,1≤ai≤1000,输入均为整数,丢失的整数唯一确定。
输入样例1
3 5 3 2
输出样例1
4
输入样例2
4 111 115 112 114
输出样例2
113
#include <bits/stdc++.h>
using namespace std;
int a[100] = {0};
int main() {
int n;
cin >> n;
for(int i=0; i<n; i++) {
cin >> a[i];
}
sort(a, a+n); //排序
for(int i=1; i<n; i++) {
if(a[i]-a[i-1]!=1) {
cout << a[i] - 1;
break;
}
}
return 0;
}几何计数
题目描述
你在坐标纸上标记了 n 个互不相同的点。
现在你想知道:从这些点中任选三个,有多少种选择方式能构成一个真正的三角形?
所谓真正的三角形,是指三个顶点不共线,即面积大于零的三角形。请计算这个数目。
输入
第一行,一个整数 n,表示点的数量。
接下来 n 行,每行包含两个整数 xi 和 yi ,表示第 i 个点的坐标。
输出
输出一个整数,表示能够构成三角形的三点组合的数量。
数据范围
3≤N≤300,-10^9≤Xi、Yi≤10^9,所有点的坐标互不相同。
输入样例1
3 0 0 2 0 0 -3
输出样例1
1
输入样例2
20 224 433 987654321 987654321 2 0 6 4 314159265 358979323 0 0 -123456789 123456789 -1000000000 1000000000 124 233 9 -6 -4 0 9 5 -7 3 333333333 -333333333 -9 -1 7 -10 -1 5 324 633 1000000000 -1000000000 20 0
输出样例2
1124
#include <bits/stdc++.h>
using namespace std;
int x[300] = {0}, y[300] = {0};
int main() {
int n, cnt = 0;
cin >> n;
for(int i=0; i<n; i++) {
cin >> x[i] >> y[i];
}
//枚举所有情况
for(int i=0; i<n; i++) {
for(int j=i+1; j<n; j++) {
for(int k=j+1; k<n; k++) {
// (x2-x1)(y3-y1)-(x3-x1)(y2-y1)不为0
long long s=(x[j]-x[i])*(y[k]-y[i])-(x[k]-x[i])*(y[j]-y[i]);
if(s!=0)
cnt++;
}
}
}
cout << cnt;
return 0;
}最佳操作数
题目描述
给定一个数字 x,再给定一个等差数列。请寻找这个等差数列距离 x 最近的数字,并输出这个最小距离。
等差数列的第一项叫做首项,用数字 a 表示,接下来每一项都比前一项多 d,d 称之为公差,数列的项数记为 n。
输入
输入四个整数分别表示 x、a、d、n。
输出
输出一个整数表示最少的操作次数。
数据范围
-10^18≤x、a≤10^18,-10^6≤d≤10^6,1≤n≤10^12。
输入样例1
3 1 3 3
输出样例1
1
输入样例2
-1000000000000000000 1 3 3
输出样例2
1000000000000000001
#include <bits/stdc++.h>
using namespace std;
int main() {
long long x, a, d, n;
cin >> x >> a >> d >> n;
if(d==0) { //公差为0
cout << abs(x-a);
} else {
long long L=a; //左边界
long long R=a+(n-1)*d; //右边界
if(d < 0)
swap(L, R);
if(x <= L) {
cout << abs(L-x);
} else if(x>=R) {
cout << abs(R-x);
} else {
long long k = (x - a) / d; //最接近的项
//比较邻近的第k-1项,k项和k+1项
long long minDelta=abs(a+k*d-x);
if(k-1>=0)
minDelta=min(minDelta, abs(a+(k-1)*d-x));
if(k+1<n)
minDelta=min(minDelta, abs(a+(k+1)*d-x));
cout << minDelta;
}
}
return 0;
}替换
有一个包含 N 个正整数 A1、A2、……、AN 的数列 A。接下来将进行 Q 次操作:
在第 i 次操作中,将数列中所有值为 Bi 的元素替换为 Ci。请针对每次操作(1≤i≤Q),输出操作后数列 A 的所有元素之和 Si。
时间限制:1000ms,内存限制:256MB
输入格式
第一行,一个整数 N;
第二行,N 个整数 A1、A2、……、AN;
第三行,一个整数 Q。
接下来 Q行,每行两个整数 Bi、Ci。
输出格式
输出 Q行,每行一个整数 Si,表示每次操作后的数列总和。注意:Si 可能超出32 位整数范围。
输入样例#1
4 1 2 3 4 3 1 2 2 4 3 4
输出样例#1
11 15 16
输入样例#2
5 1 2 3 4 5 5 1 2 2 3 3 4 4 5 5 1
输出样例#2
16 18 21 25 5
数据范围:
1≤N、Q、Ai、Bi、Ci≤105,Bi≠Ci。
//C语言
#include <stdio.h>
int a[100000];
int main() {
int i, j, n, q, b, c;
long long s;
scanf("%d", &n);
for(i=0; i<n; i++) { //输入 n 个元素
scanf("%d", &a[i]);
}
scanf("%d", &q);
for(i=0; i<q; i++) {
scanf("%d %d", &b, &c);
s = 0;
// 遍历列表进行值替换
for(j = 0; j < n; j++) {
if(a[j] == b)
a[j] = c;
s += a[j];
}
printf("%lld\r\n", s);
}
return 0;
}//C++
#include <iostream>
using namespace std;
int a[100000];
int main() {
int n, q, b, c;
long long s;
cin >> n;
for(int i=0; i<n; i++) { //输入 n 个元素
cin >> a[i];
}
cin >> q;
for(int i=0; i<q; i++) {
cin >> b >> c;
s = 0;
// 遍历列表进行值替换
for(int j = 0; j < n; j++) {
if(a[j] == b)
a[j] = c;
s += a[j];
}
cout << s << endl;
}
return 0;
}无法整除的数
给定一个长度为 N 的数列 A。请计算满足以下条件的下标 i(1≤i≤N)的数量:
对于任意 j(1≤j≤N且 i≠j),元素 Ai 不能被 Aj 整除。
时间限制:1000ms,内存限制:256MB
输入格式
第一行,一个整数 N;
第二行,N 个整数表示 A1、A2、……、AN。
输出格式
输出一个整数,表示满足条件的下标数量。
输入样例#1
5 2 3 9 11 19
输出样例#1
4
输入样例#2
10 11 18 45 28 8 19 89 86 2 4
输出样例#2
5
数据范围:
所有输入均为整数;1≤N≤2×105;1≤Ai≤106。
//C语言
#include <stdio.h>
int a[100000];
int main() {
int i, j, n, cnt;
scanf("%d", &n);
cnt = n; // 先假设所有的数都符合要求
for(i=0; i<n; i++) { //输入 n 个元素
scanf("%d", &a[i]);
}
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(i==j)
continue;
if(a[i] % a[j] == 0) {
cnt--; // 能整除则 个数减 1
break;
}
}
}
printf("%d", cnt);
return 0;
}//C++
#include <iostream>
using namespace std;
int a[100000];
int main() {
int n, c;
cin >> n;
c = n; // 先假设所有的数都符合要求
for(int i=0; i<n; i++) {
cin >> a[i];
}
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(i==j)
continue;
if(a[i] % a[j] == 0) {
c--; // 能整除则 个数减 1
break;
}
}
}
cout << c << endl;
return 0;
}咖啡机
一台自动咖啡机按以下规则接单:制作一杯咖啡需要 c 秒,只有当前订单制作完成后,才能处理下一个订单。如果在制作期间,接到新订单,则做忽略处理。
有 n 位顾客下单,其中第 i 位顾客的下单时间为第 ti 秒,保证所有下单时间均不重复。这台咖啡机最多能完成多少杯订单?
时间限制:1000ms,内存限制:256MB
输入格式
第一行,两个整数表示 n、c;
第二行,n 个整数表示 t1、t2、t3、……、tn。
输出格式
这台咖啡机最多能完成多少杯订单。
输入样例#1
6 5 1 3 12 10 8 7
输出样例#1
3
输入样例#2
3 2 0 2 4
输出样例#2
3
输入样例#3
10 3 0 3 4 9 15 12 6 17 19 20
输出样例#3
7
数据范围:
1≤n≤100;1≤c≤1000;0≤ti≤1000。
#include <bits/stdc++.h>
using namespace std;
int s[1005] = {0}, t[1005]; // s表示每秒的状态
int main() {
int n, c, cnt = 0;
cin >> n >> c;
for(int i=0; i<n; i++) { //输入 n 个元素
cin >> t[i];
}
sort(t, t + n); //从小到大排序
for(int i=0; i<n; i++) {
if(s[t[i]] == 0) {
// 将t[i]开始的c秒状态置为忙
for(int j = t[i]; j<t[i]+c; j++) {
s[j] = 1;
}
cnt++;
}
}
printf("%d", cnt);
return 0;
}字符数对
给定一个由字符 o 和 x 组成的长度为 N 的字符串 S。请计算满足以下所有条件的整数对(l,r)的数量:
(1)1≤l≤r≤N;
(2)在字符串 S 的子串 S[l...r](从第 l 个字符到第 r 个字符)中,同时包含 o 和 x 两种字符。
时间限制:1000ms,内存限制:256MB
输入格式
第一行,一个整数 N;
第二行,一个字符串 S。
输出格式
输出满足条件的整数对的数量。
输入样例#1
4 oxxo
输出样例#1
5
输入样例#2
7 xoxooxx
输出样例#2
19
数据范围:
1≤N≤106;S 仅由字符 o 和 x 组成。
#include <bits/stdc++.h>
using namespace std;
char s[1000005];
int main() {
int n, cnt = 0;
cin >> n >> s;
for(int i=0; i<n; i++) {
for(int j=i+1; j<n; j++) {
//检查s[i...j]是否包括o和x
bool of=false, xf=false;
for(int k=i; k<=j; k++) {
if(s[k] == 'o')
of = true;
if(s[k] == 'x')
xf = true;
if(of && xf)
break;
}
if(of && xf)
cnt++;
}
}
printf("%d", cnt);
return 0;
}打印金字塔
给定一个整数 n,请打印一个具有 n 层结构的三角形金字塔,具体图形见样例。
输入格式
第一行:单个整数表示 n
输出格式
若干行:表示一个金字图案,注意行末不要有空格
输入样例#1
1
输出样例#1
/\ /__\
输入样例#2
3
输出样例#2
/\ /__\ /\ /\ /__\/__\ /\ /\ /\ /__\/__\/__\
限制
时间限制:1000ms
内存限制:512MiB
#include <iostream>
using namespace std;
void draw(int num, int space) { // 绘制每层
// 每层的第一行
for (int i = 0; i < space; i++) cout << " ";
for (int i = 1; i <= num; i++) cout << " /\\ ";
cout << endl;
// 每层的第二行
for (int i = 0; i < space; i++) cout << " ";
for (int i = 1; i <= num; i++) cout << "/__\\";
cout << endl;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
draw(i, 2 * (n - i)); // 第$i$层包含$i$座金字塔,前导空格:$2×(n-i)$个
}
return 0;
}统计数带
给定两个正整数 a 和 b,它们之间的十进制数字组成了一条数带,请问其中相邻的两位数字组成 12 的情况出现了多少次?例如 a=210,b=213,则数带为
2 1 0 2 1 1 2 1 2 2 1 32~1~0~2~1~1~2~1~2~2~1~32 1 0 2 1 1 2 1 2 2 1 3
其中 12 出现了两次,第一个 12 由 211 的个位和 212 的百位组成。
输入格式
两个整数 a 和 b。
输出格式
数带中 12 出现的次数。
输入样例#1
210 212
输出样例#1
2
输入样例#2
1 9
输出样例#2
1
说明提示
1≤a≤b≤106
限制
时间限制:1000ms
内存限制:512MiB
#include <iostream>
#include <string>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
// 生成数带字符串
string tape;
for (int num = a; num <= b; ++num) {
tape += to_string(num);
}
// 统计"12"出现次数
int count = 0;
for (int i = 0; i < tape.size() - 1; ++i) {
if (tape[i] == '1' && tape[i+1] == '2') {
count++;
}
}
cout << count << endl;
return 0;
}排队序列
已知现在有 n 个人需要打电话,他们已经排好了队伍,每个人打电话的时间为Ti。请你帮助他们找到一个排队打电话的队列方案,使队伍的平均等待时间更短。
输入格式
第一行:一个正整数n,表示一共n个人。
第二行:n个数字,分别表示第1个人到第n个人每人的打电话时间T1,T2,…,Tn,每个数据之间有1个空格。
输出格式
第一行为一种排队顺序,即原先队列编号1到n的一种排列;
第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位,按照C语言的浮点数保留规则进行保留)。
输入样例
10 56 12 1 99 1000 234 33 55 99 812
输出样例
3 2 7 8 1 4 9 6 10 5 291.90
说明提示
1≤n≤100000
1≤Ti≤1000000
如果有多种排列都可以让平均等待时间最短,则输出其中字典序最小的序列。字典序指的是英文单词在字典中排序使用的规则顺序。
限制
时间限制:1000ms
内存限制:512MiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
struct Person {
int id;
int time;
};
bool cmp(const Person &a, const Person &b) {
if(a.time != b.time) return a.time < b.time;
return a.id < b.id;
}
int main() {
int n;
cin >> n;
vector<Person> people(n);
for(int i = 0; i < n; i++) {
cin >> people[i].time;
people[i].id = i + 1;
}
sort(people.begin(), people.end(), cmp);
long long total_wait = 0;
long long current_wait = 0;
for(int i = 0; i < n; i++) {
if(i > 0) cout << " ";
cout << people[i].id;
if(i > 0) current_wait += people[i-1].time;
total_wait += current_wait;
}
cout << endl;
double avg_wait = (double)total_wait / n;
cout << fixed << setprecision(2) << avg_wait << endl;
return 0;
}汽车牌照
作为汽车行驶的重要身份标志——汽车牌照也是越来越不够用了,从最早的十进制发展到三十六进制了,以前的一个汽车牌照“888888”,而现在的牌照变成了形如“A3GH11”。
三十六进制以大写字母 A 到 Z 表示数码 10 到 35。
请计算前后两辆汽车的牌照,在十进制下差多少?
输入格式
输入两行:
第一行为第一辆车的牌照
第二行为第二辆车的牌照
输出格式
共一行,表示两辆汽车牌照在十进制下的差的绝对值。
输入样例#1
888888 888889
输出样例#1
1
输入样例#2
888880 88888A
输出样例#2
10
说明提示
数据保证输入车牌转换成十进制后不超过 long long 范围。
限制
时间限制:1000ms
内存限制:512MiB
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
long long convertToDecimal(const string &plate) {
long long result = 0;
for (char c : plate) {
int value;
if (isdigit(c)) {
value = c - '0';
} else {
value = toupper(c) - 'A' + 10;
}
result = result * 36 + value;
}
return result;
}
int main() {
string plate1, plate2;
cin >> plate1 >> plate2;
long long num1 = convertToDecimal(plate1);
long long num2 = convertToDecimal(plate2);
cout << abs(num1 - num2) << endl;
return 0;
}