飞得高的个人网站

菜单

飞得高
飞得高
发布于 2025-11-17 / 83 阅读
0
0

金陵科技学院PTA校赛题解答（个人）

这是前几届金陵科技学院程序设计大赛校赛题的个人解答，如果有错可以告诉我。题目不全，因为我实力不够。

7-1 诗歌交流

思路：直接打印

#include <iostream>
using namespace std;

int main() {
    cout << "Celi dada,mimi nunu!" << endl;
    cout << "Ye dada!" << endl;
    cout << "Muhe ye!";
    return 0;
}

7-2 密码破译

思路：双指针把后面一半逐个插入到前面

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    vector<string> str;
    string tmp;
    for (int i = 0; i < 5; i++) {
        getline(cin, tmp);
        str.push_back(tmp);
    }
    int i = 0, j = str.size() - 1;
    while (i <= j) {
        cout << str[j] << endl;
        if (i != j) cout << str[i] << endl;
        i++, j--;
    }
    return 0;
}

7-3 打印菱形

思路：数学推导，得出总数量公式，先输出剩余数量，在输出菱形

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;
    int i = 1;
    while (2 * i * i - 2 * i + 1 <= n) i++;
    i--;
    vector<string> str;
    for (int j = 1; j <= i; j++) {
        string s;
        for (int k = 0; k < i - j; k++) s += " ";
        for (int k = 0; k < 2 * j - 1; k++) s += "*";
        cout << s << endl;
        str.push_back(s);
    }
    for (int i = str.size() - 2; i >= 0; i--) {
        cout << str[i] << endl;
    }
    cout << n - (2 * i * i - 2 * i + 1) << endl;
    return 0;
}

7-4 比特串(Alter)

思路：贪心，遍历每一个字符，计算所需改变的值，寻找最小即可

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string str;
    cin >> str;
    int cnt_zero = 0;
    int cnt_one = 0;
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '0') cnt_zero++;
        else if (str[i] == '1') cnt_one++;
    }
    int now_zero = 0;
    int now_one = 0;
    int result = min(cnt_zero, cnt_one);
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '0') now_zero++;
        else if (str[i] == '1') now_one++;
        int need = cnt_zero - now_zero + now_one;
        result = min(need, result);
    }
    cout << result;
    return 0;
}

7-5 Keven的援助

思路：分块为 {字母 : 当前块个数} 的形式，快速知道这一块字母个数，然后分别判断a，b，c，我没有全对，我也不知道错哪了，发现了评论告诉我

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        string str;
        cin >> str;
        vector<pair<char, int>> nums;
        int cnt = 1;
        char pre = str[0];
        for (int i = 1; i < str.size(); i++) {
            if (pre != str[i]) {
                nums.push_back({pre, cnt});
                cnt = 0;
            };
            pre = str[i];
            cnt++;
        }
        nums.push_back({pre, cnt});
        int length = 0;
        int result = 0;
        pre = '\0';
        for (auto num : nums) {
            if (num.first == 'a') {
                length = num.second;
                pre = 'a';
            }
            else if (num.first == 'b' && pre == 'a') {
                if (length == 0) continue;
                if (length < num.second) {
                    length = 0;
                }
                if (length > num.second) length = num.second;
                pre = 'b';
            }
            else if (num.first == 'c' && pre == 'b') {
                if (length == 0) continue;
                if (length > num.second) {
                    length = 0;
                    continue;
                }
                else {
                    result = max(result, length);
                }
                pre = 'c';
            }
        }
        cout << result << endl;
    }
    return 0;
}

7-6 音游

思路：暴力找，队列每次加入右侧元素，如果最大最小相差超出2w就结束，进行下一次。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, w;
    cin >> n >> w;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    int result = 0;
    for (int i = 0; i < n; i++) {
        int left = i, right = i;
        int max_num = nums[left], min_num = nums[left];
        while (right < n && max_num - min_num <= 2 * w) {
            right++;
            max_num = max(max_num, nums[right]);
            min_num = min(min_num, nums[right]);
        }
        result = max(result, right - left);
    }
    cout << result;
    return 0;
}

