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

时间:2021-09-23 19:32:24

Price List Strike Back

  Accepts: 2  Submissions: 51 Time Limit: 6000/3000 MS (Java/Others)  Memory Limit: 262144/131072 K (Java/Others)
问题描述
在Byteland一共有nn家商店,编号依次为11nn。每家商店只会卖一种物品,其中第ii家商店的物品单价为v_ivi,且它到Byteasar的家的距离为d_idi

Byteasar每天都会进行一次购物,第ii天他会选择一个区间[l_i,r_i][li,ri],并给自己设定一个距离上限c_ici,然后他会在编号在该区间内每家到自己家的距离不超过c_ici的商店购买最多一件物品,当然他也可以选择什么都不买。回家之后,Byteasar会把今天购物所花的钱的总数sum_isumi记录在账本上。

Byteasar的数学不好,他可能会把花的钱记错。

请写一个程序,帮助Byteasar判断每条记录是否一定是错的。

注意:记多或者记少都算记错。
输入描述
输入的第一行包含一个正整数T(1\leq T\leq 10)T(1T10),表示测试数据的组数。

对于每组数据,第一行包含两个正整数n,m(1\leq n\leq 20000,1\leq m\leq 100000)n,m(1n20000,1m100000),表示商店的个数和记录的个数。

第二行包含nn个正整数v_i(1\leq v_i\leq 100)vi(1vi100),依次表示每家商店的物品的单价。

第三行包含nn个正整数d_i(1\leq d_i\leq 10^9)di(1di109),依次表示每家商店到Byteasar的家的距离。

接下来mm行,每行包含四个整数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)li,ri,ci,sumi(1lirin,1ci109,1sumi100),表示一条记录。
输出描述
对于每组数据,输出一行mm个字符,依次回答每个询问。如果一定记错了,请输出'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的标解做法是分治。

*/