注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1926][Sdoi2010]粟粟的书架  

2015-01-28 21:46:48|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1926: [Sdoi2010]粟粟的书架

相当于两道水题合集
磨磨蹭蹭写了2h……我好弱
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 5E5+10;
const int M = 200+10;
const int VAL = 1000+10;
const int P = N*21;
typedef long long ll;
int n,m,T,K,ROOT,mval;
int sum[VAL][M][M],num[VAL][M][M],data1[M][M];
int lson[P],rson[P],tree[2][P],data2[N],tn[N];
int swap(int&a,int&b){a^=b,b^=a,a^=b;}
int insert(int oldr,int x){
int ro = ++T,l=1,r=1000,re=ro;
tree[0][ro] = tree[0][oldr] + x;
tree[1][ro] = tree[1][oldr] + 1;
while(l<r){
int mid = (l+r)/2;
if(x <= mid){
rson[ro] = rson[oldr];
ro = lson[ro] = ++T;
oldr = lson[oldr];
r = mid;
}else{
lson[ro] = lson[oldr];
ro = rson[ro] = ++T;
oldr = rson[oldr];
l = mid+1;
}
tree[0][ro] = tree[0][oldr] + x;
tree[1][ro] = tree[1][oldr] + 1;
}
return re;
}
int ask(int lr,int rr,int hi){
int l=1,r=1000,ll,re=0,tmp;
while(l<r){
int mid = (l+r)/2;
tmp = tree[0][rson[rr]]-tree[0][rson[lr]];
if(tmp >= hi){
lr = rson[lr];rr = rson[rr];
l = mid+1;
}else{
hi -= tmp;re += tree[1][rson[rr]]-tree[1][rson[lr]];
lr = lson[lr];rr = lson[rr];
r = mid;
}
}
ll = l;tmp = tree[0][rr]-tree[0][lr];
re += tree[1][rr] - tree[1][lr];
if(tmp < hi)return -1;
l = 0;r = tree[1][rr]-tree[1][lr];
while(l<r){
int mid = (l+r+1)/2;
if(tmp - mid*ll>= hi)l = mid;
else r = mid-1;
}
return re - l;
}
int scan(){
char cc=' ';int re=0,fh=1;while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){re=re*10+cc-'0';cc=getchar();}return re*fh;
}
void solve1(){
int i,j,k,x[2],y[2],hi,tmp;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
data1[i][j] = scan();
if(data1[i][j] > mval)mval = data1[i][j];
}
for(k=mval;k>=0;k--){
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
sum[k][i][j] = sum[k][i][j-1] + sum[k][i-1][j] - sum[k][i-1][j-1];
num[k][i][j] = num[k][i][j-1] + num[k][i-1][j] - num[k][i-1][j-1];
if(data1[i][j] > k){
sum[k][i][j] += data1[i][j];
num[k][i][j] += 1;
}
}
}
while(K--){
x[0]=scan();y[0]=scan();
x[1]=scan();y[1]=scan();
hi = scan();
int l,r;
l = -1,r = mval;
while(l < r){
int mid = (l+r+1)/2;
tmp = sum[mid][x[1]][y[1]] - sum[mid][x[0]-1][y[1]] - sum[mid][x[1]][y[0]-1] + sum[mid][x[0]-1][y[0]-1];
if(tmp>=hi)l = mid;
else r = mid-1;
}
if(l == -1)printf("Poor QLW\n");
else{
int ll=l+1,ans;
ans = num[l][x[1]][y[1]] - num[l][x[0]-1][y[1]] - num[l][x[1]][y[0]-1] + num[l][x[0]-1][y[0]-1];
tmp = sum[l][x[1]][y[1]] - sum[l][x[0]-1][y[1]] - sum[l][x[1]][y[0]-1] + sum[l][x[0]-1][y[0]-1];
r = num[l+1][x[1]][y[1]] - num[l+1][x[0]-1][y[1]] - num[l+1][x[1]][y[0]-1] + num[l+1][x[0]-1][y[0]-1];
r = ans - r;l = 0;
while(l<r){
int mid = (l+r+1)/2;
if(tmp - mid*ll >= hi)l = mid;
else r = mid-1;
}
printf("%d\n",ans-l);
}
}
}
void solve2(){
int i,j,a,b,hi;
tn[0] = ++T;lson[ROOT] = rson[ROOT] = tn[0];
swap(n,m);
for(i=1;i<=n;i++){
data2[i] = scan();
tn[i] = insert(tn[i-1],data2[i]);
}
while(K--){
scan();a=scan();scan();b=scan();
hi = scan();
a = ask(tn[a-1],tn[b],hi);
if(a<0)printf("Poor QLW\n");
else printf("%d\n",a);
}
}
int main(){
//printf("%.3f\n",(sizeof(sum)*2+sizeof(tree)*2)/1024.0/1024);
freopen("in.txt","r",stdin);
int i,j;
n = scan();m = scan();K = scan();
if(n!=1) solve1();
else solve2();
return 0;
}

题解:
贪心:必然先选大的
对于前面的50%
直接暴力1000次预处理出每个位置的二维前缀和,然后对于每个询问二分答案
对于后面的50%
建主席树之后在上面二分答案
二分的是选的最小的值
然后最后还要二分一下最小的这个值选多少个
  评论这张
 
阅读(179)| 评论(4)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017