题目资料：https://wwb.lanzouo.com/iPsOu1ujw7lg

Part_1 题目

3494 工作时长

【考点】关于时间计算和Excel的使用。
【解题思路】
1.将数据复制粘贴到Excel，并按照日期排序；
2.在Excel中使用公式将日期时间格式提取出来。这可以使用TEXT函数，语法为TEXT(value,format)，对每个日期时间单元格应用这个公式，以提取具体的时间；
3.在Excel中使用公式计算时长。对于每个时间单元格，在下一行的单元格中，用当前行的时间减去前一行的时间。然后将这个公式拖动到需要计算时长的范围，以填充其他单元格；
4.在Excel中使用公式合计时长。选择一个单元格，应用"=SUM"公式，将合计范围指定为上一步计算的时长范围；最后，将合计的时长格式设置为"[h]:mm:ss"。

/* 将数据复制粘贴到excel
step1: 按照日期排序，格式：yy/mm/dd hh:mm:ss
step2: 提取时间，公式：=TEXT(A1,"hh:mm:ss")，下拉填充
step3: 计算时长，公式：=B2-B1，下拉填充
step4: 合计时长，公式：=SUM(C1:C520)，格式：[h]:mm:ss
*/

#include <iostream>
using namespace std;

int main() {
    cout << 1417 * 3600 + 11 * 60 + 53;
    return 0;
}

3552 与或异或

【考点】递归（dfs，深度优先搜索）和位运算（与、或、异或）。
【解题思路】
1.代码中的 dfs 函数是一个递归函数，用于遍历所有可能的情况。该程序通过对 dfs 函数的调用，逐步计算出满足条件的情况数量。
2.在 dfs 函数中，根据参数 k 的值（0、1、2），分别进行按位或、按位与、按位异或操作，并将结果存储在数组 a 中。
3.当遍历到最后一行时（r == 5，j == 1），判断是否满足条件，如果满足条件（a[r][j] == 1），则增加 ans 的计数。
4.主函数中通过循环调用 dfs 函数，遍历所有可能的情况。最后输出 ans，即满足条件的情况数量。

#include <iostream>
using namespace std;
  
int ans = 0, a[6][10] = {{},{0, 1, 0, 1, 0, 1}};

void dfs(int r, int j, int k) {
    if(k == 0) 
        a[r][j] = a[r - 1][j] | a[r - 1][j + 1];
    else if(k == 1) 
        a[r][j] = a[r - 1][j] & a[r - 1][j + 1];
    else if(k == 2)
        a[r][j] = a[r - 1][j] ^ a[r - 1][j + 1];
    if(r == 5 && j == 1) {
        if(a[r][j] == 1) ans++;
        return;
    }
    if(r + j == 6) r++, j = 1;
    else j++;
    for(int s = 0; s < 3; s++)
        dfs(r, j, s);
}

int main() {
    for(int k = 0; k < 3; k++)
        dfs(2, 1, k);
    cout << ans << endl;
    return 0;  
}

3520 翻转

【考点】字符串处理和逻辑判断。
【解题思路】
1.字符串处理：题目给定了两个字符串 T 和 S，需要将字符串 S 转换成与 T 相同的字符串。在代码中，使用了一个 for 循环遍历字符串 S 中的字符，然后根据条件进行相应的处理。这里涉及到了字符串的下标访问和字符的比较。
2.逻辑判断：在代码中，通过判断 S 中的字符是否与 T 中的对应字符相同，来确定是否需要进行翻转操作。如果需要翻转，则根据特定条件执行翻转操作。同时还需要检查首尾字符是否与 T 中的相同。这里涉及到了条件判断和逻辑运算。
3.特定条件下的翻转操作：在代码中，对于需要翻转的字符，有一个特定的条件：如果当前字符与其相邻字符不相同，则进行翻转操作。这一点需要理解和实现。

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

int main() {
    vector<int> res;
    int n;
    cin >> n;
    string T, S;
    while(n--){
        cin >> T >> S;
        int count = 0, len = S.length();
        for(int i = 1; i < len - 1; i++) {
            if(S[i] != T[i]) {
                if(S[i - 1] != S[i] && S[i] != S[i + 1]) {
                    S[i] = (S[i] - '0' + 1) % 2 + '0';
                    count++;
                } else {
                    count = -1;
                    break;
                }
            }
        }
        if(S[0] != T[0] || S[len - 1] != T[len - 1]){
            count = -1;
        }
        res.push_back(count);
    }
    for(int o : res) {
        cout << o << endl;
    }
    return 0;
}

