C/C++编程四级 题库
替换
有一个包含 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;
}排队序列
已知现在有 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;
}兔子不吃窝边草
有谚语云:“兔子不吃窝边草”。现给定若干块排列成一条线的草皮,假设兔子从任何一块草皮开始吃,但吃完一块后,绝对不吃直接相邻的草皮,则兔子最多可以吃掉多少草?
时间限制:10000
内存限制:65536
输入
输入第一行给出两个正整数,即 N (≤ 105) 为草皮的块数、 i (1 ≤ i ≤ N) 为兔子开始吃的第一块草皮的编号。第二行给出 N 个正整数 (≤ 103),以空格分隔,依次表示每块草皮的含草量。
输出
首先在一行中输出这只兔子最多可以吃掉的草量。下一行按兔子吃草的顺序输出每块被吃掉的草皮的编号。同行数字以 1 个空格分隔,行首尾不得有多余空格。 注意:我们必须假设兔子只朝一个方向跳着吃草,否则如果它可以来回跳,就能吃掉所有的草了。如果朝左右两个方向得到的结果一样,则兔子总是喜欢向左边跳;并且如果有多块草皮都可以得到同样的结果,兔子总是选择跳到离自己最近的那块。
样例输入
样例1:
10 4 2 1 4 3 1 1 5 2 3 1
样例2:
10 8 2 1 4 3 1 1 5 2 3 1
样例输出
样例1:
11 4 7 9
样例2:
9 8 6 3 1
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
pair<int, vector<int>> solve_dp(const vector<int>& vals) {
int n = vals.size();
if (n == 0) return {0, {}};
vector<int> dp(n, 0);
dp[0] = vals[0];
if (n >= 1) {
dp[1] = max(vals[0], vals[1]);
}
for (int j = 2; j < n; ++j) {
dp[j] = max(dp[j - 1], dp[j - 2] + vals[j]);
}
vector<int> selected;
int j = n - 1;
while (j >= 0) {
if (j == 0) {
selected.push_back(j);
break;
}
if (dp[j] == dp[j - 1]) {
--j;
} else {
selected.push_back(j);
j -= 2;
}
}
reverse(selected.begin(), selected.end());
return {dp.back(), selected};
}
int main() {
int N, i;
cin >> N >> i;
vector<int> arr(N);
for (int j = 0; j < N; ++j) {
cin >> arr[j];
}
vector<int> left_pos, left_vals;
for (int pos = i - 2; pos >= 1; --pos) {
left_pos.push_back(pos);
left_vals.push_back(arr[pos - 1]);
}
auto [left_sum, left_idx] = solve_dp(left_vals);
int total_left = arr[i - 1] + left_sum;
vector<int> left_path;
for (int idx : left_idx) {
left_path.push_back(left_pos[idx]);
}
vector<int> right_pos, right_vals;
for (int pos = i + 2; pos <= N; ++pos) {
right_pos.push_back(pos);
right_vals.push_back(arr[pos - 1]);
}
auto [right_sum, right_idx] = solve_dp(right_vals);
int total_right = arr[i - 1] + right_sum;
vector<int> right_path;
for (int idx : right_idx) {
right_path.push_back(right_pos[idx]);
}
bool choose_left = false;
if (total_left > total_right) {
choose_left = true;
} else if (total_left == total_right) {
choose_left = true;
} else {
choose_left = false;
}
vector<int> path;
path.push_back(i);
if (choose_left) {
for (int pos : left_path) {
path.push_back(pos);
}
} else {
for (int pos : right_path) {
path.push_back(pos);
}
}
cout << (choose_left ? total_left : total_right) << endl;
for (size_t k = 0; k < path.size(); ++k) {
if (k > 0) cout << " ";
cout << path[k];
}
cout << endl;
return 0;
}漂亮的序列
对于给定的整数 m,我们称一个序列是“漂亮”的,如果它包含至少 2 个整数,并且有 2 个相邻数字的差不超过m。你的任务是计算一个给定的 n 个正整数的序列中,有多少个子序列是漂亮的。
时间限制:6000
内存限制:65536
输入
输入第一行给出 2 个正整数 n 和 m (2 ≤ n ≤ 105, 1 ≤ m ≤ 103),随后一行给出序列中 n 个不超过 105 的正整数。同行数字间以空格分隔。
输出
输出原始序列中漂亮子序列的个数。因为答案可能非常大,所以你需要输出对 1000000007 (109 + 7) 取模后的结果。
样例输入
4 2 5 3 8 6
样例输出
8
提示
样例解释:
1、子序列下标为 {1, 2}, 对应值为 {5, 3};
2、子序列下标为 {1, 4}, 对应值为 {5, 6};
3、子序列下标为 {3, 4}, 对应值为 {8, 6};
4、子序列下标为 {1, 2, 3}, 对应值为 {5, 3, 8};
5、子序列下标为 {1, 2, 4}, 对应值为 {5, 3, 6};
6、子序列下标为 {1, 3, 4}, 对应值为 {5, 8, 6};
7、子序列下标为 {2, 3, 4}, 对应值为 {3, 8, 6};
8、子序列下标为 {1, 2, 3, 4}, 对应值为 {5, 3, 8, 6}。
参考代码
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
class FenwickTree {
private:
vector<int> tree;
int n;
public:
FenwickTree(int size) : n(size) {
tree.assign(n + 2, 0); // 索引从1到n+1
}
void update(int idx, int val) {
idx++; // 树状数组从1开始
if (idx > n) return; // 超出范围的不处理
while (idx <= n) {
tree[idx] = (tree[idx] + val) % MOD;
idx += idx & -idx;
}
}
int query(int idx) {
idx++; // 转换为树状数组的索引
if (idx < 0) return 0;
int res = 0;
while (idx > 0) {
res = (res + tree[idx]) % MOD;
idx -= idx & -idx;
}
return res;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int max_a = *max_element(a.begin(), a.end());
int max_val = max_a + m;
FenwickTree bit(max_val);
long long sum_dp = 0;
int total_sum = 0;
for (int ai : a) {
int left = ai - m - 1;
int sum_left = bit.query(left);
int right = ai + m;
int sum_right = (total_sum - bit.query(right) + MOD) % MOD;
int dp_i = (sum_left + sum_right + 1) % MOD;
sum_dp = (sum_dp + dp_i) % MOD;
bit.update(ai, dp_i);
total_sum = (total_sum + dp_i) % MOD;
}
long long S = (sum_dp - n + MOD) % MOD;
// 计算2^n mod MOD
auto powmod = [](long long a, int b, int mod) {
long long res = 1;
while (b > 0) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
};
long long T = (powmod(2, n, MOD) - 1 - n + MOD) % MOD;
long long ans = (T - S + MOD) % MOD;
cout << ans << '\n';
return 0;
}园林修整
园林修整中,常利用树木来形成整齐的区域分割线。园丁要将树木按高度修剪成递增或递减的形状 —— 如果一棵树太高了,就需要裁剪;如果太矮了,则需要替换。修整所花费的力气与裁剪或替换树木的数量成正比,所以需要你替他想一种最省力的修整方案。
时间限制:10000
内存限制:65536
输入第一行给出一个正个整数 N (3 ≤ N ≤ 2000),随后一行给出 N 个正整数的树高。所有整数在区间 [1, 103] 内,同行数字间以空格分隔。
输出
首先在一行中输出需要被裁剪或替换的树木的最少数量。第二行从左到右列出这些树木的编号(从 1 开始)。如果解不唯一,输出那个需要最少替换树木的解,题目保证这样的解是唯一的。 同行数字间必须以 1 个空格分隔,行首尾不得有多余空格。 如果没有树需要调整,则根据树高的升降性质,在一行中输出 Non-ascending(表示“非递增”)或 Non-descending(表示非递减)。
样例输入
样例1:
10 2 3 8 2 4 5 10 1 7 11
样例2:
3 1 2 3
样例输出
样例1:
4 2 3 7 8
样例2:
Non-descending
提示
样例1解释:
首先,要将树木修整成按高度非递减的样式,我们需要调整 4 棵树;而要修整成非递增样式,则需要调整 7 棵树。所以我们应选择递增序列对应的解。 其次,存在 4 种不同的递增序列解:
1、保持树高为 2、3、4、5、10、11 的树不变,我们需要替换掉高度为 2、1、7 的 3 棵树,因为它们太矮了;
2、保持树高为 2、3、4、5、7、11 的树不变,我们需要替换掉高度为 2、1 的 2 棵树;
3、保持树高为 2、2、4、5、10、11 的树不变,我们需要替换掉高度为 1、7 的 2 棵树;
4、保持树高为 2、2、4、5、7、11 的树不变,我们只需要替换掉高度为 1 的 1 棵树。 所以最后选择输出第(4)组解,即裁剪编号为 2、3、7(对应高度为 3、8、10)的树,替换掉第 8 棵高度为 1 的树。
参考代码:
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
struct Result {
int changes;
int replaces;
vector<int> removed;
};
Result processDirection(const vector<int>& a, bool nonDecreasing) {
int n = a.size();
vector<int> dp(n, 1);
vector<int> prev(n, -1);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
bool valid = nonDecreasing ? (a[j] <= a[i]) : (a[j] >= a[i]);
if (valid && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
prev[i] = j;
}
}
}
int maxLen = *max_element(dp.begin(), dp.end());
vector<int> candidates;
for (int i = 0; i < n; ++i) {
if (dp[i] == maxLen) {
candidates.push_back(i);
}
}
int bestReplace = 1e9;
vector<int> bestIndices;
for (int candidate : candidates) {
vector<int> path;
int current = candidate;
while (current != -1) {
path.push_back(current);
current = prev[current];
}
reverse(path.begin(), path.end());
set<int> pathSet(path.begin(), path.end());
vector<int> sortedPath(path.begin(), path.end());
sort(sortedPath.begin(), sortedPath.end());
int replace = 0;
for (int k = 0; k < n; ++k) {
if (pathSet.count(k)) continue;
auto it = upper_bound(sortedPath.begin(), sortedPath.end(), k);
if (it != sortedPath.begin()) {
int leftIdx = *(--it);
if (a[k] < a[leftIdx]) {
replace++;
}
}
}
if (replace < bestReplace || (replace == bestReplace && path.size() > bestIndices.size())) {
bestReplace = replace;
bestIndices = sortedPath;
}
}
set<int> reserved(bestIndices.begin(), bestIndices.end());
vector<int> removed;
for (int i = 0; i < n; ++i) {
if (!reserved.count(i)) {
removed.push_back(i + 1);
}
}
sort(removed.begin(), removed.end());
return { n - maxLen, bestReplace, removed };
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
vector<int> a(N);
for (int i = 0; i < N; ++i) {
cin >> a[i];
}
bool isNonDescending = true;
for (int i = 1; i < N; ++i) {
if (a[i] < a[i-1]) {
isNonDescending = false;
break;
}
}
if (isNonDescending) {
cout << "Non-descending\n";
return 0;
}
bool isNonAscending = true;
for (int i = 1; i < N; ++i) {
if (a[i] > a[i-1]) {
isNonAscending = false;
break;
}
}
if (isNonAscending) {
cout << "Non-ascending\n";
return 0;
}
Result asc = processDirection(a, true);
Result desc = processDirection(a, false);
bool useAsc;
if (asc.changes < desc.changes) {
useAsc = true;
} else if (asc.changes > desc.changes) {
useAsc = false;
} else {
useAsc = (asc.replaces <= desc.replaces);
}
Result res = useAsc ? asc : desc;
cout << res.changes << '\n';
for (size_t i = 0; i < res.removed.size(); ++i) {
if (i > 0) cout << ' ';
cout << res.removed[i];
}
cout << '\n';
return 0;
}字母游戏
一个简单的字母游戏是这样进行的:游戏开始时,我们有两个由小写英文字母组成的串 S 和 T。两个串包含有同样的字母,只是顺序不同。换句话说,将 S 中的字母重排顺序就可以得到 T。游戏的每一步,我们可以将 S 中的任一字母移动到串头或串尾,问将 S 变换成 T 至少需要多少步?
时间限制:6000
内存限制:65536
输入
输入分两行,先后给出字母串 S 和 T。如题面所描述的,两者包含同样的小写英文字母,只是顺序不同。每个字母串的长度不超过 1000。
输出
在一行中输出将 S 变换成 T 至少需要的步骤数。
样例输入
iononmrogdg goodmorning
样例输出
8
提示
样例解释:
1、 从 iononmrogdg 开始;
2、 将最后一个 g 移动到串头: giononmrogd;
3、 将 m 移动到串尾: giononrogdm;
4、 将第一个 o 移动到串尾: ginonrogdmo;
5、 将 r 移动到串尾: ginonogdmor;
6、 将第一个 n 移动到串尾: gionogdmorn;
7、 将 i 移动到串尾: gonogdmorni;
8、 将第一个 n 移动到串尾: googdmornin;
9、 将第二个 g 移动到串尾: goodmorning。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
string s, t;
cin >> s >> t;
int n = s.size();
unordered_map<char, vector<int>> pos_map;
for (int i = 0; i < n; ++i) {
pos_map[s[i]].push_back(i);
}
int max_len = 0;
for (int i = 0; i < n; ++i) {
int current_pos = -1;
int count = 0;
for (int j = i; j < n; ++j) {
char c = t[j];
if (pos_map.find(c) == pos_map.end()) {
break;
}
vector<int>& v = pos_map[c];
auto it = upper_bound(v.begin(), v.end(), current_pos);
if (it == v.end()) {
break;
}
current_pos = *it;
count++;
}
if (count > max_len) {
max_len = count;
}
}
cout << n - max_len << endl;
return 0;
}两枚硬币
伊娃喜欢收集全宇宙的硬币,包括火星币等等。一天她到了一家宇宙商店,这家商店可以接受任何星球的货币,但有一个条件,无论什么价格,都必须用 2 枚硬币一次付清,不能多也不能少。而她有多达 105 个硬币,于是求助于你。给定任一价格,请帮她找出可以付款的 2 枚硬币。
时间限制:1000
内存限制:65536
输入
第 1 行给出 2 个正整数:n (≤ 105)为硬币枚数、m(≤ 103)为伊娃要付清的价格; 第 2 行给出 n 枚硬币的面值,均为不超过 500 的正整数。同行数字间以空格分隔。
输出
在一行中输出两枚硬币的面值 v1 和 v2 ,以 1 个空格分隔,满足条件 v1+v2=m,并且 v1 ≤ v2。如果这样的解不唯一,输出 v1 最小的那个解。如果解不存在,则输出 `No Solution`。
样例输入
样例#1:
8 15 1 2 8 7 2 4 11 15
样例#2:
7 14 1 8 7 2 4 11 15
样例输出
样例#1:
4 11
样例#2:
No Solution
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> coins(n);
for (int i = 0; i < n; ++i) {
cin >> coins[i];
}
if (n < 2) {
cout << "No Solution" << endl;
return 0;
}
sort(coins.begin(), coins.end());
int left = 0, right = n - 1;
while (left < right) {
int sum = coins[left] + coins[right];
if (sum == m) {
cout << coins[left] << " " << coins[right] << endl;
return 0;
} else if (sum < m) {
++left;
} else {
--right;
}
}
cout << "No Solution" << endl;
return 0;
}完美数列
给定一个正整数数列,和正整数 p,设这个数列中的最大值是 M,最小值是 m,如果 M ≤ m*p,则称这个数列是完美数列。
现在给定参数 p 和一些正整数,请你从中选择尽可能多的数构成一个完美数列。
时间限制:1000
内存限制:65536
输入
输入第一行给出两个正整数 n 和 p,其中 n(≤ 105)是输入的正整数的个数,p(≤ 109)是给定的参数。第二行给出 n 个正整数,每个数不超过 109。
输出
在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。
样例输入
10 8 2 3 20 4 5 1 6 7 8 9
样例输出
8
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, p;
cin >> n >> p;
vector<int> nums(n);
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
sort(nums.begin(), nums.end());
int max_len = 0;
for (int i = 0; i < n; ++i) {
long long target = (long long)nums[i] * p;
auto it = upper_bound(nums.begin() + i, nums.end(), target);
int cnt = it - (nums.begin() + i);
if (cnt > max_len) {
max_len = cnt;
}
}
cout << max_len << endl;
return 0;
}多样解码
将一个由大写英文字母组成的字符串加密为一个数字串,可以简单地将 A ~ Z 转换为 0 ~ 25。但是这种方法带来的问题是,反向解码的结果可能是不唯一的。例如 `1213407` 既可以解码为 `BCBDEAH`,也可以解码为 `MBDEAH`、 `BCNEAH`、`BVDEAH` 或 `MNEAH`。注意 `07` 和 `7` 是有区别的,不能被解码为 `H`。
本题就请你计算一下,给定的数字串有多少种不同的解码结果。
时间限制:1000
内存限制:65536
输入
输入在一行中给出一个不超过 104 位的数字串,串非空且不包含空格。
输出
输出该数字串对应的不同解码结果的数量。这个数量可能非常巨大,你只需要输出其对 1000000007 取模后的结果。
样例输入
1213407
样例输出
5
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int MOD = 1000000007;
int main() {
string s;
cin >> s;
int n = s.size();
vector<long long> dp(n + 1, 0);
dp[0] = 1; // 空字符串有一种解码方式
for (int i = 1; i <= n; ++i) {
// 单独处理当前字符,总是允许
dp[i] = dp[i-1];
// 处理两位的情况
if (i >= 2) {
// 提取前两位字符并转换为整数
int two_digit = (s[i-2] - '0') * 10 + (s[i-1] - '0');
if (two_digit >= 10 && two_digit <= 25) {
dp[i] += dp[i-2];
}
}
dp[i] %= MOD;
}
cout << dp[n] % MOD << endl;
return 0;
}