限制是a[i]<=m，b[i]>m+s，c[i]和为k 考虑到k<=100000，而a,b都很大，可以转化一下，变成询问是否有c[i]和为k，a[i]<=m，b[i]的最小值>m+s的情况，那么就可以按照询问的m排序，做一个DP
code:
#include<set>#include<map>#include<deque>#include<queue>#include<stack>#include<cmath>#include<ctime>#include<bitset>#include<string>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<climits>#include<complex>#include<iostream>#include<algorithm>#define ll long long#define lowbit(x) x&(-x)using namespace std;void read(int &x){ char c; while(!((c=getchar())>='0'&&c<='9')); x=c-'0'; while((c=getchar())>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0';}void up(int &x,int y){if(x<y)x=y;}void down(int &x,int y){if(x>y)x=y;}const int maxn = 1100;const int maxm = 1100000;struct qu{ int m,k,s,i;}q[maxm]; int m;struct node{ int a,b,c;}a[maxn]; int n;bool cmp(node x,node y) { return x.a<y.a; }bool cmpq(qu x,qu y) { return x.m<y.m; }int v[110000];bool ans[maxm];int main(){ memset(ans,true,sizeof ans); int mx=0,mxk=0; read(n); for(int i=1;i<=n;i++) { read(a[i].c); read(a[i].a); read(a[i].b); up(mx,a[i].b); }sort(a+1,a+n+1,cmp); read(m); for(int i=1;i<=m;i++) { q[i].i=i; read(q[i].m); read(q[i].k); read(q[i].s); up(mxk,q[i].k); if((ll)q[i].m+q[i].s>(ll)mx) ans[i]=false; }sort(q+1,q+m+1,cmpq); memset(v,0,sizeof v); v[0]=mx; int nw=1; for(int i=1;i<=n;i++) { while(nw<=m) { if(!ans[q[nw].i]) nw++; else if(q[nw].m<a[i].a) { ans[q[nw].i]=v[q[nw].k]>(q[nw].m+q[nw].s); nw++; } else break; } if(nw>m) break; for(int j=mxk;j>=a[i].c;j--) up(v[j],min(v[j-a[i].c],a[i].b)); } while(nw<=m) { if(!ans[q[nw].i]) nw++; else ans[q[nw].i]=v[q[nw].k]>(q[nw].m+q[nw].s),nw++; } for(int i=1;i<=m;i++) { if(ans[i]) PRintf("TAK/n"); else printf("NIE/n"); } return 0;}新闻热点
疑难解答