3527 阶乘的和

【考点】使用递归和循环来计算阶乘的和，并且考察对向量的操作和排序的理解。
【解题思路】
通过递归和循环，func函数不断操作vector a，直到无法再进行操作。操作规则是：统计最小值min的个数count，如果count是(min + 1)的整数倍，就进行一次操作，将最小值min从向量a中删除，并将(count / (min + 1))个(min + 1)添加到向量a中。最终的返回结果是无法再进行操作时的最小值min，即为阶乘的和。

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

bool compare(int x, int y) {
    return x > y;
}

int func(vector<int>& a, int n) {
    int min = a.back(), count = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == min)
            count++;
    }
    if (count % (min + 1) == 0) {
        for(int i = 0; i < count; i++) {
            a.pop_back();
        }
        for(int i = 0; i < count / (min + 1); i++) {
            a.push_back(min + 1);
        }
        return func(a, a.size());
    } else {
        return min;
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end(), compare);
    cout << func(a, n) << endl;
    return 0;   
}

3525 公因数匹配

【考点】找到一组数列中的两个数，它们的最小公因数在整个数列中的下标最小。
【解题思路】
1.声明一个map<int, int>类型的变量mp，用于存储因数和对应的下标。定义一个函数func，该函数用于找到给定数字x的最小公因数在mp中对应的下标。函数参数id表示当前数字的下标。
2.在函数func中，使用一个循环来遍历从2到sqrt(x)的整数i。若x可以整除i，则i是x的因数。判断当前因数i是否在mp中存在且对应的下标不是当前数字的下标。如果是，则更新pos为mp[i]和id中较小的那个。
3.如果i是x的因数，继续循环，将x除以i，直到i不再是x的因数。如果x大于1，说明x是一个质数，判断x是否在mp中存在且对应的下标不是当前数字的下标。如果是，则更新pos为mp[x]和id中较小的那个。返回pos，如果pos小于100000，说明存在最小公因数，否则返回0。
4.在main函数中，声明变量i并初始化为一个很大的值100000，变量j用于记录最小公因数对应的下标。输入数列的长度n。使用一个循环从1到n，读取每个数字x。
5.调用函数func(x, id)找到x的最小公因数在mp中对应的下标。如果找到的pos不为0且小于i，更新i为pos，并将j更新为当前数字的下标id。循环结束后，输出最小公因数对应的下标i和j。

/* 例子: 5 3 2 6 9
loop1: 新建 mp[5] = 1 (x = 5), pos = 0, i 不变, j 不变
loop2: 新建 mp[3] = 2 (x = 3), pos = 0, i 不变, j 不变
loop3: 新建 mp[2] = 3 (x = 2), pos = 0, i 不变, j 不变
loop4: 找到 mp[2] = 3 (x = 6 / 2 = 3), pos = 3
       找到 mp[3] = 2 (x = 3 / 3 = 1), pos = 2, i = 2, j = 4
loop5: 找到 mp[3] = 2 (x = 9 / 3 = 3), pos = 2, i 不变, j 不变
*/

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

map<int, int> mp;

int func(int x, int id) {
    int pos = 100000;
    for (int i = 2; i * i <= x; i++) {
        if (x % i) // 若 i 不是因数
            continue;
        while (x % i == 0)
            x /= i;
        if (mp.find(i) != mp.end() && mp[i] != id) {
            pos = min(pos, mp[i]);
        } else {
            mp.insert({i, id});
        }
    }
    if (x > 1) { // 若 x 是质数
        if (mp.find(x) != mp.end() && mp[x] != id) {
            pos = min(pos, mp[x]);
        } else {
            mp.insert({x, id});
        }
    }
    return pos < 100000 ? pos : 0;
}

int main() {
    int i = 100000, j;
    int n, x;
    cin >> n;
    for (int id = 1; id <= n; id++) {
        cin >> x;
        int pos = func(x, id); // 若存在 x 的因数有下标记录
        if (pos && pos < i) { // 更新下标
            i = pos;
            j = id;
        }
    }
    cout << i << " " << j;
    return 0;
}

3528 奇怪的数

