团体程序设计天梯赛----pta 练习集-Toy模板网

这篇具有很好参考价值的文章主要介绍了团体程序设计天梯赛----pta 练习集。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

L1-001 Hello World

这道超级简单的题目没有任何输入。

你只需要在一行中输出著名短句“Hello World!”就可以了。

解法

略

#include <iostream>
#include <cmath>

using namespace std;
int main(int argc, char** argv)
{
    cout << "Hello World!";
    return 0;
}

L1-002 打印沙漏

本题要求你写个程序把给定的符号打印成沙漏的形状。例如给定17个“*”，要求按下列格式打印

解法

记录一下个数就好

#include <iostream>
#include <cmath>

using namespace std;
int main(int argc, char** argv)
{
    int n;
    char c;
    cin >> n >> c;
    int maxn = 1;
    while (1)
    {
        if (maxn == 1)
        {
            n --;
        }
        else 
        {
            if (n - maxn * 2 < 0)
            {
                maxn -= 2;
                break;
            }
            else
            {
                n -= maxn * 2;
            }
        }
        maxn += 2;
    }
    
    for (int i = maxn; i >= 1; i -= 2)
    {
        int bl = (maxn - i)  /2;
        for (int j = 1; j <= bl; j ++)
               cout << " ";
        for (int j = 1; j <= i; j ++)
               cout << c;
        cout << '\n';
    }
    
    for (int i = 3; i <= maxn; i += 2)
    {
        int bl = (maxn - i)  /2;
        for (int j = 1; j <= bl; j ++)
               cout << " ";
        for (int j = 1; j <= i; j ++)
               cout << c;
        cout << '\n';
    }
    
    cout << n;
    return 0;
}

L1-003 个位数统计

给定一个 k 位整数 N，请编写程序统计每种不同的个位数字出现的次数。例如：给定 N=100311，则有 2 个 0，3 个 1，和 1 个 3。

解法

略

#include <iostream>
#include <cmath>
#include <map>
#include <set>
#define int long long
using namespace std;
map<char, int> mp;
signed main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    string str;
    cin >> str;
    for (auto i : str)
    {
        mp[i] ++;
    }
    
    for (auto it : mp)
        cout << it.first << ":" << it.second << '\n';
}

L1-004 计算摄氏温度

给定一个华氏温度F，本题要求编写程序，计算对应的摄氏温度C。计算公式：C=5×(F−32)/9。题目保证输入与输出均在整型范围内。

解法

略

#include <iostream>
#include <cmath>
#include <map>
#include <set>
#define int long long
using namespace std;
signed main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    const string str = "Celsius = ";
    int f;
    cin >> f;
    int c = 5 * (f - 32) / 9;
    cout <<str << c;
}

L1-005 考试座位号

每个 PAT 考生在参加考试时都会被分配两个座位号，一个是试机座位，一个是考试座位。正常情况下，考生在入场时先得到试机座位号码，入座进入试机状态后，系统会显示该考生的考试座位号码，考试时考生需要换到考试座位就座。但有些考生迟到了，试机已经结束，他们只能拿着领到的试机座位号码求助于你，从后台查出他们的考试座位号码。

解法

map映射一下就可以了

#include <iostream>
#include <cmath>
#include <map>
#include <set>
#define int long long
    using namespace std;
map<int, pair<string, int>> mp;
signed main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        string str;
        int m, k;
        cin >> str >> m >> k;
        mp[m] = {str, k};
    }
    
    int m;
    cin >> m;
    for (int i = 1; i <= m; i ++)
    {
        int tmp;
        cin >> tmp;
        cout << mp[tmp].first << ' ' << mp[tmp].second << '\n';
    }
}

L1-006 连续因子

一个正整数 N 的因子中可能存在若干连续的数字。例如 630 可以分解为 3×5×6×7，其中 5、6、7 就是 3 个连续的数字。给定任一正整数 N，要求编写程序求出最长连续因子的个数，并输出最小的连续因子序列。

解法

预处理前缀乘，再枚举就可以了

#include <iostream>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
int sum[10000];
int cnt = 0;
signed main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int maxnn = (1LL << 32);
    int tmp = 1;
    for (int i = 2; tmp <= maxnn; i ++)
    {
        tmp *= i;
        if (tmp <= maxnn)
            sum[++cnt] = tmp;
//         cout << tmp;
    }
    sum[0] = 1;
    
    int maxn = 0;
    int pos = 0;
//     int minn = INT_MAX;
    
    for (int i = 1; i <= cnt; i ++)
        for (int j = i; j <= cnt; j ++)
        {
            int num = sum[j] / sum[i - 1];
            int tmp = (j - i + 1);
            if (n % num == 0)
            {
                if (maxn < tmp)
                {
                    maxn = tmp;
                    pos = i;
                }
            }
        }
    if (maxn == 0)
    {
        cout << 1 << '\n';
        cout << n;
        return 0;
    }
   cout << maxn << '\n';
   for (int i = pos; i <= pos + maxn - 1; i ++)
   {
       cout << i + 1;
       if (i != pos + maxn - 1)
           cout << "*";
   }
}

L1-007 念数字

输入一个整数，输出每个数字对应的拼音。当整数为负数时，先输出fu字。十个数字对应的拼音如下：

解法

略

#include <iostream>
#include <cmath>
#include <map>
#include <set>
#include <vector>

#define int long long
using namespace std;

string str[10] = {
    "ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"
};
vector<int> v;

signed main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;
    
    if (n < 0)
        cout << "fu" << ' ';
    n = abs(n);
    if (n == 0)
        cout << str[0];
    else 
    {
    while (n)
    {
        v.push_back(n % 10);
        n /= 10;
    }
    
    for (int i = v.size() - 1; i >= 0; i --)
    {
        cout << str[v[i]];
        if (i != 0)
            cout << ' ';
    }
    }
}

L1-008 求整数段和

给定两个整数A和B，输出从A到B的所有整数以及这些数的和。

解法

printf的基本用法

#include <iostream>
#include <cmath>
#include <map>
#include <set>
#define int long long
using namespace std;
signed main()
{
    int a, b;
    cin >> a >> b;
    int cnt = 0;
    int sum = 0;
    
    for (int i = a; i <= b; i ++)
    {
        printf("% 5d", i);
        cnt ++;
        if (cnt % 5 == 0)
             cout << '\n';
        sum += i;
    }
    if (cnt % 5 != 0)
            cout << '\n';
    cout << "Sum = " << sum;
}

L1-009 N个数求和

本题的要求很简单，就是求N个数字的和。麻烦的是，这些数字是以有理数分子/分母的形式给出的，你输出的和也必须是有理数的形式。

解法

注意0等特殊数据

from math import *
n = input()
n = int(n)

arr = input().split(" ")

