DIV 2
250 PointErasingTwo
在二維平面內有一些點，坐標已知，當選擇平面內的兩個點作為矩形的對角點，問一次最多可以刪掉的點是多少個
遍歷就好Easy
int getMaximum(vector <int> y)
{
int ret=0;
for( int i=0; i<y.size(); i++)
{
for(int j=i+1; j<y.size(); j++)
{
if(y[i] > y[j])
{
int res=0;
for(int k=i+1; k<j; k++)
{
if(y[k] > y[j] && y[k] < y[i]) res++;
}
ret=max(res,ret);
}
if(y[i] < y[j])
{
int res=0;
for(int k=i+1; k<j; k++)
{
if( y[k]> y[i] && y[k]< y[j]) res++;
}
ret=max(res,ret);
}
}
}
return ret;
}
600 RowAndManyCoins
給定一個AB雜亂的序列串，A和B可以做如下操作，選擇連續一段，然后刪除掉。最后一個刪除的如果是A，則A勝，是B則B勝。A先手，
很簡單的博弈，考慮極端情況，A先手，如果字符串是A* 或者*A，則A做的操作是刪除掉*即可。如果是B*B，則A必敗。當A做了先手之后，則B的操作就是把A的所做的某一邊操作覆蓋成B*__B 或者 B__*B 下劃線為B的操作。
string getWinner(string cells)
{
if(cells[0]=='A'|| cells[cells.size()-1]=='A') return "Alice";
else return "Bob";
}
900 CorrectMultiplicationTwo
給定正整數 a,b,c 求a,b,c 加以調整之后滿足A*B=C,min(abs(A-a)+abs(B-b)+abs(C-c)) 數據范圍是10^5
一個非常直觀的想法是調整A和B使得C盡量少的變化就OK，非常直觀的是 A*(B+1)=C+A (A+1)*B=C+B, A 或者B 改變1 ，那么C就要付出A或者B的改變代價
所以C是可以盡量不動的。所以解法就非常直觀了，調整A，B即可。
int getMinimum(long long a, long long b, long long c)
{
long long ret=1000000LL* 10000000LL;
for(long long A=1; A<=1000000; A++)
{
for(long long dB=0; dB<2; dB++)
{
long long B= c/A + dB;
if(B==0) continue;
long long C= A*B;
if(abs(A-a)+ abs(B-b) + abs(C-c)< ret) ret=abs(A-a)+ abs(B-b) + abs(C-c);
}
}
return ret;
}
DIV 1
250 RowAndCoins
同DIV2 的500
450 CorrentMultiplication
題意同DIV2 的900,數據規模為 10^9 ，很顯然O(n)是不可以的。
在基于上述的觀察之后，我們可以獲得一個更進一步的觀察。A*B=C,既然C的數據規模只有10^9，那么A和B中較小的那個必然小于sqrt(10^9).
枚舉A和B中較小的那個可以取到的值就OK了！！所以復雜度降到了O(sqrt(n))
long long getMinimum(int a, int b, int c)
{
long long ret = LONG_LONG_MAX;
long long LIM = 100000;
cout<<LONG_LONG_MAX<<endl;;
cout<<INT_MAX<<endl;
for(long long A=1; A<=LIM; A++)
{
for(long long dB=0; dB<2; dB++)
{
long long B= c/A + dB;
if(B==0) continue;
long long C= A*B;
if(abs(A-a)+ abs(B-b) + abs(C-c)< ret) ret=abs(A-a)+ abs(B-b) + abs(C-c);
if(ret==0) return 0LL;
}
}
swap(a,b);
for(long long A=1; A<=LIM; A++)
{
for(long long dB=0; dB<2; dB++)
{
long long B= c/A + dB;
if(B==0) continue;
long long C= A*B;
if(abs(A-a)+ abs(B-b) + abs(C-c)< ret) ret=abs(A-a)+ abs(B-b) + abs(C-c);
if(ret==0) return 0LL;
}
}
return ret;
}
1050 PointErasing
給定一個序列，求刪除一些點之后，使得獲得的序列中不存在3個數形成嚴格升序或者嚴格降序。求剩余的點數的可能值
可以確定的是一個DP，但是不太確定狀態怎么表示。。。這周末研究一下。。