M.J的blog

algorithm,ACM-ICPC
随笔 - 39, 文章 - 11, 评论 - 20, 引用 - 0
数据加载中……

【第一场选拔赛解题报告】

今天做的还可以,当然,对我来说。唯一的缺点是别人当水题做的D我没做出来。简单的BFS,我愣是不会。哎,还是要把基础打好啊。最后A掉3道,还有一道线段树的没有过,过些时间补上。我该抓紧时间复习了...

A - River Pollution   

          线段树,求面积的并,很基础的线段树+离散化+扫描线,但我就是不会~

B - Middle number  
   
         今天这个是第一个过的,如果这个不过我相信后边会更加艰难。给定一个数的序列,然后不断的插入数字并保持递增,最后询问中间的数是多少。如果
数的个数是偶数,输出中间两个中小的。数据很大,时间是5s,我冒了个险,第一次先排序,每次二分找到要插入的位置,然后顺序修改后边的序列,过了!
二分的效率啊!!我看到后边这个题无数人TLE到死。。。这个题给了我很大信心,不然。。。
现在知道了,正解是用两个堆,一个大顶堆,一个小顶堆,大顶堆只能和小顶堆元素个数相同或者正好多一个。开始时将小的一般给大顶堆,大的一半给小顶堆,插入时和堆顶元素比一下,若大于大顶堆的堆顶元素,则插给小堆,否则给了大堆。询问时只需输出大堆的堆顶元素就可以了。
C - Game of Stones 

         JL出的题,乍一看很难,但是后来才知道简单的要命:两个人A和B玩游戏,有两堆石子M和N,每次两个人都至少从两堆中任意一堆拿至少一个石子,直到两堆石子都为空最后一个拿的人WIN。,A总是第一个拿,给定M和N,问A能否获胜。( 0 < M , N < 10^50 )
         答案:如果M==N,A输,否则,A赢。我考虑到奇偶上了,结果WA了5次,哎。。。

D - The longest athletic track  

         给定N个点,和一棵生成树(N-1条边),最后问最长的一条路是多少。

                                                                     
            上图的答案是80。
            求树的直径,两次BFS,第一次任选起点,则终点一定是直径的一个端点。然后再来一次BFS就可以了。

E - Buy Car         
    
           Brent喜欢骑摩托,现在有N个城市,Brent 想把所有城市逛一遍,但是他怕油不够。每升油可以跑10km,他可以在任何一个城市加油。给出M条边,
最后问Brent的摩托的容量最小是多少,如果不能逛完所有城市,输出-1。

           简单的最小生成树(正是Brent讲座讲的~),找出最小生成树最小的一条边长度为A。如果A%10==0,答案是A/10;否则答案是A/10+1;

最后排名大概是10名?(除去老队员和admin大概是7,8名的样子),问题应该不大了。嘻嘻,加油吧~ 可恶的BFS。。。一定搞定它。

posted @ 2010-05-16 22:37 M.J 阅读(125) | 评论 (0)编辑 收藏

TOJ 1011 Area【计算几何】

这道题用到了一个我不知道的定理,Pick定理。意思是格子面上的多边形的边的点的个数on和内部点的个数in的关系式Area = on / 2 + in - 1;
求Area可以用叉乘法。注意最后那个Area/=2.0。
Code:
/*TOJ 1011 Area
  pick theory 
*/

#include
<stdio.h>
#include
<stdlib.h>
#include
<math.h>
int px[100],py[100];
int gcd(int a,int b){
    
int temp;
    
while(b!=0){
        temp
=b;
        b
=a%b;
        a
=temp;
    }

    
return a;
}