【考点】动态规划和状态转移。
【解题思路】
1.首先，我们使用一个四维数组dp来表示动态规划的状态，dp[i][j][k][t]表示长度为i的奇怪数，满足条件的位数和为j，第一位数为k，第二位数为t的数量。
2.初始化阶段：对于位数为1的奇怪数，我们可以通过两个奇数构成，所以首先初始化边界情况，即长度为1的奇怪数的数量为1，且奇怪数的第一位取值范围为1到9，且位数和为m的范围也为1到9。
3.动态规划计算：从长度为2开始，通过状态转移方程计算满足条件的奇怪数的数量。具体地，我们使用五重循环来遍历所有可能的状态，其中第一重循环从2到n，表示奇怪数的长度。第二至五重循环从0到9，表示奇怪数每一位的取值范围。在每次更新dp[j][k][t][q]时，将dp[p][j][k][t]加到dp[j][k][t][q]上，并将结果取模，表示更新长度为i的奇怪数的状态数量。
4.计算最终答案：通过遍历长度为n时的奇怪数的最后两位的奇偶性、位数和的取值范围，将对应的状态数量加到结果变量res上，并将结果取模。最终，res就是满足条件的奇怪数的数量。

#include <iostream>
using namespace std;

const int N = 998244353;
long long dp[10][10][10][10], res = 0;

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m && i <= 9; i += 2) // 初始化边界情况
        for (int j = 0; j <= (m - i) && j <= 9; j += 2)
            for (int k = 1; k <= (m - i - j) && k <= 9; k += 2)
                for (int t = 0; t <= (m - i - j - k) && t <= 9; t += 2)
                    dp[i][j][k][t] = 1;
    for (int i = 5; i <= n; i++) { // 动态规划计算满足条件的奇怪数的数量
        for (int j = (i + 1) % 2; j <= 9 && j <= m; j += 2) {
            for (int k = i % 2; k <= 9 && k <= (m - j); k += 2) {
                for (int t = (i + 1) % 2; t <= 9 && t <= (m - j - k); t += 2) {
                    for (int p = i % 2; p <= (m - j - k - t) && p <= 9; p += 2) {
                        for (int q = i % 2; q <= (m - j - k - t - p) && q <= 9; q += 2) {
                            dp[j][k][t][q] += dp[p][j][k][t]; // 更新状态转移方程
                            dp[j][k][t][q] %= N;
                        }
                        dp[p][j][k][t] = 0; // 清空临时状态
                    }
                }
            }
        }
    }
    for (int j = (n + 1) % 2; j <= 9 && j <= m; j += 2) { // 循环计算答案
        for (int k = n % 2; k <= 9 && k <= m - j; k += 2) {
            for (int t = (n + 1) % 2; t <= 9 && t <= m - j - k; t += 2) {
                for (int q = n % 2; q <= m - j - k - t && q <= 9; q += 2) {
                    res += dp[j][k][t][q]; // 计算答案
                    res %= N;
                }
            }
        }
    }
    cout << res;
    return 0;
}

3529 太阳

【考点】排序、集合以及扫描线算法。
【解题思路】
1.结构体的运算符重载：结构体node中重载了小于号运算符和等于号运算符，用于在排序和判断相等时比较结构体对象的大小。
2.排序：代码中使用了sort函数对结构体向量v进行排序，排序的依据是结构体node中定义的小于号运算符重载。
3.使用集合：代码中使用了set容器来维护一组点的信息，set中存储了一对整数(y, i)，其中y表示点的纵坐标，i表示点的编号。通过set容器的自动排序特性，可以方便地维护点的信息。
4.扫描线算法：代码中使用了扫描线算法来解决问题。通过对所有矩形的边界进行排序，然后按照扫描线的方式从上到下依次处理每个边界，同时使用集合来维护当前扫描线上的所有矩形的信息。当扫描线遇到一个矩形的左边界时，将该矩形加入集合；当扫描线遇到一个矩形的右边界时，将该矩形从集合中移除。在扫描线过程中，通过判断集合中是否有元素，可以确定当前扫描线上是否有被覆盖的区域，从而计算出被覆盖的总面积。

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

struct node {
    int x, y, i;
    node(int x, int y, int i) : x(x), y(y), i(i) {}
    bool operator < (node t) {
        return 1LL * t.y * x < 1LL * y * t.x;
    }
    bool operator == (node t) {
        return 1LL * t.y * x == 1LL * y * t.x;
    }
};

