• <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>

            TOPCODER-SRM455

            Posted on 2009-12-19 14:07 rikisand 閱讀(553) 評論(0)  編輯 收藏 引用 所屬分類: TopcoderAlgorithm

            杯具的比賽~第一題竟然把南和北寫反了- -!第二題沒判斷好復(fù)雜度,實際上暴力方法可以的,第三題dp 必然沒寫出來

            so----跌成灰色了~~

            250pt

            Problem Statement

            Petya likes spiders. He put a spider in each cell of a rectangular grid. He has studied spiders for many years, so he predicted the behaviour of all of the spiders. At the beginning of each second, every spider will move from its cell to one of the adjacent cells (or off the grid). For each cell, he wrote the direction of its movement to matrix which is represented by a vector <string>, A. The j-th character of i-th element of A will be either 'N', 'S', 'E' or 'W' and it will represent north, south, east and west directions of movement, respectively. If a spider moves outside the grid it falls to the floor. Return the number of free cells after 1 second.

            Definition

            Class:
            SpidersOnTheGrid

            Method:
            find

            Parameters:
            vector <string>

            Returns:
            int

            Method signature:
            int find(vector <string> A)

            (be sure your method is public)

            Constraints

            -
            A will contain between 1 and 50 elements, inclusive.

            -
            Each element of A will contain between 1 and 50 characters, inclusive.

            -
            All elements of A will have the same number of characters.

            -
            Each character will be either 'N', 'E', 'S' or 'W'.

            Examples

            0)

            {"EW","NN"}
            Returns: 2

            1)

            {"EEEEEEEEEEEEEEEEEEEEEEEEEEEEEW"}
            Returns: 1

            2)

            {"EW"}
            Returns: 0

            3)

            {"ESW","ENW"}
            Returns: 4

            4)

            {"E"}
            Returns: 1

             

            Code Snippet
            class SpidersOnTheGrid
            {
                    public:
                    int find(vector <string> A)
                    {
                        int dr[]={1,0,-1,0};
                        int dc[]={0,1,0,-1};
                            vector<string > B = A;
                            map<char,int> mp;
                            mp['S']=0;mp['E']=1;mp['N']=2;mp['W']=3;
                            int r = A.size(); int c= A[0].size();
                            REP(i,r)REP(j,c){
                                int dir = mp[A[i][j]];
                                if(i+dr[dir]<0||i+dr[dir]>=r||j+dc[dir]<0||j+dc[dir]>=c)continue;
                                B[i+dr[dir]][j+dc[dir]] = 'H';
                            }
                            int ans = 0;
                            REP(i,r)REP(j,c){
                                if(B[i][j]!= 'H')ans++;
                            }
                            return ans;
                    }

             

            500pt

            這題A的大小只有7個則最多有10^7 種組合來決定下一個元素,也就是說只要枚舉10^7就可以了

            Problem Statement

            Petya likes sequences. He has an infinite sequence A[] with the following properties:

            • A[0], A[1], ..., A[N-1] are given;
            • A[i]=(A[i-1]+A[i-2]+...+A[i-N])%10 for all i>=N;
            Sequence B[] with length M is a substring of A[] if there is such index P that B[0]=A[P], B[1]=A[P+1], ..., B[M-1]=A[P+M-1]. Your task is to find the smallest possible such P. If there is no such index, return -1.
            Definition

            Class:
            EasySequence

            Method:
            find

            Parameters:
            vector <int>, vector <int>

            Returns:
            int

            Method signature:
            int find(vector <int> A, vector <int> B)

            (be sure your method is public)

            Constraints

            -
            A will contain between 1 and 7 elements, inclusive.

            -
            B will contain between 1 and 50 elements, inclusive.

            -
            Each element of A will be between 0 and 9, inclusive.

            -
            Each element of B will be between 0 and 9, inclusive.

            Examples

            0)

            {1,2,3}
            {0,7,8,5}
            Returns: 5
            Starting with 1,2,3 we have:
            1+2+3 =  6,  6 % 10 = 6
            2+3+6 = 11, 11 % 10 = 1
            3+6+1 = 10, 10 % 10 = 0
            6+1+0 =  7,  7 % 10 = 7
            1+0+7 =  8,  8 % 10 = 8
            0+7+8 = 15, 15 % 10 = 5
            7+8+5 = 20, 20 % 10 = 0
            
            1,2,3,6,1,0,7,8,5,0
                      0,7,8,5      answer = 5

            1)

            {1,2,8}
            {7,4,2,3}
            Returns: -1

            2)

            {1,2,3,4,5}
            {4,5}
            Returns: 3

            3)

            {1}
            {1,1,1}
            Returns: 0
            #define REP(i, n) for (int i = 0; i < (n); ++i)  
            int C[10000002];
            class EasySequence
            {
                    public:
                    int find(vector <int> A, vector <int> B)
                    {
                        int sum = 0; int n=A.size();
                        REP(i,A.size()) sum+= A[i],C[i]=A[i];
                        REP(i,10000000){
                            C[i+n]=sum%10;
                            sum+=(sum%10);
                            sum = (sum +10-C[i])%10;
                        }
                        for(int i=0;i<10000000;i++){
                            if(C[i] == B[0]){
                                int k=1;int j=i+1;
                                for(;k<B.size()&&j<10000000&&C[j]==B[k];k++,j++);
                                if(k==B.size())return i;
                            }
                        }
                        return -1;
                    }

            1000pt

            Problem Statement

            Petya likes donuts. He tries to find them everywhere. For example if he is given a grid where each cell contains a '0' or '.' he will construct donuts from the cells.

            To make the donuts:

            1. Petya first selects a rectangle of cells of width, w, and height, h, where both are at least 3.
            2. Then he removes a rectangular hole of width w-2 and height h-2 centered in the larger rectangle.
            3. For the remaining cells (a closed rectangular ring) to be a valid donut, all of the cells must contain '0' (because donuts are shaped like zeros). Cells in the hole can contain anything since they are not part of the donut.

            Here is an example with three overlapping donuts.

            ..........
            .00000000.
            .0......0.
            .0.000000.
            .0.0...00.
            .0.0...00.
            .0.000000.
            .0......0.
            .00000000.
            ..........
            

            The grid in this problem will be pseudo-randomly generated using the following method:
            You are given four ints: H (the grid height), W (the grid width), seed and threshold. Let x0=seed and for all i>=0 let xi+1 = (xi * 25173 + 13849) modulo 65536. Process the cells of the matrix in row major order (i.e., first row left to right, second row left to right, etc.). Each time you process a cell, calculate the next xi (starting with x1 for the upper left corner). If it is greater than or equal to threshold, the current cell will contain a '.', otherwise it will contain a '0'.

            Return the number of distinct donuts in the figure. Two donuts are considered distinct if they either have different width or height, or if the top left hand corner is in a different location (i.e., overlapping donuts are counted).

            Definition

            Class:
            DonutsOnTheGrid

            Method:
            calc

            Parameters:
            int, int, int, int

            Returns:
            long long

            Method signature:
            long long calc(int H, int W, int seed, int threshold)

            (be sure your method is public)

            Notes

            -
            The random generation of the input is only for keeping the input size small. The author's solution does not depend on any properties of the generator, and would work fast enough for any input of allowed dimensions.

            Constraints

            -
            H will be between 1 and 350, inclusive.

            -
            W will be between 1 and 350, inclusive.

            -
            seed will be between 0 and 65535, inclusive.

            -
            threshold will be between 0 and 65536, inclusive.

            Examples

            0)

            5
            5
            222
            55555
            Returns: 4

            Here is an example of the grid:

            00000
            00.0.
            .0000
            00.00
            00000

            1)

            5
            6
            121
            58000
            Returns: 3

            Here is the grid and three donuts in it:

            00000.   XXX...   XXX...   ..XXX.
            0.0000   X.X...   X.X...   ..X.X.
            0.000.   X.X...   X.X...   ..XXX.
            000.00   XXX...   X.X...   ......
            000.00   ......   XXX...   ......
            

            2)

            4
            5
            6
            50000
            Returns: 1

            The grid is:

            0.0.0
            00000
            .00.0
            0.000
            

            3)

            4
            4
            1
            65536
            Returns: 9

            Here, the grid is completely filled by 0's. There are 9 possible placements of a donut:

            XXX.  XXX.  .XXX  .XXX  ....  ....  XXXX  ....  XXXX
            X.X.  X.X.  .X.X  .X.X  XXX.  .XXX  X..X  XXXX  X..X
            XXX.  X.X.  .XXX  .X.X  X.X.  .X.X  XXXX  X..X  X..X
            ....  XXX.  ....  .XXX  XXX.  .XXX  ....  XXXX  XXXX
            #define REP(i, n) for (int (i) = 0; i < (n); ++(i)) 
            int mp[450][450]; 
            int ver[400][450];
            class DonutsOnTheGrid
            {
                    public:
                    long long calc(int R, int C, int seed, int threshold)
                    {
                        int xi = seed ; 
                        memset(mp,0,sizeof(mp)); 
                        memset(ver,0,sizeof(ver));
                        REP(i,R)REP(j,C){
                            xi = (xi * 25173 + 13849) % 65536 ;
                            mp[i][j] = (xi >= threshold ? 1:0) ;
                        }  
                        for(int i=R-1;i>=0;i--)
                            for(int j=C-1;j>=0;j--){
                                ver[i][j] = ver[i+1][j] + mp[i][j];//記錄列中的累加和
                            }
                        int64 ans=0;
                        for(int i=0;i<R;i++)
                            for(int j = i+2;j<R;j++){//求兩行之間的矩形數(shù)目
                                int cnt=0;int prev=0;
                                for(int k=0; k<C;k++){//按列從左向右找
                                    if(ver[i][k]==ver[i+1][k]&&ver[j][k]==ver[j+1][k]){//如果判斷出此位置不是0則置cnt=0
                                        if(ver[i][k]==ver[j+1][k]){//col all 0
                                            if(cnt>0){  
                                            if(prev==k-1)ans+=(cnt-1);//與之前的豎列組成矩形~
                                            else ans+=cnt; 
                                            }
                                            cnt++;prev=k;
                                        } 
                                    }
                                    else
                                        cnt=0;
                                }
                            }
                            return ans;
                    }
            亚洲国产成人精品91久久久| 日韩十八禁一区二区久久| 77777亚洲午夜久久多人| 久久精品国产色蜜蜜麻豆| 久久人妻无码中文字幕| av国内精品久久久久影院| 精品国产综合区久久久久久 | 亚洲欧美伊人久久综合一区二区 | 久久精品国产精品青草app| 亚洲一本综合久久| 色综合久久夜色精品国产| 久久精品国产清高在天天线| 国产精品99久久精品爆乳| 99久久精品免费看国产一区二区三区| 国内精品久久人妻互换| 中文字幕无码av激情不卡久久| 色综合久久久久综合体桃花网| 久久精品国产黑森林| 久久久久人妻一区二区三区vr| 欧美激情精品久久久久久| 97久久久久人妻精品专区| 久久亚洲日韩看片无码| 久久精品亚洲精品国产欧美| 久久久久久午夜成人影院 | 国产激情久久久久影院| 伊人久久大香线蕉AV色婷婷色| 久久高潮一级毛片免费| 久久香蕉一级毛片| 久久国产精品成人影院| 狠狠色婷婷久久综合频道日韩| 久久青青草原亚洲av无码| Xx性欧美肥妇精品久久久久久 | 久久精品国产亚洲AV无码娇色| 狠狠色丁香婷婷久久综合五月| 久久se精品一区精品二区国产| 久久精品a亚洲国产v高清不卡| 99精品国产综合久久久久五月天| 亚洲午夜精品久久久久久浪潮| 欧美久久久久久午夜精品| 久久人人爽人人澡人人高潮AV | 狠狠精品干练久久久无码中文字幕|