模拟算法详解：竞赛常用题型与代码实现

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

int main() {
    vector<vector<int>> vec(7, vector<int>(7, 0));
    for (int i = 0; i < 7; ++i) {
        string str;
        cin >> str;
        if (str.size() == 3) {
            for (int j = 0; j < 3; ++j) {
                vec[i][j + 2] = str[j] - '0';
            }
        } else {
            for (int j = 0; j < 7; ++j) {
                vec[i][j] = str[j] - '0';
            }
        }
    }
    bool flag = true;
    for (int i = 1; i < 6; ++i) {
        for (int j = 1; j < 6; ++j) {
            if (vec[i][j] == 1) {
                if (vec[i][j - 1] == 1 || vec[i][j + 1] == 1 || vec[i - 1][j] == 1 || vec[i + 1][j] == 1) {
                    flag = false;
                }
            }
        }
    }
    if (flag) cout << "yes" << endl;
    else cout << "no" << endl;
    return 0;
}

2. 简简单单的暴力题

问题描述

有一个长为 n 的序列 a1,a2.....an 与一个特殊的数 k，ai 小于 k。

当一个序列（元素个数 size≥2）中有一个数 x 会等于其他数的总和 sum % k，即 sum % k == x，则说明此序列为好序列。

求在长度为 n 的序列中有多少连续的子序列为好序列。

输入格式

第一行包含两个数 n，k，表示序列长和特殊的数。 第二行包含 n 个小于 k 的非负整数。

输出格式

输出一个数 sum 为好序列个数。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] vec = new int[n];
        for (int i = 0; i < n; i++) {
            vec[i] = scanner.nextInt();
        }
        int num = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int sum = 0;
                for (int z = i; z <= j; z++) {
                    sum += vec[z];
                }
                for (int z = i; z <= j; z++) {
                    sum -= vec[z];
                    if (sum % k == vec[z]) {
                        num++;
                        break;
                    }
                    sum += vec[z];
                }
            }
        }
        System.out.println(num);
        scanner.close();
    }
}

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> vec(n, 0);
    for (int i = 0; i < n; ++i) cin >> vec[i];
    int num = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int sum = 0;
            for (int z = i; z <= j; ++z) sum += vec[z];
            for (int z = i; z <= j; ++z) {
                sum -= vec[z];
                if (sum % k == vec[z]) {
                    num++;
                    break;
                }
                sum += vec[z];
            }
        }
    }
    cout << num << endl;
    return 0;
}

3. 小浩的国际象棋

问题描述

小浩有一个大小为 N×N 的国际象棋棋盘。

有 N 个主教以之字形的形式放置在棋盘的矩阵上，坐标分别为 (1,1),(2,2),(1,3),(2,4),(1,5),…。

已知主教只能斜向移动且每次可以移动任意距离。

你的任务是找到最少的移动次数，满足对于所有 1≤i≤N，棋盘矩阵上的格子 (i,i) 都被主教占领了。

输入格式

第一行输入一个正整数 T 表示测试数据的组数。 接下来 T 行每行输入一个正整数 N 表示棋盘的大小。

输出格式

对于每组测试数据，输出一个整数表示满足题目要求所需要的最少的移动次数。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t > 0) {
            int l = scanner.nextInt();
            if (l <= 2) {
                System.out.println(0);
            } else if (l == 3) {
                System.out.println(2);
            } else if (l % 2 == 0) {
                System.out.println(2 + ((l - 3) / 2) * 3 + 1);
            } else {
                System.out.println(2 + ((l - 3) / 2) * 3);
            }
            t--;
        }
        scanner.close();
    }
}

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int l;
        cin >> l;
        if (l <= 2) cout << 0 << endl;
        else if (l == 3) cout << 2 << endl;
        else if (l % 2 == 0) cout << 2 + (l - 3) / 2 * 3 + 1 << endl;
        else cout << 2 + (l - 3) / 2 * 3 << endl;
    }
    return 0;
}

4. 缩位求和

题目描述

在电子计算机普及以前，人们经常用一个粗略的方法来验算四则运算是否正确。

