省选模拟赛 7

被咕咕咕了的博客

幂等性相当强

根据群的定义,这玩意不可能是加法

不妨定义为max!

那么我们会发现查询相当于区间max

而这个东西.....要定义一些东西才行吧?

显然我们有 $nlogn$ 个机会定义max....?

树上max?

~~直接输出1是一种合法的解~~

但是不能这样

我们每个点向上跳log步得到的最大值答案都搞出来,就是用 $O(nlogn)$ 搞出一个树上ST表

剩下还有3次机会给我们的q询问

也很简单,之前树上倍增不是跳log次吗?

但是这次我们左边用两个就能拼出一个最大值

然后右边用两个也能拼出一个最大值

二者之前再拼出一个值

正好用了3次,卡满了2e6....

插头dp!

这个形态....防止计重是相当难的唉

记录什么呢?

_____|-----

划分线上每个格子向哪个方向延伸?

不对,是是否向下延伸?

是的,你会发现我们能记录很多是否向下的0/1变量

如果向下为1,那我们这个位置下一刻只能放0,否则下个位置只能放1

设计这样一个状态,我们可能会转移出不太对劲的状态吧?就是计重了?

是的!因为你会发现这样我们没有考虑颜色,而直接将颜色计入转移系数显然会算重!

因为我们本质不同的方案数只和颜色相同,而一个染色方案是否有效却和我们的插头dp相同

所以说我们打算外层dp一下染色方案并状压内层插头形态

哼,怎么可能,状压的是内层所有可行的插头方案,就是比如有2^16个插头形态,就记录 $2^2^16$

这题n是6,所以是 $2^2^6$ = $2^64$

一个ll就能存下来

当然,这个东西显然要用map记录状态并转移,因为本质不同的染色方案可能对应了相同的边界颜色....

总而言之,dp套dp

code:



#pragma G++ optimize(2)
#pragma G++ optimize(3)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
using std::map;
using std::pair;
using std::make_pair;
const int P = 998244353;
#define ull unsigned long long
#define ll long long
#define fi first
#define se second
#define mkp(x,y) make_pair(x,y)
map<pair<ll, ull>, ll> dp[3];
int n, m;
inline void update(int x, int y, ull Sc, ll vl, ull S, int t, int nc) {
	ull nS = 0;
	for(int plug = 0; plug < (1 << n); ++plug) {
		if(S >> plug & 1) {//这个状态有了
			int upc = Sc >> y & 1;//上方颜色
			int upplug = plug >> y & 1;//上方插头
			int Lc = 0, Lplug = 0;

			if(y)Lc = Sc >> (y - 1) & 1, Lplug = plug >> (y - 1) & 1;//不是第一个,0是第一个
			if(upplug) {//有下插头
				if(nc != upc)//如果颜色不一样
					nS |= 1ull << (plug ^ (1 << y));//除掉下插头
			} else {//没有下插头
				if(y && nc != Lc && Lplug) { //有右插头
					nS |= 1ull << (plug ^ (1 << (y - 1)));//除掉右插头
				}
				nS |= 1ull << (plug ^ (1 << y)); //下插头
			}
		}
	}
	if(nS)(dp[t][mkp(Sc ^ ((Sc >> y & 1) << y) ^ (nc << y), nS)] += vl) %= P;
}

int main() {
	// int n, m;
	int t = 0;

	dp[0][mkp(0, 1)] = 1;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++i) {
		for(int j = 0; j < n; ++j) {
			t ^= 1;
			dp[t].clear();
			for(auto it : dp[t ^ 1]) {//C++11
				ll vl = it.se;
				ll col = it.fi.fi;
				ull S = it.fi.se;
				for(int k = 0; k < 2; ++k) {
					update(i, j, col, vl, S, t, k);
				}
			}
		}
	}
	ll ans = 0;
	for(auto it : dp[t])
		if(it.fi.se & 1)
			ans = (ans + it.se) % P;
	printf("%lld\n", ans);
	return 0;
}

有一个结论:如果选择的长度为k的区间不包括两边子区间的最大值的话,一定无法更新答案

假设最大值为x次大值为y

而左边最次大值为A,a右边最次大值为B,b

显然x+y最大为a+b

而此时,若b>A,B+b大于a+b

若a>B,a+A大于a+b

除外则也显然不优

那么直接用线段树维护即可

finish

夏晓光(loveJY)的博客

NOIP2018 全国模拟赛 (完结!)