【HDU5808 BestCoder Round 86E】【时间排序 树状数组计数 bitsetDP 或分治】Price List Strike Back 距离范围、区间范围商店购物 使得价值和恰为m

本文主要是介绍【HDU5808 BestCoder Round 86E】【时间排序 树状数组计数 bitsetDP 或分治】Price List Strike Back 距离范围、区间范围商店购物 使得价值和恰为m，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在Byteland一共有$n$家商店，编号依次为$1$到$n$。每家商店只会卖一种物品，其中第$i$家商店的物品单价为v_iv​i​​，且它到Byteasar的家的距离为d_id​i​​。Byteasar每天都会进行一次购物，第$i$天他会选择一个区间[l_i,r_i][l​i​​,r​i​​]，并给自己设定一个距离上限c_ic​i​​，然后他会在编号在该区间内每家到自己家的距离不超过c_ic​i​​的商店购买最多一件物品，当然他也可以选择什么都不买。回家之后，Byteasar会把今天购物所花的钱的总数sum_isum​i​​记录在账本上。Byteasar的数学不好，他可能会把花的钱记错。请写一个程序，帮助Byteasar判断每条记录是否一定是错的。注意：记多或者记少都算记错。

输入的第一行包含一个正整数$T(1\le T\le 10)$，表示测试数据的组数。对于每组数据，第一行包含两个正整数$n,m(1\le n\le 20000,1\le m\le 100000)$，表示商店的个数和记录的个数。第二行包含$n$个正整数v_i(1\leq v_i\leq 100)v​i​​(1≤v​i​​≤100)，依次表示每家商店的物品的单价。第三行包含$n$个正整数d_i(1\leq d_i\leq 10^9)d​i​​(1≤d​i​​≤10​9​​)，依次表示每家商店到Byteasar的家的距离。接下来$m$行，每行包含四个整数l_i,r_i,c_i,sum_i(1\leq l_i\leq r_i\leq n,1\leq c_i\leq 10^9,1\leq sum_i\leq 100)l​i​​,r​i​​,c​i​​,sum​i​​(1≤l​i​​≤r​i​​≤n,1≤c​i​​≤10​9​​,1≤sum​i​​≤100)，表示一条记录。

对于每组数据，输出一行$m$个字符，依次回答每个询问。如果一定记错了，请输出'1'，否则输出'0'。

2
3 3
3 3 3
2 4 3
3 3 5 3
3 3 3 1
2 3 1 3
5 4
5 1 2 4 2
1 8 9 2 1
1 5 1 3
4 4 1 5
1 5 3 5
1 3 5 1

011
1101

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 2e4 + 10, M = 1e5 + 10, Z = 1e9 + 7, ms63 = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n, m;
int v[N], d[N];
struct Q
{int l, r, dis, sum, o;bool operator < (const Q&b)const{return dis < b.dis;}
}q[M];
struct A
{int v, d, p;bool operator < (const A&b)const{return d < b.d;}
}a[N];
struct BIT
{int c[N];void init(){memset(c, 0, (n + 2) * 4);}void add(int x){for (; x <= n; x += x&-x)++c[x];}int check(int x){int ret = 0;for (; x; x -= x&-x)ret += c[x];return ret;}
}bit[105];
bitset<101>dp[2];
bool check(int l, int r, int m)
{if (bit[m].check(r) - bit[m].check(l - 1))return 1;dp[0].reset(); dp[0][0] = 1;int now = 0; int nxt = 1;for (int i = 1; i < m; ++i){int have = bit[i].check(r) - bit[i].check(l - 1);int need = m / i;int g = min(have, need);if (m % i == 0 && m / i == g)return 1;g *= i; int w = i;while (g){dp[nxt] = dp[now] | (dp[now] << w);if (dp[nxt][m])return 1;if (!(dp[nxt] ^ dp[now]).count())break;now ^= 1; nxt ^= 1;g -= w;w = min(w << 1, g);}}//单组复杂度不超过min(100 * 8, 200 * 100 /32)return 0;
}
char ans[M];
int main()
{scanf("%d", &casenum);for (casei = 1; casei <= casenum; ++casei){scanf("%d%d", &n, &m);for (int i = 1; i <= 100; ++i)bit[i].init();for (int i = 1; i <= n; ++i)scanf("%d", &a[i].v);for (int i = 1; i <= n; ++i)scanf("%d", &a[i].d), a[i].p = i;sort(a + 1, a + n + 1);for (int i = 1; i <= m; ++i){scanf("%d%d%d%d", &q[i].l, &q[i].r, &q[i].dis, &q[i].sum);q[i].o = i;}sort(q + 1, q + m + 1);int l = 1;for (int i = 1; i <= m; ++i){while (l <= n&&a[l].d <= q[i].dis){bit[a[l].v].add(a[l].p);++l;}ans[q[i].o] = !check(q[i].l, q[i].r, q[i].sum) + '0';}ans[m + 1] = 0;puts(ans + 1);}return 0;
}
/*
【trick&&吐槽】
这题其实暴力可以水过去，参照luras_oil2 = =#【题意】
有n（20000）个商店，第i个商店距离家的位置为d[i]（1e9），卖的物品的价值为v[i]（100）
有m（1e5）个询问（l,r,c,sum）
问你，如果对[l,r]内，距离我家距离不超过dis的商店做购物（可以对于v[l~r]的每一者选择或不选择），
能否能够恰好使得商品总价值为sum【类型】
离线询问 双指针 树状数组 + bitsetDP【分析】
首先，因为涉及到一个距离的影响。
我们要把距离的影响消掉，所以可以考虑对——
"所有商店距离家的距离"
"所有询问距离家的距离"
这两样东西按照升序排序，这样我们就可以使得，在处理一个询问的时候，我们只考虑了所有距离范围内的商店。
过程中需要用树状数组维护前缀和，用于求出区间范围内某种价值的物品有多少件。然后开始处理询问了——
1，树状数组的查询量最多为m*100*log(n)，复杂度为1e8
2，然后我们做DP，这里的状态转移是f[i]|=f[i-物品价值]，这个显然可以用bitsetDP实现。这里需要一些优化，对于背包上限为m，物品价值为i，显然物品数量最多为m/i这样子的话，我们背包的大小最多只会为m/1+m/2+...+m/m为mlogm级别（即800左右）这时做bitsetDP的复杂度上限为800 * 100 / 32，复杂度为m * 800 * 3，复杂度为2e8我们可以用二进制拆分再次优化。或者在bitsetDP的时候，DP的终止条件为我们用当前的物品无法再更新出甚至这两个优化可以加在一起。不过不论怎么写都可以过的啦。【时间复杂度&&优化】
O(3e8)CSY的标解做法是分治。*/

这篇关于【HDU5808 BestCoder Round 86E】【时间排序 树状数组计数 bitsetDP 或分治】Price List Strike Back 距离范围、区间范围商店购物 使得价值和恰为m的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！