ansmu = 1
anszi = 0
for i in arr:
    a, b = map(int, i.split("/"))
    tmp = lcm(ansmu, b)
    anszi = anszi * (tmp // ansmu) + a * (tmp // b)
#     print(anszi)
    ansmu = tmp

ggcd = gcd(ansmu, anszi)
ansmu = ansmu // ggcd
anszi = anszi // ggcd

# print(ansmu)
# print(anszi)

if anszi < 0 and abs(anszi) < ansmu:
    print("%d/%d" % (anszi, ansmu))
elif anszi == 0:
    print("0")
else :
    if (anszi // ansmu):
        print("%d" % (anszi // ansmu), end="")
        if (anszi % ansmu):
            print(" ", end="")
    if (anszi % ansmu):
        print("%d/%d" % (anszi % ansmu, ansmu), end="")

L1-010 比较大小

本题要求将输入的任意3个整数从小到大输出。

解法

略

#include <iostream>
#include <cmath>
#include <map>
#include <set>
#include <sstream>
#include <vector>
#include <algorithm>

#define int long long
using namespace std;
signed main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    vector<int> v;
    for (int i = 1; i <= 3; i ++)
    {
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < v.size(); i ++)
    {
        cout << v[i];
        if (i != v.size() - 1)
            cout << "->";
    }
}

L1-011 A-B

本题要求你计算A−B。不过麻烦的是，A和B都是字符串 —— 即从字符串A中把字符串B所包含的字符全删掉，剩下的字符组成的就是字符串A−B。

解法

略

#include <iostream>
#include <cmath>
#include <map>
#include <set>
#include <sstream>

// #define int long long
using namespace std;
map<int, int> mp;
signed main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    string str, strb;
    getline(cin, str);
    getline(cin, strb);
    
    for (auto i : strb)
    {
        mp[i] ++;
    }
    
    for (auto i : str)
    {
        if (!mp[i])
            cout << i;
    }
}

L1-012 计算指数

真的没骗你，这道才是简单题 —— 对任意给定的不超过 10 的正整数 n，要求你输出 2 ^n 。不难吧？

解法

pow标准库即可

#include <iostream>
#include <cmath>
#include <map>
#include <set>
#include <sstream>

// #define int long long
using namespace std;
signed main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;
    
    cout << "2^" << n << " = " << pow(2, n);
}

L1-013 计算阶乘和

对于给定的正整数N，需要你计算 S=1!+2!+3!+…+N!。

解法


def chengjie(num):
    re = 1
    for i in range(1, num + 1):
        re *= i
    return re

n = int(input())

ans = 0
for i in range(1, n + 1):
    ans += chengjie(i)
print(ans)

L1-014 简单题

这次真的没骗你 —— 这道超级简单的题目没有任何输入。

你只需要在一行中输出事实：This is a simple problem. 就可以了。

解法

print("This is a simple problem.")

L1-015 跟奥巴马一起画方块

美国总统奥巴马不仅呼吁所有人都学习编程，甚至以身作则编写代码，成为美国历史上首位编写计算机代码的总统。2014年底，为庆祝“计算机科学教育周”正式启动，奥巴马编写了很简单的计算机代码：在屏幕上画一个正方形。现在你也跟他一起画吧！

解法

注意round即可

from math import *
n, c = input().split(" ")
n = int(n)
line = round(n / 2 + 0.05)
for i in range(0, line):
    for j in range(0, n):
        print(c, end="")
    print("")

L1-016 查验身份证

一个合法的身份证号码由17位地区、日期编号和顺序编号加1位校验码组成。校验码的计算规则如下：

首先对前17位数字加权求和，权重分配为：{7，9，10，5，8，4，2，1，6，3，7，9，10，5，8，4，2}；然后将计算的和对11取模得到值Z；最后按照以下关系对应Z值与校验码M的值：

解法

略

#include <iostream>
#include <cmath>
#include <map>
#include <set>
#include <sstream>

// #define int long long
using namespace std;
int quan[] = {7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2};
char x[] = {'1', '0', 'X', '9', '8', '7', '6', '5', '4', '3', '2'};
signed main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;
    
    bool flag = true;
    for (int i = 1; i <= n; i ++)
    {
        string tmp;
        cin >> tmp;
        
        int ans = 0;
        for (int i = 0; i < 17; i ++)
        {
            int num = tmp[i] - '0';
            num *= quan[i];
            ans += num;
        }
        ans %= 11;
//         cout << ans << '\n';
        if (tmp[17] != x[ans])
        {
            flag = false;
            cout << tmp << '\n';
        }
            
    }
    
    if (flag)
        cout << "All passed";
}

L1-017 到底有多二

一个整数“犯二的程度”定义为该数字中包含2的个数与其位数的比值。如果这个数是负数，则程度增加0.5倍；如果还是个偶数，则再增加1倍。例如数字-13142223336是个11位数，其中有3个2，并且是负数，也是偶数，则它的犯二程度计算为：3/11×1.5×2×100%，约为81.82%。本题就请你计算一个给定整数到底有多二。

解法

注意负数的字符串处理

n = input()
ans = 0

for i in n:
    if i == '2':
        ans += 1
siz = len(n)
if n[0] == '-':
    siz -= 1
ans = ans / siz

if n[0] == '-':
    ans *= 1.5
n =  int(n)
if n % 2 == 0:
    ans *= 2
ans *= 100
print("%.2f" % ans, end="")
print("%")

L1-018 大笨钟

微博上有个自称“大笨钟V”的家伙，每天敲钟催促码农们爱惜身体早点睡觉。不过由于笨钟自己作息也不是很规律，所以敲钟并不定时。一般敲钟的点数是根据敲钟时间而定的，如果正好在某个整点敲，那么“当”数就等于那个整点数；如果过了整点，就敲下一个整点数。另外，虽然一天有24小时，钟却是只在后半天敲1~12下。例如在23:00敲钟，就是“当当当当当当当当当当当”，而到了23:01就会是“当当当当当当当当当当当当”。在午夜00:00到中午12:00期间（端点时间包括在内），笨钟是不敲的。

下面就请你写个程序，根据当前时间替大笨钟敲钟。

解法

略

n = input()
h, m = map(int, n.split(":"))
flag = True
num = h - 12

if h < 12 or (h == 12 and m == 0):
    flag = False
elif m != 0:
    num += 1
if flag:
    for i in range(0, num):
        print("Dang", end="")
else :
    print("Only %s.  Too early to Dang." % n)

L1-019 谁先倒

划拳是古老中国酒文化的一个有趣的组成部分。酒桌上两人划拳的方法为：每人口中喊出一个数字，同时用手比划出一个数字。如果谁比划出的数字正好等于两人喊出的数字之和，谁就输了，输家罚一杯酒。两人同赢或两人同输则继续下一轮，直到唯一的赢家出现。

下面给出甲、乙两人的酒量（最多能喝多少杯不倒）和划拳记录，请你判断两个人谁先倒。

解法

注意减去同输状况

#include <iostream>
#include <cmath>
#include <map>
#include <set>
#include <sstream>

#define int long long
using namespace std;
signed main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int a, b;
    cin >> a >> b;
    int tmpa = a, tmpb = b;
    int m;
    cin >> m;
    for (int i = 1; i <= m; i ++)
    {
        int j1, j2, y1, y2;
        cin >> j1 >> j2 >> y1 >> y2;
        int tmp = j1 + y1;
        if (j2 == tmp && y2 != tmp)
            a --;
        if (y2 == tmp && j2 != tmp)
            b --;
//         cout << a << ' ' << b << '\n';
            if (a < 0 || b < 0)
               break;
    }
    if (a < 0)
    {
        cout << "A" << '\n' << tmpb - b;
    }
    else
    {
        cout << "B" << '\n' << tmpa - a;
    }
}

L1-020 帅到没朋友

当芸芸众生忙着在朋友圈中发照片的时候，总有一些人因为太帅而没有朋友。本题就要求你找出那些帅到没有朋友的人。

解法

略

#include <iostream>
#include <cmath>
#include <map>
#include <set>
#include <sstream>
#include <vector>

#define int long long
using namespace std;

map<string, bool> mp;
map<string, int> vis;
    vector<string> ans;

signed main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;
    for (int i =1; i <= n; i ++)
    {
        int m;
        cin >> m;
        
        for (int j = 1; j <= m; j ++)
        {
            string tmp;
            cin >> tmp;
            if (m > 1)
                mp[tmp] = true;
        }
    }
    
    int m;
    cin >> m;
    bool flag = true;
    for (int i =1; i <= m;  i ++)
    {
        string tmp;
        cin >> tmp;
        if (!mp[tmp] && !vis[tmp])
        {
            flag = false;
            vis[tmp] = 1;
//             cout << tmp;
            ans.push_back(tmp);
        }
    }
    if (flag)
        cout << "No one is handsome";
    else
    {
        for (int i = 0; i < ans.size(); i ++)
        {
            cout << ans[i];
            if (i != ans.size() - 1)
                cout << ' ';
        }
    }
}

L1-021 重要的话说三遍

这道超级简单的题目没有任何输入。

你只需要把这句很重要的话 —— “I’m gonna WIN!”——连续输出三遍就可以了。

注意每遍占一行，除了每行的回车不能有任何多余字符。

解法

print("I'm gonna WIN!\nI'm gonna WIN!\nI'm gonna WIN!")

L1-022 奇偶分家

给定N个正整数，请统计奇数和偶数各有多少个？

解法

略

#include <iostream>
#include <cmath>
#include <map>
#include <set>
#include <sstream>

