竞赛讨论区 > 【题解】牛客小白月赛 128
头像
Zaoly
编辑于 01-30 21:25 江苏
+ 关注

【题解】牛客小白月赛 128

感想

这是我第一次给牛客系列赛命题。

真没想到 E 题比 F 题还难！审题人审核 E 题的时候，怀疑它可能 “偏简单”；事实上，它竟然是全场最难的题目！我有点低估了某些题目的难度，以后会更加注意。

A 题出题灵感：创建过 QQ 群 “lCPC 昆明遨请赛”（现已解散），骗到了不少人。注意到，是 “lCPC” 而不是 “ICPC”，是 “遨请” 而不是 “邀请”。（不太冷的冷知识：我国机动车号牌不使用英文字母 “O” 和 “I”。）

C 题出题灵感：体育课时，老师让学生做准备运动，但又不喊 “一二三四五六七八” 的口令，让学生自己做。准备运动一般都是左 下、右 下。我做完了左 下，刚要做右 下时，老师突然喊了 “停”，这让我很难受。于是，我决定改变运动策略，从以前的 “左左左左左左左左，右右右右右右右右”，改成现在的 “左右，左右，左右，左右，左右，左右，左右，左右”。不管老师在什么时候喊停，我都能保证左边做过的动作次数与右边做过的动作次数尽量接近。换句话说，左边做过的动作次数与右边做过的动作次数之比尽量接近 。

此时，我又灵光一现：如果我希望左边做过的动作次数与右边做过的动作次数之比尽量接近 ，又该怎么做呢？于是就有了这道题。（赛前收到了管理员和内测人员的一些疑问，说为什么 是 的系数，而 是 的系数。这就是原因。）

另外，第一个样例 “12 3 2” 输出 “010100101001”，这意味着如果做 下动作，左 下，右 下，会得到结果 “左右左右左左右左右左左右”，正好与本题标题相似。但标题为了朗朗上口，加了个逗号。（其实应该分组为 “左右左右左，左右左右左，左右左右左……” 的来着……）

E 题出题灵感：原本要用另一道题的，奈何不小心跟其他平台的题目过于相似，临时搞出来的。

F 题出题灵感：在学校想的题，试着做了一下，发现解法还挺有趣。

A 模糊匹配

题解

本题有多种解法。

解法一：比较每两个字符是否 “相似”。其中，判断两个字符 “相似” 的方法为：如果两个字符完全相同，或者两个字符都在 “O” 和 “0” 中，或者两个字符都在 “I” “l” “1” 中，则两个字符相似。

解法二：将两个字符串中的所有字符 “0” 替换成 “O”，所有字符 “l” 和 “1” 替换成 “I”（或其他类似替换方法），再比较两个字符串是否相等。

代码

#include <iostream>
#include <string>

using namespace std;

bool is_O0(char c)
{
    return c == 'O' || c == '0';
}

bool is_Il1(char c)
{
    return c == 'I' || c == 'l' || c == '1';
}

bool char_similar(char a, char b)
{
    return a == b || is_O0(a) && is_O0(b) || is_Il1(a) && is_Il1(b);
}

bool similar(int n, const string& a, const string& b)
{
    for (int i = 0; i < n; ++i)
        if (!char_similar(a[i], b[i]))
            return false;
    return true;
}

void test_case()
{
    int n = 0;
    string s1, s2;
    cin >> n >> s1 >> s2;
    if (similar(n, s1, s2))
        cout << "YES";
    else
        cout << "NO";
    cout << '\n';
}

int main()
{
    int tests = 0;
    cin >> tests;
    while (tests > 0)
    {
        test_case();
        --tests;
    }
}

#include <stdio.h>

#define N 100

char s1[N + 1], s2[N + 1];

int is_O0(char c)
{
    return c == 'O' || c == '0';
}

int is_Il1(char c)
{
    return c == 'I' || c == 'l' || c == '1';
}

int char_similar(char a, char b)
{
    return a == b || is_O0(a) && is_O0(b) || is_Il1(a) && is_Il1(b);
}

int similar(int n, const char* a, const char* b)
{
    for (int i = 0; i < n; ++i)
        if (!char_similar(a[i], b[i]))
            return 0;
    return 1;
}

void test_case()
{
    int n = 0;
    scanf("%d%s%s", &n, s1, s2);
    if (similar(n, s1, s2))
        puts("YES");
    else
        puts("NO");
}

