题目大意: 给定一个 $h$ 行, $w$ 列的矩形, 接下来一行 $h$ 个数字, $hi$ 代表第 $i$ 行从左到右有连续的 $hi$ 个染成黑色的方块, 列同理, 然后问满足条件的矩形的个数 (% 1e9 + 7).
比赛写的时候第一次挂掉了, 因为判断原条件不成立的代码写挂了 = = , 不知道自己当时在想什么.
我在处理数据时, 开了两个数组, 分别记录行与列的染色情况.
- forab(i, 1, h)
- {
- cin>> r[i];
- forab(k, 1, r[i])
- G[i][k] = 1, R[i][k] = 1;
- }
- forab(i, 1, w)
- {
- cin>> c[i];
- forab(k, 1, c[i])
- G[k][i] = 1, C[k][i] = 1;
- }
我判断原条件不成立的想法是:
- forab(i, 1, h)
- {
- if (C[i][r[i] + 1] == 1)
- {
- flag = 1;
- break;
- }
- }
- forab(i, 1, w)
- {
- if (R[c[i] + 1][i] == 1)
- {
- flag = 1;
- break;
- }
- }
最后计数的判断为:
- forab(i, 1, h)
- {
- forab(j, 1, w)
- {
- if (G[i][j])
- continue;
- if (r[i] + 1 == j || c[j] + 1 == i)
- continue;
- else
- ans = 2 * ans % MOD;
- }
- }
来源: http://www.bubuko.com/infodetail-3219409.html