P5289 [十二省联考2019]皮配

十二省联考2019D2T1

不太像是正常的题,首先改下题面

题意概要：有 $c$ 个豆荚，共 $n$ 颗豆子，每颗豆子都有自己的重量，现在需要将给豆子设定为 (黄色/绿色,圆粒/皱粒)，要求满足以下条件：

给定这四种性状的阀值 $C_0,C_1,D_0,D_1$ ，要求为这种性状的豆子重量和不能超过该阀值
与此同时，这 $n$ 颗豆子中存在 $k$ 颗顽皮豆，顽皮豆都有自己的想法，比如拒绝成为 (黄圆/黄皱/绿圆/绿皱)
同一个豆荚里的豆子必须同时为黄色或同时为绿色

求有多少种给豆子设定的方案，对 $998244353$ 取模

$n,c\leq 10^3,k\leq 30$

设 $M=\max\{C_0,C_1,D_0,D_1\}$ , $M\leq 2500$

豆子重量不超过 $\min\{M,10\}$

是个DP无疑,首先我们看向前30pts

设DP[i][j][k][0/1]表示黄圆有i个,黄皱有j个,绿圆有k个,绿皱有sum-i-j-k个而且这一个豆荚选择了0/1颜色的方案数

先按照豆荚拍下序,转移时枚举下一个豆子,分是不是还是之前豆荚处理以及顽皮豆就行了

复杂度是 $O(n*M^3)$ ,可以T掉7个点

然后考虑优化一下这个做法,我们只记录绿色豆子数量和圆豆子数量就行了

转移时不同的地方就是如果没有顽皮豆的限制要注意放在圆豆还是皱豆那堆里,并相应的用圆豆子数量变不变的状态转移

这个做法是 $O(n*M^2)$ ,可以T掉5个点,~~可以发现我们T的点变少了/kk~~

然后看向第6,9个点, $k=0?$ 也就是说没有顽皮豆,这样去掉了一个限制,是不是问题就简化了呢?因为此时你分的颜色和分的性状二者是独立的,具体的,每一种合法的颜色划分方案都能对应一个性状划分方案,这样如果我们能求出合法的颜色划分方案和性状划分方案就可以直接乘一下过掉了

怎么写?就是正常0/1背包,倒序滚动的那种

再来看100pts, $k<=30$ ,~~是一个刚好不能容斥的范围,要是可以怎么容?~~

然鹅毕竟我们只有30颗顽皮豆,如果这些豆子能算出总方案,然后再和之前求得k=0的状态做一个类似背包合并的操作就可以了

30颗顽皮豆方案?好像之前50pts的做法是可以的?那我们就再用50分的那个做法把这些总方案求一下就好啦?

但是仔细想想你会发现50pts的DP是最难的...~~而且之前只是口胡~~我们回到这个题

$F[i][j][k]$ 表示前i个城市,蓝阵营有j个选,鸭派系有k个总方案数同时我们这个城市选的就是蓝阵营

$G[i][j][k]$ 表示前i个城市,蓝阵营有j个选,鸭派系有k个总方案数同时我们这个城市选的就是红阵营

i这一维先滚动掉

然后我们去枚举那些这个城市的学校

case1:讨厌小R

对于F,我们只能放进Yazid,所以只需要把大于等于人数的平移过去,其他置为0

对于G,我们照常转移即可

case2:讨厌Yazid

对于F,无法转移,相当于动都不动的

对于G,照常转移

case3:讨厌大R以及case4讨厌zayid

和之前一样对称

上面的转移都是对于第二维派系来说的,所以最后别忘了对于阵营再转移一次,和case1中的F一样,然后再把F,G数组每个状态的方案数暴力加起来就行了

最后是把求得新状态和之前的pre合并....

考虑先枚举蓝阵营/鸭派系里有多少个人

然后把求得可以额外放进蓝阵营的人数的一个范围,上界是把C0填满,下界是把C1填满

那么这些人数构成的自由方案都可以,所以要对之前处理好的自由人方案求个前缀和,得到范围内答案a

同样的可以处理鸭派系自由方案和b

这 $a,b,F[i][j]$ 三个数乘一下就是答案了....

$O((c+n)M+k^2sM)$ 前面是预处理DP后面是计算F复杂度,因为s<=10

终于结束了,最后强行推荐封面图

code:


#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

namespace fastIO {
#define BUF_SIZE (1<<19)
	static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0, f = 1;
		register char s = nc();
		for(; !isdigit(s); s = nc())if(s == '-')f = -1;
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x * f;
	}
}
using namespace fastIO;
const int MAXN = 2600;
const int P = 998244353;
bool hcty[MAXN];
int scty[MAXN], ht[MAXN], b[MAXN], s[MAXN], f[MAXN], pre_f[MAXN]
, F[MAXN][MAXN], g[MAXN], pre_g[MAXN], G[MAXN][MAXN], n, c, C0, C1, D0, D1, SUM;