int main()
{
    int tests = 0;
    scanf("%d", &tests);
    while (tests > 0)
    {
        test_case();
        --tests;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    private static final Scanner sc = new Scanner(System.in);

    private static boolean is_O0(char c) {
        return c == 'O' || c == '0';
    }

    private static boolean is_Il1(char c) {
        return c == 'I' || c == 'l' || c == '1';
    }

    private static boolean charSimilar(char a, char b) {
        return a == b || is_O0(a) && is_O0(b) || is_Il1(a) && is_Il1(b);
    }

    private static boolean similar(int n, String a, String b) {
        for (int i = 0; i < n; ++i)
            if (!charSimilar(a.charAt(i), b.charAt(i)))
                return false;
        return true;
    }

    private static void testCase() {
        int n = sc.nextInt();
        String s1 = sc.next();
        String s2 = sc.next();
        if (similar(n, s1, s2))
            System.out.println("YES");
        else
            System.out.println("NO");
    }

    public static void main(String[] args) {
        int tests = sc.nextInt();
        while (tests > 0) {
            testCase();
            --tests;
        }
    }
}

def is_O0(c):
    return c == 'O' or c == '0'


def is_Il1(c):
    return c == 'I' or c == 'l' or c == '1'


def char_similar(a, b):
    return a == b or is_O0(a) and is_O0(b) or is_Il1(a) and is_Il1(b)


def similar(n, a, b):
    for i in range(n):
        if not char_similar(a[i], b[i]):
            return False
    return True


def test_case():
    n = int(input())
    s1 = input()
    s2 = input()
    if similar(n, s1, s2):
        print('YES')
    else:
        print('NO')


tests = int(input())
for _ in range(tests):
    test_case()

B 只留专一数

题解

要对数列 进行多次变换，每次变换从数列取不同位置的两个元素 和 ，删除之，再向数列添加元素 。需要判断当不能继续变换时，数列中仅有的元素是否为专一数。

观察可知，如果原数列中至少有一个专一数，就一定可以变换得到专一数；否则，就不可能变换得到专一数。这是因为，专一数的正整数次幂一定是专一数，而非专一数的正整数次幂一定不是专一数。于是，当数列中有一个专一数时，可以在每次变换中，从数列取一个专一数作为 ，从而形成的新数 一定是专一数；而当数列中没有专一数时，无论如何变换，都不可能形成新的专一数。

要判断一个正整数是否为专一数，只需对其质因数分解即可。由于数列元素值的范围较小，一些时间复杂度较劣的算法也可接受。

代码

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

using namespace std;

const int A_MAX = 1000;

bool faithful[A_MAX + 1];

void preprocess()
{
    for (int x = 1; x <= A_MAX; ++x)
    {
        int limit = 0;
        faithful[x] = true;
        limit = floor(sqrt(x));
        for (int d = 2; d <= limit; ++d)
        {
            int y = 0;
            if (x % d != 0)
                continue;
            y = x;
            while (y % d == 0)
                y /= d;
            if (y != 1)
                faithful[x] = false;
            break;
        }
    }
}

void test_case()
{
    int n = 0;
    bool exist = false;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < n; ++i)
        if (faithful[a[i]])
        {
            exist = true;
            break;
        }
    if (exist)
        cout << "YES";
    else
        cout << "NO";
    cout << '\n';
}

int main()
{
    int tests = 0;
    preprocess();
    cin >> tests;
    while (tests > 0)
    {
        test_case();
        --tests;
    }
}

#include <math.h>
#include <stdio.h>

#define N 200000
#define A_MAX 1000

int faithful[A_MAX + 1];
int a[N];

void preprocess()
{
    for (int x = 1; x <= A_MAX; ++x)
    {
        int limit = 0;
        faithful[x] = 1;
        limit = floor(sqrt(x));
        for (int d = 2; d <= limit; ++d)
        {
            int y = 0;
            if (x % d != 0)
                continue;
            y = x;
            while (y % d == 0)
                y /= d;
            if (y != 1)
                faithful[x] = 0;
            break;
        }
    }
}

void test_case()
{
    int n = 0, exist = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", a + i);
    for (int i = 0; i < n; ++i)
        if (faithful[a[i]])
        {
            exist = 1;
            break;
        }
    if (exist)
        puts("YES");
    else
        puts("NO");
}

