Codeforces 1168C（二进制、dp）

要点

‘&’操作暗示二进制上按位思考
对于y为1的位，要求x和y之间要至少有两个此位为1的（包含x、y），这样&起来才不是0.而这些位中只要存在一个是ok的即可
dp去求每个x的每个位最早到达的y

const int maxn = 3e5 + 5, Log = 20;

int n, q, a[maxn];

int go[maxn][Log + 5], Last[Log + 5];

int main() {

	read(n), read(q);

	rep(i, 1, n)	read(a[i]);

	rep(j, 0, Log) {

		Last[j] = n + 1;

		rep(i, 1, n + 1)//注意这里，因为Last设的是这里

			go[i][j] = n + 1;

	}

	per(i, n, 1) {

		rep(j, 0, Log) {

			if ((a[i] >> j) & 1) {

				go[i][j] = i;

				rep(k, 0, Log)

					go[i][k] = min(go[i][k], go[Last[j]][k]);

				Last[j] = i;

			}

		}

	}

	for (int x, y; q; q--) {

		read(x), read(y);

		bool yes = 0;

		rep(j, 0, Log)

			yes |= ((a[y] >> j) & 1) && (go[x][j] <= y);

		puts(yes ? "Shi" : "Fou");

	}

	return 0;

}

巴特西

Codeforces 1168C（二进制、dp）

要点

最新文章

热门文章