int main() {
    int n, X, Y;
    cin >> n >> X >> Y;
    vector<node> v;
    vector<bool> vis(n + 1);
    for (int i = 1; i <= n; i++) {
        int x, y, l;
        cin >> x >> y >> l;
        v.emplace_back(x - X, Y - y, i);
        v.emplace_back(x + l - X, Y - y, -i);
    }
    sort(v.begin(), v.end());
    typedef pair<int, int> pii;
    set<pii> st;
    auto last = node(-1, 1, 0);
    for (auto t : v) {
        if (!(t == last)) {
            if (!st.empty()) vis[st.begin()->second] = true;
            last = t;
        }
        if (t.i > 0) st.emplace(t.y, t.i);
        else st.erase(make_pair(t.y, -t.i));
    }
    int ans = 0;
    for (bool t : vis) ans += t;
    cout << ans;
    return 0;
}

3526 子树的大小

【考点】数学递推和循环来计算子树的节点数量。
【解题思路】
1.使用循环来不断计算子树的节点数量，直到超过整棵树的节点数量n。初始化变量res为1，表示根节点的数量。
2.使用变量L和R表示当前子树的左右节点编号范围，初始值都为k。在循环中，通过递推公式计算下一层子树的左右节点范围，并更新L和R。
3.如果当前子树的右节点编号R不超过整棵树的节点数量n，则直接将当前子树的节点数量加到res中。
4.如果当前子树的右节点编号R超过整棵树的节点数量n，则只加上n与当前子树左节点范围的差值，然后跳出循环。

#include <iostream>
using namespace std;

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    long long res = 1, L = k, R = k;
    while(1) {
        L = (L - 1) * m + 2;
        R = R * m + 1;
        if (L > n) break;
        if (R <= n) {
            res += R - L + 1;
        } else {
            res += n - L + 1;
            break;
        }
    }
    cout << res << endl;
}