int main()
{
    int tests = 0;
    preprocess();
    scanf("%d", &tests);
    while (tests > 0)
    {
        test_case();
        --tests;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    private static final Scanner sc = new Scanner(System.in);
    private static final int A_MAX = 1000;
    private static boolean[] faithful = new boolean[A_MAX + 1];

    private static void preprocess() {
        for (int x = 1; x <= A_MAX; ++x)
            faithful[x] = true;
        for (int x = 1; x <= A_MAX; ++x) {
            int limit = (int)Math.floor(Math.sqrt(x));
            for (int d = 2; d <= limit; ++d) {
                if (x % d != 0)
                    continue;
                int y = x;
                while (y % d == 0)
                    y /= d;
                if (y != 1)
                    faithful[x] = false;
                break;
            }
        }
    }

    private static void testCase() {
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i)
            a[i] = sc.nextInt();
        boolean exist = false;
        for (int i = 0; i < n; ++i)
            if (faithful[a[i]]) {
                exist = true;
                break;
            }
        if (exist)
            System.out.println("YES");
        else
            System.out.println("NO");
    }

    public static void main(String[] args) {
        preprocess();
        int tests = sc.nextInt();
        while (tests > 0) {
            testCase();
            --tests;
        }
    }
}

from math import isqrt


A_MAX = 1000
faithful = [True for _ in range(A_MAX + 1)]


def preprocess():
    for x in range(1, A_MAX + 1):
        for d in range(2, isqrt(x) + 1):
            if x % d != 0:
                continue
            y = x
            while y % d == 0:
                y //= d
            if y != 1:
                faithful[x] = False
            break


def test_case():
    n = int(input())
    a = list(map(int, input().split()))
    if any(faithful[x] for x in a):
        print('YES')
    else:
        print('NO')


preprocess()
tests = int(input())
for _ in range(tests):
    test_case()

C 左右左右左左右，左右左左右

题解

考虑一个数列 ，定义为

规定 。于是，。

显然，有递推关系如下：

  • 如果 ，那么 。
  • 如果 ，那么 。

可以使用贪心策略。假设字符串 的前 个字符已经选好，则有解法如下：

  • 如果 ，说明 时的 比 时的 更小，因此 选 。
  • 如果 ，说明 时的 比 时的 更大，因此 选 。
  • 如果 ，说明 时的 和 时的 相等，因此 可任选 或 。

按照以上步骤选完 个字符即可。

根据字典序的定义，前两条结论显然成立。但为什么第三条结论也成立呢？

如果 ，则因为数列已经比较完毕，所以 选 和选 等价。下面仅讨论 的情况。

  • 如果 ，则不论 取何值，数列 的每一个元素都为 ，因此 的每一个字符都可以任选。这符合第三条结论。
  • 如果 且 ，则 的每一个字符都只能选 ，此时数列 的每一个元素都为 。如果从任何一个元素 起改变策略，则 将变成 ，大于 。这种情况用不到第三条结论。
  • 如果 且 ，同理， 的每一个字符都只能选 。这种情况也用不到第三条结论。

下面仅讨论 且 的情况。

如果 ，那么 或 成立。但如果 ，则 ，与 “ 且 ” 矛盾，因此 ，因此 。

如果 选 ，则 。接下来考虑 的选择情况。如果 也选 ，则 ；如果 选 ，则 。可以证明，（证明留作习题）。因此， 只能选 。

用同样的方法也可以证明，当 选 时， 只能选 。

这意味着， 和 中，必有一个选 ，另一个选 ，两者的顺序不影响 和 ，因而不影响之后的选择。

这就说明，在 处任选 或 ，都可以得到最优解。至此，我们成功证明了第三条结论成立。

时间复杂度：每个测试用例 。

代码

#include <cstdlib>
#include <iostream>

using namespace std;

void test_case()
{
    int n = 0, sum = 0;
    int a[2]{};
    cin >> n >> a[0] >> a[1];
    for (int i = 0; i < n; ++i)
        if (abs(sum - a[1]) <= abs(sum + a[0]))
        {
            sum -= a[1];
            cout << '0';
        }
        else
        {
            sum += a[0];
            cout << '1';
        }
    cout << '\n';
}

int main()
{
    int tests = 0;
    cin >> tests;
    while (tests > 0)
    {
        test_case();
        --tests;
    }
}

#include <stdio.h>
#include <stdlib.h>

void test_case()
{
    int n = 0, sum = 0;
    int a[2] = {};
    scanf("%d%d%d", &n, a, a + 1);
    for (int i = 0; i < n; ++i)
        if (abs(sum - a[1]) <= abs(sum + a[0]))
        {
            sum -= a[1];
            putchar('0');
        }
        else
        {
            sum += a[0];
            putchar('1');
        }
    putchar('\n');
}

