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

未总结。。。。。待续。。。