比如：248×15=3720

把乘数和被乘数分别逐位求和，如果是多位数再逐位求和，直到是 1 位数。

请你写一个计算机程序，对给定的字符串逐位求和。

输入描述

输入为一个由数字组成的串，表示 n (n<1000) 位数。

输出描述

输出为一位数，表示反复逐位求和的结果。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        long num = 0;
        while (str.length() > 1) {
            for (int i = 0; i < str.length(); ++i) {
                num += str.charAt(i) - '0';
            }
            str = String.valueOf(num);
            num = 0;
        }
        System.out.println(str);
        scanner.close();
    }
}

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

int main() {
    string str;
    cin >> str;
    long long num = 0;
    while (str.size() > 1) {
        for (int i = 0; i < str.size(); ++i) {
            num += str[i] - '0';
        }
        str = to_string(num);
        num = 0;
    }
    cout << str << endl;
    return 0;
}

5. Goshopping

问题描述

最近 Awell 的运气特别好，他在路边摊买彩票，居然中了大奖。秉着见者有份的原则，他准备请咱们学校 ACM-ICPC 训练基地的全体队员逛商场。

赶巧交大旁边有一家商场新店开张，正在进行打折促销活动。于是，咱们所有队员都在商场中大肆购买之后，在收银台前排起了长队。

话说回来，这家商场的打折方式有些奇怪：他们从在收银台前付账的所有 n 位顾客中，所有的第 m 的倍数名顾客享受七五折优惠，其余顾客只能享受九五折。

为了区分他们，我们规定，所有 ACM 队员必须在姓名前加上前缀 ACM。

现在，请机智的你为 Awell 编写一个小程序，算一算他总共需要花费多少钱呢？

输入格式

输入数据包含不超过 5 组，每组第一行有两个整数 n,m(1≤n,m≤1000)，分别代表着在收银台前队伍的全部人数，以及商家将会选择每第 m 位顾客打 7.5 折。

接下来有 n 行，每行将会输入消费者的姓名（长度不超过 20 个字符），以及他们各自消费的金额（消费金额不超过 1000）。

输出格式

每组数据输出一行，每行一个实数，表示 Awell 总共需要花费多少。

你应该注意的是，老板只收取'角'作为最小单位，而且他是一个锱铢必较的人，所以，如果你所付金额中存在小于 0.1 元的部分，那就至少要付 0.1 元给他。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            String str;
            double all_money = 0;
            double money;
            for (int i = 0; i < n; ++i) {
                str = scanner.next();
                money = scanner.nextDouble();
                str = str.substring(0, Math.min(3, str.length()));
                if ((i + 1) % m == 0 && str.equals("ACM")) {
                    all_money += money * 0.75;
                } else if (str.equals("ACM")) {
                    all_money += money * 0.95;
                }
            }
            System.out.printf("%.1f\n", all_money + 0.049999);
        }
        scanner.close();
    }
}

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

int main() {
    int n, m;
    while (cin >> n >> m) {
        string str;
        double all_money = 0;
        double money;
        for (int i = 0; i < n; ++i) {
            cin >> str >> money;
            if (str.length() >= 3) str = str.substr(0, 3);
            if ((i + 1) % m == 0 && str == "ACM") {
                all_money += money * 0.75;
            } else if (str == "ACM") {
                all_money += money * 0.95;
            }
        }
        printf("%.1f\n", all_money + 0.05);
    }
    return 0;
}

基础

6. 交换瓶子

题目描述

有 N 个瓶子，编号 1 ~ N，放在架子上。

比如有 5 个瓶子：2 1 3 5 4

要求每次拿起 2 个瓶子，交换它们的位置。

经过若干次后，使得瓶子的序号为：1 2 3 4 5

对于这么简单的情况，显然，至少需要交换 2 次就可以复位。

如果瓶子更多呢？你可以通过编程来解决。

输入描述

第一行：一个正整数 N (N<10^4)，表示瓶子的数目 第二行：N 个正整数，用空格分开，表示瓶子目前的排列情况。

输出描述