int main()
{
    int tests = 0;
    scanf("%d", &tests);
    while (tests > 0)
    {
        test_case();
        --tests;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    private static final Scanner sc = new Scanner(System.in);

    private static void testCase() {
        int n = sc.nextInt();
        int[] a = new int[]{sc.nextInt(), sc.nextInt()};
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            if (Math.abs(sum - a[1]) <= Math.abs(sum + a[0])) {
                sum -= a[1];
                System.out.print('0');
            } else {
                sum += a[0];
                System.out.print('1');
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int tests = sc.nextInt();
        while (tests > 0) {
            testCase();
            --tests;
        }
    }
}

def test_case():
    a = [0, 0]
    n, a[0], a[1] = map(int, input().split())
    s = 0
    for _ in range(n):
        if abs(s - a[1]) <= abs(s + a[0]):
            s -= a[1]
            print('0', end = '')
        else:
            s += a[0]
            print('1', end = '')
    print()


tests = int(input())
for _ in range(tests):
    test_case()

D 进退的艺术

题解

发生冲突时，若冲突缓解，则双方心情值都将加上自己的性格值；若冲突激化，则双方心情值都将减去对方的性格值。

暴力模拟法的时间复杂度为 ，无法通过本题。

我们先改一下题目，让每两个相同的人也发生一次冲突（即第 个人和第 个人也发生冲突）。此时我们发现，若记第 个人的心情值为 ，所有人中性格值不大于 的人数为 ，所有人中性格值大于 的人的性格值之和为 ，则

于是，只需求出 和 的值，就可以得到 了。但如何快速求出 和 的值呢？

首先，创建一个数列 ，初始化 （）。然后，给数列 排序，使得 。这一操作相当于把数列 带编号排序（可能有多种排序结果，任选一种即可）。

接下来，对于每个整数 （），在有序数列 中找出一个位置，这个位置之前的元素都不大于 ，之后的元素都大于 。于是，这个位置之前元素的个数就等于 ，之后的元素之和就等于 。可以用双指针法求出 和 的值（也可用二分查找法与后缀和数组）。

最后，别忘了把题目 “改回来”。对于每个整数 （），如果 ，说明 多加上了 的值，应减去 ；如果 ，说明 多减去了 的值，应加上 。

时间复杂度：每个测试用例 。

注意：输入的整数均未超出 位整数范围，但输出的整数可能超出这一范围，需要使用 位整数表示答案（如 C++ 的 long long）。

代码

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
using LL = long long;

void test_case()
{
    LL n = 0, m = 0, ptr = 0, sum = 0;
    cin >> n >> m;
    vector<LL> characters(n);
    for (LL i = 0; i < n; ++i)
        cin >> characters[i];
    vector<LL> order(n);
    for (LL i = 0; i < n; ++i)
        order[i] = i;
    sort(order.begin(), order.end(), [&characters](LL x, LL y) {
        if (characters[x] != characters[y])
            return characters[x] < characters[y];
        else
            return x < y;
    });
    ptr = n;
    vector<LL> moods(n);
    for (LL i = 0; i < n; ++i)
    {
        while (ptr > 0 && characters[order[ptr - 1]] > m - characters[order[i]])
        {
            --ptr;
            sum += characters[order[ptr]];
        }
        moods[order[i]] = characters[order[i]] * ptr - sum;
        if (characters[order[i]] * 2 <= m)
            moods[order[i]] -= characters[order[i]];
        else
            moods[order[i]] += characters[order[i]];
    }
    for (LL i = 0; i < n; ++i)
    {
        if (i > 0)
            cout << ' ';
        cout << moods[i];
    }
    cout << '\n';
}

int main()
{
    LL tests = 0;
    cin >> tests;
    while (tests > 0)
    {
        test_case();
        --tests;
    }
}

#include <stdio.h>
#include <stdlib.h>

#define N 200000LL

typedef long long LL;

LL characters[N], order[N], moods[N];

int character_compare(const void* x_ptr, const void* y_ptr)
{
    LL x = 0, y = 0;
    x = *(LL*)x_ptr;
    y = *(LL*)y_ptr;
    if (characters[x] < characters[y])
        return -1;
    else if (characters[x] > characters[y])
        return 1;
    else if (x < y)
        return -1;
    else if (x > y)
        return 1;
    else
        return 0;
}

void test_case()
{
    LL n = 0, m = 0, ptr = 0, sum = 0;
    scanf("%lld%lld", &n, &m);
    for (LL i = 0; i < n; ++i)
        scanf("%lld", characters + i);
    for (LL i = 0; i < n; ++i)
        order[i] = i;
    qsort(order, n, sizeof(LL), character_compare);
    ptr = n;
    for (LL i = 0; i < n; ++i)
    {
        while (ptr > 0 && characters[order[ptr - 1]] > m - characters[order[i]])
        {
            --ptr;
            sum += characters[order[ptr]];
        }
        moods[order[i]] = characters[order[i]] * ptr - sum;
        if (characters[order[i]] * 2 <= m)
            moods[order[i]] -= characters[order[i]];
        else
            moods[order[i]] += characters[order[i]];
    }
    for (LL i = 0; i < n; ++i)
    {
        if (i > 0)
            putchar(' ');
        printf("%lld", moods[i]);
    }
    putchar('\n');
}

int main()
{
    LL tests = 0;
    scanf("%lld", &tests);
    while (tests > 0)
    {
        test_case();
        --tests;
    }
    return 0;
}

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

public class Main {
    private static final Scanner sc = new Scanner(System.in);

    private static void testCase() {
        int n = sc.nextInt();
        long m = sc.nextLong();
        long[] characters = new long[n];
        for (int i = 0; i < n; ++i)
            characters[i] = sc.nextLong();
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; ++i)
            order[i] = i;
        Arrays.sort(order, (Integer x, Integer y) -> {
            if (characters[x] != characters[y])
                return Long.compare(characters[x], characters[y]);
            else
                return Integer.compare(x, y);
        });
        int ptr = n;
        long sum = 0;
        long[] moods = new long[n];
        for (int i = 0; i < n; ++i) {
            while (ptr > 0 && characters[order[ptr - 1]] > m - characters[order[i]]) {
                --ptr;
                sum += characters[order[ptr]];
            }
            moods[order[i]] = characters[order[i]] * ptr - sum;
            if (characters[order[i]] * 2 <= m)
                moods[order[i]] -= characters[order[i]];
            else
                moods[order[i]] += characters[order[i]];
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; ++i) {
            if (i > 0)
                sb.append(' ');
            sb.append(moods[i]);
        }
        System.out.println(sb);
    }

    public static void main(String[] args) {
        int tests = sc.nextInt();
        while (tests > 0) {
            testCase();
            --tests;
        }
    }
}

def test_case():
    n, m = map(int, input().split())
    characters = list(map(int, input().split()))
    order = sorted([i for i in range(n)], key=lambda x: (characters[x], x))
    ptr = n
    s = 0
    moods = [0 for _ in range(n)]
    for i in range(n):
        while ptr > 0 and characters[order[ptr - 1]] > m - characters[order[i]]:
            ptr -= 1
            s += characters[order[ptr]]
        moods[order[i]] = characters[order[i]] * ptr - s
        if characters[order[i]] * 2 <= m:
            moods[order[i]] -= characters[order[i]]
        else:
            moods[order[i]] += characters[order[i]]
    print(*moods)


tests = int(input())
for _ in range(tests):
    test_case()

E 扫雷难度调节

题解

要构造 “数字格” 数量最多的扫雷地图，可以指定对于所有整数 和 （，），第 行第 列的格子是地雷当且仅当以下条件同时满足：

  • ，或者 且 。
  • ，或者 且 。

如图为在 ， 的情况下，“数字格” 数量最多的一个扫雷地图：

alt

这种构造方法，保证了每个非地雷都是 “数字格”，不浪费任何一个格子。可以证明，此扫雷地图的 “数字格” 数量最多。为什么？

首先，定义一个新概念 “占用格”：一个格子为 “占用格”，当且仅当该格子为地雷或 “数字格”。

可以证明，一定存在一个 “数字格” 最多的扫雷地图，其所有格子都是 “占用格”。为什么？显然，“数字格” 最多的扫雷地图一定存在。任取一个 “数字格” 最多的扫雷地图，如果扫雷地图中包含非 “占用格”，则将所有非 “占用格” 变成地雷。显然，新的扫雷地图中，所有格子都是 “占用格”，“数字格” 的数量也不少于原扫雷地图。这就是所有格子均为 “占用格” 的、“数字格” 最多的扫雷地图。

我们考虑从没有地雷的扫雷地图开始，一个一个添加地雷，构造一个所有格子均为 “占用格” 的、“数字格” 最多的扫雷地图。要使 “数字格” 数量最多，就要使地雷数量最少。要使地雷数量最少，就要使添加每个地雷时添加的 “占用格” 最多（这里 “最多” 不单纯指数量最多，更是指 “你有的，我全都有” 的 “最多”）。

如果当前扫雷地图所有格子都是 “占用格”，就停止操作。

否则，取最左上角的非 “占用格”（也就是包含非 “占用格” 的最上方一行中最左侧的非 “占用格”），将其变成地雷。要使所有格子均为 “占用格”，首先就要使该格子成为 “占用格”。要使该格子成为 “占用格”，就必须将该格子或其一个相邻格子变成地雷。该格子的 个相邻格子中，只有右侧、下方、右下方相邻格子可能存在。也就是说，可以选择自身、右侧、下方、右下方格子之一变成地雷。选哪一个呢？观察可知，最优的选法是：选右下方相邻格子；若不存在，选右侧或下方相邻格子；若不存在，就选自身。该选法中扫雷地图的 “占用格” 完全包含了其他所有选法中扫雷地图的 “占用格”，是添加 “占用格” 最多的选法，故一定最优。

不断重复以上操作，直到所有格子都是 “占用格” 为止。这恰好就是在开头提及的构造方法。

最后，若想减少 “数字格” 的数量，只需要不断任选非地雷，变成地雷即可，不会对其他格子造成影响。这是因为，其他格子如果是地雷，则操作后仍是地雷，仍然不是 “数字格”；如果不是地雷，则操作后仍不是地雷且周围仍有地雷，仍然是 “数字格”；然而，被操作的格子从 “数字格” 变成地雷，不再是 “数字格” 了。于是，每次操作会将 “数字格” 的数量减少 。

时间复杂度：每个测试用例 。

代码

#include <iostream>
#include <vector>

using namespace std;

void test_case()
{
    int n = 0, m = 0, k = 0, cnt = 0;
    cin >> n >> m >> k;
    vector<int> grid(n * m);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if ((i % 3 == 1 || n % 3 == 1 && i == n - 1) && (j % 3 == 1 || m % 3 == 1 && j == m - 1))
            {
                grid[i * m + j] = 1;
                ++cnt;
            }
    cnt = n * m - k - cnt;
    if (cnt < 0)
    {
        cout << "-1\n";
        return;
    }
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
        {
            if (cnt == 0)
                break;
            if (!grid[i * m + j])
            {
                grid[i * m + j] = 1;
                --cnt;
            }
        }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
            cout << grid[i * m + j];
        cout << '\n';
    }
}

