O(1) 的小樂

  D.Jaamaa   92475  兩個騙子。。只能這么說了。。本來一場公平好玩的比賽。。竟然被搞成了這個樣子。。也經常有一些coder。。竟然注冊小號來賺個排名。。唉，你們的道德都淪喪到什么程度了。。。竟然在這種行業中，也有這么惡心的人。。看來這就是社會。。沒有辦法。。

   SRM 483 DIV 2 是一場超級簡單的題目，DIV 1 是一個超級trick的題目。。在DIV 2中500也算是一個trick點。。。

DIV 2 250

異常簡單，這種題目出現在DIV 250里面實在是純粹拼手速。。

DIV 2 500

注意當numberfriends的個數是1的時候。。。無數人fail在了這個點上，也成就了很多人challenge的成功！

DIV 2 1000

一個很簡單的二分方法，枚舉分母，然后二分分子。。。。思考的時候，有一個點差點沒有想出來--------> 怎么把一個分數，提取出它的100位小數。。這個實在是大腦短路。。分子乘以10，然后除以分母，獲得的除數就是了。。暈。。。

string findFraction(int maxDen, string number)
    {
        int rA = -1, rB = -1, rF = -1, len = (int)number.length()-2;
        for (int i = 1 ; i <= maxDen; ++i)
        {
            int L = 0, R = i-1;
            while (L <= R)
            {
                int M = (L+R)/2;
                string s = "0."; 
                int A = M, B = i;
                int diff = 0;
                int F = 0;
                for (int j = 0 ; j < len; ++j)
                {
                    A *= 10;
                    int D = A/B;
                    A -= D*B;
                    if (!diff && number[j+2] == '0'+D) ++F;
                    if (!diff) if (number[j+2] > '0'+D) diff = -1;
                    else if (number[j+2] < '0'+D) diff = 1;
                    //s = s + char(D+'0');
                }
                //for (int j = 2; j < len+2 && s[j]==number[j]; ++j, ++F);
                if (F > rF)
                {
                    //printf("%s --> %s\n", number.c_str(), s.c_str());
                    rF = F;
                    rA = M, rB = i;
                }
                if (!diff) break;
                if (diff > 0){
                    R = M-1;
                }else{
                    L = M+1;
                }
            }
        }
        memset(str, 0, sizeof(str));
        sprintf(str, "%d/%d has %d exact digits", rA, rB, rF+1);
        return string(str);
    }

=========================================================

不算華麗的分割線

========================================================

DIV 1

和DIV2 1000非常類似，但是數據范圍變小了，使得枚舉成了可能。。。。

string BestApproximationDiv1::findFraction(int x, string number) {  
  int best = -1;
  int q, w;
  FOR (i, 1, x+1) {
    REP (j, i) {
      int t = j;
      int res = 1;
      REP (f, 6) {
        t *= 10;
        int d = t / i;
        t %= i;
        if (d != number[f+2]-'0')
          break;
        ++res;
      }
      if (res > best) {
        best = res;
        q = j;
        w = i;
      }
    }
  }
  ostringstream str;
  str << q << '/' << w << " has " << best << " exact digits";
  return str.str();
}

DIV 500

Dp問題，把所有的點的resistence都降到0或者0一下需要的最少的次數

int F[55][1<<16];
bool b[55];
int in[55], resi[55];
int n;

bool check(int id){
    if(id<0) return true;
    int total=0;
    for(int i=-8;i<=8;i++) if(0<=id+i && id+i<n) {
        if(b[id+i]) total += in[id+i] / (1 << abs(i));
    }
    return (total >= resi[id]);
}

int calc(int i){
    if(i==n)
    {
        bool ok=true;
        for(int j=8;j>=1;j--) if(!check(i-j)) { ok=false; break; }
        if(ok) return 0;
        else return 1000000000;
    }
    int s=0;
    for(int j=max(i-16,0);j<=i-1;j++) s=s*2+b[j];
    int &ret=F[i][s];
    if(ret!=-1)return ret;
    ret=1000000000;
    b[i]=1;
    if(check(i-8)) ret=min(ret,1+calc(i+1));
    b[i]=0;
    if(check(i-8)) ret=min(ret,0+calc(i+1));
    return ret;
}

int Bribes::minBribes(vector <int> influence, vector <int> resistance) {
    memset(F,-1,sizeof(F));
    memset(b,0,sizeof(b));
    n=influence.size();
    for( int i=0;i<n;i++)in[i]=influence[i];
    for(int i=0 ;i<n;i++)resi[i]=resistance[i];
    int res = calc(0);
    if(res > 1000) return -1;
    return res;
}

有時間詳細總結

DIV 1000

未總結。。。。。待續。。。