输出数据为一行一个正整数，表示至少交换多少次，才能完成排序。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] vec = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            vec[i] = scanner.nextInt();
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            int j = i;
            if (vec[j] != i) {
                while (vec[j] != i) {
                    j++;
                }
                int temp = vec[j];
                vec[j] = vec[i];
                vec[i] = temp;
                ans++;
            }
        }
        System.out.println(ans);
        scanner.close();
    }
}

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

int main() {
    int n;
    cin >> n;
    vector<int> vec(n + 1, 0);
    for (int i = 1; i <= n; ++i) cin >> vec[i];
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        int j = i;
        if (vec[j] != i) {
            while (vec[j] != i) {
                j++;
            }
            vec[j] = vec[i];
            vec[i] = i;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

7. 奇怪的数列

题目描述

从 X 星截获一份电码，是一些数字，如下：

13

1113

3113

132113

1113122113

...

YY 博士经彻夜研究，发现了规律：

第一行的数字随便是什么，以后每一行都是对上一行"读出来"

比如第 2 行，是对第 1 行的描述，意思是：1 个 1，1 个 3，所以是：1113

第 3 行，意思是：3 个 1,1 个 3，所以是：3113

请你编写一个程序，可以从初始数字开始，连续进行这样的变换。

输入描述

第一行输入一个数字组成的串，不超过 100 位。 第二行，一个数字 n，表示需要你连续变换多少次，n 不超过 20。

输出描述

输出一个串，表示最后一次变换完的结果。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str1 = scanner.next();
        int t = scanner.nextInt();
        scanner.close();
        while (t-- > 0) {
            int num = 1;
            char c = str1.charAt(0);
            StringBuilder str2 = new StringBuilder();
            for (int i = 1; i < str1.length(); i++) {
                if (c != str1.charAt(i)) {
                    str2.append(num).append(c);
                    num = 1;
                    c = str1.charAt(i);
                } else {
                    num++;
                }
            }
            str2.append(num).append(c);
            str1 = str2.toString();
        }
        System.out.println(str1);
    }
}

#include <iostream>
using namespace std;

int main() {
    int t;
    string str1;
    cin >> str1 >> t;
    while (t--) {
        int num = 1;
        char c = str1[0];
        string str2 = "";
        for (int i = 1; i < str1.size(); ++i) {
            if (c != str1[i]) {
                str2 += to_string(num) + c;
                num = 1;
                c = str1[i];
            } else {
                num++;
            }
        }
        str2 += to_string(num) + c;
        str1 = str2;
    }
    cout << str1 << endl;
    return 0;
}

8. 长草

题目描述

小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。

小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。

这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，这四小块空地都将变为有草的小块。请告诉小明，k 个月后空地上哪些地方有草。

输入描述

输入的第一行包含两个整数 n,m。 接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 g，表示种了草。 接下来包含一个整数 k。其中，2≤n,m≤1000，1≤k≤1000。

输出描述

输出 n 行，每行包含 m 个字母，表示 k 个月后空地的状态。如果为小数点，表示为空地，如果字母为 g，表示长了草。

import java.util.Scanner;

public class GrassGrowthSimulation {
    static int[][] a = new int[1005][1005];
    static int[][] b = new int[1005][1005];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        scanner.nextLine();
        for (int i = 0; i < n; i++) {
            String str = scanner.nextLine();
            for (int j = 0; j < m; j++) {
                if (str.charAt(j) == '.') a[i][j] = 0;
                else a[i][j] = 1;
            }
        }
        int k = scanner.nextInt();
        scanner.close();
        while (k-- > 0) {
            dfs(n, m);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i][j] == 0) System.out.print(".");
                else System.out.print("g");
            }
            System.out.println();
        }
    }

    public static void dfs(int n, int m) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                b[i][j] = a[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (b[i][j] == 1) {
                    if (i >= 1) a[i - 1][j] = 1;
                    if (i < n - 1) a[i + 1][j] = 1;
                    if (j >= 1) a[i][j - 1] = 1;
                    if (j < m - 1) a[i][j + 1] = 1;
                }
            }
        }
    }
}