int main()
{
    int tests = 0;
    cin >> tests;
    while (tests > 0)
    {
        test_case();
        --tests;
    }
}

#include <stdio.h>

#define N 1000

int grid[N][N];

void test_case()
{
    int n = 0, m = 0, k = 0, cnt = 0;
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if ((i % 3 == 1 || n % 3 == 1 && i == n - 1) && (j % 3 == 1 || m % 3 == 1 && j == m - 1))
            {
                grid[i][j] = 1;
                ++cnt;
            }
            else
                grid[i][j] = 0;
    cnt = n * m - k - cnt;
    if (cnt < 0)
    {
        puts("-1");
        return;
    }
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
        {
            if (cnt == 0)
                break;
            if (!grid[i][j])
            {
                grid[i][j] = 1;
                --cnt;
            }
        }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
            printf("%d", grid[i][j]);
        putchar('\n');
    }
}

int main()
{
    int tests = 0;
    scanf("%d", &tests);
    while (tests > 0)
    {
        test_case();
        --tests;
    }
}

import java.util.Scanner;

public class Main {
    private static final Scanner sc = new Scanner(System.in);

    private static void testCase() {
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        int cnt = 0;
        boolean[][] grid = new boolean[n][m];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                if ((i % 3 == 1 || n % 3 == 1 && i == n - 1) && (j % 3 == 1 || m % 3 == 1 && j == m - 1)) {
                    grid[i][j] = true;
                    ++cnt;
                }
        cnt = n * m - k - cnt;
        if (cnt < 0) {
            System.out.println("-1");
            return;
        }
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                if (cnt == 0)
                    break;
                if (!grid[i][j]) {
                    grid[i][j] = true;
                    --cnt;
                }
            }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j)
                sb.append(grid[i][j] ? '1' : '0');
            sb.append('\n');
        }
        System.out.print(sb);
    }

    public static void main(String[] args) {
        int tests = sc.nextInt();
        while (tests > 0) {
            testCase();
            --tests;
        }
    }
}