7-7 四心

思路：逆天推导坐标公式

#include <iostream>
#include <cmath>
using namespace std;

void mode1(double x1, double y1, double x2, double y2, double x3, double y3, double& x, double& y) {
    double A1 = 2 * (x2 - x1), B1 = 2 * (y2 - y1), C1 = x2 * x2 + y2 * y2 - x1 * x1 - y1 * y1;
    double A2 = 2 * (x3 - x2), B2 = 2 * (y3 - y2), C2 = x3 * x3 + y3 * y3 - x2 * x2 - y2 * y2;
    x = (C1 * B2 - C2 * B1) / (A1 * B2 - A2 * B1);
    y = (A1 * C2 - A2 * C1) / (A1 * B2 - A2 * B1);
    if (abs(x) < 1e-3) x = 0;
    if (abs(y) < 1e-3) y = 0;
}

void mode2(double x1, double y1, double x2, double y2, double x3, double y3, double& x, double& y) {
    double a = sqrt((x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3));
    double b = sqrt((x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3));
    double c = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
    x = (a * x1 + b * x2 + c * x3) / (a + b + c);
    y = (a * y1 + b * y2 + c * y3) / (a + b + c);
    if (abs(x) < 1e-3) x = 0;
    if (abs(y) < 1e-3) y = 0;
}

void mode3(double x1, double y1, double x2, double y2, double x3, double y3, double& x, double& y) {
    x = (x1 + x2 + x3) / 3;
    y = (y1 + y2 + y3) / 3;
    if (abs(x) < 1e-3) x = 0;
    if (abs(y) < 1e-3) y = 0;
}

void mode4(double x1, double y1, double x2, double y2, double x3, double y3, double& x, double& y) {
    double A1 = x3 - x2, B1 = y3 - y2, C1 = A1 * x1 + B1 * y1;
    double A2 = x3 - x1, B2 = y3 - y1, C2 = A2 * x2 + B2 * y2;
    x = (C1 * B2 - C2 * B1) / (A1 * B2 - A2 * B1);
    y = (A1 * C2 - A2 * C1) / (A1 * B2 - A2 * B1);
    if (abs(x) < 1e-3) x = 0;
    if (abs(y) < 1e-3) y = 0;
}

int main() {
    int t;
    double x1, y1, x2, y2, x3, y3, x, y;
    while (cin >> t) {
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
        if (t == 1) {
            mode1(x1, y1, x2, y2, x3, y3, x, y);
            printf("Point O : (%.2f, %.2f)\n", x, y);
        }
        else if (t == 2) {
            mode2(x1, y1, x2, y2, x3, y3, x, y);
            printf("Point I : (%.2f, %.2f)\n", x, y);
        }
        else if (t == 3) {
            mode3(x1, y1, x2, y2, x3, y3, x, y);
            printf("Point G : (%.2f, %.2f)\n", x, y);
        }
        else if (t == 4) {
            mode4(x1, y1, x2, y2, x3, y3, x, y);
            printf("Point H : (%.2f, %.2f)\n", x, y);
        }
    }
    return 0;
}

7-10 小马和电梯

思路：按照题意模拟即可

#include <iostream>
#include <string>
using namespace std;

int main() {
    string str;
    cin >> str;
    int result = 0;
    for (int i = 0; i < str.size(); i++) {
        for (int j = 0; j < str.size(); j++) {
            if (i == j) continue;
            if ((str[i] == 'U' && i > j) || (str[i] == 'D' && i < j)) result += 2;
            else result++;
        }
    }
    cout << result;
    return 0;
}

7-11 小马和她的队友

