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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[ICPCCamp2015]IQ Test  

2015-03-12 15:53:35|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

IQ Test

题意:
给你n个问题,每次都是问AorB有多少个,你可以选A或B,最后求一个最多能答对多少道题
注意:
千万要尽量避免写队列,尤其是n个队列,很容易被卡常数。
提交前一定要测试一下极限数据!

#include<cstdio>
#include<cstdlib>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 2E5+10;
int n,m,pn,T[2],ans;
int scan(){int i=0;scanf("%d",&i);return i;}
int tree[N];
struct Point{
int x,y,t;
Point(int a=0,int b=0,int tt=0){x=a;y=b;t=tt;}
}point[N*2],dp[2][N*2];
bool operator < (const Point&a,const Point&b){
if(a.x-a.y!=b.x-b.y)return a.x-a.y < b.x-b.y;
return a.x < b.x;
}
void push(int x,int val){for(x++;x<=n+1;x+=x&-x)tree[x]=max(tree[x],val);}
int get(int x){int re=0;for(x++;x;x-=x&-x)re=max(re,tree[x]);return re;}
int main(){
//freopen("in.txt","r",stdin);
int i,a,b;char cc;
n = scan();
for(i=1;i<=n;i++){
scanf(" %c",&cc);
a = scan();b = scan();
if(cc=='B')a=i-1-a,b=i-1-b;
//0
if(0<=a&&a<=i-1)point[++pn]=Point(i-1,a,0);
//1
if(0<=b&&b<=i-1)point[++pn]=Point(i-1,b,1);
}
sort(point+1,point+1+pn);
int pi=1,p[2]={};
Point *pp;
for(i=0;i<=n;i++){
for(;point[pi].x-point[pi].y==i && pi<=pn;pi++){
int x = point[pi].x,y = point[pi].y;
while(p[0] <= T[0]){
pp = &dp[0][p[0]];
if(pp->x-pp->y > i)break;
if(pp->x-pp->y == i && pp->x > x)break;
push(pp->y,pp->t);
p[0]++;
}
while(p[1] <= T[1]){
pp = &dp[1][p[1]];
if(pp->x-pp->y > i)break;
if(pp->x-pp->y == i && pp->x > x)break;
push(pp->y,pp->t);
p[1]++;
}
a = get(y)+1;
ans = max(ans,a);
if(!point[pi].t){//A
dp[0][++T[0]]=Point(x+1,y+1,a);
}else{//B
dp[1][++T[1]]=Point(x+1,y+0,a);
}
}
}
printf("%d\n",ans);
return 0;
//return clock()-start;
}

题解:
数据结构+DP
因为只有两种选项,所以可以把B的都转成A的问题。
然后就得到O(n^2)dp[i][j]表示回答到了第i个问题,选了j个A,最多回答对的问题。
然后可以发现+1的部分非常少,把这些考虑为关键的事件点,用数据结构直接维护事件点的转移。
注意要先以i-j为第一关键字,i为第二关键字排序,然后每次查询是 小于等于某个i并且已经被加入的点 ,用树状数组维护一下就好了
  评论这张
 
阅读(2)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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