#include <iostream>
using namespace std;

int a[1005][1005], b[1005][1005];

void dfs(int n, int m) {
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            b[i][j] = a[i][j];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (b[i][j] == 1) {
                if (i >= 1) a[i - 1][j] = 1;
                if (i < n - 1) a[i + 1][j] = 1;
                if (j >= 1) a[i][j - 1] = 1;
                if (j < m - 1) a[i][j + 1] = 1;
            }
        }
    }
}

int main() {
    int n, m, k;
    cin >> n >> m;
    string str;
    for (int i = 0; i < n; ++i) {
        cin >> str;
        for (int j = 0; j < m; ++j) {
            if (str[j] == '.') a[i][j] = 0;
            else a[i][j] = 1;
        }
    }
    cin >> k;
    while (k--) {
        dfs(n, m);
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (a[i][j] == 0) cout << ".";
            else cout << "g";
        }
        cout << endl;
    }
    return 0;
}

日期系列

9. 跑步

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

问题描述

小蓝每周六、周日都晨跑，每月的 1、11、21、31 日也晨跑。其它时间不晨跑。

已知 2022 年 1 月 1 日是周六，请问小蓝整个 2022 年晨跑多少天？

public class Main {
    public static void main(String[] args) {
        int day = 2;
        int flag = 0;
        int[] monthDay = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        for (int i = 0; i < monthDay.length; i++) {
            for (int j = 0; j < monthDay[i]; j++) {
                if (i == 0 && (j == 1 || j == 2)) continue;
                flag++;
                if (flag % 6 == 0 || flag % 7 == 0 || j + 1 == 11 || j + 1 == 1 || j + 1 == 21 || j + 1 == 31) {
                    day++;
                }
            }
        }
        System.out.println(day);
    }
}

#include <iostream>
using namespace std;

int main() {
    int day = 2;
    int flag = 0;
    int monthDay[] = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    for (int i = 0; i < sizeof(monthDay) / sizeof(monthDay[0]); ++i) {
        for (int j = 0; j < monthDay[i]; ++j) {
            if (i == 0 && (j == 1 || j == 2)) continue;
            flag++;
            if (flag % 6 == 0 || flag % 7 == 0 || j + 1 == 11 || j + 1 == 1 || j + 1 == 21 || j + 1 == 31) day++;
        }
    }
    cout << day << endl;
    return 0;
}

10. 跑步计划

问题描述

小蓝计划在某天的日期中出现 1 时跑 5 千米，否则只跑 1 千米。注意日期中出现 1 不仅指年月日也指星期。

请问按照小蓝的计划，2023 年小蓝总共会跑步锻炼多少千米？例如，5 月 1 日、11 月 13 日、11 月 5 日、4 月 3 日 (星期一) 小蓝会跑 5 千米，而 5 月 23 日小蓝会跑 1 千米。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int s = 0;
        int[] monthDay = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        int flag = 0;
        for (int i = 0; i < monthDay.length; i++) {
            for (int j = 0; j < monthDay[i]; j++) {
                flag++;
                if (i + 1 == 1 || i + 1 >= 10) {
                    s += 5;
                } else if (j + 1 == 1 || (10 <= j + 1 && j + 1 <= 19) || j + 1 == 21 || j + 1 == 31) {
                    s += 5;
                } else if (flag % 7 == 2) {
                    s += 5;
                } else {
                    s++;
                }
            }
        }
        System.out.println(s);
    }
}

#include <iostream>
using namespace std;