思路：按照题意模拟即可

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums(3, 0);
    int n;
    cin >> n;
    int people = 0;
    while (n--) {
        int m, k;
        cin >> m >> k;
        int tmp;
        int left = 1, right = 10000;
        int index = 0;
        for (int i = 0; i < m; i++) {
            cin >> tmp;
            if (tmp < left || tmp > right) continue;
            index++;
            if (tmp < k) left = tmp + 1;
            else if (tmp > k) right = tmp - 1;
            else if (tmp == k) {
                nums[people % 3] += index;
                break;
            }
            people++;
        }
    }
    int result = 0;
    for (auto n : nums) {
        result = max(n, result);
    }
    cout << result;
    return 0;
}

7-12 小马和线性代数作业

思路：分别写出左右反转和上下反转。显然，每个方向翻转的有效数量 = 这个方向翻转的数量 % 2，由此可以大大降低运行所花费时间

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void reverse(vector<vector<int>>& nums, int m) {
    if (m == 0) {
        for (int i = 0; i < nums.size() / 2; i++) {
            for (int j = 0; j < nums[0].size(); j++) {
                int tmp = nums[i][j];
                nums[i][j] = nums[nums.size() - i - 1][j];
                nums[nums.size() - i - 1][j] = tmp;
            }
        }
    }
    if (m == 1) {
        for (int i = 0; i < nums.size(); i++) {
            reverse(nums[i].begin(), nums[i].end());
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    int cnt_zero = 0, cnt_one = 0;
    vector<vector<int>> nums(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> nums[i][j];
        }
    }
    for (int i = 0; i < m; i++) {
        int mode;
        cin >> mode;
        if (mode == 0) cnt_zero++;
        else if (mode == 1) cnt_one++;
    }
    cnt_zero %= 2;
    cnt_one %= 2;
    if (cnt_zero) reverse(nums, 0);
    if (cnt_one) reverse(nums, 1);
    for (auto num : nums) {
        for (auto n : num) {
            cout << n << " ";
        }
        cout << endl;
    }
    return 0;
}

7-13 小马和Virtual participation

思路：统计一下数量即可解决

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

int main() {
    int n;
    cin >> n;
    while (n--) {
        int m;
        cin >> m;
        vector<int> nums(13, 0);
        vector<unordered_set<int>> team(13);
        for (int i = 0; i < m; i++) {
            int x;
            char p;
            string ques;
            cin >> x >> p >> ques;
            if (ques == "Accepted") {
                auto it = team[p - 'A'].find(x);
                if (it == team[p - 'A'].end()) {
                    nums[p - 'A']++;
                    team[p - 'A'].insert(x);
                }
            }
        }
        int index = 0;
        for (int i = 0; i < 13; i++) {
            if (nums[i] > nums[index]) {
                index = i;
            }
        }
        cout << (char)('A' + index) << endl;
    }
    return 0;
}

7-14 小马和操作系统考试

思路：使用红黑树set存储剩余空间，使用lower_bound在set中进行二分查找找第一个大于待分配内存的空闲内存。注意需要用pair记录每一个数据对应的位置。

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    set<pair<int, int>> set;
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        set.insert({tmp, i + 1});
    }
    vector<int> result;
    for (int i = 0; i < m; i++) {
        int b;
        cin >> b;
        auto it = set.lower_bound({b, 0});
        if (it != set.end()) {
            int index = it->second;
            int s = it->first - b;
            result.push_back(index);
            set.erase(it);
            if (s > 0) {
                set.insert({s, index});
            }
        }
        else {
            result.push_back(-1);
        }
    }
    for (auto r : result) {
        cout << r << " ";
    }
    return 0;
}

7-15 咕咕和三色珠串

