更新日志
[2021年7月26日] 更新了难度1和2的题解。
[2021年9月5日] 更新了难度3和4的题解(部分题目是从CSDN搬运的，因为这些题目表面复杂实际简单，写出来很费时间却无助于提升)。
[2021年9月5日] 训练四题解已更新，点此<传送门>进入。
前言
文章内容为作者个人学习心得，解题思路及参考代码不一定是最优的，如发现有不正确的地方或更优的解法，欢迎批评指正或讨论交流，联系方式可以在页面下方找到。
1.部分A+B
A, DA, B, DB = input().split() #读入数据（字符串型）
PA = DA*A.count(DA) #统计A中出现DA的次数，并将DA重复这么多次，得到PA
PB = DB*B.count(DB) #统计B中出现DB的次数，并将DB重复这么多次，得到PB
PA = 0 if PA == '' else int(PA) #若DA在A中一次都没有出现，则PA为0，否则转为整型
PB = 0 if PB == '' else int(PB) #若DB在B中一次都没有出现，则PB为0，否则转为整型
print(PA + PB) #输出PA与PB的和2.导弹防御系统
此题解来自CSDN。
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n;
cin >> n;
int h[n], dp[n];
for (int i = 0; i < n; i++){
cin >> h[i];
dp[i] = 1;
}
//dp[i]:以第i个导弹作为最后拦截目标时，能够拦截的导弹数目
for (int i = 0; i < n; i++){
for (int j = 0; j < i; j++) if (h[j] >= h[i]) dp[i] = max(dp[i], dp[j] + 1);
}
int max = 0;
for (int i = 0; i < n; i++) if (dp[i] > max) max = dp[i];
cout << max << endl;
return 0;
}
3.魔咒词典
data = {}
while True:
line = input()
if line == "@END@":
break
temp = line.split(']')
data[temp[0].replace("[", "")] = temp[1].strip()
n = int(input())
for i in range(n):
line = input().strip("[]")
if line in data.keys():
print(data[line])
elif line in data.values():
for j in data:
if data[j] == line:
print(j)
else:
print("what?")
4.打牌
card = input()
numbers = "123456789"
series = ["12345", "23456", "34567", "45678", "56789"]
try:
while True:
line = input()
if len(line) == 1:
if line == "9":
print("NO")
continue
temp = []
for i in numbers[int(line):]:
if i in card:
temp.append(i)
if len(temp) != 0:
print("YES {}".format(" ".join(temp)))
else:
print("NO")
elif len(line) > 1 and len(line) < 5:
if line == "9" * len(line):
print("NO")
continue
temp = []
for i in numbers[int(line[0]):]:
if card.count(i) >= len(line):
temp.append(i * len(line))
if len(temp) != 0:
print("YES {}".format(" ".join(temp)))
else:
print("NO")
elif len(line) == 5:
if line == "56789":
print("NO")
continue
temp = []
card = list(card)
card.sort()
card = "".join(card)
for i in series[series.index(line) + 1:]:
flag = 1
for j in i:
if j not in card:
flag = 0
break
if flag == 1:
temp.append(i)
if len(temp) != 0:
print("YES {}".format(" ".join(temp)))
else:
print("NO")
except EOFError:
pass
5.最大报销额
此题解来自CSDN。
#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
int getMax(int *d, int n, int q)
//*d 存储金额的数组
//n 有多少项等待DP
//q 上限（也就是背包容量）
{
int ret; //结果
int *f;
f = new int[q + 1]; //开辟数组用于DP
for (int i = 0; i <= q; i++)
f[i] = 0; //初始化
for (int i = 1; i <= n; i++)
for (int j = q; j > 0; j--)
if (d[i - 1] <= j)
if (f[j - d[i - 1]] + d[i - 1] <= q && f[j] < f[j - d[i - 1]] + d[i - 1])
f[j] = f[j - d[i - 1]] + d[i - 1];
//f[j-d[i-1]]+d[i-1]<=q 是判断将这个东西转入背包是否会超过背包的容量上限
//f[j]<f[j-d[i-1]]+d[i-1] 是判断将这个东西装入背包是否会有更好的结果
//f[j]=f[j-d[i-1]]+d[i-1] 若以上两个条件都满足，那么更新结果
ret = f[q]; //储存结果
delete f; //释放空间
return ret; //返回结果
}
int main()
{
int N; //用于存储发票数目
char type; //报销商品类型种类
string s; //读取完没有用的发票
double d_price, d_Q; //double型的价格和上限额度
while (cin >> d_Q >> N, N) //输入
{
int count = 0, t = 0; //初始化
//count是sum数组的下标，用于指示我们用来DP的数据在数组中的位置
//同时也是函数的参数
//t是这一张发票的总额
int Q = (int)(d_Q * 100); //将double的Q转为int的Q
int *sum = new int[N]; //开辟数组，存放发票的金额
for (int i = 0; i < N; i++) //对于N张发票
{
int m;
cin >> m; //这张发票上的报销数
for (int j = 0; j < m; j++) //输入所有报销
{
scanf(" %c:%lf", &type, &d_price); //输入类型和金额
int price = (int)(d_price * 100); //将金额转为int
if (price <= 60000 && (type == 'A' || type == 'B' || type == 'C')) //判断，如果满足题意
t += price; //将这一项报销的金额计入t中
else //如果有一项不满足题意
{
if (j < m)
getline(cin, s); //读入后续所有的数据，不做处理
t = -1; //标记t为-1,
break; //退出循环
}
}
if (t <= 100000 && t > 0) //如果总金额少于1000且t满足题意
sum[count++] = t; //将t存入sum中，并将计数器++
t = 0; //恢复t的值
}
printf("%.2lf\n", getMax(sum, count, Q) / 100.0); //调用函数，记得 ÷100
delete sum; //释放空间
count = 0; //初始化计数器
}
return 0;
}6.带通配符的数
此题解来自CSDN。
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main()
{
string w, x;
int len, amount;
int res;
while (cin >> w >> x)
{
res = 0;
len = w.length();
amount = 0;
for (int i = 0; i < len; i++)
if (w[i] == '?')
amount += 1;
for (int i = 0; i < len; i++)
{
if (w[i] != '?')
{
if (w[i] > x[i]) //w当前位数字>x当前位数字，当前位置之后的所有通配符取任意值都符合条件
{
res += pow(10, amount); //结果+10的amount次方
break;
}
else if (w[i] < x[i]) //w当前位数字<x当前位数字，当前位置之后的通配符所有取值都不符合条件
break;
}
else //当前字符是通配符
{
amount -= 1; //通配符数量-1
res += (9 - (x[i] - '0')) * pow(10, amount);
//amount已经是当前位置之后通配符的数量
}
}
cout << res << endl;
}
return 0;
}
7.愚人节的礼物
try:
while True:
t = input()
while "()" in t:
t = t.replace("()", "") # 去掉成对的括号，即去掉空盒子，之后剩下的盒子就可以直接拆解了
n = t.count("(") # 统计左括号的个数，即要拆开的盒子的个数
print(n)
except EOFError:
pass
8.ab串
此题解来自CSDN。考虑过使用正则表达式求，但是只能对一半，另一半比较难处理。
#include <iostream>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
const int N = 5000;
int numa[N], numb[N];
int main()
{
string s;
cin >> s;
map<char, int> mp;
for (unsigned int i = 0; i < s.size(); i++)
{
if (s[i] == 'a' && i == 0)
numa[i] = 1;
else if (s[i] == 'b' && i == 0)
numb[i] = 1; //对第一位进行特判
else if (s[i] == 'a') //构建前缀和
{
numa[i] = numa[i - 1] + 1;
numb[i] = numb[i - 1];
}
else if (s[i] == 'b')
{
numb[i] = numb[i - 1] + 1;
numa[i] = numa[i - 1];
}
mp[s[i]]++; //存储ab的个数
}
int MAX = max(mp['b'] ? mp['a'] + 1 : mp['a'], mp['b']);
for (unsigned int i = 0; i < s.size(); i++)
{
for (int j = 0; j < i; j++)
{
int ans1 = numa[j]; //第一段a的个数
int ans2 = numb[i] - numb[j - 1]; //中间段b的个数
int ans3 = numa[s.size() - 1] - numa[i - 1]; //后面一段a的个数
int ans = ans1 + ans2 + ans3;
if (ans > MAX)
MAX = ans; //更新最大值
}
}
cout << MAX << endl;
return 0;
}
9.占座位
此题解来自CSDN。这题类似训练一的内存管理，可以照搬。
#include <iostream>
#include <vector>
#include <map>
using namespace std;
struct node
{
int left; //占座起点
int right; //占座终点
} temp;
int main()
{
int n, m;
vector<int> position;
map<int, node> map;
while (cin >> n >> m)
{
for (int i = 0; i < n * n; i++)
position.push_back(0); //0表示座位没人
int k; //命令个数
int id, num; //记录id和需要的num座位数
cin >> k;
while (k--)
{
string order;
cin >> order;
int flag = 0; //控制输出yes no
if (order[0] == 'i')
{
cin >> id >> num;
if (map.find(id) == map.end())
{ //之前没占过才可以占座
for (int i = 0; i <= n * n - num; i++)
{
int j;
for (j = i; j < i + num; j++)
{
if (position[i] == 0)
continue;
else
break;
}
if (j == i + num && !position[i + num - 1])
{ //找到了连坐
temp.left = i;
temp.right = i + num - 1;
map[id] = temp;
cout << "yes" << endl;
flag = 1;
/************连坐占座***************/
for (int k = temp.left; k <= temp.right; k++)
position[k] = 1;
break;
}
}
}
}
else
{
cin >> id;
if (map.find(id) != map.end())
{
for (int i = map[id].left; i <= map[id].right; i++)
position[i] = 0; //座位腾空
map.erase(map.find(id));
cout << "yes" << endl;
flag = 1;
}
}
if (!flag)
cout << "no" << endl;
}
}
return 0;
}
10.Maya历法
此题解来自CSDN。
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
string Haab[19] = {"pop", "no", "zip", "zotz", "tzec",
"xul", "yoxkin", "mol", "chen", "yax",
"zac", "ceh", "mac", "kankin", "muan",
"pax", "koyab", "cumhu", "uayet"};
//Haab历法
string Tzolkin[20] = {"imix", "ik", "akbal", "kan",
"chicchan", "cimi", "manik", "lamat",
"muluk", "ok", "chuen", "eb",
"ben", "ix", "mem", "cib",
"caban", "eznab", "canac", "ahau"};
//Tzolkin历法
int Stoi(string s) //由于cg不支持库函数stoi，所以只能自己编写相同功能的函数
//然后形式类似的库函数还有atoi，itoa等等，大家有兴趣可自行了解
{
int sum = 0;
for (unsigned int i = 0; i < s.size(); i++)
sum += ((s[i] - '0') * pow(10, s.size() - i - 1)); //这里就是转换的核心代码
return sum;
}
int stoday(string num, string mon) //这个是由Haab历法把天数和月数转换为总的天数
{
int month = 0;
while (Haab[month] != mon)
month++; //计算这个月名是第几个月
return month * 20 + Stoi(num); //一个月20天，加上剩余的天数
}
int main()
{
int n;
cin >> n;
getchar(); //用getline的时候记得getchar哦
string date;
string hNumber, hmonth, hyear; //Haab历法的天，月，年
string tNumber, tmonth, tyear; //Tzolkin历法的天，月，年
int sum; //总天数
while (n--)
{
sum = 0; //多case，一定要初始化
getline(cin, date);
hNumber = date.substr(0, date.find("."));
hmonth = date.substr(date.find(".") + 1, date.find(" ") - date.find(".") - 1);
hyear = date.substr(date.find(" ") + 1);
//对Haab历法进行分割
//cout<<hNumber<<" "<<hmonth<<" "<<hyear<<endl;
sum = stoday(hNumber, hmonth) + Stoi(hyear) * 365;
//stoday负责转换日和月，Stoi负责转换年
//cout<<hyear<<" "<<Stoi(hyear)<<endl;
cout << sum % 13 + 1 << " "; //根据观察，T历法的日期以13为周期，再加上1就是最后的结果
cout << Tzolkin[sum % 20] << " "; //输出月名，因为数组由0开始，所以我们sum%20之后就是对应的下标
cout << sum / (13 * 20) << endl; //总天数/每年的天数就是年数
}
return 0;
}11.数码管
abstract = {'0': "123567", '1': "36", '2': "13457", '3': "13467", '4': "2346", '5': "12467", '6': "124567", '7': "136", '8': "1234567", '9': "123467"} #数字的数码管抽象表示
while True:
data = input().split()
if data[0] == '-1': break
flag = 1
for i in range(10-1): #从0到9遍历
if flag == 0: break
short, long = (abstract[data[i]], abstract[data[i+1]]) if len(abstract[data[i]]) < len(abstract[data[i+1]]) else (abstract[data[i+1]], abstract[data[i]]) #找出抽象表示较短的和较长的
for j in short: #若较短的抽象表示中的每一个字符都包含在较长的之中，则表明二者可转化
if j not in long:
flag = 0
break
if flag == 1: print("YES")
else: print("NO")12. 多项式加法
flag = 1
data = {}
while True:
n, a = input().split()
if n == '0' and a == '0': #判断是否退出
if flag == 0:break
else:flag = 0
data[n] = data.get(n, 0)+int(a)
data = sorted(data.items(), key=lambda x: int(x[0]), reverse=True) #按幂次降序排列
for i in data:
if i[1]!=0: #系数不为0才输出
print("{} {}".format(i[0], i[1]))13.数字统计
data = {}
n = input()
for i in n: #遍历字符串，统计字符出现次数
data[i] = data.get(i, 0)+1
data=sorted(data.items(),key=lambda x:x[0]) #按字符从小到大排序
for i in data:
print("{}:{}".format(i[0], i[1]))14.A除以B
A, B = input().split()
B = int(B)
index = 0 # 处理到的位数
r = 0 # 余数
q = [] # 商
while index != len(A):
temp = int(A[index])+r*10
q.append(str(temp//B))
r = temp % B
index += 1
print("{} {}".format(int("".join(q)), r))15.公交系统
#include <iostream>
#include <cmath>
using namespace std;
int main(){
int n, w, num=0;
cin >> n >> w;
int a[n];
for (int i = 0; i < n + 1; i++) a[i] = 0;
for (int i = 1; i < n + 1; i++){
cin >> a[i];
a[i] += a[i - 1];
}
int max = -1;
int min = 1;
for (int i = 1; i < n + 1; i++){
if (a[i] > max) max = a[i];
if (a[i] < min) min = a[i];
}
for (int i = 0; i <= w; i++)
if (i + max <= w && i + min >= 0) num++;
cout << num << endl;
return 0;
}limit = int(input().split()[1])
temp = input().split()
for i in range(len(temp)):
temp[i] = int(temp[i])
for i in range(len(temp)):
if i != 0:
temp[i] += temp[i-1]
M = max(temp)
m = min(temp)
count = 0
for i in range(limit+1):
if i+M <= limit and i+m >= 0:
count += 1
print(count)16.成绩大排队
n = int(input())
data = []
for i in range(n):
data.append(input().split())
data.sort(key=lambda x: int(x[2]),reverse=True) #按成绩从大到小排序
print("{} {}\n{} {}".format(data[0][0],data[0][1], data[n-1][0], data[n-1][1]))17.字符串数字置换
count = []
number = "0123456789"
map = {'0': '(Zero)', '1': '(One)', '2': '(Two)', '3': '(Three)', '4': '(Four)',
'5': '(Five)', '6': '(Six)', '7': '(Seven)', '8': '(Eight)', '9': '(Nine)'} #替换表
s = input()
for i in number:
count.append(str(s.count(i))) #统计某个数字出现的次数
s = s.replace(i, map[i]) #替换数字
print("{}\n{}".format(s, " ".join(count)))18.写出来吧
s = input()
sum = 0
map = {'0': 'ling', '1': 'yi', '2': 'er', '3': 'san', '4': 'si',
'5': 'wu', '6': 'liu', '7': 'qi', '8': 'ba', '9': 'jiu'} #替换表
for i in s:
sum += int(i)
l = []
for i in str(sum): #转换为和的拼音形式
l.append(map[i])
print("{}".format(" ".join(l)))19.到底买不买
give = list(input())
want = list(input())
tempgive = give
flag = 1
count = 0
for i in want: #对于每个想要的珠子
if i in give: #如果它在给出的珠串中
tempgive.pop(tempgive.index(i)) #取出该珠
else:
flag = 0
count += 1
if flag == 1:
print("Yes {}".format(len(tempgive)))
else:
print("No {}".format(count))20.挖掘机技术哪家强
n = int(input())
data = {}
for i in range(n):
num, score = input().split()
data[num] = data.get(num, 0)+int(score)
data = sorted(data.items(), key=lambda x: x[1], reverse=True) #按得分从大到小排序
print("{} {}".format(data[0][0], data[0][1]))21.Web导航
此题解来自CSDN。
#include <iostream>
#include <string>
#include <stack>
using namespace std;
stack<string> f, b; //分别代表前向堆栈和后向堆栈
int main()
{
string ask; //操作
string currurl; //当前网址
currurl = "http://www.game.org/"; //初始化当前网址
while (cin >> ask, ask != "QUIT") //如果不是退出命令的话
{
if (ask == "VISIT") //访问命令
{
b.push(currurl); //将当前页面压入后向堆栈顶部
cin >> currurl; //更新当前页
cout << currurl << endl; //输出当前页
while (!f.empty())
f.pop(); //清空前向堆栈
}
else if (ask == "FORWARD") //前进命令
{
if (!f.empty()) //如果前向堆栈不为空
{
b.push(currurl); //将当前页面压入后向堆栈
currurl = f.top(); //更新当前页面
cout << currurl << endl; //输出当前页面
f.pop(); //弹出前向堆栈储存的页面
}
else
cout << "Ignored" << endl; //若前向堆栈为空，输出Ignore
}
else if (ask == "BACK") //后退命令
{
if (!b.empty()) //如果后向堆栈不为空
{
f.push(currurl); //将当前页面压入前向堆栈中
currurl = b.top(); //更新当前页面
cout << currurl << endl; //输出当前页面
b.pop(); //弹出后向堆栈储存的页面
}
else
cout << "Ignored" << endl; //若后向堆栈为空，输出Ignore
}
}
return 0;
}
进一寸有进一寸的欢喜 · 2021-08-21 17:30
B1ue1nWh1te什么时候再更新一下剩下两个实验题？觉得你的很多思路比CSDN好很多~赞
B1ue1nWh1te · 2021-08-21 17:58 作者
谢谢，最近异常的忙，在学CTF，估计下周三或周五会更新训练三和四吧。
进一寸有进一寸的欢喜 · 2021-08-21 18:18
好的 (憨憨敬礼.jpg