int main() {
    int s = 0;
    int monthDay[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int flag = 0;
    for (int i = 0; i < sizeof(monthDay) / sizeof(monthDay[0]); ++i) {
        for (int j = 0; j < monthDay[i]; ++j) {
            flag++;
            if (i + 1 == 1 || i + 1 >= 10) s += 5;
            else if (j + 1 == 1 || (10 <= j + 1 && j + 1 <= 19) || j + 1 == 21 || j + 1 == 31) s += 5;
            else if (flag % 7 == 2) s += 5;
            else s++;
        }
    }
    cout << s << endl;
    return 0;
}

11. 定时任务

问题描述

Cron 表达式在定时任务中经常被使用，在这里我们用了一种简化后的版本 SimpleCron 表达式：SimpleCron 表达式是一个具有时间含义的字符串，字符串以 4 个空格隔开，分为 5 个域，格式为 XXXXXXXXXX，其中 XX 是一个域的占位符。5 个域从左至右依次为秒 (0−59)、分钟 (0−59)、小时 (0−23)、日期 (1−31)、月份 (1−12)。

特殊字符 * 表示所有可能的值。特殊字符 , 表示列出枚举值。特殊字符 - 表示范围。

现在给出你一个合法的 SimpleCron 表达式，其中用到的所有数字均没有前导零。请问在 2023 一整年当中，使用了这个表达式的定时任务总计会执行多少次？

输入格式

输入一行，包含一个 SimpleCron 字符串。

输出格式

输出一行，包含一个整数表示答案。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static List<Integer> generateNum(String str, int range) {
        List<Integer> res = new ArrayList<>();
        int cur = 0;
        int lis = -1;
        for (char c : str.toCharArray()) {
            if (c == ',') {
                res.add(cur);
                cur = 0;
            } else if (c == '-') {
                lis = cur;
                cur = 0;
            } else if (c == '*') {
                for (int i = 0; i < range; i++) res.add(i + 1);
                return res;
            } else {
                cur = cur * 10 + (c - '0');
            }
        }
        if (lis != -1) {
            for (int i = lis; i <= Math.min(range, cur); i++) res.add(i);
        } else {
            res.add(cur);
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] monthDay = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        String S = scanner.next();
        String M = scanner.next();
        String H = scanner.next();
        String D = scanner.next();
        String MON = scanner.next();
        int num1 = generateNum(S, 60).size() * generateNum(M, 60).size() * generateNum(H, 24).size();
        int num2 = 0;
        for (int i : generateNum(MON, 12)) {
            num2 += generateNum(D, monthDay[i - 1]).size() * num1;
        }
        System.out.println(num2);
        scanner.close();
    }
}

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

vector<int> generateNum(string str, int range) {
    vector<int> res;
    int cur = 0;
    int lis = -1;
    for (char c : str) {
        if (c == ',') {
            res.push_back(cur);
            cur = 0;
        } else if (c == '-') {
            lis = cur;
            cur = 0;
        } else if (c == '*') {
            for (int i = 0; i < range; i++) res.push_back(i + 1);
            return res;
        } else {
            cur = cur * 10 + c - '0';
        }
    }
    if (lis != -1) {
        for (int i = lis; i <= min(range, cur); ++i) res.push_back(i);
    } else {
        res.push_back(cur);
    }
    return res;
}

int main() {
    int monthDay[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    string S, M, H, D, MON;
    cin >> S >> M >> H >> D >> MON;
    int num1 = generateNum(S, 60).size() * generateNum(M, 60).size() * generateNum(H, 24).size();
    int num2 = 0;
    for (int i : generateNum(MON, 12)) {
        num2 += generateNum(D, monthDay[i - 1]).size() * num1;
    }
    cout << num2 << endl;
    return 0;
}

进阶

12. 赢球票

题目描述

某机构举办球票大奖赛。获奖选手有机会赢得若干张球票。

主持人拿出 N 张卡片（上面写着 1⋯N 的数字），打乱顺序，排成一个圆圈。

你可以从任意一张卡片开始顺时针数数：1,2,3 ⋯⋯

如果数到的数字刚好和卡片上的数字相同，则把该卡片收入囊中，从下一个卡片重新数数。

直到再无法收获任何卡片，游戏结束。囊中卡片数字的和就是赢得球票的张数。

本题的目标：已知顺时针卡片序列，随便你从哪里开始数，求最多能赢多少张球票。

输入描述

第一行一个整数 N (N≤100)，表示卡片数目。 第二行 N 个整数，表示顺时针排列的卡片。

输出描述

输出一行，一个整数，表示最好情况下能赢得多少张球票。

import java.util.Scanner;
import java.util.Arrays;

public class CardGame {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] vec = new int[n];
        for (int i = 0; i < n; i++) {
            vec[i] = scanner.nextInt();
        }
        int flag = 0;
        for (int i = 0; i < n; i++) {
            boolean[] used = new boolean[n];
            int cur = 0;
            int index = i;
            int count = 1;
            int num = 0;
            while (true) {
                if (!used[index]) {
                    if (vec[index] == count) {
                        cur++;
                        num += count;
                        used[index] = true;
                        count = 1;
                    } else {
                        count++;
                    }
                }
                index = (index + 1) % n;
                if (count > n || cur == n) break;
            }
            flag = Math.max(num, flag);
        }
        System.out.println(flag);
        scanner.close();
    }
}

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

