社区讨论

【求调】悬两关

llcfollower
P6240好吃的题目参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mlj5cxro
此快照首次捕获于
2026/02/12 15:38
7 天前
此快照最后确认于
2026/02/14 22:00
5 天前
查看原帖
题目
nn 个物品，第 ii 个物品有价值 viv_i 和体积 wiw_i，QQ 次询问，每次给出 (l,r,m)(l ,r ,m)，要求从 [l,r][l ,r] 间选出若干个物品（每个物品至多选一次），使得这些物品的体积 ≤m\le m，价值最大，输出每个询问的最大价值，以及达到最大价值的方案数。
Samples\text{Samples}CPP
input:
5
1 5
8 1
1 6
4 10
10 2
5
2 4 1
1 3 6
1 5 10
2 3 5
2 4 4
output:
8 1
9 1
19 2
8 1
8 1
CPP
input:
20
2 3
4 3
3 1
2 2
5 3
1 1
1 1
1 1
2 3
5 1
3 1
4 2
5 2
4 3
2 2
1 3
2 2
2 1
5 3
1 1
20
9 17 2
13 13 1
6 14 4
10 14 2
14 16 5
3 5 2
15 19 5
14 16 4
15 17 1
4 11 5
5 7 4
15 17 3
7 14 1
15 19 5
3 6 4
10 13 1
16 16 1
6 11 2
8 14 3
16 18 2
output:
8 1
0 0
13 1
8 1
6 1
3 1
7 3
4 1
0 0
13 1
6 2
2 2
5 1
7 3
8 1
5 1
0 0
8 1
10 1
2 2
WA code and it needs dalao’s help\text{WA code and it needs dalao's help}
注：能正确求最大价值不能正确求方案数。
CPP
#include <bits/stdc++.h>

#define int long long
#define up(i ,x ,y) for(int i = x ; i <= y ; i ++)
#define dn(i ,x ,y) for(int i = x ; i >= y ; i --)
#define inf 1e18

using namespace std;

inline int read(){int x = 0 ; bool w = 0 ; char ch = getchar();while(!isdigit(ch)) {w |= (ch == '-') ,ch = getchar();}while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48) ,ch = getchar();} return w ? -x : x;}
inline void write(int x){if(x < 0) putchar('-') ,x = -x;if(x > 9) write(x / 10);putchar(x % 10 | 48);}
inline void writesp(int x){write(x) ,putchar(' '); }
inline void writeln(int x){write(x) ,putchar('\n');}

const int N = 2e4 + 10 ,Q = 2e5 + 10 ,V = 505 ,mod = 998244353;
int n ,m ,f[N][V] ,sum[N][V] ,h[N] ,w[N];
struct node{int l ,r ,t ,id;} ;
pair <int ,int> ans[Q];

namespace lolcrying {

	inline bool cmp(node x ,node y){
        return x.r < y.r;  
    } inline void divide(int l ,int r ,vector <node> q){
        if(l == r) {
            for(auto i : q) ans[i.id].first = (i.t >= h[l] ? w[l] : 0) ,ans[i.id].second = (ans[i.id].first ? 1 : 0);
            return ;
        }
        int mid = ((l + r) >> 1);
        vector <node> q1 ,q2 ,q3;
        for(auto i : q) {
            if(i.r <= mid) q1.push_back(i);
            else if(i.l > mid) q2.push_back(i);
            else q3.push_back(i);
        }
        divide(l ,mid ,q1) ,divide(mid + 1 ,r ,q2);
        sort(q3.begin() ,q3.end() ,cmp);
        memset(f[mid + 1] ,0 ,sizeof(f[mid + 1]));
        memset(sum[mid + 1] ,0 ,sizeof(sum[mid + 1]));
        sum[mid + 1][0] = 1;
        dn(i ,mid ,l) {
            up(j ,0 ,500) f[i][j] = f[i + 1][j] ,sum[i][j] = sum[i + 1][j];
            dn(j ,500 ,h[i]) {
            	if(f[i][j] < f[i + 1][j - h[i]] + w[i]) {
            		f[i][j] = f[i + 1][j - h[i]] + w[i];
            		sum[i][j] = sum[i + 1][j - h[i]];
				} else if(f[i][j] == f[i + 1][j - h[i]] + w[i]) {
					sum[i][j] += sum[i + 1][j - h[i]] ,sum[i][j] %= mod;
				}
			}
        }
        int p = mid + 1 ,fr[V] = {0} ,sumr[V] = {0} ,x[V] = {0} ,xsum[V] = {0} ,y[V] = {0} ,ysum[V] = {0};
        sumr[0] = 1;
        for(auto i : q3) {
            while(p <= i.r) {
                dn(j ,500 ,h[p]) {
            		if(fr[j - h[p]] + w[p] > fr[j]) fr[j] = fr[j - h[p]] + w[p] ,sumr[j] = sumr[j - h[p]];
            		else if(fr[j - h[p]] + w[p] == fr[j]) {
            			sumr[j] += sumr[j - h[p]] ,sumr[j] %= mod;
					}
				}
                ++ p;
            }
            up(j ,1 ,500) {
            	if(f[i.l][j] > x[j - 1]) x[j] = f[i.l][j] ,xsum[j] = sum[i.l][j];
				else if(x[j - 1] == f[i.l][j]) x[j] = x[j - 1] ,xsum[j] = xsum[j - 1] + sum[i.l][j];
				else x[j] = x[j - 1] ,xsum[j] = xsum[j - 1];
			}
            up(j ,1 ,500) {
            	if(fr[j] > y[j - 1]) y[j] = fr[j] ,ysum[j] = sumr[j];
				else if(y[j - 1] == fr[j]) y[j] = y[j - 1] ,ysum[j] = ysum[j - 1] + sumr[j];
				else y[j] = y[j - 1] ,ysum[j] = ysum[j - 1];
			}
            int mx = 0 ,res = 0 ;
            up(j ,0 ,i.t){
            	if(x[j] + y[i.t - j] > mx) {
            		mx = x[j] + y[i.t - j] ,res = xsum[j] * ysum[i.t - j];
				} else if(x[j] + y[i.t - j] == mx) res += xsum[j] * ysum[i.t - j] ,res %= mod;
			}
			if(!mx) res = 0 ;
            ans[i.id] = {mx ,res};
        }
    } signed main(){
		
		n = read();
        up(i ,1 ,n) w[i] = read() ,h[i] = read();
		 
        vector <node> que;
    	m = read();
        up(i ,1 ,m) {
            int l = read() ,r = read() ,t = read() ;
            que.push_back({l ,r ,t ,i});
        }

        divide(1 ,n ,que);

        up(i ,1 ,m) writesp(ans[i].first) ,writeln(ans[i].second);

		return 0;
	}
} signed main(){
	
//	freopen("knapsack.in" ,"r" ,stdin);
//	freopen("knapsack.out" ,"w" ,stdout);
	
	int T = 1;
	while(T --) lolcrying :: main();
	return 0;
}

回复

共 0 条回复，欢迎继续交流。

正在加载回复...