思路：找规律题，发现三种球的数量全是奇数或者偶数的时候最后一定会剩下两个，否则可以消成一个。但是要注意的是，如果只有一种球或者一种球远远大于其它两种的情况，可能就会剩余超过两个，校赛样例没考虑这种情况

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        string str;
        cin >> str;
        int r = 0, g = 0, b = 0;
        for (int i = 0; i < str.size(); i++) {
            if (str[i] == 'r') r++;
            else if (str[i] == 'g') g++;
            else if (str[i] == 'b') b++;
        }
        if (r + g == 0 || r + b == 0 || b + g == 0) {
            cout << r + g + b << endl;
        }
        else if (r + g < b || r + b < g || g + b < r) {
            cout << max(r + g - b, max(r + b - g, g + b - r)) << endl;
        } //校赛题目有bug，上面两个判断条件不写也能对
        else if ((r % 2 == 0 && g % 2 == 0 && b % 2 == 0) || (r % 2 && g % 2 && b % 2)) cout << 2 << endl;
        else cout << 1 << endl;
    }
    return 0;
}

7-18 阶乘之和取模

思路：大于24后阶乘后六位完全一致，可以直接终止循环，剩下的正常迭代取模运算就行。

#include <iostream>
using namespace std;

const int mod = 1000000;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int n;
    cin >> n;
    int tmp = 1;
    int result = 0;
    for (int i = 1; i <= n; i++) {
        if (i > 24) break;
        tmp = (i % mod * tmp % mod) % mod;
        result = (result % mod + tmp % mod) % mod;
    }
    cout << result << endl;
}

7-21 你究竟有几个好妹妹

思路：思路上没什么难度，但是很坑，一不小心就会错

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct fri {
    string name;
    char sex;
    int age;
    string addTime;
};

bool cmp(fri& a, fri& b) {
    if (a.name != b.name) return a.name < b.name;
    else if (a.age != b.age) return a.age < b.age;
    else if (a.addTime != b.addTime) return a.addTime < b.addTime;
}

string toLower(string str) {
    string result = "";
    for (auto s : str) {
        if ('A' <= s && s <= 'Z') {
            result += s - 'A' + 'a';
        }
        else result += s;
    }
    return result;
}

int main() {
    string str;
    cin >> str;
    int n;
    cin >> n;
    vector<fri> people(n);
    for (int i = 0; i < n; i++) {
        string name, addTime;
        char sex;
        int age;
        cin >> name >> sex >> age >> addTime;
        people[i] = {name, sex, age, addTime};
    }
    vector<fri> hmm;
    for (int i = 0; i < n; i++) {
        if (people[i].sex != 'F') continue;
        if (toLower(people[i].name.substr(0, str.size())) == toLower(str)) {
            fri f;
            f.name = people[i].name.substr(str.size());
            f.age = people[i].age;
            f.addTime = people[i].addTime;
            hmm.push_back(f);
        }
        else if (people[i].name.size() > str.size() && toLower(people[i].name.substr(people[i].name.size() - str.size())) == toLower(str)) {
            fri f;
            f.name = people[i].name.substr(0, people[i].name.size() - str.size());
            f.age = people[i].age;
            f.addTime = people[i].addTime;
            hmm.push_back(f);
        }
    }
    sort(hmm.begin(), hmm.end(), cmp);
    cout << hmm.size() << endl;
    for (auto h : hmm) {
        cout << h.name << " " << h.age << " " << h.addTime << endl;
    }
    return 0;
}

7-22 暴力小学(二年级篇)-求出4个数字

思路：真暴力

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> result;
    for (int a = 0; a < 10; a++) {
        for (int b = 0; b < 10; b++) {
            for (int c = 0; c < 10; c++) {
                for (int d = 0; d < 10; d++) {
                    if (a != b && a != c && a != d && b != c && b != d && c != d) {
                        if (d * 1000 + c * 100 * 2 + b * 10 * 3 + a * 4 == n) {
                            result.push_back({d, c, b, a});
                        }
                    }
                }
            }
        }
    }
    sort(result.begin(), result.end());
    if (result.size() != 0) {
        cout << result.size() << endl;
        for (auto r : result) {
            cout << r[0] << r[1] << r[2] << r[3] << endl;
        }
    }
    else {
        cout << 0 << endl;
    }
    return 0;
}

7-26 欢迎来到JIT

思路：打印

#include <iostream>
using namespace std;

int main() {
    cout << "Welcome To Jinling Institute of Technology!";
    return 0;
}