int main() {
    int n;
    cin >> n;
    vector<int> vec(n, 0);
    for (int i = 0; i < n; ++i) cin >> vec[i];
    int flag = 0;
    for (int i = 0; i < n; ++i) {
        vector<bool> used(n, false);
        int cur = 0;
        int index = i;
        int count = 1;
        int num = 0;
        while (1) {
            if (!used[index]) {
                if (vec[index] == count) {
                    cur++;
                    num += count;
                    used[index] = true;
                    count = 1;
                } else {
                    count++;
                }
            }
            index = (index + 1) % n;
            if (count > n || cur == n) break;
        }
        flag = max(num, flag);
    }
    cout << flag << endl;
    return 0;
}

13. 神奇闹钟

问题描述

小蓝发现了一个神奇的闹钟，从纪元时间（1970 年 1 月 1 日 00:00:00）开始，每经过 x 分钟，这个闹钟便会触发一次闹铃。

对于给出的任意一个格式为 yyyy-MM-dd HH:mm:ss 的时间，小蓝想要知道在这个时间点之前 (包含这个时间点) 的最近的一次闹铃时间是哪个时间？

输入格式

输入的第一行包含一个整数 T，表示每次输入包含 T 组数据。 接下来依次描述 T 组数据。 每组数据一行，包含一个时间和一个整数 x，其中 x 表示闹铃时间间隔（单位为分钟）。

输出格式

输出 T 行，每行包含一个时间，依次表示每组数据的答案。

import java.util.Scanner;

public class TimeCalculation {
    public static long generate(int year, int month, int day, int hour, int minute, int second, int sub) {
        int totalDays = 0;
        for (int y = 1970; y < year; y++) {
            if (isLeapYear(y)) totalDays += 366;
            else totalDays += 365;
        }
        for (int m = 1; m < month; m++) {
            totalDays += getDaysInMonth(m, year);
        }
        totalDays += (day - 1);
        return (long) totalDays * 24 * 60 + hour * 60 + minute;
    }

    public static boolean isLeapYear(int year) {
        return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
    }