def test_case():
    n, m, k = map(int, input().split())
    grid = [[False for _ in range(m)] for _ in range(n)]
    cnt = 0
    for i in range(n):
        for j in range(m):
            if (i % 3 == 1 or n % 3 == 1 and i == n - 1) and (j % 3 == 1 or m % 3 == 1 and j == m - 1):
                grid[i][j] = True
                cnt += 1
    cnt = n * m - k - cnt
    if cnt < 0:
        print('-1')
        return
    for i in range(n):
        for j in range(m):
            if cnt == 0:
                break
            if not grid[i][j]:
                grid[i][j] = True
                cnt -= 1
    for i in range(n):
        print(''.join(map(str, map(int, grid[i]))))


tests = int(input())
for _ in range(tests):
    test_case()

F 徽章计数

题解

题目要求对于数列 的每个元素 ，在 中都恰有 个元素与之相等（含自身）。

首先，将集合 分组，使得对于任意整数 和 （）， 和 在同一组当且仅当 。假设分成了 组，编号为 ，第 组元素作为 时的 值为 ，第 组包含的元素数量为 。

容易看出，如果存在整数 （），使得 不能被 整除，那么这样的数列 不存在，可以直接回答 。

否则，这就说明每个 都能被 整除。对于每个整数 （），继续给第 组分块，分成 块，保证每块大小均为 。根据题意，同一块内所有元素作为 时的 值必须相等；不同块间（包括同一组不同块间和不同组不同块间）任何两个元素作为 时的 值必须不相等。因此，要得到满足条件的数列 ，就需要进行以下步骤：

  • 首先，在不小于 、不大于 的所有整数中，选择 个互不相同的整数，按顺序分配给每组每块。这一步有 种方法。
  • 然后，给每组分块，每组所有块之间没有顺序之分（顺序在上一步已经分好了）。这一步有 种方法。

