noip模拟赛但有用

题目描述

给定一个 n ∗ m 个矩阵，矩阵中每个数都是 [1, 12] 内的整数。你可以执行下列两个操作任意多次:

• 指定一行，将该行所有数字 +1.

• 指定一列，将该列所有数字 +1.

如果执行完上述操作之后，矩阵中某个数变成了 3, 6, 9, 12 其中的某一个，我们认为这个数是稳的。

给定初始矩阵，求出任意执行操作之后稳数的最多个数。

输入输出格式

输入格式：

第一行包含两个正整数 n, m。

接下来 n 行，每行 m 个数，描述这个矩阵。

输出格式：

一个整数，表示答案。

输入输出样例

输入样例#1：

输出样例#1：

输入样例#2：

5 5

2 4 6 8 10

1 2 3 4 5

3 4 5 6 7

7 8 9 10 11

5 10 12 3 7

输出样例#2：

分析：对于每一行和每一列而言，加i次一定比加i+3次更优，因为3次一个循环，有可能i+3次后数就大于12了，所以对于每一行每一列最多只需要加2次.这种题行与列之间互相有影响，但是行与行，列与列之间没有影响的，可以先把行的操作给枚举出来，列是独立的，贪心地考虑每一列操作多少次即可.

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

int n, m, a[][], cnt[], c1, c2, c0, res, ans;

void solve()

{

    res = ;

    for (int i = ; i <= m; i++)

    {

        c0 = c2 = c1 = ;

        for (int j = ; j <= n; j++)

        {

            if ((a[j][i] + cnt[j]) %  ==  && a[j][i] + cnt[j] <= )

                c0++;

            if ((a[j][i] + cnt[j] + ) %  ==  && a[j][i] + cnt[j] +  <= )

                c1++;

            if ((a[j][i] + cnt[j] + ) %  ==  && a[j][i] + cnt[j] +  <= )

                c2++;

        }

        res += max(max(c0, c1), c2);

    }

    ans = max(ans, res);

}

void dfs(int dep)

{

    if (dep == n + )

    {

        solve();

        return;

    }

    for (int i = ; i <= ; i++)

    {

        cnt[dep] = i;

        dfs(dep + );

    }

}

int main()

{

    scanf("%d%d", &n, &m);

    for (int i = ; i <= n; i++)

        for (int j = ; j <= m; j++)

            scanf("%d", &a[i][j]);

    dfs();

    printf("%d\n", ans);

    return ;

}

巴特西

noip模拟赛但有用

题目描述

输入输出格式

输入输出样例

最新文章

热门文章

巴特西

noip模拟赛 但有用

题目描述

输入输出格式

输入输出样例

最新文章

热门文章

noip模拟赛但有用