int main(void)
{
    
int cas,dx,dy,on,in,i,j,n;
    
double area;
    scanf(
"%d",&cas);    
    
for(j=1;j<=cas;j++){
        scanf(
"%d",&n);
        px[
0]=py[0]=dx=dy=area=on=0;
        
for(i=1;i<=n;i++){
            scanf(
"%d%d",&dx,&dy);
            on
+=gcd(abs(dx),abs(dy));
            px[i]
=px[i-1]+dx;
            py[i]
=py[i-1]+dy;
            area
+=(px[i-1]*py[i]-px[i]*py[i-1]);
        }

        area
=area/2.0;
        
in=area+1-on/2;
        printf(
"Scenario #%d:\n%d %d %.1lf\n\n",j,in,on,area);
    }

}


posted @ 2010-05-11 09:09 M.J 阅读(158) | 评论 (0)编辑 收藏

TOJ 3051.Hopeless Coach【DP】

简单的DP,大意是给出N场比赛球队的输,平,赢的场数,最后问M场比赛至少拿S分的概率。赢一场3分,平一场1分,输0分。
dp[i][j]表示 i  场比赛得 j  分的概率。则有转移方程dp[i][j]=dp[i-1][j-3]*r1+dp[i-1][j-1]*r2+dp[i-1][j]*r3;(r1,r2,r3分别表示每一场赢,平,输的概率)
Code:
#include<stdio.h>
#include
<string.h>
#include
<stdlib.h>
double dp[90][270];
int main()
{
    
int i,j,k,n,m;
    
double r1,r2,r3,sum;    
    
while(scanf("%d%d",&n,&m),n+m){
        scanf(
"%d%d%d",&i,&j,&k);
        r1
=i*1.0/(i+j+k);
        r2
=j*1.0/(i+j+k);
        r3
=k*1.0/(i+j+k);
        memset(dp,
0,sizeof(dp));
        dp[
1][0]=r3;dp[1][1]=r2;dp[1][3]=r1;
        
for(i=2;i<=n;i++)
            
for(j=0;j<=3*i;j++){
                
if(j<=0)                        // 防止数组下标出现负数 
                    dp[i][j]=dp[i-1][j]*r3;
                
else if(j<=1)                      //同上 
                    dp[i][j]=dp[i-1][j]*r3+dp[i-1][j-1]*r2;
                
else
                    dp[i][j]
=dp[i-1][j]*r3+dp[i-1][j-1]*r2+dp[i-1][j-3]*r1;
            }

        sum
=0.0;
        
for(i=m;i<=3*n;i++)
            sum
+=dp[n][i];
        printf(
"%.1lf\n",sum*100);
    }

}

posted @ 2010-05-10 20:02 M.J 阅读(120) | 评论 (0)编辑 收藏

TOJ 3001 Score【数论】

一个结论很简单的问题,对于任意两个数a,b(a,b>=2)
1)如果gcd (a,b)==1,则最大的不能由a,b线性表示的数为a*b-a-b;
2)否则这个数时无穷大
至于证明,期待大牛给出,我还是不懂,一开始往拓展欧几里得想的,但后来也没什么结论。
哪位神牛知道证明给点提示,不胜感谢~
Code略去(太水了)

posted @ 2010-05-10 19:22 M.J 阅读(102) | 评论 (0)编辑 收藏

POJ.2299 Ultra-QuickSort【树状数组+离散化】

一个求逆序对的题,N个数,N<=500000,问排成递增序列需要相邻的数交换多少次。一开始没有仔细看题,上来就做,后来才发现数的范围是999999999。因为最多500000个数,所以数和数之间的间隔很大,可以处理一下,使数的间隔变小,然后使用树状数组统计某个数前边的比它大的数的个数。将所有的数放到一个结构体里,称作num,并增加一个成员id,然后按num递增排列,再另开一个数组给每个数重新编号,使数的范围都在N以内。然后就可以很自然的用树状数组做了。时间500ms。据说归并排序比这个要快。
Code:
 1 #include<iostream>
 2 #include<algorithm>
 3 #define M 500001
 4 using namespace std;
 5 int c[M],aa[M],n;                   //aa数组为排序后重新编号用
 6 struct digit
 7 {
 8     int num,id;
 9 }a[M];                              //num为数的大小
