狗厂笔试826_给定一个长度为n 的序列a,请你构造一个序列b,序列b满足以下条件1.序列b的长度

第一题

给定长度为n的序列a，请构造一个序列b，序列b满足一下条件：

1. 序列b的长度为n
2. 对于任意i∈[1, n],满足(a_i + b_i) mod i = 0
3. 对于任意i∈[1, n], 满足1≤b_1≤10^9
4. 对于任意1≤i<j≤n, 满足b_i≠b_j
   输入描述
   第一行输入一个整数n(1≤n≤10^5)
   第二行输入n个整数，第i个位a_i（1≤a_i≤10^6）

输出描述
输出n个整数，表示答案
若有多个不同的答案，输出任意一个即可。

示例1
输入
5
3 4 7 8 10

输出
1 6 2 4 5

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> nums(n + 1);
    vector<int> res;
    unordered_map<int, bool> map;
    
    for (int i = 1; i <= n; i++) {
        cin >> nums[i];
        for (int j = 1; j <= n; j++) {
            if ((nums[i] + j) % i == 0) { // 满足条件 (a_i + b_i) mod i = 0
                int temp = j;
                while (map[temp]) { // 如果 temp 已经被使用，寻找下一个满足条件的值
                    temp += i;
                }
                map[temp] = true; // 标记 temp 已被使用
                res.push_back(temp); // 将找到的值添加到结果序列中
                break;
            }
        }
    }
    
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << " ";
    }
    cout << endl;
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

第二题

在这个游戏中，有n个单位，每个单位的身份是"人"或者“兽"。每个人只知道自己的身份,不知道别人的身份。每个人的战斗力为a_i。
当两个单位相遇的时候，首先第一环节是确认身份(每个人可能会告诉对方自己身份，也可能隐藏)。

如果一个兽得知了对方是人,那么兽会直接攻击人，两方发生战斗;
如果一个人得知了对方是兽，那么他会权衡双方的战斗力:只有自己的战斗力大于对方时他才会发起攻击。
如果两个单位的阵营相同，则无事发生。

当两个单位攻击时，如果他们的战斗力相等，则最终同归于尽。如果某一方战斗力高,则战斗力高的将把对方杀死。

现在小红进行了m轮遭遇（每次选两个单位遭遇)，请你输出最终的存活情况。请注意，如果选择遭遇的两方存在某一方已经死亡,显然也不会发生战斗。

输入描述
第一行输入两个正整教n, rm,代表单位数量、回合数。
接下来的n行，每行输入一个字符串s_i、一个正整数a_i，分别代表第i个单位的身份、战斗力。
接下来的m行，每行输入两个正整数u,v 以及两个字符c_1,c_2，代表第u个单位和第v个单位遭遇。c_1是’Y’字符代表u向v公布自己的身份，'N’代表隐藏身份;c_2是’Y’字符代表v向u.公布自己的身份，N’代表隐藏身份。
1≤n≤10^5
1≤a_i≤10^9
1≤u,v≤n

输出描述
输出一个长度为n的字符串,仅由"Y’和’N’组成。'Y’代表第i个单位存活,N代表死亡。

输入：
输入
4 3
human 2
monster 3
monster 10
monster 1
1 2 N Y
1 4 Y N
2 3 Y Y