int main() {
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

3530 高塔

【考点】取模运算和逆元的计算。
【解题思路】
1.div(ll x) 函数：该函数实现了对 x 求模 MOD 的逆元，即 x 的模 MOD 的乘法逆元。此处使用了扩展的欧几里得算法求解逆元。
2.C(ll u, ll v) 函数：该函数计算组合数 C(u, v) 的值，即从 u 个元素中选取 v 个元素的组合数。计算过程分为两个部分：
第一个 for 循环用于计算 u! / (u - v)!，采用逐个相乘的方式计算并对 MOD 取模。
第二个 for 循环用于计算 v! 的乘法逆元，即计算 v! 的模 MOD 的逆元，再将结果乘到答案中。这里使用了之前定义的 div(ll x) 函数。
3.Lucas(ll n, ll m, ll p = MOD) 函数：该函数使用了 Lucas 定理求解 C(n, m) % MOD 的值。Lucas 定理是组合数学中的一个定理，用于计算大数模 MOD 的组合数。
4.main() 函数：主函数负责程序的读入和输出。计算数组 ma，ma[i] 表示从 a[1] 到 a[i] 的乘积并对 MOD 取模。
初始化一些变量，包括 ans（答案）和临时变量 tmp、qq。进行循环计算，每次计算折线上第 i 个点的贡献并更新答案。具体计算方式涉及乘法、加法和取模运算。
最后加上 C(m + n, 2 * n) % MOD * ma[n] % MOD 的结果，得到最终答案。

#include <iostream>
using namespace std;

typedef long long ll;
const ll MOD = 998244353;
const int N = 200000 + 50;

ll div(ll x) {
    ll mul = 1, b = MOD - 2;
    x %= MOD;
    while (b) {
        if (b & 1) mul = mul * x % MOD;
        x = x * x % MOD;
        b >>= 1;
    }
    return mul;
}

ll C(ll u, ll v) {
    ll ans = 1;
    for (ll i = u; i > u - v; i--)
        ans = ans * (i % MOD) % MOD;
    for (ll i = 0; i < v; i++)
        ans = ans * div(i + 1) % MOD;
    return ans;
}

ll Lucas(ll n, ll m, ll p = MOD) {
    if (!m) return 1;
    return (C(n % p, m % p) * Lucas(n / p, m / p, p)) % p;
}

int main() {
    ll n, m, ans = 0, a[N], ma[N];
    cin >> n >> m;
    for (ll i = 1; i <= n; i++)
        cin >> a[i];
    ma[0] = 1;
    for (ll i = 1; i <= n; i++)
        ma[i] = ma[i - 1] * a[i] % MOD;
    ll tmp = m % MOD;
    ll qq = (m % MOD) * (m % MOD) % MOD;
    for (ll i = 1; i < n; i++) {
        ans = (ans + ma[i] * tmp) % MOD;
        tmp = tmp * ((qq + MOD * 50 - i * i) % MOD) % MOD;
        tmp = tmp * (div(4 * i * i + 2 * i)) % MOD;
    }
    ans += Lucas(m + n, 2 * n) % MOD * ma[n] % MOD;
    cout << ans % MOD;
}

5003 反异或01串

【考点】回文串和马拉车算法。
【解题思路】
1.首先定义了一个函数count，这个函数用来统计字符串中1的个数。它通过遍历字符串，如果字符为'1'，则计数器cnt加一。
2.定义了一个函数Manacher，用来寻找字符串的最长回文子串。这里使用了马拉车算法（Manacher's Algorithm）来实现。算法的核心思想是在字符串每个字符的前后都插入一个特殊字符（这里使用'#'），以处理奇数和偶数长度的回文串。然后遍历字符串，维护一个回文半径数组p，p[i]表示以str[i]为中心的回文串的半径长度。遍历过程中不断更新最右边界mx和对应的回文中心id，以及记录最长回文子串的长度len和中心位置center。最后返回原字符串s中以center为中心、长度为len-1的子串。
3.在main函数中，首先读取输入的字符串s。然后通过调用count函数统计字符串中1的个数，并通过调用Manacher函数找到最长回文子串。最后，计算回文子串中1的个数减去回文子串中0的个数，并输出结果。

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

int count(string s) {
    int cnt = 0;
    for(char c : s)
        if(c == '1') cnt++;
    return cnt;
}

string Manacher(string s) {
    string str = "$#";
    for (char c : s)
        str += c, str += '#';
    int id = 0, mx = 0, len = 0, center = 0;
    vector<int> p(str.size(), 0);
    for (int i = 1; i < str.size(); i++) {
        p[i] = (mx > i) ? min(p[2 * id - i], mx - i) : 1;
        while (str[i + p[i]] == str[i - p[i]]) 
            p[i]++;
        if (i + p[i] > mx) 
            mx = i + p[i], id = i;
        if (p[i] > len)
            len = p[i], center = i;
    }
    return s.substr((center - len) / 2, len - 1);
}

int main() {
    string s;
    cin >> s;
    cout << count(s) - count(Manacher(s)) / 2;
    return 0;
}

Part_2 题目

试题A：小蓝与钥匙

#include <iostream>
using namespace std;

long long D(long long a) {
    if (a == 0 || a == 1)    return 0;
    if (a == 2)              return 1;
    return (a - 1) * (D(a - 1) + D(a - 2));
}

int main() {
    long long res = 1;
    for (int i = 0; i < 14; i++) {
        res = res * (28 - i) / (i + 1);
    }
    // 恰好有 14 个分到, 有 14 个没分到：
    // C(14 28) / A(14 14) * 错排列 (14)
    cout << res * D(14) << endl;
    return 0;
}

试题B：排列距离

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

map<char, int> mp; // 映射每个字母到其在排列中的位置
long long arr[20]; // 存储阶乘结果，用于计算排列的权值

long long work(string s) {
    long long ans = 0;
    int n = s.length();
    for (int i = 0; i < n; i++) {
        long long val = mp[s[i]]; // 当前字符的映射值
        for (int j = 0; j < i; j++) {
            if (s[j] < s[i])
                val--; // 统计在当前字符之前比它小的字符数
        }
        ans += val * arr[n - 1 - i]; // 加上当前字符的贡献值
    }
    return ans;
}

int main() {
    arr[0] = 1;
    // 计算阶乘结果
    for (int i = 1; i <= 17; i++) 
        arr[i] = arr[i - 1] * i;
    int cnt = 1;
    // 初始化字母映射
    for (char c : "abcdefghijklnopqr") 
        mp[c] = cnt++;
    // 计算排列 A 和排列 B 的权值
    long long a1 = work("aejcldbhpiogfqnkr");
    long long a2 = work("ncfjboqiealhkrpgd");
    // 输出排列 A 到排列 B 的最小转移次数
    cout << min(a2 - a1, arr[17] - a2 + a1) << endl;
    return 0;
}

试题C：近似GCD

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

int main() {
    int n, t;
    cin >> n >> t;
    vector<int> a(n + 1);       // 存储输入的数组元素
    vector<int> sum(n + 1, 0);  // 存储前缀和
    for (int i = 1; i <= n; i++) {
        cin >> a[i]; 
        if (a[i] % t != 0) sum[i]++;
    }
    for (int i = 1; i <= n; i++) 
        sum[i] += sum[i - 1];   // 计算前缀和
    long long cnt = 0;
    for (int i = 1; i <= n; i++) {
        int l = i, r = n;
        while (l < r) { // 二分查找满足条件的右边界
            int mid = (l + r + 1) / 2;
            sum[mid] - sum[i - 1] <= 1 ? l = mid : r = mid - 1; // 更新左右指针
        }
        cnt += l - i; // 统计满足条件的子数组数量
    }
    cout << cnt << endl;
    return 0;
}

试题D：交通信号

#include <bits/stdc++.h>
using namespace std;

struct edge {
    int v, g, r, y; // 目标节点v，绿灯时间g，红灯时间r，黄灯时间y
};

struct dis {
    int u;
    long long d; // 到达该节点的时间
    bool operator < (dis d1) const {
        return d1.d < d; // 重载比较运算符，用于小顶堆的排序
    }
};

int n, m, s, t;
const int N = 1e5 + 10;
vector<edge> green[N], red[N]; // 正向的绿灯边和反向的红灯边
vector<long long> f(N, LLONG_MAX); // 记录到达每个节点的最短时间，默认为无穷大

int main() {
    priority_queue<dis> q; // 使用小顶堆存储到达每个节点的最短时间
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; i++) {
        int u, v, g, r, d;
        cin >> u >> v >> g >> r >> d;
        green[u].push_back({v, g, r, d}); // 添加正向的绿灯边
        red[v].push_back({u, g, r, d}); // 添加反向的红灯边
    }
    q.push({0, s}); // 将起点加入小顶堆，距离为0
    f[s] = 0; // 起点到自身的最短时间为0
    while (!q.empty()) {
        auto [times, node] = q.top(); // 取出堆顶元素，即到达时间最短的节点
        q.pop(); // 弹出堆顶元素
        for (auto& e : green[node]) { // 遍历当前节点的正向绿灯边
            long long temp = f[node] % (1ll * e.g + e.y + 1ll * e.r + e.y); // 计算当前节点经过时间模拟交通灯周期后的剩余时间
            if (temp < e.g) { // 如果剩余时间小于绿灯时间
                if (f[e.v] > f[node] + e.y) { // 如果通过当前边到达目标节点的时间更短
                    f[e.v] = f[node] + e.y; // 更新到达目标节点的最短时间
                    q.push({f[e.v], e.v}); // 将更新后的最短时间和目标节点加入堆中
                }
            } else { // 如果剩余时间大于等于绿灯时间
                if (f[e.v] > f[node] + e.y + 1ll * e.g + e.y + 1ll * e.r + e.y - temp) { // 考虑等待绿灯的时间
                    f[e.v] = f[node] + e.y + 1ll * e.g + e.y + 1ll * e.r + e.y - temp; // 更新到达目标节点的最短时间
                    q.push({f[e.v], e.v}); // 将更新后的最短时间和目标节点加入堆中
                }
            }
        }
        for (auto& e : red[node]) { // 遍历当前节点的反向红灯边
            long long temp = f[node] % (1ll * e.g + e.y + 1ll * e.r + e.y); // 计算当前节点经过时间模拟交通灯周期后的剩余时间
            if (temp >= 1ll * e.g + e.y && temp <= 1ll * e.g + e.y + e.r) { // 如果剩余时间处于红灯时间段
                if (f[e.v] > f[node] + e.y) { // 如果通过当前边到达目标节点的时间更短
                    f[e.v] = f[node] + e.y; // 更新到达目标节点的最短时间
                    q.push({f[e.v], e.v}); // 将更新后的最短时间和目标节点加入堆中
                }
            } else if (temp < 1ll * e.g + e.y) { // 如果剩余时间处于绿灯时间段之前
                if (f[e.v] > f[node] + 1ll * e.y + e.g + e.y - temp) { // 考虑等待绿灯的时间
                    f[e.v] = f[node] + e.y + e.g + e.y - temp; // 更新到达目标节点的最短时间
                    q.push({f[e.v], e.v}); // 将更新后的最短时间和目标节点加入堆中
                }
            } else { // 如果剩余时间处于绿灯时间段之后
                if (f[e.v] > f[node] + 1ll * e.y + e.g + e.y + e.r + e.y - temp + e.g + e.y) { // 考虑等待绿灯和红灯的时间
                    f[e.v] = f[node] + e.y + e.g + e.y + e.r + e.y - temp + e.g + e.y; // 更新到达目标节点的最短时间
                    q.push({f[e.v], e.v}); // 将更新后的最短时间和目标节点加入堆中
                }
            }
        }
    }
    cout << (f[t] == numeric_limits<long long>::max() ? -1 : f[t]); // 输出到达终点的最短时间，如果不可达输出-1
    return 0;
}

