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，但是不太確定狀態怎么表示。。。這周末研究一下。。