繼續(xù)補(bǔ)上srm的總結(jié)：
250pt
Problem Statement
Desertification (the process of good land turning into desert) is a severe problem on Bob's island. Bob's island is a rectangular grid of cells. You are given a vector <string> island that shows the current state of Bob's island. The j-th character of the i-th element of island is 'D' if cell in row i, column j of the grid is desert and is 'F' if this cell is forest.
The desert spreads each year as follows:
- If a cell is desert, it remains desert forever.
- If a cell is forest and it is adjacent to at least one desert cell (in one of the four orthogonal directions), it becomes desert after one year.
- Otherwise the cell remains forest for another year.
Return the number of desert cells after
T years.
Definition
Class:
Desertification
Method:
desertArea
Parameters:
vector <string>, int
Returns:
int
Method signature:
int desertArea(vector <string> island, int T)
(be sure your method is public)
Constraints
-
island will contain between 1 and 10 elements, inclusive.
-
Each element of island will contain between 1 and 10 characters, inclusive.
-
Each character in island will be 'D' or 'F'.
-
Each element of island will contain the same number of characters.
-
T will be between 1 and 1,000,000,000, inclusive.
記得當(dāng)時(shí)寫(xiě)了遍歷，如果一個(gè)是沙漠則把周圍的都設(shè)置為沙漠，這樣牽涉到一個(gè)問(wèn)題，循環(huán)到某年時(shí)候遇到的可能是剛剛變成沙漠的，因此需要每次用一個(gè)Vector<string> 記錄新的。
其實(shí)對(duì)每一個(gè)來(lái)計(jì)算在其T距離內(nèi)有沒(méi)有沙漠即可，復(fù)雜度 O(n^4)不過(guò)數(shù)據(jù)很小可以過(guò)
Code Snippet
int desertArea(vector <string> land, int T)
{
int r= land.size(); int c = land[0].size();
int cnt=0;
REP(i,r)REP(j,c) {
if(land[i][j] == 'D') {cnt++;continue;}
bool tag=false;
REP(x,r){
if(tag)break;
REP(y,c){
if(land[x][y]=='D'&&abs(x-i)+abs(y-j)<=T){
tag=true;break;
}
}
}
if(tag)cnt++;
}
return cnt;
}
500pt
Problem Statement
John is playing with balls. All of the balls are identical in weight and considered to have a zero radius. All balls are located on the same straight line and can move only along this line. If a ball rolling to the right and a ball rolling to the left at the same speed collide, they do not change speed, but they change direction.
You are given vector <int> x. x[i] is the initial position of the i-th ball. John decides the direction for each ball (right or left) with equal probability. At time 0, he rolls the balls in the chosen directions simultaneously at a speed of one unit per second. Return the expected number of bounces between all balls during T seconds (including those collisions that happen exactly at T seconds).
Definition
Class:
BouncingBalls
Method:
expectedBounces
Parameters:
vector <int>, int
Returns:
double
Method signature:
double expectedBounces(vector <int> x, int T)
(be sure your method is public)
Notes
-
There is no friction. Each ball continues rolling at the same speed forever.
-
Your return value must have an absolute or relative error less than 1e-9.
Constraints
-
x will contain between 1 and 12 elements, inclusive.
-
Each element of x will be between 0 and 100,000,000, inclusive.
-
All elements of x will be distinct.
-
T will be between 1 and 100,000,000, inclusive.
Examples
蠻有意思的題，只需要注意到，兩個(gè)球碰撞后立即反向，而且速度不變，可以看做兩個(gè)球穿越····然后枚舉所有可能的方向2^n種可能即可~~
Code Snippet
class BouncingBalls
{
public:
double expectedBounces(vector <int> x, int T)
{
int n = x.size();int ans=0;
sort(x.begin(),x.end());
REP(i,(1<<n)){
int mask=1;
vector<int> vec(n);
for(int k=0;k<n;k++,mask<<=1){
if(mask&i)vec[k] = x[k] + T;
else vec[k] = x[k] - T;
}
for(int a=0;a<n;a++)
for(int b=a+1;b<n;b++){
if(vec[a]>=vec[b])ans++;
}
}
return double(ans)/(1<<n);
}
500分和250分的基本都會(huì)用到一些簡(jiǎn)化的思想，化復(fù)雜為簡(jiǎn)單，化特殊為一般~
1000pt
Problem Statement
You are given six integers, minx, maxx, miny, maxy, minz and maxz. Return the number of triplets of integers (x,y,z) that satisfy the following three conditions:
- x is between minx and maxx, inclusive.
- y is between miny and maxy, inclusive.
- z is between minz and maxz, inclusive.
- x * y = z
Definition
Class:
ProductTriplet
Method:
countTriplets
Parameters:
int, int, int, int, int, int
Returns:
long long
Method signature:
long long countTriplets(int minx, int maxx, int miny, int maxy, int minz, int maxz)
(be sure your method is public)
Constraints
-
maxx will be between 1 and 1,000,000,000, inclusive.
-
maxy will be between 1 and 1,000,000,000, inclusive.
-
maxz will be between 1 and 1,000,000,000, inclusive.
-
minx will be between 1 and maxx, inclusive.
-
miny will be between 1 and maxy, inclusive.
-
minz will be between 1 and maxz, inclusive.
貼一下tutorial中的解釋，挺明白：
The problem asks about the number of triplets of integers (x, y, z), such that
x1 ≤ x ≤ x2
y1 ≤ y ≤ y2
z1 ≤ z ≤ z2
and x * y = z
Let's look at a special case of the problem. Given a fixed x0. Calculate the number of integer triplets (x0, y, z), such that
y1 ≤ y ≤ y2
z1 ≤ z ≤ z2
and x0 * y = z
The conditions on z will derive the following conditions on y.
z1 ≤ x0 * y ≤ z2
z1/x0 ≤ y ≤ z2/x0
ceil(z1/x0) ≤ y ≤ floor(z2/x0)
Another condition on y is y1 ≤ y ≤ y2. So, max(y1, ceil(z1/x0)) ≤ y ≤ min(y2, floor(z2/x0)) are the only limiting conditions on y and z, because any value of y in this range will give a valid (x0, y, z) triplet.
The number of candidate values to y is: min(y2, floor(z2/x0))-max(y1, ceil(z1/x0))+1, provided that the result of the subtraction is not negative. i.e.: the interval is not empty.
然后按照這種思想很容易得到第一種方法：
Code Snippet
int64 cacl(int x,int miny,int maxy,int minz,int maxz){
minz = max(minz,x*x+1);
if(minz>maxz)return 0;
miny = max(miny,(minz+x-1)/x);
maxy = min(maxy,maxz/x);
return max(0,maxy-miny+1);
}
class ProductTriplet
{
public:
long long countTriplets(int minx, int maxx, int miny, int maxy, int minz, int maxz)
{
int64 ans=0;
for(int64 i=minx;i<=maxx && i*i<maxz ;i++)
ans+=cacl(i,miny,maxy,minz,maxz);
for(int64 i=miny;i<=maxy && i*i<maxz ;i++)
ans+=cacl(i,minx,maxx,minz,maxz);
for(int64 i=max(minx,miny);i<=min(maxx,maxy) && i*i<=maxz;i++)
if(i*i>=minz)ans++;
return ans;
}
首先計(jì)算出x<sqrt(z) 然后y<sqrt(z) 最后x==y
注意cacl 中首先要更新minz至少為x*x+1保證x<y;
關(guān)鍵是想到x*y=z直接枚舉會(huì)超時(shí)，但是分別枚舉x,y 均在sqrt(z) 之內(nèi)可以完成
其他的方法：
Code Snippet
int64 cacl2(int x1,int x2,int y1,int y2,int z1,int z2){
int x=x1,y=y1;
int64 ans=0;
while(x<=x2 && y<=y2 && x*y<=z2){
int low = (z1+x-1)/x ;
int high = z2/x;
low = max(y,low);
high = min(y2,high);
if(high>=low)ans+=(high-low+1);
x++;
if(high-low<100)
swap(x,y),swap(x2,y2);
}
return ans;
}
int64 cacl(int x1,int x2,int y1,int y2,int z){
if(z==0)return 0;
int x=x1,y=y1;
int64 ans=0;
while(x<=x2 && y<=y2 && x*y<=z){
if(x>y){
swap(x2,y2);swap(x,y);
}
int k = z/x ;
int low = max(1,y);
int high = min(y2,k);
if(high>=low)ans+=(high-low+1);
x++;
}
return ans;
}
class ProductTriplet
{
public:
long long countTriplets(int minx, int maxx, int miny, int maxy, int minz, int maxz)
{
int64 ans = cacl(minx,maxx,miny,maxy,maxz);
return ans-cacl(minx,maxx,miny,maxy,minz-1);
/*return cacl(minx,maxx,miny,maxy,minz,maxz2);*/
}
一種使用cacl函數(shù)，計(jì)算1 ~maxz的可用對(duì)數(shù)，然后減去1~(minz-1)的可用對(duì)數(shù)即可
計(jì)算過(guò)程中，枚舉x的值，如果x>y則swap(x,y)其實(shí)也是保證枚舉次數(shù)不超過(guò)sqrt(z)
另一種方法使用cacl2函數(shù)直接計(jì)算結(jié)果，同樣枚舉x的值，不過(guò)在得到的y的值小于一定大小
->100 的時(shí)候交換x和y，這是基于此時(shí)枚舉y值可能更有效率而來(lái)的。
在計(jì)算ceil(x) 時(shí)候有點(diǎn)技巧 low = (z-1+x)/x;