说明
第一轮,第一个单位(人）和第二个(兽）遭遇, 兽公布了自己的身份，由于人的战斗力低于兽,他不会选择战斗。
第二轮,第一个单位(人）和第四个(兽）遭遇，人公布了自己的身份,兽直接选择战斗,但人获胜。
第三轮,两个单位都公布了身份,由于身份相同,因此不会战斗。最终只有第四个单位死亡。

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n; // 输入单位的数量
    cin >> m; // 输入战斗事件的数量

    vector<pair<string, int>> units; // 存储单位的类型和战斗力
    vector<bool> isDeath(n); // 标记单位是否已被消灭

    string type;
    int power;
    for (int i = 0; i < n; i++) {
        cin >> type; // 输入单位类型
        cin >> power; // 输入单位战斗力
        units.push_back({ type, power }); // 将单位类型和战斗力添加到 units
    }

    int u, v;
    char c1, c2;
    for (int i = 0; i < m; i++) {
        cin >> u; // 输入战斗中的单位 u
        cin >> v; // 输入战斗中的单位 v
        cin >> c1; // 输入战斗结果 c1
        cin >> c2; // 输入战斗结果 c2

        u--;
        v--;

        if (isDeath[u] || isDeath[v]) continue; // 如果其中一个单位已死亡，跳过此次战斗

        // 根据规则判断战斗结果，以及是否需要消灭单位
        if ((units[u].first == "human" && units[v].first == "monster" && c1 == 'Y') ||
            (units[u].first == "monster" && units[v].first == "human" && c2 == 'Y')) {
            if (units[u].second == units[v].second) {
                isDeath[u] = true;
                isDeath[v] = true;
            } else if (units[u].second > units[v].second) {
                isDeath[v] = true;
            } else {
                isDeath[u] = true;
            }
            continue;
        }

        if (units[u].first == "human" && units[v].first == "monster" && c2 == 'Y') {
            if (units[u].second > units[v].second){
                isDeath[v] = true;
            }
            continue;
        }

        if (units[u].first == "monster" && units[v].first == "human" && c1 == 'Y') {
            if (units[u].second < units[v].second) {
                isDeath[u] = true;
            }
            continue;
        }
    }

    // 输出最终单位状态
    for (int i = 0; i < n; i++) {
        if (isDeath[i]) {
            cout << 'N'; // 单位被消灭
        } else {
            cout << 'Y'; // 单位存活
        }
    }
    cout << endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

第三题

小红正在参加笔试,已知笔试一共有n个编程题，每个编程题有若干个测试用例,小红获得的分数和通过的测试用例数量成正比。
对于一个题而言，小红可以写一个暴力算法获得部分分，这样相对的比较节省时间，另外她还可以直接尝试正解,这样可以获得满分，但需要花费更多的时间。现在给定了总时间,以及每个题目暴力算法的用时和得分、正确算法的用时和得分。
请你帮小红规划一个做题方案,可以在有限的时间内获得更多分数。
输入描述
第一行输入两个正整数n,t，代表题目数量,以及笔试的总时长。
接下来n行，每行输入四个正整数t_i1, s_i1,t_i2, s_i2，分别代表小红写出正解的用时，正确算法的得分，小红写暴力算法的用时，暴力算法的得分。
1≤n,t ≤2000
1<t_i2<t_i1 ≤ 2000
1≤s_i2≤ s_i1 ≤ 10^5
输出一个长度为n的字符串，第i个字符代表第i道题的策略:
如果这道题写暴力算法，则用字符’B’表示;如果写正确算法,则用字符’A’表示;如果放弃此题(不耗时间,但这道题0分)，则用F"表示。
请务必保证总耗时不超过t，且总得分尽可能大。如果有多种做题方案都能拿到最高分数,输出任意一种即可。

输入
3 10
4 10 2 5
4 20 2 5
6 20 1 15
输出
AAB
说明
前两题写正解,第三题写暴力算法，这样总耗时为9，总得分为10+20+15=45。可以证明,这样安排是最优的。

#include <iostream>
#include <vector>

using namespace std;

struct Problem {
    int correctTime;
    int correctScore;
    int bruteTime;
    int bruteScore;
};

int main() {
    int n, t;
    cin >> n >> t;

    vector<Problem> problems(n);
    for (int i = 0; i < n; ++i) {
        cin >> problems[i].correctTime >> problems[i].correctScore >> problems[i].bruteTime >> problems[i].bruteScore;
    }

    vector<vector<int>> dp(n + 1, vector<int>(t + 1, 0));
    vector<vector<char>> strategy(n + 1, vector<char>(t + 1, 'F'));

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= t; ++j) {
            // Trying brute force
            if (j >= problems[i - 1].bruteTime) {
                if (dp[i][j] < dp[i - 1][j - problems[i - 1].bruteTime] + problems[i - 1].bruteScore) {
                    dp[i][j] = dp[i - 1][j - problems[i - 1].bruteTime] + problems[i - 1].bruteScore;
                    strategy[i][j] = 'B';
                }
            }

            // Trying correct solution
            if (j >= problems[i - 1].correctTime) {
                if (dp[i][j] < dp[i - 1][j - problems[i - 1].correctTime] + problems[i - 1].correctScore) {
                    dp[i][j] = dp[i - 1][j - problems[i - 1].correctTime] + problems[i - 1].correctScore;
                    strategy[i][j] = 'A';
                }
            }

            // Skipping the problem
            if (dp[i][j] < dp[i - 1][j]) {
                dp[i][j] = dp[i - 1][j];
                strategy[i][j] = 'F';
            }
        }
    }

    // Backtrack to find the strategy
    int i = n, j = t;
    string result = "";
    while (i > 0 && j > 0) {
        char current = strategy[i][j];
        result = current + result;

        if (current == 'B') {
            j -= problems[i - 1].bruteTime;
        } else if (current == 'A') {
            j -= problems[i - 1].correctTime;
        }

        --i;
    }

    cout << result << endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71