// #define int long long
using namespace std;
signed main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;
    int a = 0, b = 0;
    for (int i =1; i <= n; i ++)
    {
        int tmp;
        cin >> tmp;
        if (tmp % 2 == 1)
            b ++;
        else 
            a ++;
    }
    cout << b << ' ' << a;
}

L1-023 输出GPLT

给定一个长度不超过10000的、仅由英文字母构成的字符串。请将字符重新调整顺序，按GPLTGPLT…这样的顺序输出，并忽略其它字符。当然，四种字符（不区分大小写）的个数不一定是一样多的，若某种字符已经输出完，则余下的字符仍按GPLT的顺序打印，直到所有字符都被输出。

解法

注意大小写都可

#include <iostream>
#include <cmath>
#include <map>
#include <set>
#include <queue>

#define int long long
using namespace std;
int q1, q2, q3, q4;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    string str;
    cin >> str;
    
    for (int i = 0; i < str.size(); i ++)
    {
        if (str[i] == 'G' || str[i] == 'g')
            q1 ++;
        else if (str[i] == 'P' || str[i] == 'p')
            q2 ++;
        else if (str[i] == 'L' || str[i] == 'l')
            q3 ++;
        else if (str[i] == 'T' || str[i] == 't')
            q4 ++;
    }
    
    while (q1 || q2 || q3 || q4)
    {
        if (q1)
        {
            cout << "G";
            q1 --;
        }
        if (q2)
        {
            cout << "P";
            q2 --;
        }
        if (q3)
        {
            cout << "L";
            q3 --;
        }
        if (q4)
        {
            cout << "T";
            q4 --;
        }
    }
}

L1-024 后天

如果今天是星期三，后天就是星期五；如果今天是星期六，后天就是星期一。我们用数字1到7对应星期一到星期日。给定某一天，请你输出那天的“后天”是星期几。

解法

略

#include <iostream>
#include <cmath>
#include <map>
#include <set>
#define int long long
using namespace std;
signed main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;
    n --;
    n += 2;
    n %= 7;
    cout << n + 1 ;
}

L1-025 正整数A+B

题的目标很简单，就是求两个正整数A和B的和，其中A和B都在区间[1,1000]。稍微有点麻烦的是，输入并不保证是两个正整数。

解法

略

#include <iostream>
#include <cmath>
#include <map>
#include <set>
#include <sstream>

// #define int long long
using namespace std;
signed main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    string a, b;
    cin >> a;
    cin.get();
    getline(cin, b);
    
    bool flaga = true, flagb = true;
    for (int i = 0; i < a.size(); i ++)
    {
        if (!(a[i] >= '0' && a[i] <= '9'))
            flaga = false;
    }
    for (int i = 0; i < b.size(); i ++)
    {
        if (!(b[i] >= '0' && b[i] <= '9'))
            flagb = false;
    }
    
    stringstream strr;
    int tmpa, tmpb;
    
    if (flaga)
    {
        strr << a;
        strr >> tmpa;
        if (tmpa > 1000 || tmpa <= 0)
        {
            flaga = false;
            cout << "?";
        }
        else 
            cout << a;
    }
    else 
        cout << '?';
    
    cout << " + ";
    
    if (flagb)
    {
        strr.clear();
        strr << b;
        strr >> tmpb;
        if (tmpb > 1000 || tmpb <= 0)
        {
            flagb = false;
            cout << "?";
        }
        else 
            cout << b;
    }
    else 
        cout << '?';
    cout << " = ";
    
    if (flaga && flagb)
    {
        cout << tmpa + tmpb;
    }
    else 
    {
        cout << "?";
    }
}

L1-026 I Love GPLT

这道超级简单的题目没有任何输入。

你只需要把这句很重要的话 —— “I Love GPLT”——竖着输出就可以了。

所谓“竖着输出”，是指每个字符占一行（包括空格），即每行只能有1个字符和回车。

解法

略

print('''I
 
L
o
v
e
 
G
P
L
T''')

L1-027 出租

一时间网上一片求救声，急问这个怎么破。其实这段代码很简单，index数组就是arr数组的下标，index[0]=2 对应 arr[2]=1，index[1]=0 对应 arr[0]=8，index[2]=3 对应 arr[3]=0，以此类推…… 很容易得到电话号码是18013820100。

本题要求你编写一个程序，为任何一个电话号码生成这段代码 —— 事实上，只要生成最前面两行就可以了，后面内容是不变的。

解法

别搞错映射关系即可

#include <iostream>
#include <cmath>
#include <map>
#include <set>
#include <sstream>
#include <vector>
#include <algorithm>

// #define int long long
using namespace std;
vector<int> v;
signed main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    string str;
    cin >> str;
    set<int> st;
    for (int i = 0; i < str.size(); i ++)
    {
        st.insert(str[i]);
    }
    
    for (auto i : st)
        v.push_back(i);
    reverse(v.begin(), v.end());
    vector<int> ans;
    for (auto i : str)
    {
        for (int j = 0; j < v.size(); j++)
            if (v[j] == i)
            {
                ans.push_back(j);
            }
    }
    
    cout << "int[] arr = new int[]{";
    for (int i = 0; i < v.size(); i ++)
    {
        cout << v[i] - '0';
        if (i != v.size() - 1)
            cout << ',';
    }
    cout << "};\n";
    
    cout << "int[] index = new int[]{";
    for (int i = 0; i < ans.size(); i ++)
    {
        cout << ans[i];
        if (i != ans.size() - 1)
            cout << ',';
    }
    cout << "};\n";
}

L1-028 判断素数

本题的目标很简单，就是判断一个给定的正整数是否素数。

解法

这个题挺离谱的，注意2是一个质数

#include <iostream>
#include <cmath>
#include <map>
#include <set>
#include <sstream>
#include <algorithm>
#include <vector>

#define int long long
using namespace std;
signed main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;
    
    for (int i = 1; i <= n; i ++)
    {
        int num;
        cin >> num;
        if (num == 1)
        {
                cout << "No" << '\n';
        }
        else
        {
        int sq = sqrt(num);
        bool flag = true;
        for (int j = 2; j <= sq; j ++)
        {
            if (num % j == 0)
            {
                flag = false;
                break;
            }
        }
        if (flag)
            cout << "Yes" << '\n';
        else 
                cout << "No" << '\n';
        }
    }
}

L2-001 紧急救援

作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。

解法

跑堆优dijkstra，记录路径。注意最短的路径条数要用加法原则

/**
 * @file codeforceModel.cpp
 * @author lighteverthing (wanxinnb@outlook.com)
 * @brief codeforces的答题模板
 * @date 2022-09-30
 * 
 * @copyright Copyright (c) 2022
 * 
 */
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <cstring>
#include <random>
#include <climits>

using namespace std;
#define int long long
#ifdef  RANDOM 
mt19937 engine(random_device{}())
uniform_int_distribution<long long> rd(1, LLONG_MAX);
#endif
const int maxn = 505;
int people[maxn];

struct node
{
    int v, w;
    bool operator<(const node& b) const
    {
        return  w > b.w;
    }
};

vector<node> e[maxn];
int dis[maxn];
int sum[maxn];
int path[maxn];
int vis[maxn];
int shortpath[maxn];
int n, m, s, d;

void dji()
{
    priority_queue<node> pq;
    pq.push({s, 0});

    for (int i = 0; i < n; i ++)
        dis[i] = 1E9 + 7;
    dis[s] = 0;
    sum[s] = people[s];
    shortpath[s] = 1;
    while (!pq.empty())
    {
        auto tmp = pq.top();
        pq.pop();
        int y = tmp.v, w = tmp.w;

        if (vis[y]) continue;
        vis[y] = 1;

        for (auto it : e[y])
        {
            int v = it.v, wv =it.w;
            if (wv + w < dis[v])
            {
                dis[v] = wv + w;
                sum[v] = sum[y] + people[v];
                path[v] = y;
                shortpath[v] = shortpath[y];
                pq.push({v, dis[v]});
            }
            else if (wv + w == dis[v])
            {
                shortpath[v] += shortpath[y];
                if (sum[y] + people[v] > sum[v])
                {
                         path[v] = y;
                         sum[v] = sum[y] + people[v];
                }
            }
        }
    }
}

