总的来说，这套题比昨天的要简单了点。
实际得分： (50+100+100 = 250)
(T1) 赛时的做法在你谷吸氧能得到 (88) 分的好成绩，稍微改改就 (A) 了，你谷数据也太水了吧。
(T2) 稍微推一下 (dp) 的柿子就出来了，用线段树维护也比较容易想到。
(T3) 之前做过，还写过 题解，不在多说。
T1 SZA-Cloakroom
题意描述
有 (n) 件物品，每件物品有三个属性 (a_i b_i, c_i (a_i<b_i))。
再给出 (q) 个询问，每个询问由非负整数 (m, k, s) 组成，问是否能够选出某些物品使得：
-
对于每个选的物品 (i) ，满足 (a_ileq m) 且 (b_i>m+s)。
-
所有选出物品的 (c_i) 的和正好是 (k)。
如果能选出输出 (TAK) 否则输出 (NIE)
数据范围：(nleq 1000, a_i,b_i leq 10^9, c_ileq 1000,kleq 100000)
做法一
这道题的限制比较多，不难想到离线处理。
我们先把所有的询问都离线下来，按 (m_i) 从小到大排一下序，在把所有的物品按 (a_i) 从小到大排一遍序。
我们维护一个序列 (q) 表示当前所有 (a_ileq m) 的物品中按 (b_i) 从大到小的顺序，排名为 (i) 的物品的编号是多少。
设 (f[i][j]) 表示能否在序列 (q) 的前 (i) 个物品中，选若干个物品使得其 (c_i) 总和为 (j) 。
对于每个询问，先把所有的符合条件的物品都加入到序列 (q) 中，然后找出第一个 (b[q[i]] leq m+s) 的 (i), 那么显然如果 (f[i-1][k]) 为 (1) 这个询问的答案为 (TAK) 否则为 (NIE) 。
每加入一个物品都需要重新维护一下 序列 (q[i]) 和 (f[i][j]) ，但维护出 (f[i][j]) 的复杂度为 (O(nk)) 的，所以还要用 (bitset) 优化一下 (f) 的转移。
吸氧就能在你谷过掉了。
做法2（正解）
还是先把询问和物品排一下序。
设 (f[k]) 表示在所有 (a_i leq m) 的物品中，(c) 属性之和为 (k) 的方案中 (b[i]) 的最小值最大是多少。
每加入一个物品，用类似于背包的转移方法就可以维护出 (f[i])。
对于每一个询问，只需要判断 (f[k]) 和 (m+s) 的大小关系即可。
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<bitset>
using namespace std;
const int inf = 1e9+10;
int n,m,num,f[100010],ans[1000010];
struct node
{
int a,b,c;
}e[2010];
struct Query
{
int x,y,k,id;
}q[1000010];
inline int read()
{
int s = 0, w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
bool comp(node a,node b)
{
return a.a < b.a;
}
bool cmp(Query a,Query b)
{
if(a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
void add(int x)
{
for(int j = 100000; j >= e[x].c; j--)
{
f[j] = max(f[j],min(f[j-e[x].c],e[x].b));
}
}
int main()
{
n = read();
for(int i = 1; i <= n; i++)
{
e[i].c = read();
e[i].a = read();
e[i].b = read();
}
sort(e+1,e+n+1,comp);
m = read();
for(int i = 1; i <= m; i++)
{
q[i].x = read();
q[i].k = read();
q[i].y = q[i].x + read();
q[i].id = i;
}
sort(q+1,q+m+1,cmp);
int l = 1; f[0] = inf;
for(int i = 1; i <= m; i++)
{
while(l <= n && e[l].a <= q[i].x) add(l), l++;
ans[q[i].id] = f[q[i].k] > q[i].y;
}
for(int i = 1; i <= m; i++)
{
if(ans[i] == 1) printf("TAK
");
else printf("NIE
");
}
return 0;
}
T2 Bookshelf G
题意描述
当农夫约翰闲的没事干的时候，他喜欢坐下来看书。多年过去，他已经收集了 (N) ((Nleq 10^5))本书 他想造一个新的书架来装所有书。
每本书 (i) 都有宽度 (W(i)) 和高度 (H(i))。书需要按顺序添加到一组书架上；比如说，第一层架子应该包含书籍 (1 ... k)，第二层架子应该以第 (k + 1) 本书开始，以下如此。每层架子的总宽度最大为 (L) ((Lleq 10^9))。每层的高度等于该层上最高的书的高度，并且整个书架的高度是所有层的高度的总和，因为它们都垂直堆叠。
请帮助农夫约翰计算整个书架的最小可能高度。
简化题意：给你一个长度为 (n) 的序列 (w[i])，让你把这个序列分为若干段，满足每段的 (w[i]) 之和都小于 (L) ,最小化每一段的 (h[i]) 的最大值之和。
solution
线段树优化 (dp)。
首先 (O(n^2)) 的 (dp) 方法应该很容易想到。
设 (sum[i]) 表示 (w[i]) 的前缀和， (f[i]) 表示把前 (i) 个物品分成若干段的价值之和最小是多少。
(f[i] = min(f[i],f[j]+max(h[j+1],h[j+2]...h[i]))) （(sum[i]-sum[j]leq m)）
考虑怎么把转移优化一下。
设 (a[i][j] = max(h[j+1],h[j+2]....h[i])) 。
转移方程就可以写成： $f[i] = min(f[i],f[j]+a[i][j]) $。
显然 (a[i][j] = max(a[i-1][j],h[i]))。
设 (ls[i]) 表示第一个大于 (h[i]) 的数所在的位置，可以用单调栈来维护出来。
不难发现，加入第 (i) 个元素时，只会使 ((ls[i],i-1)) 这一段的 (a[i][j]) 变为 (h[i])，其他位置不变为 (a[i-1][j])，相当于是线段树的区间覆盖操作。
之后用线段树维护一下 (f[j]) 和 (f[j]+a[i][j]) 的最小值即可。
code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
const int N = 1e5+10;
const int inf = 1e15+10;
int n,L,res,top;
int h[N],sum[N],sta[N],ls[N];
struct node
{
int lc,rc;
int sum,mx,tag;
}tr[N<<2];
#define l(o) tr[o].lc
#define r(o) tr[o].rc
#define sum(o) tr[o].sum
#define mx(o) tr[o].mx
#define tag(o) tr[o].tag
inline int read()
{
int s = 0, w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
void up(int o)
{
sum(o) = min(sum(o<<1),sum(o<<1|1));
mx(o) = min(mx(o<<1),mx(o<<1|1));
}
void cover(int o,int val)
{
tag(o) = val;
sum(o) = mx(o) + val;
}
void down(int o)
{
if(tag(o))
{
cover(o<<1,tag(o));
cover(o<<1|1,tag(o));
tag(o) = 0;
}
}
void build(int o,int L,int R)
{
l(o) = L, r(o) = R;
if(L == R)
{
sum(o) = mx(o) = inf;
return;
}
int mid = (L + R)>>1;
build(o<<1,L,mid);
build(o<<1|1,mid+1,R);
up(o);
}
void chenge(int o,int l,int r,int val)
{
if(l <= l(o) && r >= r(o))
{
cover(o,val);
return;
}
down(o);
int mid = (l(o)+r(o))>>1;
if(l <= mid) chenge(o<<1,l,r,val);
if(r > mid) chenge(o<<1|1,l,r,val);
up(o);
}
void modify(int o,int x,int val)
{
if(l(o) == r(o))
{
sum(o) = mx(o) = val;
return;
}
down(o);
int mid = (l(o)+r(o))>>1;
if(x <= mid) modify(o<<1,x,val);
if(x > mid) modify(o<<1|1,x,val);
up(o);
}
int query(int o,int l,int r)
{
int res = inf;
if(l <= l(o) && r >= r(o)) return sum(o);
down(o);
int mid = (l(o)+r(o))>>1;
if(l <= mid) res = min(res,query(o<<1,l,r));
if(r > mid) res = min(res,query(o<<1|1,l,r));
return res;
}
signed main()
{
// freopen("b.in","r",stdin);
// freopen("b.out","w",stdout);
n = read(); L = read();
for(int i = 1; i <= n; i++)
{
h[i] = read();
sum[i] = sum[i-1] + read();
}
sta[++top] = 0;
for(int i = 1; i <= n; i++)
{
while(top && h[sta[top]] <= h[i]) top--;
ls[i] = sta[top]; sta[++top] = i;
}
build(1,0,n);
modify(1,0,0);
for(int i = 1; i <= n; i++)
{
chenge(1,ls[i],i-1,h[i]);
int pos = lower_bound(sum,sum+n+1,sum[i]-L)-sum;
res = query(1,pos,i-1);
modify(1,i,res);
}
printf("%lld
",res);
return 0;
}