    public static int getDaysInMonth(int month, int year) {
        switch (month) {
            case 1: case 3: case 5: case 7: case 8: case 10: case 12: return 31;
            case 4: case 6: case 9: case 11: return 30;
            case 2: return isLeapYear(year) ? 29 : 28;
            default: return 0;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        for (int i = 0; i < t; i++) {
            String date = scanner.next();
            String time = scanner.next();
            int sub = scanner.nextInt();
            String[] dateParts = date.split("-");
            int year = Integer.parseInt(dateParts[0]);
            int month = Integer.parseInt(dateParts[1]);
            int day = Integer.parseInt(dateParts[2]);
            String[] timeParts = time.split(":");
            int hour = Integer.parseInt(timeParts[0]);
            int minute = Integer.parseInt(timeParts[1]);
            int second = Integer.parseInt(timeParts[2]);
            long allMinutes = generate(year, month, day, hour, minute, second, sub);
            long adjustedMinutes = allMinutes - (allMinutes % sub);
            long totalDays = adjustedMinutes / (24 * 60);
            long hours = (adjustedMinutes / 60) % 24;
            long minutes = adjustedMinutes % 60;
            long currentYear = 1970;
            long currentMonth = 1;
            long currentDay = 1;
            while (totalDays >= 0) {
                int daysInYear = isLeapYear((int) currentYear) ? 366 : 365;
                if (totalDays < daysInYear) break;
                totalDays -= daysInYear;
                currentYear++;
            }
            while (totalDays > 0) {
                int daysInMonth = getDaysInMonth((int) currentMonth, (int) currentYear);
                if (totalDays < daysInMonth) break;
                totalDays -= daysInMonth;
                currentMonth++;
            }
            currentDay += totalDays;
            System.out.printf("%04d-%02d-%02d %02d:%02d:%02d\n", (int) currentYear, (int) currentMonth, (int) currentDay, (int) hours, (int) minutes, 0);
        }
        scanner.close();
    }
}

#include "bits/stdc++.h"
#define ll long long
using namespace std;

ll generate(int y, int M, int d, int h, int m, int s, int sub) {
    int D = 0;
    for (int i = 1970; i <= y - 1; ++i) {
        if ((i % 4 == 0 && i % 100 != 0) || i % 400 == 0) D += 366;
        else D += 365;
    }
    for (int i = 1; i <= M - 1; ++i) {
        if (i == 1 || i == 3 || i == 5 || i == 7 || i == 8 || i == 10 || i == 12) D += 31;
        else if (i == 2 && ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0)) D += 29;
        else if (i == 2) D += 28;
        else D += 30;
    }
    D += (d - 1);
    ll num = D * (24 * 60) + h * 60 + m;
    return num;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int y, M, d, h, m, s, sub;
        scanf("%d-%d-%d %d:%d:%d %d", &y, &M, &d, &h, &m, &s, &sub);
        ll all_min = generate(y, M, d, h, m, s, sub);
        ll acc_time = all_min - (all_min % sub);
        ll lday = acc_time / (24 * 60);
        ll lh = acc_time / 60 % 24;
        ll lm = acc_time % 60;
        ll YYYY = 1970, MM = 1, dd = 1, HH = lh, mm = lm, ss = 0;
        while (lday >= 0) {
            if ((YYYY % 4 == 0 && YYYY % 100 != 0) || YYYY % 400 == 0) {
                if (lday < 366) break;
                lday -= 366;
            } else {
                if (lday < 365) break;
                lday -= 365;
            }
            YYYY++;
        }
        while (lday > 0) {
            if (MM == 1 || MM == 3 || MM == 5 || MM == 7 || MM == 8 || MM == 10 || MM == 12) {
                if (lday < 31) break;
                lday -= 31;
            } else if (MM == 2 && ((YYYY % 4 == 0 && YYYY % 100 != 0) || YYYY % 400 == 0)) {
                if (lday < 29) break;
                lday -= 29;
            } else if (MM == 2) {
                if (lday < 28) break;
                lday -= 28;
            } else {
                if (lday < 30) break;
                lday -= 30;
            }
            MM++;
        }
        dd += lday;
        printf("%04lld-%02lld-%02lld %02lld:%02lld:%02lld\n", YYYY, MM, dd, HH, mm, ss);
    }
    return 0;
}

最后一题：拉马车

题目描述

小的时候，你玩过纸牌游戏吗？有一种叫做"拉马车"的游戏，规则很简单，却很吸引小朋友。

其规则简述如下：假设参加游戏的小朋友是 A 和 B，游戏开始的时候，他们得到的随机的纸牌序列如下：

A 方：[K,8,X,K,A,2,A,9,5,A] B 方：[2,7,K,5,J,5,Q,6,K,4]

其中的 X 表示 "10"，我们忽略了纸牌的花色。

从 A 方开始，A、B 双方轮流出牌。

当轮到某一方出牌时，他从自己的纸牌队列的头部拿走一张，放到桌上，并且压在最上面一张纸牌上（如果有的话）。

当轮到 B 出牌时，他的牌 K 与桌上的纸牌序列中的 K 相同，则把包括 K 在内的以及两个 K 之间的纸牌都赢回来，放入自己牌的队尾。注意：为了操作方便，放入牌的顺序是与桌上的顺序相反的。

