Rockdu's Blog

题目描述

The annual rich citizen's reunion is taking place in Byteotia.

They meet to boast about their incomes, Lebytene's shoes and other luxuries.

Naturally, not all these objects of pride are carried into the banquet - coats, jackets, umbrellas and such are left in the cloakroom, and picked up upon leave.

Unfortunately for the well off, a gang of Byteotian thieves plans to break into the cloakroom and steal part of the items stored therein.

At this very moment the gang's leader is examining the plans of the robbery put forward by other gang members (they are a democratic lot!).

A plan typically looks as follows: the thieves break into the cloakroom at time m_jmj​ , take items worth exactly k_jkj​and escape, where the whole heist takes them s_jsj​ time.

The gang leader would first of all like to know which of these plans are feasible and which are not.

A plan is feasible if at time m_jmj​ it is possible to collect items of total value k_jkj​ in such a way that up to the very m_j+s_jmj​+sj​ moment no one shows up to retrieve any of the stolen goods (in such event, they would notify security, and the robbery would fail).

In particular, if at time m_jmj​ it is impossible to select items of exact total worth k_jkj​ , then the plan is infeasible and consequently rejected.

Knowing the drop off and retrieval times for each item, determine which plans are feasible and which are not.

We assume that an item left in the cloakroom the moment a robbery starts can already be stolen (see the example).

有n件物品，每件物品有三个属性a[i], b[i], c[i] (a[i]<b[i])。

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

1. 对于每个选的物品i，满足a[i]<=m且b[i]>m+s。

2. 所有选出物品的c[i]的和正好是k。

输入输出格式

输入格式：

In the first line of the standard input there is a single integer $n$ ( $1\le n\le 1000$ ) denoting the number of items that will be left in the cloakroom.

Those items are described in the $n$ lines that follow.

Each of those lines consists of three integers c_ici​ , a_iai​ , and b_ibi​ ( 1\le c_i\le 1\ 0001≤ci​≤1 000 , 1\le a_i<b_i\le 10^91≤ai​<bi​≤109 ), separated by single spaces, that denote respectively: the item's value, the moment it is left in the cloakroom, and the moment it will be retrieved by the owner.

The next line holds an integer $p$ ( $1\le p\le 1000000$ ),the number of plans the gang came up with. Each is specified in a separate line by three integers, m_jmj​ , k_jkj​ and s_jsj​ ( 1\le m_j\le 10^91≤mj​≤109 , 1\le k_j\le 100\ 0001≤kj​≤100 000 , 0\le s_j\le 10^90≤sj​≤109 ), separated by single spaces, that denote respectively: the moment the thieves would enter the cloakroom, the value of goods they would like to steal, and the time the robbery would take them.

In test worth 16% of the total points $p\le 10$ holds in addition.

n some other tests, also worth 16% of the points, all the items have the same a_iai​ values.

In yet other tests, worth 24% of the points, all the queries share the same s_jsj​ value.

输出格式：

For each plan put forward by the gang determine if it is feasible, i.e., whether it is possible to steal items of total worth exactly k_jkj​ and escape before anyone asks for their belongings.

If the plan is feasible, your program should print the word TAK (Polish for yes) on the standard output, otherwise it should print NIE (Polish for no).

输入输出样例

5
6 2 7
5 4 9
1 2 4
2 5 8
1 3 9
5
2 7 1
2 7 2
3 2 0
5 7 2
4 1 5

TAK
NIE
TAK
TAK
NIE

说明

有n件物品，每件物品有三个属性a[i], b[i], c[i] (a[i]<b[i])。

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

1. 对于每个选的物品i，满足a[i]<=m且b[i]>m+s。

2. 所有选出物品的c[i]的和正好是k。

不是很板的DP题。一个数能不能被凑出的问题目前已知的方法应该只有背包(最多bitset优化)。我们考虑把所有物品按a[i]排序，询问离线下来按m排序。这样之后我们要满足条件a[i]<=m，就只需要询问和物品同时往后挪，按照这个顺序一个一个把物品加入就行了。然后我们考虑b[i]>m+s这个条件，发现01背包的复杂度浪费太多。可不可以不计01节约空间呢？我们考虑只维护一维dp[j]表示当前能凑出j的最小的b[i]是多少，每一次遇到物品就用这个物品转移，遇到询问就直接比较dp[c[i]]和b[i]，这样我们就可以一边做DP一边处理询问。总复杂度O(n*k)，感觉这题有点卡常。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cctype>
#define For(i, a, b) for(register int i = a; i <= b; ++i)
#define Down(i, a, b) for(register int i = a; i >= b; --i)
using namespace std;
const int maxn = 1e3 + 5, maxm = 1e6 + 5, maxk = 1e5 + 5, K = 1e5;
struct Q {
    int a, b, c, id;
    bool operator < (const Q &A) const {return a < A.a;}
};
Q qs[maxm];
Q itm[maxn];
int n, m, a, b, c, dp[maxk], ans[maxm];
int qcnt = 1, icnt = 1;

void read(int & x) {
    static char c = getchar(); x = 0;
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
}

int main() {
    scanf("%d", &n);
    For(i, 1, n) read(itm[i].c), read(itm[i].a), read(itm[i].b);
    sort(itm + 1, itm + n + 1);
    scanf("%d", &m);
    For(i, 1, m) {
        read(a), read(c), read(b);
        qs[i] = (Q){a, a + b, c, i};
    }
    sort(qs + 1, qs + m + 1), dp[0] = 0x3f3f3f3f;
    For(i, 1, m) {
        while(icnt <= n && itm[icnt].a <= qs[i].a) {
            Down(k, K, itm[icnt].c) 
                dp[k] = max(dp[k], min(dp[k - itm[icnt].c], itm[icnt].b));
            ++icnt;
        }
        ans[qs[i].id] = dp[qs[i].c] > qs[i].b;
    }
    For(i, 1, m) printf("%s\n", ans[i] ? "TAK" : "NIE");
    return 0;
}

5
6 2 7
5 4 9
1 2 4
2 5 8
1 3 9
5
2 7 1
2 7 2
3 2 0
5 7 2
4 1 5

TAK
NIE
TAK
TAK
NIE