void print()
{
    vector<int> ans;
    int now = d;

    while (now != s)
    {
        ans.push_back(now);
        now = path[now];
    }
    ans.push_back(s);
    reverse(ans.begin(), ans.end());
    
    cout << shortpath[d] << ' ' << sum[d] << '\n';
    
    for (int i = 0; i < ans.size(); i ++)
    {
        cout << ans[i];
        if (i != ans.size() - 1)
            cout << ' ';
    }
}

inline void solve()
{
#ifdef DEBUG
    for (int i = 1; i <= 100; i++);
#endif
    cin >> n >> m >> s >> d;

    for (int i = 0; i < n; i ++)
        cin >> people[i];
    for (int i = 1; i <= m; i ++)
    {
        int u, v, w;
        cin >> u >> v >> w;

        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }

    dji();
    print();
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

L2-002 链表去重

给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。

解法

用map和set去模拟链表就可以了，属于小模拟

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <cstring>
#include <random>
#include <climits>
#include <set>

using namespace std;

#ifdef  RANDOM 
mt19937 engine(random_device{}())
uniform_int_distribution<long long> rd(1, LLONG_MAX);
#endif

struct node
{
    int val;
    string next;
};

map<string, node> mp;
set<int> st;
map<string, node> now;
map<string, node> q;

inline void solve()
{
#ifdef DEBUG
    for (int i = 1; i <= 100; i++);
#endif
    string first;
    int n;

    cin >> first  >> n;

    for (int i = 1; i<= n; i++)
    {
        string now;
        int val;
        string next;
        cin >> now >> val >> next;
        mp[now] = {val, next};
    }

   string preq = "-1";
    string pren = "-1";
    string firstq = "-1";
    string firstn = "-1";

    while (first != "-1")
    {
        int val = mp[first].val;
        string next = mp[first].next;

        if (st.count(abs(val))) 
        {
            if (preq != "-1")
                q[preq].next = first;
            else
                firstq = first;

            q[first].val = val;
            preq = first;
        }
        else
        {
            st.insert(abs(val));
            if (pren != "-1")
                now[pren].next = first;
            else 
                firstn = first;

            now[first].val = val;
            pren = first;
        }
        
        first = next;
    }

    now[pren].next = "-1";
    q[preq].next = "-1";

    while (firstn != "-1")
    {
        cout << firstn << ' ';
        cout << now[firstn].val << ' ' << now[firstn].next;
        firstn = now[firstn].next;
        cout << '\n';
    }

    while (firstq != "-1")
    {
        cout << firstq << ' ';
        cout << q[firstq].val << ' ' << q[firstq].next;
        firstq = q[firstq].next;
        cout << '\n';
    }

}

int main(int argc, char** argv)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

L2-003 月饼

月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。

注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有 3 种月饼，其库存量分别为 18、15、10 万吨，总售价分别为 75、72、45 亿元。如果市场的最大需求量只有 20 万吨，那么我们最大收益策略应该是卖出全部 15 万吨第 2 种月饼、以及 5 万吨第 3 种月饼，获得 72 + 45/2 = 94.5（亿元）。

解法

对每个月饼的单价进行排序，最后从大到小买就可以了

/**
 * @file codeforceModel.cpp
 * @author lighteverthing (wanxinnb@outlook.com)
 * @brief codeforces的答题模板
 * @date 2022-09-30
 * 
 * @copyright Copyright (c) 2022
 * 
 */
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <cstring>
#include <random>
#include <climits>

using namespace std;

#ifdef  RANDOM 
mt19937 engine(random_device{}())
uniform_int_distribution<long long> rd(1, LLONG_MAX);
#endif

const int maxn = 1E3 + 7;
double a[maxn];
double sum[maxn];

struct node
{
    double w;
    double sum;
    
    bool operator<(const node& a) const
    {
        return w > a.w;
    }
}arr[maxn];

inline void solve()
{
#ifdef DEBUG
    for (int i = 1; i <= 100; i++);
#endif
    int n;
    double d;
    cin >> n >> d;
    
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    for (int i = 1; i <= n; i ++)
        cin >> sum[i];
    
    for (int i = 1; i <= n; i ++)
    {
        arr[i] = {sum[i] / a[i], a[i]};
//         cout << arr[i].w << ' ' << arr[i].sum << '\n';
    }
    
    sort(arr + 1, arr + 1 + n);
    double ans = 0;
    
    for (int i = 1; d && i <= n; i ++)
    {
        if (d >= arr[i].sum)
        {
            ans += arr[i].w * arr[i].sum;
            d -= arr[i].sum;
        }
        else
        {
            ans += arr[i].w * d;
            d = 0;
        }
    }
    
    printf("%.2lf", ans);
}

int main(int argc, char** argv)
{
    int T = 1;
    while (T--)
    {
        solve();
    }
    return 0;
}

L2-004 这是二叉搜索树吗？

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，

其左子树中所有结点的键值小于该结点的键值；
其右子树中所有结点的键值大于等于该结点的键值；
其左右子树都是二叉搜索树。
所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。

给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

解法

挺有意思的一道题，正着递归判断一次，反着递归判断一次即可

/**
 * @file codeforceModel.cpp
 * @author lighteverthing (wanxinnb@outlook.com)
 * @brief codeforces的答题模板
 * @date 2022-09-30
 * 
 * @copyright Copyright (c) 2022
 * 
 */
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <cstring>
#include <random>
#include <climits>

using namespace std;

#ifdef  RANDOM 
mt19937 engine(random_device{}())
uniform_int_distribution<long long> rd(1, LLONG_MAX);
#endif

const int maxn = 1E3 + 7;
int a[maxn];

bool pdz(int l, int r)
{
    if (l >= r)
        return true;
    int num = a[l] ;
//     cout << l << ' ' << r << '\n';
    bool flag = true;
    int pos = 0;
    
    for (int i = l + 1; i <= r; i ++)
    {
        if (a[i] >= num)
        {
            pos = i;
            break;
        }
    }
    
    if (!pos)
    {
        pos = r + 1;
    }
    
    for (int i = pos; i <= r; i ++)
    {
        if (a[i] < num)
        {
            flag = false;
            break;
        }
    }
    
    bool flagl = pdz(l + 1, pos - 1), flagr = pdz(pos, r);
    return (flagl && flagr && flag);
}

bool pdf(int l, int r)
{
    if (l >= r)
        return true;
    int num = a[l] ;
    
    bool flag = true;
    int pos = 0;
    
    for (int i = l + 1; i <= r; i ++)
    {
        if (a[i] < num)
        {
            pos = i;
            break;
        }
    }
    
    if (!pos)
    {
        pos = r + 1;
    }
    for (int i = pos; i <= r; i ++)
    {
        if (a[i] >= num)
        {
            flag = false;
            break;
        }
    }
    
    bool flagl = pdf(l + 1, pos - 1), flagr = pdf(pos, r);
    return (flagl && flagr && flag);
}

vector<int> v;

void print(int l, int r, int p)
{
    int num = a[l];
    
    if (l > r)
        return ;
    int pos = 0;
    for (int i = l + 1; i <= r; i ++)
    {
        if (p)
        {
            if (a[i] < num)
            {
                pos = i;
                break;
            }
        }
        else 
        {
            if (a[i] >= num)
            {
                pos = i;
                break;
            }
        }
    }
    if (!pos)
    {
        pos = r + 1;
    }
    print(l + 1 ,pos - 1, p);
    print(pos, r, p);
    v.push_back(num);
}

inline void solve()
{
#ifdef DEBUG
    for (int i = 1; i <= 100; i++);
#endif
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    
    bool flagz = pdz(1, n), flagf = pdf(1, n);
    if (flagz || flagf)
    {
        cout << "YES" << '\n';
        if (flagz)
            print(1, n, 0);
        else 
            print(1, n, 1);
        
        for (int i = 0; i < v.size(); i ++)
        {
            cout << v[i];
            if (i != v.size() - 1)
                cout << ' ';
        }
    }
    else 
        cout << "NO";
}

int main(int argc, char** argv)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
//     cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

L2-005 集合相似度

给定两个整数集合，它们的相似度定义为：N c/N t×100%。其中N c 是两个集合都有的不相等整数的个数，N t
是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。

解法

用set去模拟即可，注意，这题卡常要稍微优化一下

#include <iostream>
#include <cmath>
#include <map>
#include <set>
#include <sstream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <queue>

// #define int long long
using namespace std;
set<int> st[55];

signed main()
{

    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++)
    {
        int m;
        scanf("%d", &m);
        
        for (int j = 1; j <= m; j ++)
        {
            int tmp;
                    scanf("%d", &tmp);
            st[i].insert(tmp);
        }
    }
    
    int k;
        scanf("%d", &k);
    for (int i = 1; i <= k; i ++)
    {
        int op1, op2;
//         cin >> op1 >> op2;
        scanf("%d%d", &op1, &op2);
        
        int now = st[op1].size() < st[op2].size() ? op1 : op2;
        int fnow = now == op1 ? op2 : op1;
        
        int nc = 0, nt = 0;
        for (auto i : st[now])
        {
            if (st[fnow].count(i))
                nc ++;
        }
        printf("%.2lf%\n", double(nc) / double(st[op1].size() + st[op2].size() - nc) * 100);
    }
}