10 bool cmp(digit a,digit b){
11     return a.num<b.num;
12 }
13 int lowbit(int t){                 
14     return t&(t^(t-1));
15 }
16 int sum(int t){
17     int total=0;
18     while(t>0){
19         total+=c[t];
20         t-=lowbit(t);
21     }
22     return total;
23 }
24 void update(int t,int key){
25     while(t<=n){
26         c[t]+=key;
27         t+=lowbit(t);
28     }
29 }
30 int main()
31 {
32     int i,j;
33     long long ans;
34     while(scanf("%d",&n),n){
35         memset(c,0,sizeof(c));
36         ans=0;
37         for(i=1;i<=n;i++){
38             scanf("%d",&a[i].num);
39             a[i].id=i;
40         }
41         sort(a+1,a+n+1,cmp);
42         aa[a[1].id]=1;                                 //最小的数编号为1
43         for(i=2;i<=n;++i){
44             if(a[a[i].id].num!=a[a[i-1].id].num)      //如果前后两个数不等,则编号为下标
45                 aa[a[i].id]=i;
46             else
47                 aa[a[i].id]=aa[a[i-1].id];            //否则编号与前一个相同
48         }
49         //for(i=1;i<=n;i++) printf("%d ",aa[i]);
50         for(i=1;i<=n;++i){
51             update(aa[i],1);
52             ans+=(sum(n)-sum(aa[i]));                 //每次累加该数前边比它大的数的个数
53         }
54         printf("%lld\n",ans);
55     }
56 }

posted @ 2010-05-03 17:24 M.J 阅读(968) | 评论 (2)编辑 收藏

POJ.1195 Mobile phones【二维树状数组】