inline void init() {
	n = read();
	c = read();
	SUM = 0;
	for(int i = 1; i <= c; ++i)hcty[i] = 0, scty[i] = 0;
	C0 = read(), C1 = read(), D0 = read(), D1 = read();
	for(int i = 1; i <= n; ++i)b[i] = read(), s[i] = read(), scty[b[i]] += s[i], ht[i] = -1, SUM += s[i];
	int K, x;
	K = read();
	for(int i = 1; i <= K; ++i) {
		x = read();
		ht[x] = read();
		hcty[b[x]] = 1;
		//这个城市完了
	}

	memset(f, 0, sizeof(f));
	pre_f[0] = f[0] = 1;
	for(int i = 1; i <= c; ++i) {
		if(!hcty[i] && scty[i]) {
			for(int j = C0; j >= scty[i]; --j) {
				(f[j] += f[j - scty[i]]) %= P;
			}
		}
	}
	for(int i = 1; i <= C0; ++i)pre_f[i] = (pre_f[i - 1] + f[i]) % P;// printf("%d\n", pre_f[i]);

	memset(g, 0, sizeof(g));
	pre_g[0] = g[0] = 1;
	for(int i = 1; i <= n; ++i) {
		if(-1 == ht[i]) {
			for(int j = D0; j >= s[i]; --j) {
				(g[j] += g[j - s[i]]) %= P;
			}
		}
	}
	for(int i = 1; i <= D0; ++i)pre_g[i] = (pre_g[i - 1] + g[i]) % P;// printf("%d\n", pre_g[i]);

	memset(F, 0, sizeof(F));
	memset(G, 0, sizeof(G));
	F[0][0] = 1;
}

inline void solve() {
	int Cs = 0, Ss = 0;
	for(int ct = 1; ct <= c; ++ct) {
		if(hcty[ct]) {
			Cs += scty[ct], Cs = min(Cs, C0);
			//Cs是城市的人数前缀和与C0取min
			//printf("%d!\n", Cs);
			for(int i = 0; i <= Cs; ++i) {
				for(int j = 0; j <= Ss; ++j) {
					G[i][j] = F[i][j];
				}
			}
			for(int a = 1; a <= n; ++a)
				if(b[a] == ct && ~ht[a]) {
					const int t = s[a];

					Ss += t;
					Ss = min(Ss, D0);
					//printf("ha%d %d %d?\n", t, Ss, ht[a]);
					if(ht[a] == 1) {
						for(int i = 0; i <= Cs; ++i) {//最外层枚举阵营人数
							for(int j = Ss; j >= t; --j)F[i][j] = F[i][j - t];
							//F数组是考虑选择蓝阵营
							//等于1就相当于我们只能选Yazid
							for(int j = t - 1; ~j; --j)F[i][j] = 0;
						}
					}
					if(ht[a] >= 2) {
						for(int i = 0; i <= Cs; ++i) {
							for(int j = Ss; j >= t; --j)(F[i][j] += F[i][j - t]) %= P;
							//直接转移就行了我们放弃
						}
					}
					if(ht[a] == 3) {
						for(int i = 0; i <= Cs; ++i) {
							for(int j = Ss; j >= t; --j)G[i][j] = G[i][j - t];
							for(int j = t - 1; ~j; --j)G[i][j] = 0;
						}
					}
					if(ht[a] <= 1) {
						for(int i = 0; i <= Cs; ++i) {
							for(int j = Ss; j >= t; --j) {
								(G[i][j] += G[i][j - t]) %= P;
								//要么yazid要么小R
							}
						}
					}
				}
			for(int j = 0, t = scty[ct]; j <= Ss; ++j) {
				for(int i = Cs; i >= t; --i) F[i][j] = F[i - t][j];
				for(int i = t - 1; ~i; --i)F[i][j] = 0;
			}
			for(int i = 0; i <= Cs; ++i) {
				for(int j = 0; j <= Ss; ++j) {
					(F[i][j] += G[i][j]) %= P;
					//printf("%lld? ", F[i][j]);
				}
				//puts("");
			}
		}
	}
	int res = 0;
	for(int i = 0; i <= Cs; ++i) {
		for(int j = 0; j <= Ss; ++j) {
			int l1 = max(0, SUM - C1 - i), r1 = C0 - i;
			//枚举派系的一个划分
			//考虑最少装多少个和最多装多少个
			//最多把C0装满,最少把C1装满
			//对一个r1和l1
			if(l1 > r1)continue;
			int l2 = max(0, SUM - D1 - j), r2 = D0 - j;
			//枚举导师的一个划分
			if(l2 > r2)continue;
			int vf = pre_f[r1];
			if(l1)vf += P - pre_f[l1 - 1];
			int vg = pre_g[r2];
			if(l2)vg += P - pre_g[l2 - 1];
			//前缀和部分233
			(res += 1ll * vf * vg % P * F[i][j] % P) %= P;
		}
	}
	printf("%d\n", res);
}


int main() {
	//freopen("test.in", "r", stdin);
	int T;
	T = read();
	while(T-- > 0) {
		init();
		solve();
	}
	return 0;
}

夏晓光(loveJY)的博客

case1:讨厌小R

case2:讨厌Yazid

case3:讨厌大R以及case4讨厌zayid

P4688 [Ynoi2016]掉进兔子洞