L2-006 树的遍历

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

解法

简单题，用二叉树存起来就可以了，这里给了智能指针的写法

#include <cstddef>
#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
#include <memory>

using namespace std;

#ifdef SPTR
template <class T>
using sptr = shared_ptr<T>;
#endif
#ifndef SPTR
template <class T>
using sptr = T*;
#endif

struct nodeTree
{
    int value;
    sptr<nodeTree> left;
    sptr<nodeTree> right;
    nodeTree(int v) : value(v){}
};

vector<int> postOder;
vector<int> inOder;
int n;

sptr<nodeTree> build(int il, int ir, int pl, int pr)
{
	if (il > ir) return nullptr;
	if (pl > pr) return nullptr;

	sptr<nodeTree> root(new nodeTree(postOder[pr]));

	int i = il;
	for (; i <= ir; i++)
		if (inOder[i] == postOder[pr])
			break;
	int cnt = i - il;
	
	root->left = build(il, i - 1, pl, pl + cnt - 1);
	root->right = build(i + 1, ir, pl+cnt, pr - 1);
	return root;
}

int main(int argc, char** argv)
{
    cin >> n;
    postOder.resize(n);
	inOder.resize(n);
	
    for (int i = 0; i < n;i++)
        cin >> postOder[i];

	for(int i = 0; i < n; i++)
		cin >> inOder[i];

    sptr<nodeTree> root = build(0, n-1, 0, n-1);
    queue<sptr<nodeTree>> q;
    int cnt = 0;
    q.push(root);

    while(!q.empty())
    {
        sptr<nodeTree> tmp = q.front();
        cnt++;
        cout << tmp->value;
        if (cnt < n)
            cout << ' ';
        
        if (tmp->left != nullptr)
            q.push(tmp->left);
        if (tmp->right != nullptr)
            q.push(tmp->right);
        q.pop();
    }

    return 0;
}

L2-011 玩转二叉树

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

解法

基础题，注意细节就可以了

#include <memory>
#include <queue>
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

#define SPTR
#ifdef SPTR
template <class T>
using sptr = shared_ptr<T>;
#endif
#ifndef SPTR
template <class T>
using sptr = T*;
#endif

struct nodeTree
{
    int value;
    sptr<nodeTree> left;
    sptr<nodeTree> right;
    nodeTree(int v) : value(v){}
};

int n;
vector<int> preOrder;
vector<int> inOrder;

sptr<nodeTree> build(int il, int ir, int pl, int pr)
{
    if (il > ir) return nullptr;
    if (pl > pr) return nullptr;

    sptr<nodeTree> root (new nodeTree(preOrder[pl]));
    int i = il;
    while (inOrder[i] != preOrder[pl]) i++;
    int cnt = i - il;

    root->left = build(il, i - 1, pl + 1, pl + cnt);
    root->right = build(i + 1, ir, pl + cnt + 1, pr);
    return root;
}

void printTree(sptr<nodeTree> root)
{
    queue<sptr<nodeTree>> q;
    int cnt = 1;
    q.push(root);

    while (!q.empty())
    {
        auto tmp = q.front();q.pop();
        cout << tmp->value;
        if (cnt++ < n)
            cout << ' ';
        if (tmp->right) q.push(tmp->right);
        if (tmp->left)  q.push(tmp->left);
    }
}

void swapTree(sptr<nodeTree> root)
{
    if (root->left || root->right)
    {
        auto temp = root->right;
        root->right = root->left;
        root->left = temp;
        if (root->left) swapTree(root->left);
        if (root->right) swapTree(root->right);
    }
}

int main(int argc, char** argv)
{
    cin >> n;
    preOrder.resize(n);
    inOrder.resize(n);

    for (int i = 0; i < n; i++)
        cin >> inOrder[i];
    for (int i = 0; i < n;i++)
        cin >> preOrder[i];

    sptr<nodeTree> root = build(0, n-1, 0, n-1);

    printTree(root);

    return 0;
}

L2-017 人以群分

社交网络中我们给每个人定义了一个“活跃度”，现希望根据这个指标把人群分为两大类，即外向型（outgoing，即活跃度高的）和内向型（introverted，即活跃度低的）。要求两类人群的规模尽可能接近，而他们的总活跃度差距尽可能拉开。

解法

要求两类人群的规模尽可能接近，所以排序之后对半分，但是要考虑奇数的情况。尝试性的把奇数放在f，s集合比较最大值就可以了

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <cstring>
#include <random>
#include <climits>

using namespace std;

#ifdef  RANDOM 
mt19937 engine(random_device{}())
uniform_int_distribution<long long> rd(1, LLONG_MAX);
#endif
const int maxn = 1E5 + 7;
int a[maxn];

inline void solve()
{
#ifdef DEBUG
    for (int i = 1; i <= 100; i++);
#endif
    int n;
    cin >> n;

    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
    }

    sort(a + 1, a + 1 + n);

    int n1 = 0, n2 = 0, n3 = 0, n4 = 0;
    int tmp = n / 2;

    for (int i = 1; i <= tmp; i ++)
        n3 += a[i];
    
    for (int i = tmp + 1 + n % 2; i <= n; i ++)
        n4 += a[i];
    
    int maxnn = 0;
    
    int flag = 3;
    
    if (n % 2 == 0)
        maxnn = abs(n3 - n4);
    else 
    {
        flag = 1;
        maxnn = abs(n3 + a[n / 2 + 1] - n4);
        if (maxnn < abs(n3 - n4 - a[n / 2 + 1]))
        {
             maxnn = abs(n3 - n4 - a[n / 2 + 1]);
             flag = 0;
        }

    }

    cout << "Outgoing #: " << n - (tmp + (flag == 1? 1 : 0))<< '\n';
    cout << "Introverted #: " << tmp + (flag == 1? 1 : 0)<< '\n';
    cout << "Diff = " << maxnn;
}

int main(int argc, char** argv)
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

L2-018 多项式A除以B

这仍然是一道关于A/B的题，只不过A和B都换成了多项式。你需要计算两个多项式相除的商Q和余R，其中R的阶数必须小于B的阶数。

解法

手动模拟就可以了，一开始我还以为是ntt

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <map>

using ll = long long;

using namespace std;
struct node
{
    int e;
    double c;
};

const int maxn = 1E5 + 7;
map<int, double> dr, dd, ans;
node arr_dd[maxn];
const double eps = 0.05;

