杯具的比賽~第一題竟然把南和北寫反了- -！第二題沒判斷好復雜度，實際上暴力方法可以的，第三題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:
- Petya first selects a rectangle of cells of width, w, and height, h, where both are at least 3.
- Then he removes a rectangular hole of width w-2 and height h-2 centered in the larger rectangle.
- 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;
}