题解 | #活动#

C题：活动

解析：

1. O(n²)：暴力

很容易联想到完全背包，但又有些许不同。因为每次放的时候要看目前总重量，我们就记为 j ；然后要再选一个物品，这个物品就记作 i ；即 F[j] 意味着总重量为 j 时的方案数，且下面要选的物品是 i 。要注意的是，i 为所选物品，要作为阶段放在外面。

首先，易得 1<=i<=j , i!=y 且 i>=j （题目的特殊要求）, j+i<=x (最多放满) . 那么，又选了个 i ，总重量就为 j+i ,即 F[j] -> F[j+i] += F[j]. F[1] 赋初值为 1 。

然后就可以愉快地写代码了。

#include<cstdio>
using namespace std;
const int N=1e5+5,P=998244353;
int n,x,y,f[N];
int main() {
	scanf("%d%d%d",&n,&x,&y);
    f[0]=1;
    for(int i=1;i<=n;++i)
       if(i!=y)
          for(int j=0;i>=j&&j+i<=x;++j)
             f[j+i]=(f[j+i]+f[j])%P;
    printf("%d",f[x]);
	return 0;
}

分数：65 ~ 75 分（不同的写法，不同的输入，不同的分数）

2.O(n)：前缀和优化后的正解

注意 F[j+i] += F[j], 即为 F[j] += F[j-i] ，就是每一个 k(枚举前一个重量) + i(选的物品) = j(现在的重量).

根据题目限制，j-i<=j/2 , 也就是 i <= j/2 (注意，这里要上取整). 因为 k = j - i > 0, 所以 i < j. 于是 i 的范围即为 j/2 <= i <= j. 这样就可以把第一维度完全弄掉，取而代之用前缀和维护（内层循环就变成唯一一层循环了）。设 sum[i] = F[0] + F[1] +...+ F[i], 即重量小于等于 i 的方案数。

F[j] += F[j-i] (j-i<=j/2)，就变成了 F[j] = F[0] + F[1]+...+F[j/2] = sum[j/2].

但要注意两点：

(1). k + i = j , 其中 j - k = i <= n. 如果 j <= n ,那以上等式一定成立；但如果 j > n, 那就不一定了：对于一些较小的 k , j - k > n . 此时 k < j - n, 也就是 k <= j - n - 1. 所以，对于所有 k <= j - n - 1 的情况，都是多算的不合法的情况，应当舍去。而这些 k 所组成的 F[k] 之和，就是 F[0] + F[1] +...+ F[j-n-1] = sum[j-n-1] , 即当 j > n 时，F[j] = sum[j/2] -sum[j-n-1].

(2). 有可能 sum[i/2] 把 y 所参与的 k 也算进去了。我们要认识到，y 是增长的量，也就是上文的 i ，所以 k + y = j，k = j - y. 由于 i 的取值范围是 j/2 <= i <= j ，如果 y 在这个范围内，j/2 <= y <= j, 就说明我们把 y 也算进去了。那么，多的那个 F[k] ,就是 F[j-y] ，去掉即可。所以，当 j/2 <= y <= j 时， F[j] = sum[j/2] - F[j-y].

但是，这两者可能有交集，所以要先把 F[j] 赋值为 sum[j/2]，再对应减去多余的部分。

C++ 取模时，为避免结果变成负数，减法要先加后模，即 ans = (a1 - a2 + P) % P.

下面就可以写代码啦( 前缀和要赋初值为 F[0], 而 F[0] = 1 )：

#include<cstdio>
#include<cmath>
using namespace std;
const int N=1e5+5,P=998244353;
int n,x,y,f[N],sum[N];
int main() {
	scanf("%d%d%d",&n,&x,&y);
	f[0]=1,sum[0]=f[0];
	for(int j=1; j<=x; ++j) {
		f[j]=sum[j/2];//总更新
		if(j>n) f[j]=(f[j]-sum[j-n-1]+P)%P;//情况一
		if(y>=ceil(j/2.0)&&y<=j) f[j]=(f[j]-f[j-y]+P)%P;//情况二
		sum[j]=(sum[j-1]+f[j])%P;//前缀和
	}
	printf("%d",f[x]);
	return 0;
}