void solve()
{
    // getdr
    int n, m;
    cin >> n;
    int maxnndr = 0;
    for (int i =1; i <= n; i ++)
    {
        int e;
        double c;
        cin >> e >> c;
        dr[e] = c;
        maxnndr = max(maxnndr, e);
    }
    cin >> m;

    int maxnndd = 0;
    double ddc = 0;

    for (int i = 1; i <= m; i ++)
    {
        int e;
        double c;
        cin >> e >> c;
        dd[e] = c;
        arr_dd[i] = {e, c};
        if (i == 1)
            maxnndd = e, ddc = c;
    }

    for (int i = maxnndr; i >= maxnndd; i --)
    {
        ans[i - maxnndd] = dr[i] / ddc;
        // 模拟减法
        for (int j = 1; j <= m; j ++)
            dr[i - maxnndd + arr_dd[j].e] -= ans[i - maxnndd] * arr_dd[j].c;
    }

    int ansnum = 0;
    int anss = 0;
    // 减少精度
    for (int i = maxnndr; i >= 0; i --)
    {
        if (fabs(ans[i]) < eps)
            ans[i] = 0;
    }

    for (int i = maxnndr; i >= 0; i --)
    {
        if (fabs(dr[i]) < eps) 
            dr[i] = 0;
    }

    for (int i = maxnndr; i >= 0; i --)
    {
        if (ans[i]) ansnum ++;
        if (dr[i]) anss ++;
    }

    cout << ansnum;
    if (ansnum == 0)
    {
        cout << " 0 0.0" << '\n';
    }
    else 
    {
      for (int i = maxnndr; i >= 0; i --)
        if (ans[i])
            printf(" %d %.1lf", i, ans[i]);

        cout << '\n';
    }

    cout << anss;
    if (anss == 0)
    {
        cout << " 0 0.0" << '\n';
    }
    else 
    {
      for (int i = maxnndr; i >= 0; i --)
        if (dr[i])
            printf(" %d %.1lf", i, dr[i]);
    }

}

int main(int argc, char **argv)
{
    solve();
    return 0;
}

L2-019 悄悄关注

新浪微博上有个“悄悄关注”，一个用户悄悄关注的人，不出现在这个用户的关注列表上，但系统会推送其悄悄关注的人发表的微博给该用户。现在我们来做一回网络侦探，根据某人的关注列表和其对其他用户的点赞情况，扒出有可能被其悄悄关注的人。

解法

用map或者是set先存好关注的，然后排序暴力遍历一遍，如果满足不在集合内并且大于平均值就是答案

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <cstring>
#include <random>
#include <climits>
#include <set>

using namespace std;

#ifdef  RANDOM 
mt19937 engine(random_device{}())
uniform_int_distribution<long long> rd(1, LLONG_MAX);
#endif

struct node
{
    string name;
    int ci;
};

set<string> st;
vector<node> v;
vector<string> ans;
int sum = 0;

inline void solve()
{
#ifdef DEBUG
    for (int i = 1; i <= 100; i++);
#endif
    int n;
    cin >> n;
    
    for (int i = 1; i<= n; i ++)
    {
        string str;
        cin >> str;

        st.insert(str);
    }

    int m;
    cin >> m;
    for (int i = 1; i <= m; i ++)
    {
        string name;
        int ci;
        cin >> name >> ci;
        v.push_back({name, ci});
        sum += ci;
    }
    
    int avg = sum / m;

    for (auto& it : v)
    {
        if (it.ci > avg && st.count(it.name) == 0)
            ans.push_back(it.name);
    }

    sort(ans.begin(), ans.end());
    
    if (ans.size() == 0)
        cout << "Bing Mei You";
    else 
    {
        for (auto& it : ans)
        {
            cout << it << '\n';
        }
    }
}

int main(int argc, char** argv)
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

L2-020 功夫传人

一门武功能否传承久远并被发扬光大，是要看缘分的。一般来说，师傅传授给徒弟的武功总要打个折扣，于是越往后传，弟子们的功夫就越弱…… 直到某一支的某一代突然出现一个天分特别高的弟子（或者是吃到了灵丹、挖到了特别的秘笈），会将功夫的威力一下子放大N倍 —— 我们称这种弟子为“得道者”。

这里我们来考察某一位祖师爷门下的徒子徒孙家谱：假设家谱中的每个人只有1位师傅（除了祖师爷没有师傅）；每位师傅可以带很多徒弟；并且假设辈分严格有序，即祖师爷这门武功的每个第i代传人只能在第i-1代传人中拜1个师傅。我们假设已知祖师爷的功力值为Z，每向下传承一代，就会减弱r%，除非某一代弟子得道。现给出师门谱系关系，要求你算出所有得道者的功力总值。

解法

简单遍历一遍树，然后记录答案就可以了

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <cstring>
#include <random>
#include <climits>

using namespace std;

#ifdef  RANDOM 
mt19937 engine(random_device{}())
uniform_int_distribution<long long> rd(1, LLONG_MAX);
#endif
const int maxn = 1E5 + 7;
vector<int> e[maxn];
map<int, int> mp;

double sum = 0;
double z, r;

void dfs(int now, double val)
{
    if (mp.count(now))
    {
        sum += val * mp[now];
        return ;
    }

    for (auto& it : e[now])
    {
        dfs(it, val * (100 - r) / 100.0);
    }
}

inline void solve()
{
#ifdef DEBUG
    for (int i = 1; i <= 100; i++);
#endif
    int n;
    cin >> n >> z >> r;

    for (int i = 0; i < n; i ++)
    {
        int tmp;
        cin >> tmp;
        if (tmp == 0)
            cin >> mp[i];
        else 
        {
            for (int j = 1; j <= tmp; j ++)
            {
                int num;
                cin >> num;
                e[i].push_back(num);
            }
        }
    }

    dfs(0, z);
    cout << int(sum);
}

int main(int argc, char** argv)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

L2-033 简单计算器

本题要求你为初学数据结构的小伙伴设计一款简单的利用堆栈执行的计算器。如上图所示，计算器由两个堆栈组成，一个堆栈 S1 存放数字，另一个堆栈 S 2存放运算符。计算器的最下方有一个等号键，每次按下这个键，计算器就执行以下操作：从 S1 中弹出两个数字，顺序为 n 1和 n 2；从 S2中弹出一个运算符 op；执行计算 n2 op n1 将得到的结果压回 S1。直到两个堆栈都为空时，计算结束，最后的结果将显示在屏幕上。

解法

用栈进行简单模拟就可以了，属于简单的stl运用

#include <cstdio>
#include <stack>
#include <iostream>
#include <string>

using namespace std;

int main()
{
	int n;
	cin >> n;
	stack<int> num;
	stack<char> cc;

	for (int i =0; i < n; i++)
	{
		int tmp;
		cin >> tmp;
		num.push(tmp);
	}

	for (int i = 0; i < n-1; i++)
	{
		char c;
		cin >> c;
		cc.push(c);
	}

	while ((!cc.empty()) && (num.size() != 1))
	{
		int n1, n2;
		n1 = num.top(); num.pop();
		n2 = num.top(); num.pop();

		char c = cc.top(); cc.pop();


		if (c == '+')
			num.push(n2 + n1);
		else if (c == '-')
			num.push(n2 - n1);
		else if (c == '*')
			num.push(n2 * n1);
		else
		{
			if (n1 == 0)
			{
				cout << "ERROR: " << n2 << '/' << 0;
				return 0;
			}

			num.push(n2 / n1);
		}
	}

	cout << num.top();
	return 0;
}

L2-035 完全二叉树的层序遍历

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是完美二叉树。对于深度为 D 的，有 N 个结点的二叉树，若其结点对应于相同深度完美二叉树的层序遍历的前 N 个结点，这样的树就是完全二叉树。

给定一棵完全二叉树的后序遍历，请你给出这棵树的层序遍历结果。

解法

算法基础，层次遍历完全二叉树

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
#include <memory>

using namespace std;

#define SPTR
#ifdef SPTR
template <class T>
using sptr = shared_ptr<T>;
#endif
#ifndef SPTR
template <class T>
using sptr = T*;
#endif

struct nodeTree
{
    int value;
    sptr<nodeTree> left;
    sptr<nodeTree> right;
    nodeTree(int v) : value(v){}
};

vector<int> postOder;
int n;
int local;

sptr<nodeTree> build(int bandle)
{
    sptr<nodeTree> root(new nodeTree(postOder[--local]));
    if (bandle * 2 + 1 <= n) root->right = build(bandle*2 + 1);
    if (bandle *2 <= n) root->left = build(bandle*2);
    return root;
}