简单的二维树状数组,求一个矩形区域内的和,因为要随时增减,而且可能减的数比原来都大,所以需要保留原来的数组。
在求矩形区域和的时候,只要用最大的矩形减去两个小的,再加上那个多减的最小的,就OK了。1y~~
Code:
 1 #include<iostream>
 2 #define M 1300
 3 int c[M][M],a[M][M],n;
 4 int lowbit(int t){
 5     return t&(t^(t-1));
 6 }
 7 int sum(int p,int q){
 8     int x=p,y,total=0;
 9     while(x>0){
10         y=q;
11         while(y>0){
12             total+=c[x][y];
13             y-=lowbit(y);
14         }
15         x-=lowbit(x);
16     }
17     return total;
18 }
19 void modify(int p,int q,int key){
20     int x=p,y;
21     while(x<=n){
22         y=q;
23         while(y<=n){
24             c[x][y]+=key;
25             y+=lowbit(y);
26         }
27         x+=lowbit(x);
28     }
29 }
30 int main()
31 {
32     int i,j,k,jj,kk,m,order,ans;
33     scanf("%d%d",&i,&n);
34     memset(c,0,sizeof(c));
35     memset(a,0,sizeof(a));
36     while(scanf("%d",&order)!=EOF){
37         if(order==3break;
38         else if(order==1){
39             scanf("%d%d%d",&j,&k,&m);
40             ++j;  ++k;
41             if(m<0&&m*(-1)>a[j][k]){
42                 m=(-1)*a[j][k];
43                 modify(j,k,m);
44                 a[j][k]=0;
45             }
46             else{
47                 modify(j,k,m);
48                 a[j][k]+=m;
49             }
50         }
51         else if(order==2){
52             scanf("%d%d%d%d",&j,&jj,&k,&kk);
53             ++j; ++jj; ++k; ++kk;
54             //printf("%d ",sum(n,n));
55             ans=sum(k,kk)+sum(j-1,jj-1)-sum(k,jj-1)-sum(j-1,kk);
56             printf("%d\n",ans);
57         }
58     }
59 }

posted @ 2010-05-03 17:13 M.J 阅读(190) | 评论 (0)编辑 收藏

POJ.2481 Cows【树状数组】

今天联系树状数组,但是我发现我真的很笨,做了好几道了还是不熟。这个题和前边的也没什么分别,是说每个牛有一个区间[s,e],两个牛[s1,e1], [s2,e2],当s1<=s2并且e1>=e2并且e1-s1>e2-s2时,我们说牛1比牛2强,给N个牛的区间,对于每个牛,输出比这个牛强的牛的个数。
还是需要预处理,先对每个牛的e进行降序排序,e相同时对s进行升序排列,这样循环时可以保证后边的牛绝对不比前边的牛强。在循环时,只需找出比当前牛s小的牛的个数。如果遇到特殊情况,即两个牛区间完全一样,赋值就可以了。哎,加油吧~
Code:
 1 #include<iostream>
 2 #include<algorithm>
 3 #include<map>
 4 #define MAX 100002                   
 5 using namespace std;
 6 int c[MAX],ans[MAX],n,imax;
 7 struct cow
 8 {
 9     int l,r,id;
10 }a[MAX];                          
11 bool cmp(cow a,cow b){                
12     if(a.r==b.r)                          //如果两个牛区间右边界相同,按左边界的升序排列
13         return a.l<b.l;  
14     return a.r>b.r;                       //按右边界的降序排列
15 }
16 int lowbit(int t){
17     return t&(t^(t-1));
18 }
19 int sum(int t){
20     int total=0;
21     while(t>0){
22         total+=c[t];
23         t-=lowbit(t);
24     }
25     return total;
26 }
27 void modify(int posi,int key){
28     while(posi<=imax){
29         c[posi]+=key;
30         posi+=lowbit(posi);
31     }
32 }
33 int main()
34 {
35     int i,j,k,n;
36     while(scanf("%d",&n),n){
37         memset(c,0,sizeof(c));
38         imax=0;
39         for(i=1;i<=n;i++){
40             scanf("%d%d",&a[i].l,&a[i].r);
41             a[i].id=i;                                    //每个牛有个id防止排序完顺序变乱
42             ++a[i].l; ++a[i].r;
43             if(imax<a[i].l) imax=a[i].l;                 //用imax表示右边界最大值,即求和时的边界
44         }
45         sort(a+1,a+n+1,cmp);
46         for(i=1;i<=n;++i){
47             if(i==1){
48                 ans[a[i].id]=sum(a[i].l);              //这里注意是ans[a[i].id]而不是ans[i]
49                 modify(a[i].l,1);
50             }
51             else{
52                 if(a[i].l==a[i-1].l&&a[i].r==a[i-1].r) //如果两个牛完全相同,直接赋值
53                     ans[a[i].id]=ans[a[i-1].id];
54                 else
55                     ans[a[i].id]=sum(a[i].l);         //否则找出左边界l比这个牛小的
56                 modify(a[i].l,1);
57             }
58         }
59         for(i=1;i<n;++i)
60             printf("%d ",ans[i]);
61         printf("%d\n",ans[i]);
62     }
63 }
64 

posted @ 2010-05-03 17:12 M.J 阅读(81) | 评论 (0)编辑 收藏

POJ.3067 Japan【树状数组】

这道题和那道Star如出一辙,可我还是做了很长时间 ...太菜了...有K条连接东西两个城市的路,东西方向每个城市都有一个编号M,N,从北到南,最后问共有多少个十字路都,即有多少个交点。
先预处理,用结构体表示每条边,对结构体按N进行从小到大的排序,如果N相同,按M从小到大排序。接下来就和Star一样了,唯一不同的是Star那道题是每次求出当前星星前边的个数,而这个是求当前点后边的个数。用c[]表示树状数组,sum(n)求出的是N编号小于等于n的city的个数,只需每次拿出一个city,求出N编号大于它的city的个数,然后更新数组就可以了。
 关键代码:
1 long long ans=0;
2 for(i=1;i<=K;i++){                       //K表示边的个数
3     ans+=sum(max)-sum(a[i].east);        //east即为N编号
4     modify(a[i].east,1);                 //将a[i].east插入到当前数组
5 }
6 
解决了这一步,其余就是套路了,很简单。
Code:
 1 #include<iostream>
 2 #include<algorithm>
 3 #define MAX 10005                      //最大的city个数
 4 using namespace std;
 5 int c[MAX],n,N,M,K,omax;
 6 struct road
 7 {
 8     int west,east;
 9 }a[MAX*MAX];                            //MAX*MAX为最多的边的个数
10 bool cmp(road a,road b){                
11     if(a.west==b.west)
12         return a.east<b.east;
13     return a.west<b.west;
14 }
15 int lowbit(int t){
16     return t&(t^(t-1));
17 }
18 int sum(int t){
19     int total=0;
20     while(t>0){
21         total+=c[t];
22         t-=lowbit(t);
23     }
24     return total;
25 }
26 void modify(int posi,int key){
27     while(posi<=omax){
28         c[posi]+=key;
29         posi+=lowbit(posi);
30     }
31 }
32 int main()
33 {
34     int i,j,k,m,cas;
35     long long ans;
36     scanf("%d",&cas);
37     for(i=1;i<=cas;++i){
38         omax=0;                                //用omax表示所有east的最大值,以确定求和区间
39         memset(c,0,sizeof(c));
40         scanf("%d%d%d",&N,&M,&K);
41         for(j=1;j<=K;++j){
42             scanf("%d%d",&a[j].east,&a[j].west);
43             if(a[j].east>omax)
44                 omax=a[j].east;
45         }
46         sort(a+1,a+1+K,cmp);
47         ans=0;
48         for(j=1;j<=K;++j){                        //key code
49             ans+=(sum(omax)-sum(a[j].east));
50             modify(a[j].east,1);
51         } 
52         printf("Test case %d: %lld\n",i,ans);
53     }
54 }
55 

posted @ 2010-05-03 17:11 M.J 阅读(100) | 评论 (0)编辑 收藏

POJ.2352 Stars【树状数组】

大意是N个星星,规定每个星星的等级为在它左下方星星的数量(包括某个坐标相等),N范围是15000,输入按y坐标的升序给出,如果两个星星y坐标相等,按x坐标升序给出。
用树状数组,不用管y坐标(因为已经是升序,后边的星星不影响前边星星的等级),用sum(n)来统计x坐标为n以前的星星个数,但是千万注意树状数组需要数组以1为首项,由于坐标有0,所以每次需要给x坐标+1。另外,通过这个题,我发现++i果然比i++快。两者一个420ms,一个360ms。还是差不少的,以后尽量用++i了:D
Code:
 1 #include<stdio.h>
 2 #include<string.h>
 3 #define M 32006                      //坐标范围是32000
 4 int c[M],ans[M/2];                   //c为树状数组,ans[i]表示level为i的星星个数
 5 int lowbit(int t){
 6     return t&(t^(t-1));
 7 }
 8 int sum(int m){
 9     int total=0;
10     while(m>0){
11         total+=c[m];
12         m-=lowbit(m);
13     }
14     return total;
15 }
16 void modify(int position){
17     while(position<=32002){          
18         ++c[position];
19         position+=lowbit(position);
20     }
21 }
22 int main()
23 {
24     int x,y,i,j,n;
25     scanf("%d",&n);
26     j=n;
27     memset(c,0,sizeof(c));
28     memset(ans,0,sizeof(ans));
29     while(n--){
30         scanf("%d%d",&x,&y);
31         ++ans[sum(x+1)];
32         modify(x+1);
33     }
34     for(i=0;i<j;++i)
35         printf("%d\n",ans[i]);
36 }

posted @ 2010-05-03 17:11 M.J 阅读(149) | 评论 (0)编辑 收藏

Binary Indexed Tree-树状数组【TOJ 3505】

     TOJ有道题,大意是有N个位置,每个位置有若干瓶子,Mike很淘气,他每次会增加或减少位置i的瓶子数,然后有M次询问,求位置A到B的瓶子数的和。最开始,我一直用最直观的做法,但是由于是O(n)的复杂度,所以一直超时。今天看了BIT的相关东西,才发现那个题其实是典型的BIT题目,而且是最基础的,但是就和RMQ问题一样,高效的算法背后深刻的数学理论还是不能很透彻的理解,这个只有靠以后熟练的慢慢来了:D

                        

     先来看一下树状数组的概念:树状数组是一种静态树状数据结构,它的首要作用是维护前缀和,即改变数组中某一元素a[i]的值,若要询问前N项的和,树状数组便可完美解决。时间复杂度O(logn)。
     先来直观看一下树状数组的结构(图片来自http://fqq11679.blog.hexun.com/21722866_d.html#
                 
     在上图中,红色的数组c[]便是树状数组。改变数组a的某一个元素i,则需要相应的改变数组c,若要询问前N项和,只需累加相应的c,而这当中一个核心的问题便是相应的数组c的下标问题。可以用位操作lowbit解决。c[i]=a[i-2^k+1]到a[i]的和,k是指i用二进制表示时末位0的个数,即将i表示成幂方和后最小的指数。利用位运算,我们可以得知2^k=i&(i^(i-1));
相应的代码为:
1 int lowbit(int n)
2 {
3     return n&(n^(n-1));
4 }

这样,当a[i]改变时,我们只需从c[i]开始一直向上回溯,改变路上相应的数组c的值,若要求前N项和,只需求N以前所有最大子树c[]的和。然后我们来看相应下标的操作:
              修改a[i],则修改一路的父节点c[p], p=i-bit(i);

若要前i项求和,只需一路找子节点c[p],  p=i-lowbit(i);

求前N项和:
1 int sum(int n)
2 {
3     int total=0;
4     while(n>0){
5         total+=c[n];
6         n-=lowbit(n);
7     }
8     return total;
9 }
TOJ 3505  Naughty mike
Code:
 1 /*TOJ 3505 Naughty mike*/
 2 #include<stdio.h>                          //注意在使用树状数组时下标一定不能从0开始
 3 #include<string.h>
 4 #define M 100002
 5 int a[M],n;                
 6 int c[M];
 7 int lowbit(int t)                           //关键的位操作确定数组下标
 8 {
 9     return t&(t^(t-1));
10 }
11 int sum(int end)                           //求前end项和的函数,通过不断累加最大子树得到
12 {
13     int i;
14     int total=0;
15     while(end>0){
16         total+=c[end];
17         end-=lowbit(end);
18     }
19     return total;
20 }
21 void modify(int t,int key)                 //对数组某一项进行修改时,只需沿该项一直向上回溯修改相应的数组c
22 {
23     while(t<=n){
24         c[t]+=key;
25         t+=lowbit(t);
26     }
27 }
28 int main()
29 {
30     int i,j,k,m,cas;
31     char e[50];
32     scanf("%d",&cas);
33     while(cas--){
34         scanf("%d",&n);
35         memset(c,0,sizeof(c));
36         for(i=1;i<=n;i++){
37             scanf("%d",&a[i]);
38             modify(i,a[i]);
39         }
40         scanf("%d",&m);
41         while(m--){
42             scanf("%s%d%d",e,&i,&j);
43             if(e[0]=='A'){
44                 modify(i,j);
45                 a[i]+=j;
46             }
47             else if(e[0]=='D'){
48                 if(j>=a[i]) j=(-1)*a[i];                 //由于可能删除的比现有的还多,需要分开考虑
49                 else    j*=(-1);
50                 modify(i,j);
51                 a[i]+=j;
52             }
53             else
54                 printf("%d\n",sum(j)-sum(i-1));          //区间[i,j]的和
55         }
56     }
57 }
58 

posted @ 2010-05-01 11:53 M.J 阅读(308) | 评论 (0)编辑 收藏

仅列出标题
共4页: 1 2 3 4