西南财经大学 奇点工作室 程序设计部暑期训练营第二周 题目分析
A 小H和迷宫
题目分析：一道比较简单的题目，但是比较考察初学者的细节理解。3种药水全排列仅有3*2*1=6种情况，使用next_permutation枚举即可。需要注意的是，我们要注意类型转换造成的精度问题，所以数据范围要开为long long，并采用先乘后除的思想即可通过（方法不唯一）。
#include <bits/stdc++.h>
using namespace std;
int main(){
long long n;
long long num[3];
scanf("%lld%lld%lld%lld",&n,&num[0],&num[1],&num[2]);
sort(num,num+3); //先排序，因为next_permutation是从第一个字典序大的开始，否则会少情况
long long m=-1; //记录所有答案的最大值
do{
long long sum=0; //计算每一种情况的答案
sum=n*(100-num[0])/100; //剩余血量
sum=sum*(100-num[1])/100;
sum=sum*(100-num[2])/100;
sum=n-sum;
m=max(m,sum);
}while(next_permutation(num,num+3));
printf("%lld",m);
return 0;
}
其实，我们不难发现，本题目可以采用贪心的思想来解决，我们可以通过数学公式证明先使用厉害的药水比其他情况更优。所以我们可以直接排序然后输出结果。#include<bits/stdc++.h>
using namespace std;
int main() {
long long n;
double a[4];
cin >> n >> a[1] >> a[2] >> a[3];
long long nn = n; //直接计算答案
sort(a + 1,a + 4);
nn = nn - nn*a[3]/100;
nn = nn - nn*a[2]/100;
nn = nn - nn*a[1]/100;
printf("%lld\n",n - nn);
return 0;
}
B 脸盆大哥的木桶
题目分析：因为底面积是固定的,并且总的盛水量肯定是由最短的那个木板决定的,我们考虑贪心,就是先排序，从高到低每次都将k个放在一组,此时答案最优。下面是简单的证明：我们考虑贪心时的分组a和b，其中各有k个元素，此时
我们把a中的最小值记作min_a，b中的记作min_b。很显然，两个分组下木桶可以装的水只由min_a,min_b决定。此时我们考虑其他策略，任选a组中一个元素i，b组一个元素j，我们进行交换，由于我们经过排序，一定有i>=min_a>=j>=min_b。交换过后，a组中的最小值就会变为j，b组中最小值不变。由于j<=min_a，a组中装的水会减少（特殊情况没有影响），所以我们采取的策略最优。
我们把a中的最小值记作min_a，b中的记作min_b。很显然，两个分组下木桶可以装的水只由min_a,min_b决定。此时我们考虑其他策略，任选a组中一个元素i，b组一个元素j，我们进行交换，由于我们经过排序，一定有i>=min_a>=j>=min_b。交换过后，a组中的最小值就会变为j，b组中最小值不变。由于j<=min_a，a组中装的水会减少（特殊情况没有影响），所以我们采取的策略最优。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t,n,k,s,a[1001];
cin >> t;
while(t--){
cin >> n >> k >> s;
memset(a,0,sizeof(a)); //数组的初始化
for(int i = 0;i < n;i ++){
cin >> a[i];
}
sort(a,a+n);
int sum=0; //记录答案
for(int i = n-k;i >= 0;i -= k){ //反向遍历
sum += a[i]*s;
}
cout << sum << endl;
}
return 0;
}
C 竞赛技巧
题目分析：按照题意排序即可，方法多种多样，可以使用结构体，可以使用vector，可以使用pair<int,pair<int,int>>等等等，这里给出使用vector的程序。
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> t; //初始化
int cmp(vector<int> &a,vector<int> &b){ //定义两个vector的比较函数，先按第一位，再按第二问，最后按第三位
if(a[0] == b[0]){
if(a[1] == b[1])return a[2] < b[2];
else return a[1] < b[1];
}
else return a[0] < b[0];
}
int main(){
int n;
cin >> n;
for(int i = 0;i < n;i ++){
int a,b,c;
cin >> a >> b >> c;
int time[3] = {a,b,c};
vector<int> p(time,time+3); //利用数组初始化vetcor
t.push_back(p); //存入容器中
}
sort(t.begin(),t.end(),cmp);
for(auto p:t){
cout << p[0] << " " << p[1] << " " << p[2] << endl;
}
return 0;
}
总结：本题是一道基础的排序题目，考察大家对匿名函数的掌握，通过率不足50%，主要原因有：有很多同学把输入的字符串进行排序，这是不科学的，因为对于字符串“9 10 10”它是大于“10 10 10”，这会导致结果出错；还有很多同学计算总时间进行排序，然后再拆分，这个思路是正确的，但是表达式写错了（）
D 凌波微步
题目分析：由于只能往高处走，方向也无所谓，所以我们只需要记录里面有多少不一样的值就行，不难想到用集合set。
#include<bits/stdc++.h> //这个题目我认为不需要注释了
using namespace std;
int main()
{
int t,n,x;
cin>>t;
while(t--)
{
set<int>a;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>x;
a.insert(x);
}
cout<<a.size()<<endl;
}
return 0;
}
总结：本题通过率很低，主要原因是大家一开始没有读懂题，然后有部分同学对set的用法不熟练，希望大家加强对STL的敏感。
此外，我们可以思考两个问题
1.如果在此题基础上，要求你输出路径，应该如何实现？
2.如果在此题基础上，要求只能从第一个开始，方向只能向右，应该如何实现？
欢迎大家讨论交流
E 老子的全排列呢
题目分析：直接套函数全排列即可，不过也推荐大家去尝试一下递归的写法。
#include <bits/stdc++.h> //这个题目我认为不需要注释了
using namespace std;
int main() {
vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8};
do {
for (int num : nums) {
cout << num << " ";
}
cout << endl;
} while (next_permutation(nums.begin(), nums.end()));
return 0;
}
本题大家出错主要在不清楚next_permutation是从第一个比他字典序大的开始，如果使用while循环，会少输出它本身，所以我们这里建议使用do while循环。
F 简单的数据结构
题目分析：直接使用vector等容器模拟即可。
#include<bits/stdc++.h> //这个题目我认为不需要注释了
using namespace std;
int main(){
int n,m;cin >> n >> m;
vector<int> v;
for(int i = 0; i < m;i++){
int op;cin >> op;
if(op == 1){
int x;cin >> x;
v.insert(v.begin(),x);
}
else if(op == 2) v.erase(v.begin());
else if(op == 3) {
int x;cin >> x;
v.push_back(x);
}
else if(op == 4) v.pop_back();
else if(op == 5) reverse(v.begin(), v.end());
else if(op == 6){
cout << v.size() << endl;
for(auto x:v) cout << x << " ";
cout << endl;
}
else sort(v.begin(),v.end());
}
return 0;
}
G 投票统计
题目分析：注意到编号ai是非连续的，且范围为1-1e9，我们考虑使用map来存储票数，由于map是按照键进行排序的，所以我们可以在统计时顺便计算最大值，然后遍历一遍判断是否所有的票数一致，如果一致，则输出-1，否则，我们遍历找出票数等于最大值的编号。
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
map<long long, long long> mp;
long long maxx = 0; //记录最大票数
for (int i = 0; i < n; i++)
{
long long x;
cin >> x;
mp[x]++;
maxx = max(maxx,mp[x]);
}
int cnt = 0; //记录有多少个票数等于最大票数，即去看题目中的特殊情况是否满足
for (auto x : mp) if(x.second == maxx) cnt ++;
if(cnt == mp.size()) cout << -1 << endl; //若都是一个票数，就输出-1
else{
cout << cnt << endl;
for (auto x : mp) if(x.second == maxx) cout << x.first << " "; //遍历一次，找票数等于最大值的下标并输出
cout << endl;
}
}
int main()
{
int t;
cin >> t;
while (t--)
solve();
return 0;
}
H 进制转换
题目分析：题意很简单，但需要注意s最大可以达到36的200次，显然是非常巨大的，即使是long long也记录不了，所以不能采取先转换为10进制再转为为目标进制的做法。这里给出一种比较经典的基于短除法的方法，类似于目标进制为10的短除法，这里的目标进制为k。短除法，就是把每一位（这里指的每一位是指个位十位之类的）除以要转换的进制的余数在乘以当前进制的值加到下一位去，当前位的值就为商，然后这样一直进行到最后一位（也就是个位）个位在对所须转换的进制在取模，那么这个模就是转换后的结果。多次重复，直到最后一位为0，从后往前看就是答案。以以八进制742转换为16进制1E2为例，首先需要将八进制数742倒置为247,由number数组按位保存，然后从后往前每一次循环做一次短除法,其中每个位置处理前都是上一位的余数乘上进制(这里进制为八)加上这个位置上的数,然后将当前位置对k进制的余数作为k进制的数(这里k为16),同时更新当前位置上的数为其除以k的商,不断重复直到s进制中的数全部为零。数学证明不在此赘述，毕竟我们不是数竞，一些进制转换算法的原理与证明 - 知乎 (zhihu.com)讲的比较清楚，大家可以尝试手推一下（不会推无所谓，还是那句话，毕竟我们不是数竞，会用就行）。
#include <bits/stdc++.h>
using namespace std;
int main() {
string n;
cin >> n;
int s, k;
cin >> s >> k;
//把数字存到vector里面，字母数字分别处理
vector<int> v;
for (int i = n.size() - 1; i >= 0; i--) {
if (n[i] >= '0' && n[i] <= '9') v.push_back(n[i] - '0');
else v.push_back(n[i] - 'a' + 10);
}
//短除法模板
stack<int> st;
while (!v.empty()) {
int t = 0;
for (int i = v.size() - 1; i >= 0; i--) {
v[i] += t * s;
t = v[i] % k;
v[i] /= k;
}
st.push(t);
while (!v.empty() && v.back() == 0) v.pop_back();
}
//输出结果，字母数字分别处理
while (!st.empty()) {
int num = st.top();
if (num <= 9) cout << num;
else cout << (char)(num - 10 + 'a');
st.pop();
}
return 0;
}
总结：这道题目如果小学老师没讲短除法（的应用）然后自己手推公式确实比较难，这里推荐用栈，比其他的略快一点，但其他的也可以通过。
I 牛牛学括号
题目分析：这是一个比较简单的贪心问题，对于每个右括号，它可以选择它左边任何一个左括号匹配，所以我们直接记录左括号数目即可。
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
int left = 0; //记录左括号的数目
long long mod = 1e9+7;
long long ans = 1; //初始化结果
for(int i = 0;i < s.length();i ++){
if(s[i]=='(') left ++; //如果是左括号，则可选的情况加1
else{
ans = ans * left % mod; //如果是右括号，就在左括号里面随便选一个出来，然后左括号数目减1
left --;
}
}
cout << ans << endl;
return 0;
}
最后总结
本周主题为C++STL和STL算法，但是STL真的太泛了，所以只能从牛客网找最几道算是基础的题目给大家练练手。而且不难发现，STL的使用是带有个体差异性的，有的人喜欢用数组，有的人喜欢用vector，有的人喜欢直接算答案，但其实大差不差，这只是大家解决题目的工具。工具的选择是非常重要的，比如map，set都有非常棒的应用场景，我们要做好选择，才能事半功倍。题目总体难度比上周略大，但主要难在综合性比较高，细节比较多，导致大家通过率不高，但主要的思路还是不难想的（除了H，需要一定数学能力）。大家不要慌张害怕，代码能力需要慢慢练习，祝大家第三周愉快，加油！
京公网安备 11010502036488号