首页 > 其他分享 >P3537 [POI2012]SZA-Cloakroom 题解

P3537 [POI2012]SZA-Cloakroom 题解

时间:2022-12-26 19:45:56浏览次数:47  
标签:tmp now const leq POI2012 题解 Cloakroom int include

题目大意

有 \(n\) 件物品,每件物品有三个属性 \(a_i, b_i, c_i (a_i < b_i)\)。

再给出 \(q\) 个询问,每个询问由非负整数 \(m, k, s\)组成,问是否能够选出某些物品使得:

  1. 对于每个选的物品 \(i\),满足 \(a_i \leq m\) 且 \(b_i > m + s\)。

  2. 所有选出物品的 \(c\) 的和正好是 \(k\)。

分析

如果没有 \(a_i \leq m\) 且 \(b_i > m + s\) 的条件,明显是个背包。

然而有这两个限制就不好办了。我们可以先把询问离线下来,按照 \(m\) 排序(当然 \(a_i\) 也要排序),这样就把二维偏序转化成了一维。(大概可以这样理解)。

接下来,我们需要判断在 \(\forall a_i \leq m\) 和 \(\sum c_i = k\) 满足后 \([\forall b_i > m + s]\) 是否成立。

这个也很好办。我们只需要将背包状态设为 \(f_i\) 表示背包容积(即放入的 \(c\))大小为 \(i\) 时 \(b\) 的最小值的最大值。只要这个最小值比 \(m + s\) 大,那么就一定合法,否则一定不合法。

最后一定注意输入顺序是 \(c, a, b\) 而不是 \(a, b, c\)!

参考代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 1010, M = 1000010;
struct Node {
    int a, b, c;
    bool operator < (const Node& tmp)const {
        return a < tmp.a;
    }
}p[N];
struct Queries {
    int m, k, s, id;
    bool operator < (const Queries& tmp)const {
        return m < tmp.m;
    }
}q[M];
int f[100010];
int n, m;
bool ans[M];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
        scanf("%d%d%d", &p[i].c, &p[i].a, &p[i].b);
    sort(p + 1, p + n + 1);
    scanf("%d", &m);
    for (int i = 1; i <= m; i ++ )
        scanf("%d%d%d", &q[i].m, &q[i].k, &q[i].s),
        q[i].id = i;
    sort(q + 1, q + m + 1); // 将限制 A 消除

    int now = 1; f[0] = 0x3f3f3f3f;
    for (int i = 1; i <= m; i ++ ) {
        while (now <= n && p[now].a <= q[i].m) {
            for (int j = 100000; j >= p[now].c; j -- )
                f[j] = max(f[j], min(f[j - p[now].c], p[now].b)); // 背包满足限制 C
            now ++ ;
        }
        if (f[q[i].k] > q[i].m + q[i].s) ans[q[i].id] = true; // 判断限制 B 是否满足
    }

    for (int i = 1; i <= m; i ++ )
        puts(ans[i] ? "TAK" : "NIE");
    return 0;
}

标签:tmp,now,const,leq,POI2012,题解,Cloakroom,int,include
From: https://www.cnblogs.com/LcyRegister/p/17006672.html

相关文章

  • P4928 [MtOI2018]衣服?身外之物! 题解
    题意gcd共有\(n\)件衣服,编号为\(A_1,A_2,\cdotsA_n\)。每一件衣服分别拥有颜色值和清洗时间,他在每一件衣服穿完以后都会将其送去清洗,而这件衣服当天所拥有的舒适感......
  • NSIS编辑时的乱码问题解决方法
    在Windows中文系统中,HMNISEdit下使用非中文和英文,比如韩文、日语或者阿拉伯语等。会发现编辑的文字变成乱码或者问号。     1、在安装的过程中显示乱码。2、......
  • AcWing291.蒙德里安的梦想题解
    题解:蒙德里安的梦想注:本题解内容简陋,多有不周,敬请谅解。如果有问题请在评论区留言。谢谢。由于作者能力有限,这篇题解不会给出太严谨的证明,只是旨在帮助大家更好地理解此......
  • AcWing83场周赛题解
    第一题、奇偶题目链接:https://www.acwing.com/activity/content/problem/content/7862/比较麻烦(本人做法)找出不同字符个数,再判断。#include<iostream>usingnamespac......
  • 洛谷P4146 序列终结者 题解 splay tree
    题目链接:https://www.luogu.com.cn/problem/P4146题目大意:支持:区间更新(+x)区间翻转区间查询(最大值)解题思路:几乎和AcWing2437.Splay这题一模一样。示例程序:#inc......
  • Codeforces 983 D Arkady and Rectangles 题解
    题目链接挺有意思的数据结构题,题面看着像个板子,其实还是有不少学问的。平面上一堆矩形的题目常见套路就是对\(x\)轴扫描线,\(y\)轴线段树维护,这题也不例外。我们先对坐标......
  • CF732D Exams 题解
    题目链接题目分析:首先可以发现,如果当前第\(i\)天可以完成所有考试,那么第\(i+1\)天一定也可以。因此,答案具有单调性。考虑二分,将原问题转换为判定性问题。判定是否......
  • AT_jag2018summer_day2_a 10^N+7 题解
    题目传送门题目大意有三个非负整数$x,y,z$,找到符合以下条件的最小非负整数\(n\);$n\{\rm\mod}\10^1+7\=\x$$n\{\rm\mod}\10^2+7\=\y$$n\{\rm\mo......
  • CF864C Bus 题解
    题目传送门题目大意一辆汽车从\(0\)到\(a\)往返\(k\div2\)次(也就是去算一次,回算一次);原来有\(b\)升油,每行驶一单位距离消耗一升油,在\(f\)有加油站(可以加满油......
  • UVA13197 Cuberoot This 题解
    题目传送门题目大意求满足\(x^3\bmodp=a\)且\(x<p\)的数\(x\),升序输出。解题思路在\(0\)到\(p-1\)的范围内,查找满足条件的\(x\);值得注意的是,输出要留意:最......