[2021夏季学期编程训练题三]解题思路及参考代码

更新日志

[2021年7月26日] 更新了难度1和2的题解。

[2021年9月5日] 更新了难度3和4的题解(部分题目是从CSDN搬运的,因为这些题目表面复杂实际简单,写出来很费时间却无助于提升)。

[2021年9月5日] 训练四题解已更新,点此<传送门>进入。

前言

文章内容为作者个人学习心得,解题思路及参考代码不一定是最优的,如发现有不正确的地方或更优的解法,欢迎批评指正或讨论交流,联系方式可以在页面下方找到。

1.部分A+B

1

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.导弹防御系统

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.魔咒词典

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.打牌

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.最大报销额

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.带通配符的数

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.愚人节的礼物

7

try:
    while True:
        t = input()
        while "()" in t:
            t = t.replace("()", "")  # 去掉成对的括号,即去掉空盒子,之后剩下的盒子就可以直接拆解了
        n = t.count("(")  # 统计左括号的个数,即要拆开的盒子的个数
        print(n)
except EOFError:
    pass

8.ab串

8

此题解来自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.占座位

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历法

10

此题解来自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.数码管

11-1

11-2

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. 多项式加法

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.数字统计

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

14

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.公交系统

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.成绩大排队

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.字符串数字置换

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.写出来吧

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.到底买不买

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.挖掘机技术哪家强

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导航

21-1

21-2

此题解来自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;
}

3 条留言

  1. 进一寸有进一寸的欢喜
    进一寸有进一寸的欢喜 · 2021-08-21 17:30

    B1ue1nWh1te什么时候再更新一下剩下两个实验题?觉得你的很多思路比CSDN好很多~赞

    1. B1ue1nWh1te
      B1ue1nWh1te · 2021-08-21 17:58 作者

      谢谢,最近异常的忙,在学CTF,估计下周三或周五会更新训练三和四吧。

      1. 进一寸有进一寸的欢喜
        进一寸有进一寸的欢喜 · 2021-08-21 18:18

        好的 (憨憨敬礼.jpg

发表留言