试题E：六六大顺

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

vector<int> add(vector<int> A, vector<int> B) {
    vector<int> C;
    if (A.size() < B.size()) return add(B, A); // 确保A的长度不短于B
    int t = 0; // 进位
    for (int i = 0; i < A.size(); i++) {
        if (i < B.size()) t += B[i];
        t += A[i];
        C.push_back(t % 10); // 存储和的个位数
        t = t / 10; // 更新进位以供下一位使用
    }
    if (t) C.push_back(t); // 如果还有进位，加到结果中
    return C;
}

vector<int> sub(vector<int> A, vector<int> B) {
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i++) {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10); // 确保结果是非负数
        if (t >= 0) t = 0; // 如果t是正数，重置进位为0
        else t = 1; // 如果t是负数，设置进位为1以便借位
    }
    // 移除结果中的前导零
    while (C.size() > 1 && C.back() == 0) 
        C.pop_back();
    return C;
}

vector<int> mul(vector<int> A, int b) {
    vector<int> C;
    int t = 0; // 进位
    for (int i = 0; i < A.size() || t; i++) {
        if (i < A.size()) t += b * A[i];
        C.push_back(t % 10); // 存储乘积的个位数
        t = t / 10; // 更新进位以供下一位使用
    }
    return C;
}

vector<int> del(vector<int> A, int b) {
    vector<int> C;
    int r = 0; // 余数
    for (int i = A.size() - 1; i >= 0; i--) {
        r = r * 10 + A[i];
        C.push_back(r / b); // 存储除法的结果
        r = r % b; // 更新余数以供下一次除法使用
    }
    reverse(C.begin(), C.end());
    // 移除结果中的前导零
    while (C.size() > 1 && C.back() == 0) 
        C.pop_back();
    return C;
}