于是，整数数列的数量即为

答案即为上述表达式对 取模。注意可能需要预先计算阶乘的结果，也可能需要求出模意义下的乘法逆元来代替除法。

时间复杂度：每个测试用例 。

我们常说的 “吧唧”，其实就是 “徽章” 的意思，音译自英语 “badge”。

代码

#include <iostream>
#include <vector>

using namespace std;
using LL = long long;

const LL N = 200'000, MOD = 1'000'000'007;

LL factorials[N + 1], inverse_factorials[N + 1];

LL fast_pow(LL base, LL exp)
{
    LL result = 0, mult = 0;
    result = 1;
    mult = base % MOD;
    while (exp != 0)
    {
        if (exp % 2 != 0)
            result = result * mult % MOD;
        mult = mult * mult % MOD;
        exp /= 2;
    }
    return result;
}

LL get_inverse(LL x)
{
    return fast_pow(x, MOD - 2);
}

void preprocess()
{
    factorials[0] = 1;
    for (LL i = 1; i <= N; ++i)
        factorials[i] = factorials[i - 1] * i % MOD;
    inverse_factorials[0] = 1;
    for (LL i = 1; i <= N; ++i)
        inverse_factorials[i] = inverse_factorials[i - 1] * get_inverse(i) % MOD;
}

void test_case()
{
    LL n = 0, m = 0, t = 0, result = 0;
    cin >> n >> m;
    vector<LL> a(n);
    for (LL i = 0; i < n; ++i)
        cin >> a[i];
    vector<LL> groups(n + 1);
    for (LL i = 0; i < n; ++i)
        ++groups[a[i]];
    for (LL x = 1; x <= n; ++x)
        if (groups[x] % x != 0)
        {
            cout << "0\n";
            return;
        }
    t = m;
    result = 1;
    for (LL x = 1; x <= n; ++x)
        for (LL i = groups[x] / x; i >= 1; --i)
        {
            result = result * t % MOD;
            --t;
        }
    for (LL x = 1; x <= n; ++x)
    {
        result = result * factorials[groups[x]] % MOD;
        result = result * fast_pow(inverse_factorials[x], groups[x] / x) % MOD;
        result = result * inverse_factorials[groups[x] / x] % MOD;
    }
    cout << result << '\n';
}

int main()
{
    LL tests = 0;
    preprocess();
    cin >> tests;
    while (tests > 0)
    {
        test_case();
        --tests;
    }
}

#include <stdio.h>

typedef long long LL;

#define N 200000LL
#define MOD 1000000007LL

LL factorials[N + 1], inverse_factorials[N + 1];
LL a[N], groups[N + 1];

LL fast_pow(LL base, LL exp)
{
    LL result = 0, mult = 0;
    result = 1;
    mult = base % MOD;
    while (exp != 0)
    {
        if (exp % 2 != 0)
            result = result * mult % MOD;
        mult = mult * mult % MOD;
        exp /= 2;
    }
    return result;
}

LL get_inverse(LL x)
{
    return fast_pow(x, MOD - 2);
}

void preprocess()
{
    factorials[0] = 1;
    for (LL i = 1; i <= N; ++i)
        factorials[i] = factorials[i - 1] * i % MOD;
    inverse_factorials[0] = 1;
    for (LL i = 1; i <= N; ++i)
        inverse_factorials[i] = inverse_factorials[i - 1] * get_inverse(i) % MOD;
}

