第十五届哈尔滨华德学院程序设计大赛 出题组题解
签到了签到了
https://ac.nowcoder.com/acm/contest/78220/A
前言
这次比赛为了能让学弟们也体验一下校赛，所以出题的是两个大四退役的老东西。 两个出题人的水平退役之前也只有灰，省赛都打铁，退役之后水平更低了。如果题目有什么不好的地方，望海涵。
| 出题人CF ID | 最高奖项 | max rating |
|---|---|---|
| wenyalong | 省铜，区域铁 | 1167 |
| td1336065617 | 省铁，区域铁，什么奖都没有的菜鸡 | 1199 |
一.难度评估
出题信息表
| 题号 | 题目名称 | 出题人 |
|---|---|---|
| A | 签到了签到了 | td1336065617 |
| B | 裁决之时 | td1336065617 |
| C | 总成绩计算 | td1336065617 |
| D | WYL的善良之平均成绩 | wenyalong |
| E | 单表代换密码 | td1336065617 |
| F | 考试排名 | td1336065617 |
| G | 质数质数质数，到底有多少个质数？ | td1336065617 |
| H | 字符串呀，字符串。 | td1336065617 |
| I | WYL的善良之等差数列 | wenyalong |
| J | 奇妙的购物体验 | td1336065617 |
难度对照表
| 难度 | 题号 | 预计通过率 | 预计对应codeforces | 预计对应洛谷 |
|---|---|---|---|---|
| easy | A | 100% | 0 | 入门 |
| easy-mid | BC | 60% | 400 | 入门 |
| mid | DEF | 30% | 800 | 普及- |
| mid-hard | GHI | 10% | 1200 | 普及 |
| hard | J | 1% | 1500 | 提高 |
二.题解
A签到了签到了
知识点： 输出语句
解题思路：
A题签到了签到了，显而易见，就是让输出 Harbin Huade University 。我们输出就可以了。
标准程序：
#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"Harbin Huade University"<<endl;
return 0;
}
B裁决之时
知识点：
分支语句，输入输出语句，循环语句。
解题思路：
B题裁决之时，显而易见，就是判断考试成绩是否小于60分，小于60分就是挂科输出WA ，否则输出AC。
标准程序：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
while(n--)
{
int a;
cin>>a;
if(a<60)
{
cout<<"WA"<<endl;
}else{
cout<<"AC"<<endl;
}
}
return 0;
}
C总成绩计算
知识点：
小数取整，输入输出语句，循环语句。
解题思路：
C题总成绩计算，显而易见，就是用给出的平时成绩和期末考试成绩，根据题意计算最终得分。先计算 平时成绩0.4+期末考试成绩0.6，然后小数点两位以后的小数，直接舍弃。最后向上取整。
标准程序：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
while(n--)
{
double a,b;
cin>>a>>b;
double bl=int((a*0.4+b*0.6)*100)/100.0;
cout<<ceil((bl))<<endl;
}
return 0;
}
D平均成绩
知识点：
贪心，排序。
解题思路：
D题的数据范围是某温的恶趣味，看你们上不上当。显而易见，如果想要平均分四舍五入到5分，应该优先修改最低的分数，修改为5分，即可拉高平均分。因此就是排序后从最低的那个开始挨个修改为5，直到平均分四舍五入后达到五分。
标准程序：
#include<bits/stdc++.h>
using namespace std;
int a[10000],n;
int main(){
double zf=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
zf+=a[i];
}
sort(a+1,a+1+n);
int i=0;
for(i=1;int(zf/n+0.5)<5;i++)
{
zf+=5;
zf-=a[i];
}
cout<<i-1;
return 0;
}
E单表代换密码
知识点：
简单密码学，map/桶的应用。
解题思路：
E题的由题意可知，就是根据题面描述的规则，一步一步生成密码对照表，这个对照表可以通过数组存也可以通过map存，甚至因为只有26位，都可以现用现遍历，然后根据指令，进行对应输出。
标准程序：
#include<bits/stdc++.h>
using namespace std;
map<char, char>dzbjm,dzbjem;
int main() {
string my,myjs;
getline(cin, my);
map<char, int>qc;
for (int i = 0; i < my.length(); i++)
{
if (my[i] <= 'Z' && my[i] >= 'A' || my[i] <= 'z' && my[i] >= 'a')
{
if (my[i] <= 'z' && my[i] >= 'a')
{
myjs += my[i]-32;
}
else {
myjs += my[i];
}
}
}
my = "";
for (int i = 0; i < myjs.length(); i++)
{
if (qc.find(myjs[i]) == qc.end())
{
my += myjs[i];
qc[myjs[i]];
}
}
for (char i = 'A'; i <= 'Z'; i++)
{
if (qc.find(i) == qc.end())
{
my += i;
}
}
for (int i = 0;i+'a'<='z'; i++)
{
dzbjm[i + 'a'] = my[i];
dzbjem[my[i]] = i + 'a';
}
while (1)
{
string zl,clstr;
cin >> zl;
getchar();
if (zl == "encryption")
{
getline(cin, clstr);
for (int i = 0; i <clstr.length(); i++)
{
if (dzbjm.find(clstr[i]) == dzbjm.end())
cout << clstr[i];
else
cout << dzbjm[clstr[i]];
}
}
else if(zl == "decryption"){
getline(cin, clstr);
for (int i = 0; i < clstr.length(); i++)
{
if (dzbjem.find(clstr[i]) == dzbjem.end())
cout << clstr[i];
else
cout << dzbjem[clstr[i]];
}
}
else
{
cout << "Thanks for using goodbye!" << endl;
return 0;
}
cout<<endl;
}
return 0;}
F考试排名
知识点：
贪心，排序, map的优化应用。
解题思路：
F题的其实就是按题目意思实现功能即可，我们通过读题可以发现，其实就是需要实现四个功能。
1.学号和课程编号查询成绩。
2.学号和课程编号查询考试排名（本题内定义排名并列后，后面不空位直接接上，详见题面）。
3.输入课程编号，查询这门课的学生的考试的排名信息（根据题面输出）。
4.输入学号查询该学生的参加的所有考试的信息（根据题面输出）。
通过这些功能和其的输出顺序我们可以总结为，需要两种map，第一种是map套map，以通过学号和课程编号查询考试信息，第二种是以课程编号为键值，内包含一个vector这门课的存放考试信息。
我们需要对于第二种map，以键值为单位，对其的内容vector进行排序处理，排序规则为分数不相等分数高的在前，分数相等学号小的在前。
排序后进行一次遍历，进行计算考试排名。把计算出的排名赋值给对应想vector元素的同时，通过学号和班号更新第一种map内的数据。
这样处理之后前两种指令即可在第一种map内直接查询。第三种指令就是在第二种map内直接查询然后循环输出，第四种指令，只需要通过查询第一种map即可，因为map循环遍历的时候，其是根据键值从小到大自动排序好的。
标准程序：
#include<bits/stdc++.h>
using namespace std;
struct chengji {
long long int xuehao,kcbh,fs,pm;
};
map<long long int, map<long long int,chengji>>xuehaocha;
map<long long int, vector<chengji>>kecheng_chaxun;
bool cmp(chengji x, chengji y) {
if (x.fs == y.fs)
{
return x.xuehao < y.xuehao;
}
return x.fs > y.fs;
}
int n;
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
{
long long int xuehao, kcbh, fs;
cin >> xuehao >> kcbh >> fs;
xuehaocha[xuehao][kcbh]={ xuehao, kcbh, fs ,0};
kecheng_chaxun[kcbh].push_back({ xuehao, kcbh, fs ,0 });
}
for (auto& kc : kecheng_chaxun)
{
sort(kc.second.begin(), kc.second.end(), cmp);
int pm = 0,jyfs=-1;
for (int i = 0; i <kc.second.size(); i++)
{
if (kc.second[i].fs != jyfs)
{
pm++;
jyfs = kc.second[i].fs;
}
kc.second[i].pm = pm;
xuehaocha[kc.second[i].xuehao][kc.second[i].kcbh] = kc.second[i];
}
}
int sczs=0;
while (true)
{
string zl;
long long int xuehao, kcbh;
cin >> zl;
if (zl == "query1")
{
cin >> xuehao >> kcbh;
cout << xuehaocha[xuehao][kcbh].fs << endl;
sczs++;
}
else if (zl == "query2") {
cin >> xuehao >> kcbh;
cout << xuehaocha[xuehao][kcbh].pm << endl;
sczs++;
}
else if (zl == "query3") {
cin >> kcbh;
for (auto& cjxx : kecheng_chaxun[kcbh])
{
cout << cjxx.xuehao<<" " << cjxx.fs<<" " << cjxx.pm<<endl;
sczs++;
}
}
else if (zl == "query4") {
cin >> xuehao;
for (auto& cjxx : xuehaocha[xuehao])
{
cout << cjxx.first << " " << cjxx.second.fs << " " << cjxx.second.pm << endl;
sczs++;
}
}
else {
cout << "OK" << endl;
sczs++;
if(sczs>200001)return -100086;
return 0;
}
}
return 0;
}
G质数质数质数，到底有多少个质数？
知识点：
素数筛，前缀和。
解题思路：
这题没啥可说的，就是个素数筛+前缀和板子。
标准程序：
#include<bits/stdc++.h>
using namespace std;
int n=1e6,t;
int sst[10000000],ss[1000000],qzh[10000000],ssz;
int main(){
for(int i=2;i<=n;i++)
{
if(sst[i]==0)
{
ss[++ssz]=i;
qzh[i]=qzh[i-1]+1;
}else{
qzh[i]=qzh[i-1];
}
for(int j=1;j<=ssz&&i*ss[j]<=n;j++)
{
sst[i*ss[j]]=1;
if(i%ss[j]==0)
{
break;
}
}
}
cin>>t;
while(t--)
{
int x,y;
cin>>x>>y;
cout<<qzh[y]-qzh[x-1]<<endl;
}
return 0;
}
H字符串呀，字符串。
知识点：
字典树，思维+map，动态规划。
解题思路：
H题的做法有很多，出题人的做法为字典树。通过题意可知，这个符合规律的字符串合集，正好符合字典树的存储规律。我们只要在向字典树添加新的字符串的时候，每次添加字符串的时候计算路径上的已有的字符串数量，计算求和，最后在加上这个字符串本身。然后每次在这些运算结束后，进行取最值。最后这些求和结果中最大的就是答案了。
标准程序：
#include<bits/stdc++.h>
using namespace std;
int zds[2000005][30], jyh[2000005], idx,num_cd=0;
int add(string s) {
int jd = 0, len_num=0;
for (int i = 0; i < s.length(); i++)
{
if (!zds[jd][s[i] - 'a']) {
zds[jd][s[i] - 'a'] = ++idx;
}
jd = zds[jd][s[i] - 'a'];
len_num=max(jyh[jd], len_num);
}
jyh[jd]= len_num+1;
num_cd=max(num_cd, jyh[jd]);
return 0;
}
vector<string>str_vector;
int main() {
//freopen("12.in", " r ", stdin);
//freopen("12.out", " w ", stdout);
int n;
cin >> n;
if (n > 1e4 || n < 1)
return -1;
while (n--)
{
string zl, str;
cin >> str;
if (str.size() > 200 || str.size() < 1)return -1;
str_vector.push_back(str);
}
sort(str_vector.begin(), str_vector.end());
for (auto &str:str_vector)
{
add(str);
}
cout << num_cd << endl;
return 0;
}
I等差数列
知识点：
枚举，数学知识，公差。
解题思路：
本题主要的突破口是，等差数列这四个字，以及修改的范围。
首先等差数列，其的公差是个固定数值，只需要一个数列前两项的差值，即可确定这个数列如果是等差数列的其公差为多少。确定了公差，那么就可以确定这个等差数列的每一项为多少。
而本题的元素变动范围为-1 1 0，因此前两项定义为ai和aj的话，这个数列的前两项的变化的可能包含在了(aj，ai) (aj+1，ai) (aj，ai+1) (aj+1，ai+1) (aj-1，ai+1) (aj+1，ai-1) (aj-1，ai) (aj，ai-1) (aj-1，ai-1)，9种可能性内。
因此只需要枚举这9种可能，通过其确定的公差，计算出的等差数列。来验证，后面的元素能不能在-1 +1 0三种可能性中变为等差数列。
如果可以，就计算需要-1 +1才能变为等差数列的元素的个数。
记得前两项在变动的时候也会消耗修改次数哦。然后计算这9中可能性中那种变为等差数列需要消耗的修改次数最少。
如果9种可能性都不能变为等差数列就是不可能变 输出-1了。
这个题放在次压轴就是因为这个题多少需要动脑子，前面的题除了板子就是根据题面模拟。
标准程序：
#include<bits/stdc++.h>
using namespace std;
int daan=10000000,a[100010],b[100010],n;
int pd(int x,int y)
{
int jg=0;
jg+=abs(x)+abs(y);
b[1]=a[1]+x;
b[2]=a[2]+y;
int gc=b[2]-b[1];
for(int i=3;i<=n;i++)
{
b[i]=b[i-1]+gc;
// cout<<b[i]<<" ";
if(abs(b[i]-a[i])>1)
{
return -1;
}
if(abs(b[i]-a[i])==1)
jg++;
}
return jg;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=-1;i<=1;i++)
{
for(int j=-1;j<=1;j++)
{
int jg=pd(i,j);
// cout<<endl;
if(jg!=-1)
{
daan=min(jg,daan);
}
}
}
cout<<daan;
return 0;
}
J奇妙的购物体验
知识点：
Floyd，二进制多重背包，状态压缩动态规划。
解题思路：
我们通过读题可以发现，其是这个问题可以分为两部分。
第一部分，在一张图上求1-n全都要走过的情况下最少要多少路费，钱够不够。
第二部分是个多重背包问题，去除路费后，剩下的钱可以产生多少快乐值。
第二部分显而易见是经典的二进制多重背包。
第一部分我们需要考虑到其和传统的TSP问题不同在于，同一个点可以走多次。但是换个思路，我们要求的是最少的值，其实可以在原有的图上通过Floyd跑出一个所有点之间都是连通的图。这个图上每个点距离其他点的距离都是已经求好的两点最短距离。然后在这张图上通过状态压缩动态规划求TSP问题即可。
因为还要返回，所以还需要枚举走完n个点后，以每个点为终点所花费的钱加上回家所需要的钱。才能求出最少需要的路费。如果钱够路费，剩下的钱跑一下多重背包问题，看一下快乐值够不够就行了。
标准程序：
#include<bits/stdc++.h>
using namespace std;
int N, M, K, SHABU, ldz;
struct bian {
int x, y, z;
}bian_arr[100000];
struct spxx {
int S, BW, BQ;
}spxx_arr[100000];
int dt[50][50];
int floyd() {
for (int i = 0; i <= N; i++)
{
for (int j = 0; j <= N; j++)
{
dt[i][j] = 10000000;
if (i == j) {
dt[i][j] = 0;
}
}
}
for (int i = 1; i <= M; i++)
{
dt[bian_arr[i].x][bian_arr[i].y] = min(bian_arr[i].z, dt[bian_arr[i].x][bian_arr[i].y]);
dt[bian_arr[i].y][bian_arr[i].x] = min(bian_arr[i].z, dt[bian_arr[i].y][bian_arr[i].x]);
}
for (int t = 0; t <= N; t++)
{
for (int i = 0; i <= N; i++)
{
for (int j = 0; j <= N; j++)
{
dt[i][j] = min(dt[i][j], dt[i][t] + dt[t][j]);
}
}
}
return 0;
}
const int maxfs = 1 << 21;
int tsp_arr[maxfs][21];
int TSP() {
for (int i = 0; i < maxfs; i++)
{
for (int j = 0; j < 21; j++)
{
tsp_arr[i][j] = 1000000000;
}
}
tsp_arr[1][0] = 0;
for (int i = 0; i < (1 << N); i++)
{
for (int j = 0; j < N; j++) {
if (i >> j & 1) {
for (int k = 0; k < N; k++)
{
if (i >> k & 1)
{
tsp_arr[i][j] = min(tsp_arr[i][j], tsp_arr[i - (1 << j)][k] + dt[k][j]);
}
}
}
}
}
int daan = 1e9;
for (int i = 0; i < N; i++)
{
daan = min(daan, tsp_arr[(1 << N) - 1][i] + dt[i][0]);
}
return daan;
}
struct sz {
int v, w;
};
vector<sz>dl;
int beibao_dp[1000000];
int beibao() {
for (int i = 1; i <= K; i++)
{
int v = spxx_arr[i].BW, w = spxx_arr[i].BQ, s = spxx_arr[i].S;
for (int j = 1; j <= s; j *= 2)
{
s -= j;
dl.push_back({ j * v,j * w });
}
if (s > 0)
{
dl.push_back({ s * v,s * w });
}
}
//cout << dl.size();
for (int i = 0; i < dl.size(); i++)
{
for (int j = SHABU; j >= dl[i].v; j--)
{
beibao_dp[j] = max(beibao_dp[j], beibao_dp[j - dl[i].v] + dl[i].w);
}
}
return beibao_dp[SHABU];
}
int main() {
cin >> N >> M >> K >> SHABU >> ldz;
if (N < 1 || N>20)return -1;
if (M < 1 || M>2000)return -1;
if (K < 1 || K>2000)return -1;
if (SHABU < 0 || SHABU>2000)return -1;
if (ldz < 0 || N>10000)return -1;
for (int i = 1; i <= M; i++)
{
cin >> bian_arr[i].x >> bian_arr[i].y >> bian_arr[i].z;
bian_arr[i].x--;
bian_arr[i].y--;
}
for (int i = 1; i <= K; i++)
{
cin >> spxx_arr[i].S >> spxx_arr[i].BW >> spxx_arr[i].BQ;
}
floyd();
int lufei = TSP();
cout << lufei << endl;
if (lufei >= SHABU)
{
cout << "Shub, go work overtime!" << endl;
}
else {
SHABU -= lufei;
int kuailezhi = beibao();
cout << kuailezhi << endl;
if (kuailezhi > ldz)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
return 0;
}
查看7道真题和解析