链接:

https://codeforces.com/contest/1228/problem/B

题意:

Suppose there is a h×w grid consisting of empty or full cells. Let's make some definitions:

ri is the number of consecutive full cells connected to the left side in the i-th row (1≤i≤h). In particular, ri=0 if the leftmost cell of the i-th row is empty.

cj is the number of consecutive full cells connected to the top end in the j-th column (1≤j≤w). In particular, cj=0 if the topmost cell of the j-th column is empty.

In other words, the i-th row starts exactly with ri full cells. Similarly, the j-th column starts exactly with cj full cells.

These are the r and c values of some 3×4 grid. Black cells are full and white cells are empty.

You have values of r and c. Initially, all cells are empty. Find the number of ways to fill grid cells to satisfy values of r and c. Since the answer can be very large, find the answer modulo 1000000007(109+7). In other words, find the remainder after division of the answer by 1000000007(109+7).

思路:

枚举每个位置的情况, 挨个乘起来即可.

代码:

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9+7;

int r[1100], c[1100];

int h, w;

bool Check(int x, int y, int op)

{

    if (y == 1 && r[x] == 0 && op == 1)

        return false;

    if (x == 1 && c[y] == 0 && op == 1)

        return false;

    if (y == r[x]+1 && op == 1)

        return false;

    if (x == c[y]+1 && op == 1)

        return false;

    if (y <= r[x] && op == 0)

        return false;

    if (x <= c[y] && op == 0)

        return false;

    return true;

}

int main()

{

    cin >> h >> w;

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

        cin >> r[i];

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

        cin >> c[i];

    int res = 1;

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

    {

        for (int j = 1;j <= w;j++)

        {

            int tmp = 0;

            if (Check(i, j, 0))

                tmp++;

            if (Check(i, j, 1))

                tmp++;

//            cout << i << ' ' << j << ' ' << tmp << endl;

            res = (res*tmp)%MOD;

        }

    }

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

    return 0;

}

巴特西

Codeforces Round #589 (Div. 2) B. Filling the Grid

链接:

题意:

思路:

代码:

最新文章

热门文章