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
未總結。。。。。待續。。。