int main() {
    int n;
    cin >> n;
    vector<int> A, B, C, N;
    A.push_back(0);
    B.push_back(0);
    for (int i = 1; i <= n; i++) {
        A.push_back(0);
        A.push_back(1);
        B.push_back(2);
    }
    int x = n;
    while (x) {
        N.push_back(x % 10);
        x = x / 10;
    }
    C = del(mul(sub(add(A, N), B), 4), 9);
    for (int i = C.size() - 1; i >= 0; i--)
        cout << C[i];
    return 0;
}

试题F：owo

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

vector<bool> st; // 用于记录字符串是否已经被选取

int count(string ss) {
    int l = ss.find("owo"), res = 0;
    while (l != string::npos) {
        res++;
        l = ss.find("owo", l + 1);
    }
    return res;
}

void dfs(int cnt, int oc, string p, int fron, vector<string>& s, int& res) {
    if (cnt == fron) { // 如果已经选取了所有字符串
        res = max(res, oc); // 更新最优解
        return;
    }
    for (int i = 0; i < fron; ++i) {
        if (st[i]) continue; // 如果字符串已经被选取，则跳过
        st[i] = true; // 标记字符串为已选取
        string pp = p + s[i]; // 将当前字符串加入拼接字符串中
        string t = pp.length() <= 1 ? 
        pp : string(1, pp[pp.length() - 2]) + pp.back(); // 拼接字符串
        dfs(cnt + 1, oc + count(pp), t, fron, s, res); 
        st[i] = false; // 回溯，标记字符串为未选取
    }
}