7-27 余数

思路：简单的余数判断

#include <iostream>
using namespace std;

int main() {
    int q;
    cin >> q;
    while (q--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (x1 % y1 == x2 % y2) cout << "yes" << endl;
        else cout << "no" << endl;
    }
    return 0;
}

7-28 让yjj讨厌的数字

思路：暴力找4

#include <iostream>
using namespace std;

bool searchFour(int n) {
    while (n) {
        if (n % 10 == 4) return true;
        n /= 10;
    }
    return false;
}

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (searchFour(i)) cnt++;
        }
        cout << cnt << endl;
    }
    return 0;
}

7-29 666666

思路：6作为分割点，小于6补全，大于6去掉

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    int cnt = 0;
    int time = 0;
    while (n) {
        if (cnt < 6) {
            time += abs(n % 10 - 6);
        }
        else time += n % 10;
        n /= 10;
        cnt++;
    }
    if (cnt < 6) time += (6 - cnt) * 6;
    cout << time << endl;
    return 0;
}

7-30 字符串

思路：纵向匹配即可

#include <iostream>
#include <string>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    string str;
    cin >> str;
    while (q--) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        int cnt = 0;
        for (int i = x, j = y; i < n && j < n; i++, j++) {
            if (str[i] == str[j]) cnt++;
            else break;
        }
        cout << cnt << endl;
    }
    return 0;
}

7-31 yjj打怪兽

思路：贪心，总是使用伤害最大的两把武器攻击，如果只有一把武器且无法对怪物一击必杀，则输出-1。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define int long long

signed main() {
    int t;
    cin >> t;
    while (t--) {
        int n, x;
        cin >> n >> x;
        int max_a = 0, max_b = 0;
        for (int i = 0; i < n; i++) {
            int tmp;
            cin >> tmp;
            if (max_a <= tmp) {
                max_b = max_a;
                max_a = tmp;
            }
            else if (max_b <= tmp) {
                max_b = tmp;
            }
        }
        if (n == 1 && max_a < x) {
            cout << -1 << endl;
            continue;
        }
        else if (n == 1 && max_a >= x) {
            cout << 1 << endl;
            continue;
        }
        int sum = max_a + max_b;
        int cnt = 2 * x / sum;
        int need = x % sum;
        if (need != 0) cnt += 1;
        cout << cnt << endl;
    }
    return 0;
}

7-34 遍历图

思路：寻找最大的点，我们可以逆向思维，从最大的点开始向下搜寻，找到哪个点，就说明那个点可以找到这个最大的点

#include <iostream>
#include <vector>
#include <list>
using namespace std;