int main(int argc, char** argv)
{
    cin >> n;
    local = n;
    postOder.resize(n);
    for (int i = 0; i < n;i++)
        cin >> postOder[i];

    sptr<nodeTree> root = build(1);
    queue<sptr<nodeTree>> q;
    int cnt = 0;
    q.push(root);

    while(!q.empty())
    {
        sptr<nodeTree> tmp = q.front();
        cnt++;
        cout << tmp->value;
        if (cnt < n)
            cout << ' ';
        
        if (tmp->left != nullptr)
            q.push(tmp->left);
        if (tmp->right != nullptr)
            q.push(tmp->right);
        q.pop();
    }

    return 0;
}

L2-039 清点代码库

上图转自新浪微博：“阿里代码库有几亿行代码，但其中有很多功能重复的代码，比如单单快排就被重写了几百遍。请设计一个程序，能够将代码库中所有功能重复的代码找出。各位大佬有啥想法，我当时就懵了，然后就挂了。。。”

这里我们把问题简化一下：首先假设两个功能模块如果接受同样的输入，总是给出同样的输出，则它们就是功能重复的；其次我们把每个模块的输出都简化为一个整数（在 int 范围内）。于是我们可以设计一系列输入，检查所有功能模块的对应输出，从而查出功能重复的代码。你的任务就是设计并实现这个简化问题的解决方案。

解法

先用数字表示一个数组，然后将所有代表数组的数字放在一起排序（这题我写的比较依赖于STL）。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <cstring>
#include <random>
#include <climits>
#include <set>

using namespace std;
const int maxn = 1E4 + 7;
map<vector<int>, int> to_id;
map<int, vector<int>> to_arr;
map<int, int> mp;
int cnt = 0;

#ifdef  RANDOM 
mt19937 engine(random_device{}())
uniform_int_distribution<long long> rd(1, LLONG_MAX);
#endif

bool cmp(const pair<int, int>& a, const pair<int, int>& b)
{
    int af = a.first, as = a.second, bf = b.first, bs = b.second;
    if (as != bs)
        return as > bs;
    else 
    {
        const vector<int>& arra = to_arr[af], arrb = to_arr[bf];
        int siz = arra.size();
        for (int i = 0; i < siz; i ++)
        {
            if (arra[i] != arrb[i])
            {
                if (arra[i] < arrb[i])
                    return true;
                else 
                    return false;
            }
        }
    }
}

inline void solve()
{
#ifdef DEBUG
    for (int i = 1; i <= 100; i++);
#endif
    int n, m;
    cin >> n >> m;

    for (int i =1; i <= n; i ++)
    {
        vector<int> tmp;

        for (int j = 1; j <= m; j ++)
        {
            int num;
            cin >> num;
            tmp.push_back(num);
        }

        if (to_id[tmp] == 0) 
        {
            to_id[tmp] = ++cnt;
            to_arr[cnt] = tmp;
        }
        mp[to_id[tmp]] ++;
    }

    vector<pair<int, int>> ans(mp.begin(), mp.end());
    int siz = ans.size();
    sort(ans.begin(), ans.end(), cmp);
    
    cout << siz << '\n';
    for (auto& it : ans)
    {
        int arr_num = it.first, num = it.second;
        const vector<int>& arr = to_arr[arr_num];
        cout << num << ' ';

        for (int i = 0; i < arr.size(); i ++)
        {
            cout << arr[i];
            if (i != arr.size() - 1)
                cout << ' ';
        }
        cout << '\n';
    }
}

int main(int argc, char** argv)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

L2-040 哲哲打游戏

哲哲是一位硬核游戏玩家。最近一款名叫《达诺达诺》的新游戏刚刚上市，哲哲自然要快速攻略游戏，守护硬核游戏玩家的一切！

为简化模型，我们不妨假设游戏有 N 个剧情点，通过游戏里不同的操作或选择可以从某个剧情点去往另外一个剧情点。此外，游戏还设置了一些存档，在某个剧情点可以将玩家的游戏进度保存在一个档位上，读取存档后可以回到剧情点，重新进行操作或者选择，到达不同的剧情点。

为了追踪硬核游戏玩家哲哲的攻略进度，你打算写一个程序来完成这个工作。假设你已经知道了游戏的全部剧情点和流程，以及哲哲的游戏操作，请你输出哲哲的游戏进度。

解法

用map记录存档，然后在图上dfs就可以了

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <cstring>
#include <random>
#include <climits>

using namespace std;
const int maxn = 1E5 + 7;
map<int, int> son[maxn];
map<int, int> save;

#ifdef  RANDOM 
mt19937 engine(random_device{}())
uniform_int_distribution<long long> rd(1, LLONG_MAX);
#endif

inline void solve()
{
#ifdef DEBUG
    for (int i = 1; i <= 100; i++);
#endif
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i ++)
    {
        int tmp;
        cin >> tmp;

        for (int j = 1; j <= tmp; j ++)
        {
            int v;
            cin >> v;
            son[i][j] = v;
        }
    }


    int now = 1;
    for (int i = 1; i <= m; i ++)
    {
        int op, j;
        cin >> op >> j;

        if (op == 0)
        {
            now = son[now][j];
        }
        else if (op == 1)
        {
            save[j] = now;
            cout << now << '\n';
        }
        else 
        {
            now = save[j];
        }
    }
    cout << now << '\n';
}

int main(int argc, char** argv)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

L2-043 龙龙送外卖

龙龙是“饱了呀”外卖软件的注册骑手，负责送帕特小区的外卖。帕特小区的构造非常特别，都是双向道路且没有构成环 —— 你可以简单地认为小区的路构成了一棵树，根结点是外卖站，树上的结点就是要送餐的地址。

每到中午 12 点，帕特小区就进入了点餐高峰。一开始，只有一两个地方点外卖，龙龙简单就送好了；但随着大数据的分析，龙龙被派了更多的单子，也就送得越来越累……

看着一大堆订单，龙龙想知道，从外卖站出发，访问所有点了外卖的地方至少一次（这样才能把外卖送到）所需的最短路程的距离到底是多少？每次新增一个点外卖的地址，他就想估算一遍整体工作量，这样他就可以搞明白新增一个地址给他带来了多少负担。

解法

这题属于是套路题，算每条路径的贡献，发现每条路径在要回到外卖店的时候至少要走2次，如果不要回到外卖店，则总数量减去那条最长的就是最小的路径。

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;
const int maxn = 1E5 + 7;
vector<int> son[maxn], fa[maxn];
int sum = 0;
int vis[maxn];
int dep[maxn];

void dfs(int now, int ans)
{
    if (vis[now])
    {
        sum += ans * 2;
        return ;
    }

    vis[now] = 1;
    dfs(fa[now][0], ans + 1);
}

void dfs1(int now,int deep)
{
    dep[now] = deep;

    for (auto& y : son[now])
    {
        dfs1(y, deep + 1);
    }
}

int main(int argc ,char** argv)
{
    int n, m;
    cin >> n >> m;
    int root = 0;

    for (int i = 1; i <= n; i ++)
    {
        int tmp;
        cin >> tmp;
        if (tmp == -1) 
        {
            root = i;
            continue;
        }
        son[tmp].push_back(i);
        fa[i].push_back(tmp);
    }

    dfs1(root, 0);
    vis[root] = 1;
    int maxnn = 0;

    for (int i = 1; i <= m; i ++)
    {
        int tmp;
        cin >> tmp;
        maxnn = max(dep[tmp], maxnn);
        dfs(tmp, 0);
        cout << sum - maxnn << '\n';
    }

    return 0;
}

L3-001 凑零钱

韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里，发现这家店有个特别的规矩：你可以用任何星球的硬币付钱，但是绝不找零，当然也不能欠债。韩梅梅手边有 10 ^ 4 枚来自各个星球的硬币，需要请你帮她盘算一下，是否可能精确凑出要付的款额。

解法

简单的dp，中间暴力判断一下数组就可以了

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <cstring>
#include <random>
#include <climits>

using namespace std;

