• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            ACM___________________________

            ______________白白の屋
            posts - 182, comments - 102, trackbacks - 0, articles - 0
            <2013年5月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            常用鏈接

            留言簿(24)

            隨筆分類(332)

            隨筆檔案(182)

            FRIENDS

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋    

             

            題目地址:

                 http://acm.hdu.edu.cn/showproblem.php?pid=1892 

            題目描述:

            代碼
            See you~

            Time Limit: 
            5000/3000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
            Total Submission(s): 
            921    Accepted Submission(s): 291


            Problem Description
            Now I am leaving hust acm. In the past two and half years, I learned so many knowledge about Algorithm and Programming, and I met so many good friends. I want to say sorry to Mr, Yin, I must leave now 
            ~~>.<~~. I am very sorry, we could not advanced to the World Finals last year. 
            When coming into our training room, a lot of books are 
            in my eyes. And every time the books are moving from one place to another one. Now give you the position of the books at the early of the day. And the moving information of the books the day, your work is to tell me how many books are stayed in some rectangles. 
            To make the problem easier, we divide the room into different grids and a book can only stayed 
            in one grid. The length and the width of the room are less than 1000. I can move one book from one position to another position, take away one book from a position or bring in one book and put it on one position. 
             

            Input
            In the first line of the input file there 
            is an Integer T(1<=T<=10), which means the number of test cases in the input file. Then N test cases are followed. 
            For each test 
            casein the first line there is an Integer Q(1<Q<=100,000), means the queries of the case. Then followed by Q queries. 
            There are 
            4 kind of queries, sum, add, delete and move. 
            For example: 
            S x1 y1 x2 y2 means you should tell me the total books of the rectangle used (x1,y1)
            -(x2,y2) as the diagonal, including the two points. 
            A x1 y1 n1 means I put n1 books on the position (x1,y1) 
            D x1 y1 n1 means I move away n1 books on the position (x1,y1), 
            if less than n1 books at that position, move away all of them. 
            M x1 y1 x2 y2 n1 means you move n1 books from (x1,y1) to (x2,y2), 
            if less than n1 books at that position, move away all of them. 
            Make sure that at first, there 
            is one book on every grid and 0<=x1,y1,x2,y2<=1000,1<=n1<=100
             

            Output
            At the beginning of each 
            case, output "Case X:" where X is the index of the test case, then followed by the "S" queries. 
            For each 
            "S" query, just print out the total number of books in that area. 
             

            Sample Input
            2
            3
            1 1 1 1
            1 1 2
            1 1 1 1
            3
            1 1 1 1
            1 1 2
            1 1 1 2
             

            Sample Output
            Case 
            1:
            1
            3
            Case 
            2:
            1
            4

             

            題目分析 :

               一道二維樹狀數(shù)組 的裸題, 只是需要對坐標(biāo)做些處理即可, 另外, 初始化的時候 原來 com[i][j] = lowbit (i) * lowbit (j);      WA 好多次, 直接用的modify(i,j,1)

            好了,  直接代碼吧, 代碼過長, 內(nèi)存多了一點點 , HDU 第二     

            2HUT-MiYu156MS8044K3172BC++

             

             /*

            MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋

                      http://www.cnblog.com/MiYu

            Author By : MiYu

            Test      : 1

            Program   : 1892

            */


            #include <iostream>

            #include <cmath>

            #include <algorithm>

            using namespace std;

            #define lowbit(x) (x&(-x))

            int T,N;

            const int MAX = 1001;

            int mat[1002][1002];

            int com[1002][1002];

            void modify ( int x,int y, int n )

            {

                 while ( x <= MAX ){

                       int t = y;

                       while ( t <= MAX ){

                              com[x][t] += n;

                              t += lowbit(t); 

                       } 

                       x += lowbit(x);

                 } 

            }

            int quy ( int x, int y )

            {

                 int sum = 0;

                 while ( x > 0 ){

                       int t = y;

                       while ( t > 0 ){

                              sum += com[x][t];

                              t -= lowbit(t); 

                       } 

                       x -= lowbit(x);

                 } 

                 return sum; 

            }

            inline bool scan_d(int &num)

            {

                    char in;bool IsN=false;

                    in=getchar();

                    if(in==EOF) return false;

                    while(in!='-'&&(in<'0'||in>'9')) in=getchar();

                    if(in=='-'){ IsN=true;num=0;}

                    else num=in-'0';

                    while(in=getchar(),in>='0'&&in<='9'){

                            num*=10,num+=in-'0';

                    }

                    if(IsN) num=-num;

                    return true;

            }

            int main ()

            {

                  scan_d(T);{

                        int ca = 1;

                        while ( T -- ){

                               printf ( "Case %d:\n",ca++ );

                               scan_d(N);  char s[5];  int a,b,x,y,m,res,maxx,maxy,minx,miny;

                               for ( int i = 1; i <= MAX; ++ i )

                                    for ( int j = 1; j <= MAX; ++ j )

                                          com[i][j] = lowbit(i) * lowbit(j), mat[i][j] = 1;

                               for ( int i = 1; i <= N;  ++ i ){

                                     scanf ( "%s",s );

                                     switch ( s[0] ){

                                            case 'S' : scan_d(a);scan_d(b);scan_d(x);scan_d(y); minx = min ( a,x );miny=min(b,y);maxx=max(a,x)+1;maxy=max(b,y)+1;

                                                       res = 0;  res += quy( maxx,maxy ); res -= quy (maxx,miny); res -= quy(minx,maxy); res += quy(minx,miny);

                                                       printf ( "%d\n",res ); break;   

                                            case 'A' : scan_d(x);scan_d(y);scan_d(a);x++;y++; modify ( x,y,a ); mat[x][y] += a; break;

                                            case 'D' : scan_d(x);scan_d(y);scan_d(a);x++;y++; if ( mat[x][y] >= a ) { modify ( x,y,-a ); mat[x][y] -= a; }

                                                                                    else  { modify ( x,y,-mat[x][y] ); mat[x][y] = 0; } break;   

                                            case 'M' : scan_d(a);scan_d(b);scan_d(x);scan_d(y);scan_d(m);a++;b++;x++;y++; if ( mat[a][b] >= m )

                                                                                              {  mat[a][b] -= m; mat[x][y] += m; modify ( a,b,-m ); modify ( x,y,m ); }

                                                                                              else { modify ( a,b,-mat[a][b] ); modify ( x,y,mat[a][b] ); mat[x][y] += mat[a][b]; mat[a][b] = 0; } break;

                                     }

                               } 

                        } 

                }

                return 0;

            }


             

             

            亚洲国产精品久久久久网站| 久久国产精品99精品国产| 色综合久久久久久久久五月| 日本五月天婷久久网站| 久久精品无码一区二区WWW| 久久久久亚洲AV无码网站| 久久精品麻豆日日躁夜夜躁| 99久久精品费精品国产一区二区| 激情久久久久久久久久| 久久久噜噜噜久久中文字幕色伊伊 | 久久九九精品99国产精品| 久久精品视频免费| 久久精品国产色蜜蜜麻豆| 久久国产精品99国产精| 久久久久久A亚洲欧洲AV冫 | 亚洲综合伊人久久大杳蕉| 久久亚洲视频| 久久国产精品免费一区| 久久精品国产99久久久古代| 伊人久久大香线焦综合四虎| 久久久久久久精品妇女99| 精品欧美一区二区三区久久久| 麻豆AV一区二区三区久久 | 精品久久久无码人妻中文字幕豆芽 | 亚洲Av无码国产情品久久| 日本精品久久久中文字幕| 久久精品黄AA片一区二区三区| 久久精品国产一区二区| 97热久久免费频精品99| 熟妇人妻久久中文字幕| 亚洲精品美女久久久久99| 思思久久精品在热线热| 国产精品九九久久免费视频 | 伊人 久久 精品| 久久久久久久波多野结衣高潮| 国产综合免费精品久久久| 99久久精品国产毛片| 日本免费久久久久久久网站| 国产精品久久永久免费| 国产精品美女久久久| 美女写真久久影院|