计蒜客信息学 2023 年 10 ⽉编程新⼿赛题解
题⽬ 知识点
机票优惠系统 条件分⽀
库存报告 数组、排序、模拟
⽂本编辑 字符串、结构体
⼦数组 异或、前缀和思想
机票优惠系统
题解
本题考察的是条件分⽀的应⽤。
只需要计算出年龄折扣的钱数、会员折扣的钱数，最后再使⽤ 减掉这两个折扣的最⼤值即可。
标程
#include
using namespace std;
int main() {
int age;
char vip;
cin >> age >> vip;
int discount_age = 0, discount_vip = 0;
if (age <= 5) {
discount_age = 1000 * 80 / 100;
} else if (6 <= age && age = 60) {
discount_age = 1000 * 30 / 100;
}
if (vip == ‘b’) {
discount_vip = 1000 * 10 / 100;
} else if (vip == ‘s’) {
discount_vip = 1000 * 15 / 100;
} else if (vip == ‘g’) {
discount_vip = 1000 * 20 / 100;
}
if (discount_age > discount_vip) {
cout << 1000 – discount_age << endl;
} else {
cout << 1000 – discount_vip << endl;
}
return 0;
}
1000
库存报告
题解
本题考察的是数组和 sort 函数的应⽤。
使⽤数组存储每个数，并使⽤ sort 进⾏从⼤到⼩排序。
最后按照规则依次输出即可，注意⻓度为奇数的情况，中间的数只需要输出⼀次。
标程
#include
#include
using namespace std;
int main() {
int n, nums[105];
cin >> n;
for (int i = 0; i > nums[i];
}
sort(nums, nums + n, greater());
for (int i = 0, j = n – 1; i <= j; i++, j–) {
cout << nums[i] << " ";
if (i != j) {
cout << nums[j] << " ";
}
}
return 0;
}
⽂本编辑
题解
本题需要使⽤ getline 读取⼀⾏带空格的字符串。
然后从字符串中提取每个单词，使⽤结构体维护每种单词的数量，最后按照规则排序输出即可。
标程
#include
#include
#include
using namespace std;
struct WORD {
string word;
int cnt;
} words[1010];
bool cmp(WORD word1, WORD word2) {
if (word1.cnt != word2.cnt) {
return word1.cnt > word2.cnt;
}
return word1.word < word2.word;
}
void inset(int& cnt, const string &word) {
for (int i = 0; i < cnt; i++) {
if (words[i].word == word) {
words[i].cnt++;
return;
}
}
words[cnt].word = word;
words[cnt++].cnt = 1;
}
int main() {
int word_cnt = 0;
string sentence, word = "";
getline(cin, sentence);
sentence += '.';
for (int i = 0; i < sentence.size(); i++) {
if ('a' <= sentence[i] && sentence[i] <= 'z') {
word += sentence[i];
} else {
if (word != "") {
inset(word_cnt, word);
}
word = "";
}
}
sort(words, words + word_cnt, cmp);
cout << word_cnt << endl;
for (int i = 0; i < word_cnt; i++) {
cout << words[i].word << " " << words[i].cnt << endl;
}
return 0;
}
⼦数组
题解
对于异或运算： a ^ a 的结果为 ，所以可以使⽤前缀和思想对数组 a[i] 做⼀个前缀异或和。
令 pre[i] 表示前 个数的异或和。那么区间 的异或和为 pre[r] ^ pre[l – 1] 。
根据异或和的性质： 如果有两个⾮负整数 的异或的和为 ，则 。
那么对于⼀段异或和为 的区间 ，满⾜（其中 表示异或运算）：
所以我们可以在求解前缀异或和 的时候，快速的计算出以 为右端点的合法区间的个数：即在 中有多少个数等于 ，这个
时候我们可以使⽤ map 维护这个数量。
标程
#include
#include
#include