• <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
            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(24)

            隨筆分類(332)

            隨筆檔案(182)

            FRIENDS

            搜索

            積分與排名

            最新隨筆

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(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ù)組 的裸題, 只是需要對(duì)坐標(biāo)做些處理即可, 另外, 初始化的時(shí)候 原來 com[i][j] = lowbit (i) * lowbit (j);      WA 好多次, 直接用的modify(i,j,1)

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

            2HUT-MiYu156MS8044K3172BC++

             

             /*

            MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(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;

            }


             

             

            色播久久人人爽人人爽人人片aV | 国产农村妇女毛片精品久久| 思思久久精品在热线热| 久久99精品久久久久久噜噜| 久久天天躁狠狠躁夜夜不卡| 亚洲国产精品无码久久久秋霞2 | 精产国品久久一二三产区区别| 99久久国产热无码精品免费| 久久综合精品国产二区无码| www.久久热.com| 色99久久久久高潮综合影院| 久久成人国产精品免费软件| 久久久久AV综合网成人| 中文字幕精品无码久久久久久3D日动漫| 久久久精品人妻一区二区三区蜜桃| 久久亚洲sm情趣捆绑调教| 精品国产乱码久久久久久郑州公司 | 亚洲精品无码久久久| 久久亚洲AV成人无码国产| 国产精品久久久久久搜索| 久久久久99精品成人片| av无码久久久久久不卡网站| 国产精品九九久久精品女同亚洲欧美日韩综合区| 久久精品一区二区三区中文字幕| 亚洲午夜久久久久妓女影院| 99久久伊人精品综合观看| 无码国内精品久久人妻蜜桃| 久久精品国产亚洲Aⅴ香蕉| 久久久久亚洲AV无码专区体验| 日韩十八禁一区二区久久| 久久精品国产亚洲网站| 久久婷婷五月综合国产尤物app| 狠狠精品干练久久久无码中文字幕 | 久久精品国产第一区二区| 久久精品aⅴ无码中文字字幕不卡 久久精品aⅴ无码中文字字幕重口 | 亚洲精品乱码久久久久久不卡| 久久精品免费一区二区三区| 一本久久a久久精品亚洲| 人妻中文久久久久| 久久精品视屏| 精品无码久久久久久国产|