void dfs(int now, int max, vector<list<int>>& grid, vector<bool>& visited, vector<int>& A) {
    visited[now] = true;
    A[now] = max;
    for (auto next : grid[now]) {
        if (visited[next] == false) {
            dfs(next, max, grid, visited, A);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<list<int>> grid(n + 1);
    while (m--) {
        int u, v;
        cin >> u >> v;
        grid[v].push_back(u);
    }
    vector<int> A(n + 1, 0);
    vector<bool> visited(n + 1, false);
    for (int i = n; i >= 1; i--) {
        if (visited[i] == false) {
            dfs(i, i, grid, visited, A);
        }
    }
    for (int i = 1; i < n; i++) {
        cout << A[i] << " ";
    }
    cout << A[n];
    return 0;
}

7-33 二次函数

思路：梦回高数有没有，求最大值，提前先写好f(x)函数，判断两端点+极值点

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

#define int long long

int f(int x, int a, int b, int c) {
    int y1 = -1 * a * x * x + b * x + c;
    int y2 = b * x + c;
    int y3 = 1 * a * x * x + b * x + c;
    return max(y1, max(y2, y3));
}

signed main() {
    int t;
    cin >> t;
    while (t--) {
        int a, b, c, l, r;
        cin >> a >> b >> c >> l >> r;
        int max_x = round(-1.0 * b / (2.0 * a));
        if (max_x > r) max_x = r;
        if (max_x < l) max_x = l;
        int result = max(f(max_x, a, b, c), max(f(l, a, b, c), f(r, a, b, c)));
        cout << result << endl;
    }
    return 0;
}

7-35 一尺之棰

思路：模拟打卡题

#include <iostream>
using namespace std;

int main() {
    long long n;
    while (cin >> n) {
        long long cnt = 1;
        while (n != 1) {
            cnt++;
            n /= 2;
        }
        cout << cnt << endl;
    }
    return 0;
}

7-36 一道非常有意思的题目

思路：注意一下转义字符\，其它没啥的

#include <iostream>
using namespace std;

int main() {
    cout << "|       |" << endl;
    cout << "| \\     |" << endl;
    cout << "|   \\   |" << endl;
    cout << "|     \\ |";
    return 0;
}

7-37 统计数对

思路：力扣两数之和一般的题目，暴力会超时，用哈希表就可以了

#include <iostream>
#include <cmath>
#include <unordered_map>
#include <algorithm>
using namespace std;

int main() {
    int n, c;
    cin >> n >> c;
    unordered_map<int, int> hash;
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        hash[tmp]++;
    }
    int result = 0;
    for (auto h : hash) {
        auto it = hash.find(c + h.first);
        if (it != hash.end()) {
            result += h.second * it->second;
        }
    }
    cout << result << endl;
    return 0;
}

7-38 幸运数

思路：通过除法求两个数在区间占多少，加起来，容斥原理减去公因数的倍数（去除重复元素）。

#include <iostream>
#include <algorithm>
using namespace std;

#define int long long

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

signed main() {
    int t;
    cin >> t;
    while (t--) {
        int a, b, l, r;
        cin >> a >> b >> l >> r;
        int cnt_a = r / a - (l - 1) / a;
        int cnt_b = r / b - (l - 1) / b;
        int lcm_num = lcm(a, b);
        int cnt_lcm = r / lcm_num - (l - 1) / lcm_num;
        cout << cnt_a + cnt_b - cnt_lcm << endl;
    }
    return 0;
}

7-42 高中の排列组合问题

思路：并非高中的排列组合，其实这题是DP，错位排列，假设n封信件有D(n)种情况，有我们考虑两种情况：

  1. 错位排列为互换，选出一个数，那么还可以从n - 1个数中选一个互换，那么剩下其它情况为D(n - 2)，也就是说这种情况一定有(n - 1)D(n - 2)种情况

  2. 错位排列为A - B，B - C，选出一个数，放到另一个上面（n - 1种情况），另一个数不能放到第一个数位置处（否则变为情况1），这时就相当于是一个D(n - 1)，那么这种情况共(n - 1)D(n - 1)

合并两种情况，得到递推式D(n) = (n - 1) (D(n - 1) + D(n - 2))，使用迭代取模即可解决。

#include <iostream>
#include <vector>
using namespace std;

#define int long long
const int mod = 1000000007;

signed main() {
    int t;
    cin >> t;
    vector<int> nums(100001);
    nums[1] = 0;
    nums[2] = 1;
    for (int i = 3; i < 100001; i++) {
        nums[i] = ((i - 1) * (nums[i - 1] % mod + nums[i - 2] % mod)) % mod;
    }
    while (t--) {
        int n;
        cin >> n;
        cout << nums[n] << endl;
    }
    return 0;
}

7-45 奖学金评选

思路：结构体数组，结构体排序，看清楚题目条件就没啥问题

#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct Student {
    string ID;
    int a, b, c;
    int l;
};

bool cmp(Student& stu1, Student& stu2) {
    if (stu1.l != stu2.l) return stu1.l < stu2.l;
    int sum1 = stu1.a + stu1.b + stu1.c;
    int sum2 = stu2.a + stu2.b + stu2.c;
    if (sum1 != sum2) return sum1 > sum2;
    if (stu1.a != stu2.a) return stu1.a > stu2.a;
    if (stu1.b != stu2.b) return stu1.b > stu2.b;
    if (stu1.c != stu2.c) return stu1.c > stu2.c;
    return stu1.ID < stu2.ID;
}

