首页 > 代码库 > BZOJ1135: [POI2009]Lyz
BZOJ1135: [POI2009]Lyz
1135: [POI2009]Lyz
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 264 Solved: 106
[Submit][Status]
Description
初始时滑冰俱乐部有1到n号的溜冰鞋各k双。已知x号脚的人可以穿x到x+d的溜冰鞋。 有m次操作,每次包含两个数ri,xi代表来了xi个ri号脚的人。xi为负,则代表走了这么多人。 对于每次操作,输出溜冰鞋是否足够。
Input
n m k d ( 1≤n≤200,000 , 1≤m≤500,000 , 1≤k≤10^9 , 0≤d≤n ) ri xi ( 1≤i≤m, 1≤ri≤n-d , |xi|≤10^9 )
Output
对于每个操作,输出一行,TAK表示够 NIE表示不够。
Sample Input
4 4 2 1
1 3
2 3
3 3
2 -1
1 3
2 3
3 3
2 -1
Sample Output
TAK
TAK
NIE
TAK
TAK
NIE
TAK
HINT
Source
题解:
暴力的话是每次构图跑个最大匹配,显然会T。
然后因为只需要判断能否把人全部匹配完了,所以我们有二分图匹配中的hall定理:
Hall定理:
此定理使用于组合问题中,二部图G中的两部分顶点组成的集合分别为X, Y, X={X1, X2, X3,X4,.........,Xm}, Y={y1, y2, y3, y4 ,.........,yn},G中有一组无公共点的边,一端恰好为组成X的点的充分必要条件是:
X中的任意k个点至少与Y中的k个点相邻。(1≤k≤m)
那么有解的条件就是任意一个人的集合的人数<=所连接的鞋子数量
可以看出,当人是连续的时候鞋子所连接数量最少,所以我们只需要判断连续的子序列是否满足题意即可。否则既然连续的都满足题意,那么分开之后一定会有更多的鞋子被连进来。
用 表示鞋号为i的人的个数
那么
令
则
维护t‘i的最长连续子序列 ---zky
代码:
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 25000014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26 int x=0,f=1;char ch=getchar();27 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29 return x*f;30 }31 struct seg{ll l,r,lx,rx,mx,sum;}t[4*maxn];32 ll n,m,kk,d;33 inline void build(int k,int l,int r)34 {35 t[k].l=l;t[k].r=r;int mid=(l+r)>>1;36 t[k].lx=t[k].rx=t[k].mx=-kk;t[k].sum=-(r-l+1)*kk;37 if(l==r)return;38 build(k<<1,l,mid);build(k<<1|1,mid+1,r);39 }40 inline void pushup(int k)41 {42 int l=k<<1,r=k<<1|1;43 t[k].lx=max(t[l].lx,t[l].sum+t[r].lx);44 t[k].rx=max(t[r].rx,t[r].sum+t[l].rx);45 t[k].mx=max(t[l].rx+t[r].lx,max(t[l].mx,t[r].mx));46 t[k].sum=t[l].sum+t[r].sum;47 }48 inline void add(int k,int x,ll y)49 {50 int l=t[k].l,r=t[k].r,mid=(l+r)>>1;51 if(l==r){t[k].sum+=y;t[k].mx=t[k].lx=t[k].rx=t[k].sum;return;}52 if(x<=mid)add(k<<1,x,y);else add(k<<1|1,x,y);53 pushup(k);54 }55 int main()56 {57 freopen("input.txt","r",stdin);58 freopen("output.txt","w",stdout);59 n=read();m=read();kk=read();d=read();60 build(1,1,n);61 while(m--)62 {63 int x=read();ll y=read();64 add(1,x,y);65 printf("%s\n",t[1].mx<=d*kk?"TAK":"NIE");66 }67 return 0;68 }
BZOJ1135: [POI2009]Lyz
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。