赢牌的一方继续出牌。也就是 B 接着出 5，A 出 K，B 出 J，A 出 A，B 出 5，又赢牌了。

当某一方出掉手里最后一张牌，但无法从桌面上赢取牌时，游戏立即结束。

本题的任务就是已知双方初始牌序，计算游戏结束时，赢的一方手里的牌序。当游戏无法结束时，输出 -1。

输入描述

输入为 2 行，2 个串，分别表示 A、B 双方初始手里的牌序列。我们约定，输入的串的长度不超过 30。

输出描述

输出为 1 行，1 个串，表示 A 先出牌，最后赢的一方手里的牌序。

import java.util.*;

public class CardGameSimulation {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s_A = scanner.next();
        String s_B = scanner.next();
        scanner.close();
        Queue<Character> A = new LinkedList<>();
        Queue<Character> B = new LinkedList<>();
        Stack<Character> storage = new Stack<>();
        Set<Character> repeated = new HashSet<>();
        for (char c : s_A.toCharArray()) A.add(c);
        for (char c : s_B.toCharArray()) B.add(c);
        boolean game_over = false;
        int flag = 0;
        while (!A.isEmpty() && !B.isEmpty() && !game_over) {
            if (flag % 2 == 0) {
                char c = A.poll();
                if (!repeated.contains(c)) {
                    storage.push(c);
                    repeated.add(c);
                } else {
                    A.add(c);
                    get_storage(A, storage, repeated, c);
                    continue;
                }
            } else if (flag % 2 == 1) {
                char c = B.poll();
                if (!repeated.contains(c)) {
                    storage.push(c);
                    repeated.add(c);
                } else {
                    B.add(c);
                    get_storage(B, storage, repeated, c);
                    continue;
                }
            }
            flag++;
            if (flag >= 1000000) game_over = true;
        }
        if (game_over) {
            System.out.println(-1);
        } else if (!A.isEmpty()) {
            while (!A.isEmpty()) System.out.print(A.poll());
        } else if (!B.isEmpty()) {
            while (!B.isEmpty()) System.out.print(B.poll());
        }
    }

    public static void get_storage(Queue<Character> in_q, Stack<Character> out_s, Set<Character> se, char c1) {
        char c;
        do {
            c = out_s.pop();
            se.remove(c);
            in_q.add(c);
        } while (c != c1);
    }
}

#include <iostream>
#include <queue>
#include <stack>
#include <set>
using namespace std;

void get_storage(queue<char>& in_q, stack<char>& out_s, set<char>& se, char c1) {
    char c;
    do {
        c = out_s.top();
        out_s.pop();
        se.erase(c);
        in_q.push(c);
    } while (c != c1);
}

int main() {
    string s_A, s_B;
    cin >> s_A >> s_B;
    queue<char> A, B;
    stack<char> storage;
    set<char> repeated;
    for (char c : s_A) A.push(c);
    for (char c : s_B) B.push(c);
    bool game_over = false;
    int flag = 0;
    while (!A.empty() && !B.empty() && !game_over) {
        if (flag % 2 == 0) {
            char c = A.front();
            A.pop();
            if (repeated.find(c) == repeated.end()) {
                storage.push(c);
                repeated.insert(c);
            } else {
                A.push(c);
                get_storage(A, storage, repeated, c);
                continue;
            }
        } else if (flag % 2 == 1) {
            char c = B.front();
            B.pop();
            if (repeated.find(c) == repeated.end()) {
                storage.push(c);
                repeated.insert(c);
            } else {
                B.push(c);
                get_storage(B, storage, repeated, c);
                continue;
            }
        }
        flag++;
        if (flag >= 1e6) game_over = true;
    }
    if (game_over) cout << -1 << endl;
    else if (!A.empty()) {
        while (!A.empty()) {
            char c = A.front();
            A.pop();
            cout << c;
        }
    } else if (!B.empty()) {
        while (!B.empty()) {
            char c = B.front();
            B.pop();
            cout << c;
        }
    }
    return 0;
}