int main() {
    int n, x, y;
    cin >> n >> x >> y;
    vector<Student> stu;
    for (int i = 0; i < n; i++) {
        string ID;
        int a, b, c, l;
        cin >> ID >> a >> b >> c;
        if (a >= x && b >= x && c >= x) l = 1;
        else if ((a >= y && b >= y && c >= y) && (a >= x || b >= x || c >= x)) l = 2;
        else if (a >= y && b >= y && c >= y) l = 3;
        else l = 4;
        stu.push_back({ID, a, b, c, l});
    }
    sort(stu.begin(), stu.end(), cmp);
    int i = 0;
    cout << "One" << endl;
    while (stu[i].l == 1) {
        cout << stu[i].ID << endl;
        i++;
    }
    cout << "Two" << endl;
    while (stu[i].l == 2) {
        cout << stu[i].ID << endl;
        i++;
    }
    cout << "Three" << endl;
    while (stu[i].l == 3) {
        cout << stu[i].ID << endl;
        i++;
    }
    return 0;
}

7-46 简单的A+B问题

思路：高精度模板题

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> add(vector<int>& a, vector<int>& b) {
    if (a.size() < b.size()) return add(b, a);
    vector<int> c;
    int tmp = 0;
    for (int i = 0; i < a.size(); i++) {
        tmp += a[i];
        if (i < b.size()) tmp += b[i];
        c.push_back(tmp % 10);
        tmp /= 10;
    }
    return c;
}

int main() {
    string aStr, bStr;
    cin >> aStr >> bStr;
    vector<int> a(aStr.size()), b(bStr.size());
    for (int i = aStr.size() - 1, j = 0; i >= 0; i--, j++) {
        a[j] = aStr[i] - '0';
    }
    for (int i = bStr.size() - 1, j = 0; i >= 0; i--, j++) {
        b[j] = bStr[i] - '0';
    }
    vector<int> c = add(a, b);
    while (c.back() == 0) c.pop_back();
    for (int i = c.size() - 1; i >= 0; i--) {
        cout << c[i];
    }
    cout << endl;
    return 0;
}

7-47 最好的位置

思路：用红黑树map存储（有顺序）左区间和右区间，左区间加1，右区间右侧减1（差分），之后从头到尾遍历每个位置，寻找中间重叠部分最大的位置。

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    map<int, int> hash;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        hash[l]++;
        hash[r + 1]--;
    }
    int result = 0, curr = 0;
    for (auto h : hash) {
        curr += h.second;
        result = max(curr, result);
    }
    cout << result << endl;
    return 0;
}

7-49 粗心的同学

思路：我都直接暴力了，分都没拿全，无思路

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> nums(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> nums[i];
        int cnt = 0;
        for (int j = 1; j < i; j++) {
            if (nums[j] > nums[i]) cnt++;
        }
        cout << cnt << " ";
    }
    return 0;
}

7-50 小李同学的努力

思路：贪心算法，从左往右进行遍历，小的位置必定会比大的位置提前变为0，中断也就出现在这些地方。如果右侧值大于左侧，我没就加上右边和左边的差值，每次都要更新pre

#include <iostream>
#include <vector>
using namespace std;

#define int long long

signed main() {
    int n;
    cin >> n;
    int pre = 0;
    int result = 0;
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        if (tmp > pre) result += tmp - pre;
        pre = tmp;
    }
    cout << result << endl;
    return 0;
}

7-52 欢迎你来到金陵科技学院~

思路：打印

#include <iostream>
using namespace std;

int main() {
    cout << "欢迎来到金陵科技学院，欢迎你进入大学生活！" << endl;
    return 0;
}

7-53 大众优先（复旦）

