青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

TOPCODER-SRM455

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

杯具的比賽~第一題竟然把南和北寫反了- -!第二題沒判斷好復雜度,實際上暴力方法可以的,第三題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++){//求兩行之間的矩形數目
                    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;
        }
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            国产精品久久久久久久9999| 国产麻豆9l精品三级站| 亚洲国产经典视频| 欧美激情性爽国产精品17p| 欧美成人按摩| 亚洲在线成人| 新片速递亚洲合集欧美合集 | 亚洲国产精品免费| 欧美人与性动交cc0o| 亚洲综合精品| 久久久久久久网| 一区二区三区蜜桃网| 亚洲欧美激情一区| 亚洲国产精品久久久久秋霞蜜臀| 欧美激情一区在线| 国产精品久久久久一区二区三区| 久久精品视频免费| 欧美激情va永久在线播放| 亚洲尤物视频在线| 免费成人激情视频| 西西裸体人体做爰大胆久久久| 久久精品视频99| 亚洲网站啪啪| 久久免费高清视频| 欧美一级视频精品观看| 美日韩精品视频免费看| 午夜精品久久久久久久99水蜜桃| 玖玖综合伊人| 欧美一区二区三区四区在线观看| 免费久久久一本精品久久区| 亚洲欧美在线磁力| 欧美经典一区二区| 免费精品99久久国产综合精品| 欧美日韩亚洲激情| 欧美黄色片免费观看| 国产麻豆视频精品| 亚洲美女性视频| 亚洲国产一区在线| 欧美在线你懂的| 亚欧成人精品| 国产精品进线69影院| 亚洲激情电影在线| 在线观看91久久久久久| 欧美亚洲专区| 午夜欧美不卡精品aaaaa| 欧美日韩国产经典色站一区二区三区| 久久久亚洲精品一区二区三区| 欧美午夜电影网| 99re6这里只有精品视频在线观看| 狠狠色狠狠色综合| 欧美一级二级三级蜜桃| 性欧美办公室18xxxxhd| 国产精品大片wwwwww| 日韩午夜在线| 亚洲视频在线观看| 欧美色中文字幕| 亚洲精品国产欧美| 日韩视频在线一区| 欧美精品一区二区三区蜜臀| 欧美激情亚洲视频| 亚洲欧洲在线看| 欧美福利电影在线观看| 亚洲风情在线资源站| 亚洲精品综合精品自拍| 欧美不卡视频一区| 亚洲精品免费看| 一区二区久久久久| 国产精品成人aaaaa网站| 99re这里只有精品6| 亚洲午夜国产成人av电影男同| 欧美日韩一区二区在线观看视频 | 亚洲天堂久久| 亚洲男女自偷自拍| 国产三级精品三级| 久久久久久久97| 亚洲国产女人aaa毛片在线| 亚洲日本成人| 欧美视频在线免费| 欧美一区二区三区视频免费| 久久一区二区三区国产精品| 在线看片日韩| 欧美日韩精品免费看| 亚洲欧美成aⅴ人在线观看| 久久久久久婷| 亚洲美女精品成人在线视频| 国产精品xxx在线观看www| 午夜精品一区二区三区在线视| 久久性色av| 亚洲美女精品成人在线视频| 欧美午夜性色大片在线观看| 欧美亚洲视频在线观看| 亚洲第一主播视频| 亚洲免费视频一区二区| 在线观看91精品国产入口| 欧美日韩一区二区在线播放| 欧美一级欧美一级在线播放| 欧美激情欧美狂野欧美精品| 亚洲一区二区三区精品在线| 国产色综合天天综合网| 欧美精品 国产精品| 欧美亚洲日本网站| 一本久久a久久免费精品不卡| 久久精品最新地址| 一本色道久久综合亚洲精品不卡 | 欧美视频专区一二在线观看| 欧美专区在线播放| 日韩视频在线免费| 欧美成人黑人xx视频免费观看| 亚洲综合二区| 亚洲看片一区| 亚洲第一精品久久忘忧草社区| 国产精品白丝jk黑袜喷水| 老司机精品视频网站| 午夜精品久久久久久久99樱桃| 亚洲欧洲美洲综合色网| 久久婷婷国产综合国色天香| 亚洲一区二区视频| 亚洲日本中文字幕区 | 欧美成ee人免费视频| 午夜视频一区二区| 一区二区三区国产在线| 亚洲国产另类 国产精品国产免费| 久久精品理论片| 亚洲免费视频成人| 亚洲天堂黄色| 国产精品99久久99久久久二8| 在线视频成人| 在线成人黄色| 伊人久久av导航| 国产日韩综合| 国产亚洲欧美日韩美女| 国产精品视频| 国产精品一区二区在线| 国产精品黄视频| 国产精品成人一区二区| 欧美视频一区二区在线观看| 欧美精品一区二| 欧美乱人伦中文字幕在线| 欧美激情久久久久久| 欧美成人亚洲成人日韩成人| 久久资源在线| 欧美激情视频免费观看| 欧美精品午夜| 欧美三级在线| 国产精品色一区二区三区| 国产精品乱人伦一区二区| 国产精品美女www爽爽爽| 国产精品久久久久久久久久久久 | 亚洲无线一线二线三线区别av| 亚洲免费激情| 亚洲午夜激情免费视频| 亚洲欧美日韩精品| 欧美一级大片在线免费观看| 久久国产精品久久久久久电车 | 亚洲激情综合| 一区二区三区久久网| 午夜精品久久久久久久99黑人| 欧美中文在线视频| 久久一本综合频道| 亚洲黄色片网站| 在线视频欧美精品| 欧美有码视频| 欧美精品麻豆| 国产欧亚日韩视频| 影音先锋中文字幕一区| 99国产一区二区三精品乱码| 亚洲一区www| 老鸭窝毛片一区二区三区| 亚洲国内精品在线| 一区二区三区.www| 久久精品欧洲| 欧美日韩另类一区| 国产亚洲欧美日韩在线一区| 最新国产の精品合集bt伙计| 亚洲一区二区三区四区五区午夜| 久久精品国产精品| 亚洲欧洲一区二区三区久久| 亚洲欧美激情视频在线观看一区二区三区 | 日韩午夜黄色| 久久精品国产一区二区三区免费看| 免费亚洲电影| 亚洲免费影视| 国产精品99久久99久久久二8 | 麻豆精品在线观看| 一区二区三区蜜桃网| 久久久久久香蕉网| 国产精品人人爽人人做我的可爱| 亚洲成色最大综合在线| 欧美一级片久久久久久久| 亚洲黄色天堂| 久久影院亚洲| 国产一级揄自揄精品视频| 一区二区国产精品| 欧美福利视频| 久久久青草婷婷精品综合日韩| 国产精品久久99| 亚洲天堂男人| 91久久午夜| 欧美成人中文| 91久久久久久国产精品|