int main() {
    int n;
    cin >> n;
    vector<string> s(n);
    for (int i = 0; i < n; i++) cin >> s[i];
    for (int i = 1; i <= n; i++) { 
        st.assign(n, false); // 初始化标记数组
        int res = 0;
        dfs(0, 0, "", i, s, res);
        cout << res << endl;
    }
    return 0;
}

试题G：最少的1

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

int main() {
    int n;
    cin >> n;
    vector<int> dp(n + 1);
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        int prev = i / 2;
        // i为偶数，则二进制中1的个数与i/2相同
        if (i % 2 == 0) dp[i] = dp[prev];
        // i为奇数，则二进制中1的个数比i/2多1
        else dp[i] = dp[prev] + 1;
    }
    cout << dp[n] << endl;
    return 0;
}

试题H：选素数

#include <iostream>
using namespace std;

bool isPrime(int x) {
    for(int i = 2; i * i <= x; i++)
        if(x % i == 0)
            return false;
    return true;
}

int find(int x) {
    int cnt = 2, p = 10e+6;
    while(!isPrime(p)){
        if(x % cnt) cnt++;
        p = x / cnt++;
    }
    return x - p + 1;
}

int main() {
    int x;
    cin >> x; 
    if(isPrime(x)){
        cout << -1;
        return 0;
    }
    int res = 10e+6;
    for(int x2 = find(x); x2 <= x; x2++)
        if(!isPrime(x2)) // 更新初始值
            res = min(res, find(x2)); 
    cout << res;
    return 0;
}

试题I：好等差数列

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

int res(vector<int>& nums) {
    int n = nums.size(); 
    // 存储相邻元素之间的差值及其出现次数
    unordered_map<int, int> diffCount;
    // 遍历数组，计算相邻元素之间的差值，并统计其出现次数
    for (int i = 1; i < n; ++i) {
        int diff = nums[i] - nums[i - 1];
        diffCount[diff]++;
    }
    int minChanges = INT_MAX;
    // 遍历相邻元素差值及其出现次数
    for (auto& it : diffCount) {
        int targetDiff = it.first; // 目标公差
        int changes = 0; // 当前公差需要修改的次数
        int expected = nums[0]; // 期望的下一个元素
        for (int i = 1; i < n; ++i) {
            expected += targetDiff; // 计算期望的下一个元素值
            if (nums[i] != expected) // 若当前元素不等于期望值
                changes++;
        }
        minChanges = min(minChanges, changes); // 更新最小修改次数
    }
    return minChanges;
}

int main() {
    int n, m, j, x;
    cin >> n;
    vector<int> arr(n);
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    cin >> m;
    vector<int> Res(m);
    for(int i = 0; i < m; i++) {
        cin >> j >> x;
        arr[j] = x;
        Res[i] = res(arr);
    }
    for(int o : Res) 
        cout << o << " ";
    return 0;
}

试题J：分石头

#include <iostream>
#include <unordered_set>
#include <cstring>
using namespace std;

const int M = 1e6 + 10;
int n, cnt, f[M], primes[M], st[M];

// 获取小于等于n的所有质数
void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i])
            primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)
                break;
        }
    }
}

// 计算Nim游戏的斐波那契值
int sg(int x) {
    int &v = f[x];
    if (v != -1) return v;
    unordered_set<int> S;
    for (int i = 0; i < cnt && primes[i] <= x; i++) {
        if (x % primes[i] == 0) {
            int w = x / primes[i];
            if (primes[i] % 2)
                S.insert(sg(w));
        }
    }
    S.insert(0);
    for (int i = 0;; i++)
        if (!S.count(i))
            return v = i;
}

int main() {
    memset(f, -1, sizeof(f)); // 初始化斐波那契值数组为-1
    get_primes(M);
    string Res;
    int T;
    cin >> T;
    while (T--) {
        int res = 0;
        cin >> n; // 输入堆数
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            res ^= sg(x); // 计算每一堆石子的斐波那契值并异或
        }
        if (res) Res.push_back('1'); // 判断是否存在必胜策略
        else Res.push_back('0');
    }
    for(char c : Res)
        cout << c << endl; // 输出结果
    return 0;
}