#ifdef  RANDOM 
mt19937 engine(random_device{}())
uniform_int_distribution<long long> rd(1, LLONG_MAX);
#endif
const int maxn = 1E4 + 7;
int a[maxn];
int dp[105];
vector<int> ans[105];

inline void solve()
{
#ifdef DEBUG
    for (int i = 1; i <= 100; i++);
#endif
    int n, m;
    cin >> n >> m;

    for (int i = 1; i<=n ; i++)
        cin >> a[i];

    sort(a + 1, a + 1 + n);

    // dp[0][0] = 1;
    dp[0] = 1;
    ans[0].push_back(-1);
    // int pre = 0;
    for (int i = 1; i <= n; i ++)
    {
        for (int j = m; j >= a[i]; j --) 
        {
            if (dp[j - a[i]] == 1 && dp[j] == 0)
            {
                dp[j] = 1;
                
                for (auto it : ans[j - a[i]])
                    ans[j].push_back(it);
                ans[j].push_back(a[i]);
            }
            else if (dp[j - a[i]] == 1 && dp[j] != 0)
            {
                bool flag = true;
                for (int q = 0; q < ans[j - a[i]].size(); q ++)
                    if (q < ans[j].size() && ans[j][q] > ans[j - a[i]][q])
                    {
                        flag = false;
                        break;
                    }

                if (!flag)
                {
                    ans[j].clear();

                    for (int q = 0; q < ans[j - a[i]].size(); q ++)
                        ans[j].push_back(ans[j - a[i]][q]);
                    ans[j].push_back(a[i]);
                }
            }
        }
    }

    if (dp[m])
    {

        for (int i = 1; i < ans[m].size(); i ++)
        {
            cout << ans[m][i];
            if (i != ans[m].size() - 1)
                cout << ' ';
        }

    }
    else 
    {
        cout << "No Solution";
    }
}

int main(int argc, char** argv)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

L3-002 特殊堆栈

堆栈是一种经典的后进先出的线性结构，相关的操作主要有“入栈”（在堆栈顶插入一个元素）和“出栈”（将栈顶元素返回并从堆栈中删除）。本题要求你实现另一个附加的操作：“取中值”——即返回所有堆栈中元素键值的中值。给定 N 个元素，如果 N 是偶数，则中值定义为第 N/2 小元；若是奇数，则为第 (N+1)/2 小元。

解法

入栈出栈用普通的栈模拟，取中值操作用平衡树或者是线段树维护就可以了，注意，线段树要使用二分，多一个logn。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <cstring>
#include <random>
#include <climits>

using namespace std;
const int maxn = 1E5 + 7;
class DsegmentTree
{
public:
    int cnt = 0;
    int tree[maxn << 2], lch[maxn << 2], rch[maxn << 2];
    int root = 0;


    void change(int& now, int l, int r, int pos, int val)
    {
        if (!now) now = ++cnt;

        if (l == r && r == pos)
        {
            tree[now] += val;
            return ;
        }
        int mid = (l + r) / 2;

        if (pos <= mid) change(lch[now], l, mid, pos, val);
        if (pos >= mid + 1) change(rch[now], mid + 1, r, pos, val);

        tree[now] = tree[lch[now]] + tree[rch[now]];
    }

    int query(int now, int l, int r, int dl, int dr)
    {
        if (!now) return 0;

        if (dl <= l && dr >= r)
            return tree[now];

        int mid = (l + r) / 2;
        int ans = 0;

        if (dl <= mid) ans += query(lch[now], l, mid, dl, dr);
        if (dr >= mid + 1) ans += query(rch[now], mid + 1, r, dl, dr);

        return ans;
    }
};

#ifdef  RANDOM 
mt19937 engine(random_device{}())
uniform_int_distribution<long long> rd(1, LLONG_MAX);
#endif

DsegmentTree dt;

int check(int pos)
{
    int l = 1, r = 1E5;
    
    while (l <= r)
    {
        int mid = (l + r) / 2;
        int tmp = dt.query(dt.root, 1, 1E5, 1, mid);
        if( tmp < pos) l = mid + 1;
        else r = mid - 1;
    }
    return r + 1;
}

inline void solve()
{
#ifdef DEBUG
    for (int i = 1; i <= 100; i++);
#endif
    int n;
    cin >> n;
    stack<int> st;

    for (int i = 1; i <= n; i++)
    {
        string op;
        cin >> op;
        if (op == "Pop")
        {
            if (st.empty())
                cout << "Invalid" << '\n';
            else 
            {
                int tmp = st.top();
                cout << tmp << '\n';
                st.pop();
                dt.change(dt.root, 1, 1E5, tmp, -1);
            }
        }
        else if (op == "PeekMedian")
        {
            int num = st.size();
            int pos = (num % 2 == 0 ? num / 2 : (num + 1) / 2);

            if (num == 0)
                cout << "Invalid" << '\n';
            else 
                cout << check(pos) << '\n';
        }
        else 
        {
            int n;
            cin >> n;

            st.push(n);
            dt.change(dt.root, 1, 1E5, n, 1);
        }
    }
}

int main(int argc, char** argv)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

L3-013 非常弹的球

刚上高一的森森为了学好物理，买了一个“非常弹”的球。虽然说是非常弹的球，其实也就是一般的弹力球而已。森森玩了一会儿弹力球后突然想到，假如他在地上用力弹球，球最远能弹到多远去呢？他不太会，你能帮他解决吗？当然为了刚学习物理的森森，我们对环境做一些简化：…

解法

物理题，根据题意来算能量的减少量就可以了

#include <cstdio>

const double eps = 1E-8;

int main()
{
    double w, p;
    scanf("%lf %lf", &w, &p);

    double v = 2E5 / w;
    double sum = 0;

    while (v > eps)
    {
        sum += v / 9.8;
        v = v * (100 - p) * 0.01;
    }
    printf("%.3lf", sum);
}

L3-015 球队“食物链”

某国的足球联赛中有N支参赛球队，编号从1至N。联赛采用主客场双循环赛制，参赛球队两两之间在双方主场各赛一场。

联赛战罢，结果已经尘埃落定。此时，联赛主席突发奇想，希望从中找出一条包含所有球队的“食物链”，来说明联赛的精彩程度。“食物链”为一个1至N的排列…

解法

dfs剪枝，由于最后成环比如3-4-5-1-6，可以经过旋转变成1-6-3-4-5，这样就保证了字典序最小。也就是说必须从1开始，而且后面的所有结点中，必须有一个能打赢1的，这样才能形成环。先对邻接表排序，求出来的第一个就是路径就是答案。文章来源地址https://www.toymoban.com/news/detail-645265.html

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <cstring>
#include <random>
#include <climits>

using namespace std;

#ifdef  RANDOM 
mt19937 engine(random_device{}())
uniform_int_distribution<long long> rd(1, LLONG_MAX);
#endif

const int maxn = 1E5;
vector<int> e[maxn];
bool vis[maxn];
vector<int> tmp, ans;
bool flag = false;
int n;

void dfs(int now)
{
    if (flag) return ;
    if (tmp.size() == n - 1)
    {
        ans = tmp;
        flag = true;
        return ;
    }

    bool f = false;
    for (int i = 1; i<= n; i ++) // 有无一节点
        if (vis[i] == 0 && find(e[i].begin(), e[i].end(), 1) != e[i].end())
            f = true;
    if (!f) return ;
    
    for (auto& y : e[now])
    {
        if (!vis[y])
        {
            vis[y] = true;
            tmp.push_back(y);
            dfs(y);
            tmp.pop_back();
            vis[y] = false;
        }
    }
}

inline void solve()
{
#ifdef DEBUG
    for (int i = 1; i <= 100; i++);
#endif
    cin >> n;

    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= n; j ++)
        {
            char c;
            cin >> c;

            if (c == 'W')
                e[i].push_back(j);
            else if (c == 'L')
                e[j].push_back(i);
        }
    }

    for (int i = 1; i <= n; i ++)
    {
        sort(e[i].begin(), e[i].end());
    }

    vis[1] = true;
    dfs(1);
    if (flag)
    {
        cout << 1 ;
        for (auto& it : ans)
            cout << ' ' << it;
    }
    else 
        cout << "No Solution";
}
int main(int argc, char** argv)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}