void test_case()
{
    LL n = 0, m = 0, t = 0, result = 0;
    scanf("%lld%lld", &n, &m);
    for (LL i = 0; i < n; ++i)
        scanf("%lld", a + i);
    for (LL x = 1; x <= n; ++x)
        groups[x] = 0;
    for (LL i = 0; i < n; ++i)
        ++groups[a[i]];
    for (LL x = 1; x <= n; ++x)
        if (groups[x] % x != 0)
        {
            puts("0");
            return;
        }
    t = m;
    result = 1;
    for (LL x = 1; x <= n; ++x)
        for (LL i = groups[x] / x; i >= 1; --i)
        {
            result = result * t % MOD;
            --t;
        }
    for (LL x = 1; x <= n; ++x)
    {
        result = result * factorials[groups[x]] % MOD;
        result = result * fast_pow(inverse_factorials[x], groups[x] / x) % MOD;
        result = result * inverse_factorials[groups[x] / x] % MOD;
    }
    printf("%lld\n", result);
}

int main()
{
    LL tests = 0;
    preprocess();
    scanf("%lld", &tests);
    while (tests > 0)
    {
        test_case();
        --tests;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    private static final Scanner sc = new Scanner(System.in);
    private static final int N = 200_000;
    private static final long MOD = 1_000_000_007;
    private static final long[] factorials = new long[N + 1];
    private static final long[] inverseFactorials = new long[N + 1];

    private static long fastPow(long base, long exp) {
        long result = 1;
        long mult = base;
        while (exp != 0) {
            if (exp % 2 != 0)
                result = result * mult % MOD;
            mult = mult * mult % MOD;
            exp /= 2;
        }
        return result;
    }

    private static long getInverse(long x) {
        return fastPow(x, MOD - 2);
    }

    private static void preprocess() {
        factorials[0] = 1;
        for (int i = 1; i <= N; ++i)
            factorials[i] = factorials[i - 1] * i % MOD;
        inverseFactorials[0] = 1;
        for (int i = 1; i <= N; ++i)
            inverseFactorials[i] = inverseFactorials[i - 1] * getInverse(i) % MOD;
    }

    private static void testCase() {
        int n = sc.nextInt();
        long m = sc.nextLong();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i)
            a[i] = sc.nextInt();
        int[] groups = new int[n + 1];
        for (int i = 0; i < n; ++i)
            ++groups[a[i]];
        for (int x = 1; x <= n; ++x)
            if (groups[x] % x != 0) {
                System.out.println("0");
                return;
            }
        long t = m;
        long result = 1;
        for (int x = 1; x <= n; ++x)
            for (int i = groups[x] / x; i > 0; --i) {
                result = result * t % MOD;
                --t;
            }
        for (int x = 1; x <= n; ++x) {
            result = result * factorials[groups[x]] % MOD;
            result = result * fastPow(inverseFactorials[x], groups[x] / x) % MOD;
            result = result * inverseFactorials[groups[x] / x] % MOD;
        }
        System.out.println(result);
    }

    public static void main(String[] args) {
        preprocess();
        int tests = sc.nextInt();
        while (tests > 0) {
            testCase();
            --tests;
        }
    }
}

N = 200_000
MOD = 1_000_000_007
factorials = [0 for _ in range(N + 1)]
inverse_factorials = [0 for _ in range(N + 1)]


def preprocess():
    factorials[0] = 1
    for i in range(1, N + 1):
        factorials[i] = factorials[i - 1] * i % MOD
    inverse_factorials[0] = 1
    for i in range(1, N + 1):
        inverse_factorials[i] = inverse_factorials[i - 1] * pow(i, -1, MOD) % MOD


def test_case():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    groups = [0 for _ in range(n + 1)]
    for x in a:
        groups[x] += 1
    for x in range(1, n + 1):
        if groups[x] % x != 0:
            print('0')
            return
    t = m
    result = 1
    for x in range(1, n + 1):
        for _ in range(groups[x] // x):
            result = result * t % MOD
            t -= 1
    for x in range(1, n + 1):
        result = result * factorials[groups[x]] % MOD
        result = result * pow(inverse_factorials[x], groups[x] // x, MOD) % MOD
        result = result * inverse_factorials[groups[x] // x] % MOD
    print(result)


preprocess()
tests = int(input())
for _ in range(tests):
    test_case()

题解及代码下载

牛客小白月赛 128 题解.zip

2026最新求职资料大礼包领取
真题
历年笔试真题附答案
2023年用友集团秋招Java岗笔试
【2023】微众银行校招技术类A卷
2023年搜狐畅游秋招运营策划岗笔试
全部 >
面经
面试常考问题整理
腾讯三面已上岸
0926腾讯音乐笔试题解
Springboot全套注解解析《看不懂算我输》
全部 >
内推
员工内推码获取
拼多多26届校招 拼多多内推 拼多多内推码
国科微电子最新社招/校招，岗位多多
【虎牙内推】虎牙2026届秋招补录火热进行中！！！
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(1) 回帖
加载中...
话题 回帖
返回全部帖子

本文相关内容

等你来战

查看全部

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”