topcoder srm 420 div1
problem1 link
暴力即可。因為即便所有數字的和是50，50所有的不同的劃分數只有204226中。所以最長的循環也就這么大。
problem2 link
令$f[i][j]$表示有$i$個紅色和$j$個黑色時最大的期望，那么：
（1）當$j=0$時,$f[i][0]=f[i-1][0]+1$;
（2）當$j>0$但是$i=0$時,$f[i][j]=0$;
（3）當$j>0$且$i>0$時,$f[i][j]=max(0,(f[i-1][j]+1)*\frac{i}{i+j}+(f[i][j-1]-1)*\frac{j}{i+j})$
problem3 link
設$B$為$outputValues$中的最大值。
當$inputValue \geq B*(B-1)$時，在將$inputValue$置換后的輸出中一定有$B$。否則，將有大于等于$B$個小于等于$B-1$的數字。那么這大于等于$B$個數字中，一定有某些數字的和是$B$的倍數（$x_{1},x_{1}+x_{2},,,,,x_{1}+x_{2}+..+x_{n}$中要么存在$B$倍數的數字，要么一定存在兩個數字模$B$的值相等，它們的差就是$B$的倍數）。這時將其拿掉換成都是$B$得到的數字個數更小。
這樣的話，只需要解決小于$B*(B-1)$的部分（大于等于$B*(B-1)$的部分都可以直接換成若干$B$）。這里可以使用動態規劃。記錄置換$i$需要的最少數量以及在這種置換中用到的最大的是$outputValues$中哪一種。
這里需要解決的是，當$i$是$outputValues$中的某個數字時，一定要將$i$替換成至少兩個數字之和。可以令$bestPay[i]$表示將$i$置換所需要的最小的個數（可以是一個數字），$bestChange[i]$表示將$i$置換所需要的最小的個數（至少兩個數字），而$bestPayCoin[i],bestChangeCoin[i]$分別表示兩種情況下最大的是$outputValues$中哪一個。
有了這些，可以推導出小于$B*(B-1)$的$inputValue$被置換成了:
$t_{1}=bestChangeCoin[inputValue]$
$t_{2}=bestPayCoin[inputValue-t_{1}]$
$t3=bestPayCoin[inputValue-t_{1}-t_{2}]$
$...$
最后是對于最終答案的計算。可以從大到小依次置換每一種$outputValues$。
code for problem1
import java.util.*;
import java.math.*;
import static java.lang.Math.*; public class SolitaireSimulation { public int periodLength(int[] heaps) { List<Integer> list=new ArrayList<>();
for(int x:heaps) {
list.add(x);
}
List<Integer> list1=next(list);
while(!list.equals(list1)) {
list=next(list);
list1=next(next(list1));
}
int step=1;
list=next(list);
while(!list.equals(list1)){
++step;
list=next(list);
}
return step;
} List<Integer> next(List<Integer> list) {
List<Integer> list1=new ArrayList<>();
for(int i=0;i<list.size();++i) {
if(list.get(i)>1) {
list1.add(list.get(i)-1);
}
}
list1.add(list.size());
Collections.sort(list1);
return list1;
}
}
code for problem2
import java.util.*;
import java.math.*;
import static java.lang.Math.*; public class RedIsGood { public double getProfit(int R, int B) { double[][] f=new double[2][B+1];
for(int i=0;i<=B;++i) {
f[0][i]=0;
} int pre=0,cur=1; for(int i=1;i<=R;++i) {
for(int j=0;j<=B;++j) { if(j==0) {
f[cur][j]=i;
continue;
} double p=1.0*i/(i+j);
f[cur][j]=p*(f[pre][j]+1)+(1-p)*(f[cur][j-1]-1);
if(f[cur][j]<0) {
f[cur][j]=0;
}
}
pre^=1;
cur^=1;
}
return f[pre][B];
}
}
code for problem3
import java.util.*;
import java.math.*;
import static java.lang.Math.*; public class ChangeOMatic { public long howManyRounds(int[] outputValues,long inputValue) { if(outputValues.length==1) {
return 1;
} final int N=outputValues.length;
final int B=outputValues[N-1];
final int MAX=B*B+B+47;
int[] bestPay=new int[MAX];
int[] bestPayCoin=new int[MAX];
int[] bestChange=new int[MAX];
int[] bestChangeCoin=new int[MAX];
for(int i=0;i<MAX;++i) {
bestPay[i]=bestChange[i]=i;
}
for(int c=1;c<N;++c) {
for(int i=outputValues[c];i<MAX;++i) {
if(bestPay[i]>=bestPay[i-outputValues[c]]+1) {
bestPay[i]=bestPay[i-outputValues[c]]+1;
bestPayCoin[i]=c;
}
}
for(int i=outputValues[c]+1;i<MAX;++i) {
if(bestChange[i]>=bestPay[i-outputValues[c]]+1) {
bestChange[i]=bestPay[i-outputValues[c]]+1;
bestChangeCoin[i]=c;
}
}
} long[] coinCounts=new long[N]; if(inputValue>=MAX) {
coinCounts[N-1]=(inputValue-(MAX-1))/B;
inputValue-=coinCounts[N-1]*B;
if(inputValue>=MAX) {
inputValue-=B;
++coinCounts[N-1];
}
while(inputValue>0) {
++coinCounts[bestPayCoin[(int)inputValue]];
inputValue-=outputValues[bestPayCoin[(int)inputValue]];
}
}
else {
++coinCounts[bestChangeCoin[(int)inputValue]];
inputValue-=outputValues[bestChangeCoin[(int)inputValue]];
while(inputValue>0) {
++coinCounts[bestPayCoin[(int)inputValue]];
inputValue-=outputValues[bestPayCoin[(int)inputValue]];
}
} long result=1;
for(int q=N-1;q>0;--q) {
result+=coinCounts[q];
int remains=outputValues[q];
coinCounts[bestChangeCoin[remains]]+=coinCounts[q];
remains-=outputValues[ bestChangeCoin[remains ]];
while(remains>0) {
coinCounts[bestPayCoin[remains]]+=coinCounts[q];
remains-=outputValues[bestPayCoin[remains]];
}
}
return result;
}
}
總結
以上是生活随笔為你收集整理的topcoder srm 420 div1的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Linux系统运维笔记(五),CentO
- 下一篇： wrv汽车之家？