题目链接 ECNU Monthly 2018.10 Problem E
从开场写到结束……
显然要把三角形分成上下两部分。
把每一部分分成三部分，以上部分为例。
上面和右边，以及左下角的正方形。
也就是两个小三角形和一个正方形合起来。
处理正方形的时候稍微麻烦一些。
然后直接倍增就可以了。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define fi first #define se second #define MP make_pair typedef long long LL; const int N = 1e3 + 10; bitset <102> f[N][N][10], g[N][N][10], ff[N][N][10], gg[N][N][10]; int n, m, q; int T; int lg[N + 10]; inline int check(int x, int y){ return x >= 1 && x <= n && y >= 1 && y <= m; } int main(){ lg[1] = 0; rep(i, 2, 1001) lg[i] = lg[i >> 1] + 1; scanf("%d%d", &n, &m); rep(i, 1, n){ rep(j, 1, m){ int x; scanf("%d", &x); f[i][j][0].set(x); g[i][j][0].set(x); ff[i][j][0].set(x); gg[i][j][0].set(x); } } rep(k, 1, 9){ rep(i, 1, n){ rep(j, 1, m){ int xx, yy, zz = 1 << (k - 1); f[i][j][k] |= f[i][j][k - 1]; xx = i - zz; yy = j; if (check(xx, yy)) f[i][j][k] |= f[xx][yy][k - 1]; xx = i; yy = j + zz; if (check(xx, yy)) f[i][j][k] |= f[xx][yy][k - 1]; xx = i - zz; yy = j + zz; if (check(xx, yy)) f[i][j][k] |= f[xx][yy][k - 1]; ff[i][j][k] |= ff[i][j][k - 1]; xx = i + zz; yy = j; if (check(xx, yy)) ff[i][j][k] |= ff[xx][yy][k - 1]; xx = i; yy = j + zz; if (check(xx, yy)) ff[i][j][k] |= ff[xx][yy][k - 1]; xx = i + zz; yy = j + zz; if (check(xx, yy)) ff[i][j][k] |= ff[xx][yy][k - 1]; } } } rep(k, 1, 9){ rep(i, 1, n){ rep(j, 1, m){ int xx, yy, zz = 1 << (k - 1); g[i][j][k] |= f[i][j][k - 1]; xx = i - zz; yy = j; if (check(xx, yy)) g[i][j][k] |= g[xx][yy][k - 1]; xx = i; yy = j + zz; if (check(xx, yy)) g[i][j][k] |= g[xx][yy][k - 1]; gg[i][j][k] |= ff[i][j][k - 1]; xx = i + zz; yy = j; if (check(xx, yy)) gg[i][j][k] |= gg[xx][yy][k - 1]; xx = i; yy = j + zz; if (check(xx, yy)) gg[i][j][k] |= gg[xx][yy][k - 1]; } } } scanf("%d", &q); while (q--){ int x, y, z; scanf("%d%d%d", &x, &y, &z); if (z == 1){ puts("1"); continue; } int c = lg[z]; bitset <102> ret; int xx, yy, zz = 1 << c; xx = x - z + zz; yy = y; ret |= g[xx][yy][c]; xx = x; yy = y + z - zz; ret |= g[xx][yy][c]; int t = (z) >> 1; int l = lg[t], ll = 1 << l; ret |= f[x][y][l]; xx = x - t + ll; yy = y; ret |= f[xx][yy][l]; xx = x; yy = y + t - ll; ret |= f[xx][yy][l]; xx = x - t + ll; yy = y + t - ll; ret |= f[xx][yy][l]; xx = x + z - zz; yy = y; ret |= gg[xx][yy][c]; xx = x; yy = y + z - zz; ret |= gg[xx][yy][c]; ret |= ff[x][y][l]; xx = x + t - ll; yy = y; ret |= ff[xx][yy][l]; xx = x; yy = y + t - ll; ret |= ff[xx][yy][l]; xx = x + t - ll; yy = y + t - ll; ret |= ff[xx][yy][l]; printf("%d\n", (int)ret.count()); } return 0; }
转载于:https://www.cnblogs.com/cxhscst2/p/9741207.html