思路：模拟即可

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string str;
    cin >> str;
    int result = 0;
    while (1) {
        bool have = false;
        for (int i = 0; i < str.size(); i++) {
            if (str[i] == '1' && str[i + 1] == '0') {
                swap(str[i], str[i + 1]);
                have = true;
                i++;
            }
        }
        if (have) result++;
        else break;
    }
    cout << result << endl;
    return 0;
}

7-54 可乐促销（浙大）

思路：先创建根据可乐数量喝兑换可乐所需瓶盖数量获取可以喝到可乐的最大数量，再二分查找到最小的可以满足条件的值即可

#include <iostream>
using namespace std;

int check(int numBottles, int numExchange) {
    int result = 0;
    int empty = 0;
    while ((numBottles + empty) / numExchange) {
        result += numBottles;
        int tmp = (numBottles + empty);
        empty = tmp % numExchange;
        numBottles = tmp / numExchange;
    }
    result += numBottles;
    return result;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int p, k;
        cin >> p >> k;
        if (p == 1) {
            cout << 1 << endl;
            continue;
        }
        int left = 0, right = k + 10;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (check(mid, p) >= k) right = mid;
            else left = mid + 1;
        }
        cout << left << endl;
    }
    return 0;
}

7-55 相邻差值（南大）

思路：暴力DFS，从前往后看，每次对pre * 10 + 当前

#include <iostream>
using namespace std;

#define int long long

void dfs(int start, int left, int right, int& count) {
    if (start >= 10 && start >= left && start <= right) {
        count++;
    }
    if (start > right) return;
    int pre = start % 10;
    if (pre == 0) {
        dfs(start * 10 + 1, left, right, count);
    }
    else if (pre == 9) {
        dfs(start * 10 + 8, left, right, count);
    }
    else {
        dfs(start * 10 + pre + 1, left, right, count);
        dfs(start * 10 + pre - 1, left, right, count);
    }
}

signed main() {
    int t;
    cin >> t;
    while (t--) {
        int l, r;
        cin >> l >> r;
        int result = 0;
        for (int i = 1; i <= 9; i++) {
            dfs(i, l, r, result);
        }
        cout << result << endl;
    }
    return 0;
}

7-59 杀

思路：根据题意写if -else

#include <iostream>
#include <string>
using namespace std;

int main() {
    string str;
    cin >> str;
    if (str == "XuSheng") {
        cout << "DaBao" << endl;
    }
    else if (str == "GanNing") {
        cout << "DaGui" << endl;
    }
    else if (str == "QuYi") {
        cout << "BaiMa" << endl;
    }
    else if (str == "HuangZhong") {
        cout << "LaoBao" << endl;
    }
    return 0;
}

7-60 铲

思路：广度优先搜索BFS模板题

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

int length = -1;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
bool bfs(vector<vector<int>> grid, int x, int y) {
    length = -1;
    queue<pair<int, int>> que;
    que.push({x, y});
    grid[x][y] = 0;
    while (!que.empty()) {
        int size = que.size();
        length++;
        for (int i = 0; i < size; i++) {
            int curr_x = que.front().first;
            int curr_y = que.front().second;
            que.pop();
            if (curr_y == grid[0].size() - 1) {
                return true;
            }
            for (int d = 0; d < 4; d++) {
                int next_x = curr_x + dir[d][0];
                int next_y = curr_y + dir[d][1];
                if (next_x < 0 || next_x >= grid.size() || next_y < 0 || next_y >= grid[0].size() || grid[next_x][next_y] == 0) {
                    continue;
                } 
                que.push({next_x, next_y});
                grid[next_x][next_y] = 0;
            }
        }
    }
    return false;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    int minLength = INT_MAX;
    for (int i = 0; i < n; i++) {
        if (grid[i][0] == 1 && bfs(grid, i, 0)) {
            minLength = min(minLength, length);
        }
    }
    if (minLength != INT_MAX) cout << minLength << endl;
    else cout << -1 << endl;
    return 0;
}

旷课汇总程序
之前的一些日记

评论