今天下午整了個線段樹
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.shnenglu.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ǎ崽 閱讀(410)
評論(1) 編輯 收藏 引用