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

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>
            欧美激情精品久久久六区热门| 久久成人羞羞网站| 欧美精品综合| 一区二区三区四区精品| 亚洲精品久久久久久下一站| 欧美电影在线观看| 日韩一级精品| 亚洲无毛电影| 尤物视频一区二区| 亚洲国产电影| 欧美性做爰毛片| 久久er99精品| 免费h精品视频在线播放| 亚洲理伦在线| 午夜精品视频在线观看一区二区| 在线精品视频一区二区| 一本色道久久综合亚洲91| 国产精品欧美日韩一区二区| 久久一区二区三区超碰国产精品| 欧美成人精品在线视频| 亚洲一区二区久久| 久久久免费精品| 亚洲一区二区在线视频| 久久久噜噜噜久久| 亚洲视频视频在线| 久久久久久免费| 亚洲嫩草精品久久| 久久婷婷人人澡人人喊人人爽| 中文欧美日韩| 老牛嫩草一区二区三区日本 | 欧美 日韩 国产 一区| 亚洲少妇一区| 免费亚洲一区| 久久久久免费| 国产精品看片资源| 亚洲精品欧美激情| 在线精品视频一区二区| 午夜精品国产更新| 一本久久综合亚洲鲁鲁五月天| 欧美主播一区二区三区| 亚洲免费在线看| 欧美日韩久久不卡| 亚洲国产精品久久久久久女王| 国内精品视频在线播放| 中日韩美女免费视频网址在线观看| 亚洲国产精品久久久久秋霞蜜臀 | 亚洲色诱最新| 一区二区日韩伦理片| 麻豆乱码国产一区二区三区| 久久久久久电影| 国产日韩在线视频| 亚洲嫩草精品久久| 午夜一区二区三区在线观看 | 久久久久www| 久久精品99无色码中文字幕| 国产精品第13页| 99视频精品全国免费| 一本色道久久综合亚洲精品高清| 麻豆精品视频在线观看| 欧美1区视频| 亚洲高清视频一区| 免费日韩av电影| 欧美刺激午夜性久久久久久久| 激情欧美亚洲| 久久久精彩视频| 女人色偷偷aa久久天堂| 亚洲国产精品一区二区第四页av| 久久综合九色99| 亚洲国产成人一区| 99精品热视频只有精品10| 欧美刺激午夜性久久久久久久| 亚洲国产成人久久综合| 日韩视频不卡| 国产精品久久久| 欧美一区二区三区精品电影| 久久综合网络一区二区| 亚洲电影视频在线| 欧美黄色免费网站| 一区二区高清视频| 久久激五月天综合精品| 在线电影国产精品| 欧美激情第六页| 一区二区激情| 久久久噜噜噜| 日韩亚洲欧美一区二区三区| 欧美视频福利| 欧美一区二区女人| 亚洲高清视频在线| 亚洲资源av| 亚洲大胆人体视频| 欧美日韩日本网| 欧美专区亚洲专区| 亚洲欧洲在线观看| 久久精品99国产精品| 亚洲肉体裸体xxxx137| 国产精品免费观看视频| 玖玖玖国产精品| 一区二区三区视频观看| 免费国产一区二区| 亚洲欧美区自拍先锋| 激情五月***国产精品| 欧美日韩一区二区三区在线观看免| 欧美在线观看视频在线 | 久久综合九色综合久99| 在线视频亚洲| 精久久久久久久久久久| 欧美午夜性色大片在线观看| 久久精品国产清高在天天线| 99伊人成综合| 欧美激情第五页| 久久精品123| 亚洲欧美日韩国产一区二区三区 | 欲色影视综合吧| 国产精品毛片| 欧美日本国产| 快播亚洲色图| 欧美一区91| 亚洲一区视频| 日韩视频一区二区三区在线播放免费观看 | 1024国产精品| 国产日韩在线看| 欧美午夜精品久久久久久孕妇| 美女爽到呻吟久久久久| 欧美中文在线免费| 亚洲一区久久久| 日韩一区二区精品葵司在线| 亚洲高清不卡av| 欧美成人亚洲| 蜜桃av一区二区| 久久久久中文| 久久人人爽人人爽爽久久| 久久www成人_看片免费不卡| 亚洲欧美成人一区二区在线电影 | 国产婷婷色一区二区三区在线| 欧美日韩一区二区视频在线| 欧美高清在线精品一区| 欧美成人a视频| 免费亚洲电影在线观看| 欧美不卡高清| 欧美国产日韩视频| 欧美a一区二区| 欧美成人精品激情在线观看| 六月婷婷一区| 欧美电影免费观看高清完整版| 欧美激情a∨在线视频播放| 欧美freesex8一10精品| 欧美aⅴ一区二区三区视频| 欧美电影在线免费观看网站| 欧美成年人视频网站| 欧美精品久久久久久久久老牛影院| 欧美激情综合在线| 欧美网站大全在线观看| 国产精品一区二区三区成人| 国产日本欧美在线观看| 黑人一区二区| 亚洲开发第一视频在线播放| 一区二区三区精品在线 | 一区二区三区在线免费播放| 亚洲国产黄色| 在线视频欧美一区| 久久精品国产欧美激情| 欧美激情一区在线| 日韩视频一区二区| 欧美与黑人午夜性猛交久久久| 久久看片网站| 欧美三级韩国三级日本三斤| 国产欧美日韩综合一区在线播放 | 欧美视频在线免费| 国产亚洲视频在线观看| 亚洲日本免费| 欧美一区二区免费观在线| 欧美成人免费全部| 在线综合亚洲欧美在线视频| 久久久精品国产99久久精品芒果| 欧美.www| 国内精品视频一区| 中文高清一区| 美女视频网站黄色亚洲| 日韩系列在线| 久久三级视频| 国产精品视屏| 亚洲九九精品| 久久视频在线免费观看| 一本久久综合| 免费不卡在线视频| 国产女主播视频一区二区| 亚洲精品在线二区| 久久精品色图| 中日韩美女免费视频网站在线观看| 久久一综合视频| 国产三区精品| 亚洲一区二区视频在线| 免费不卡在线观看| 香蕉久久夜色精品国产使用方法| 欧美精品福利在线| 亚洲国产成人在线视频| 久久免费黄色| 午夜伦理片一区| 国产精品久久久999| 99精品国产在热久久下载|