今天下午整了个线段树
http://acm.hdu.edu.cn/showproblem.php?pid=1698按照模板打了一遍
然后想做这道
http://acm.hdu.edu.cn/showproblem.php?pid=1754也是比较简单的线段树
想了很久才想出思路来，打好代码结果连sample都通不过，发现想是query那里错了
但是时间到6点了，有DIY，我也先放下，去做DIY
http://acm.hdu.edu.cn/diy/contest_show.php?cid=2081密码ac
是斌仔出的
第一道是数学题
我想了好点时间才想出方法并证明了，第一次这么有条理的思考，呵呵，赛后还写了解题报告
http://www.cppblog.com/notonlysuccess/archive/2009/02/11/73510.html第二道是大数比较，是这些题目中最水的了。。。
规模不大直接暴力就好过的，就算大的话用二分也行
不过我大数不太行，调试了好久才AC，汗。。。。。
第三道是经典的矩阵的DP
2维的转化成n(n+1)/2个一维的求最大就行了
第四道是最小生成树，不会
线段树掌握后一定要解决这个问题~~~！！
第五道是搜索
哈哈，这道题目有意思，我抓住了A和C的本质区别，A中间的空格广搜出去一定全找到*，而其他的则会越界，果然是正确的，1下就AC了
第六道就是解码
挺好处理的，不知道为什么这么多人WA，我开始PE是自己处理数据打印观察之后忘了去掉一个回车
第七道是博弈
全场没有人动过，我到外边看了提交记录，有几百MS过的，大概广搜+剪枝也能过吧
有空去想一下
第八道回文
开始想不出方法，后来TTBJ指点一下，从中间向两边延伸来做就马上AC了
做完这些题目后继续那道线段树
终于改好了，一提交。。。结果TLE。。。
我开始还以为是哪里不小心死循环了，后来才发现我读入数据就建树，每次都是log(n)
方法太糟糕了200000*log(200000)不超时才怪
改进一下先用数组先保存分数，再一起建树这样就会快很多了。。。。
1 int a = query(l,mid,id<<1);
2 int b = query(mid,r,(id<<1)+1);
3 return Max(a,b);
4 这个是AC的代码
5 else
6 return Max(query(l,mid,id<<1),query(mid,r,(id<<1)+1));
7 这个是TLE的代码
8
9 竟然相差这么多，我晕，改了长时间。。。
终于刷到了第一
心满意足的睡觉去了
#include<stdio.h>
#include<string>
#define Max(a,b) a>b?a:b
struct Tree{
int l,r,max;
}T[3*200001];
int score[200001];
void Creat(int l,int r,int id)
{
T[id].l = l;
T[id].r = r;
if(r-l>1)
{
int mid = (l + r)>>1;
Creat(l,mid,id<<1);
Creat(mid,r,(id<<1)+1);
T[id].max = Max(T[id<<1].max,T[(id<<1)+1].max);
}
else
T[id].max = Max(score[l],score[r]);
}
void updata(int num,int id)
{
if(T[id].r - T[id].l <= 1)
{
T[id].max = Max(score[T[id].r],score[T[id].l]);
return ;
}
if(T[id<<1].r >= num)
updata(num,id<<1);
if(T[(id<<1)+1].l <= num)
updata(num,(id<<1)+1);
T[id].max = Max(T[id<<1].max,T[(id<<1)+1].max);
}
int query(int l,int r,int id)
{
if(l==T[id].l && T[id].r==r)
return T[id].max;
int mid = (T[id].l + T[id].r)>>1;
if(l>=mid)
return query(l,r,(id<<1)+1);
else if(r<=mid)
return query(l,r,id<<1);
else
{
int a = query(l,mid,id<<1);
int b = query(mid,r,(id<<1)+1);
return Max(a,b);
}
}
int getval()
{
char c;
int ret=0;
while((c=getchar())!=' '&&c!='\n')
ret=ret*10+(c-'0');
return ret;
}
int main()
{
int n,m,i,a,b;
char ch;
while(scanf("%d%d",&n,&m)==2)
{
getchar();
for(i=1;i<=n;i++)
{
int ret=0;
score[i] = getval();
}
Creat(1,n,1);
while(m--)
{
ch = getchar();
getchar();
a = getval();
b = getval();
if(ch=='U')
{
score[a] = b;
updata(a,1);
}
else
{
if(a==b)
printf("%d\n",score[a]);
else
{
int ans = query(a,b,1);
printf("%d\n",ans);
}
}
}
}
return 0;
}
明天要好好休息了，早点睡觉。后天早上上火车回学校咯。。。
posted on 2009-02-12 03:23
shǎ崽 阅读(396)
评论(1) 编辑 收藏 引用