problem1 link
枚举每一种大于等于$n$的计算其概率即可。
problem2 link
首先二分答案，然后计算。令$f[i][j]$表示移动完前$i$最后一个在位置$j$的最小代价。
problem3 link
假如一个数质因子分解为$n=p_{1}^{x_{1}}p_{2}^{x_{2}}..p_{t}^{x_{t}}$，那么其约数的个数为$(x_{1}+1)(x_{2}+1)..(x_{t}+1)$
所以只需要将$k$分解成若干数字之积，然后分配每个约数最小的一些质数即可。
令$f[i][j]$表示到第$i$个质数，还剩下的数字之积为$j$的最小值。
code for problem1
import java.util.*;
import java.math.*;
import static java.lang.Math.*; public class DrawingMarbles { public double sameColor(int[] colors,int n) {
int m=0;
for(int i=0;i<colors.length;++i) {
m+=colors[i];
}
double result=0;
for(int i=0;i<colors.length;++i) {
if(colors[i]<n) {
continue;
}
double t=1;
for(int k=0;k<n;++k) {
t*=1.0*(colors[i]-k)/(m-k);
}
result+=t;
}
return result;
}
}
code for problem2
import java.util.*;
import java.math.*;
import static java.lang.Math.*; public class ConnectTheCities { public int minimalRange(int distance, int funds, int[] position) {
Arrays.sort(position);
int low=1,high=distance;
int result=high;
while(low<=high) {
int mid=(low+high)>>1;
if(check(mid,distance,funds,position)) {
result=Math.min(result,mid);
high=mid-1;
}
else {
low=mid+1;
}
}
return result;
}
boolean check(int mid,int distance,int funds,int[] positions) {
final int n=positions.length;
int[][] f=new int[n+1][distance+1];
for(int i=0;i<n+1;++i) {
for(int j=0;j<distance+1;++j) {
f[i][j]=-1;
}
}
f[0][0]=0;
for(int i=1;i<=n;++i) {
for(int j=0;j<distance+1;++j) {
if(-1==f[i-1][j]) {
continue;
}
for(int k=j;k<=j+mid&&k<=distance;++k) {
final int cost=f[i-1][j]+Math.abs(positions[i-1]-k);
if(cost>funds) {
continue;
}
if(f[i][k]==-1||f[i][k]>cost) {
f[i][k]=cost;
}
}
}
}
for(int i=distance-mid;i<=distance;++i) {
if(i>=0&&f[n][i]!=-1) {
return true;
}
}
return false;
}
}
code for problem3
import java.util.*;
import java.math.*;
import static java.lang.Math.*; public class NumberOfDivisors { final static int N=100;
final static int MAX=50000;
final static long INF=1000000000000000000L; long[][] f=new long[N][MAX+1];
int[] p=new int[N]; public long smallestNumber(int n) {
if(n==1) {
return 1;
}
for(int i=0,k=2;i<N;++i) {
while(!isPrime(k)) {
++k;
}
p[i]=k++;
}
for(int i=0;i<N;++i) {
for(int j=0;j<n+1;++j) {
f[i][j]=-1;
}
}
return dfs(0,n)<=INF?dfs(0,n):-1;
} long dfs(int id,int n) {
if(n==1) {
return 1;
}
if(f[id][n]!=-1) {
return f[id][n];
}
f[id][n]=pow(p[id],n-1);
for(int i=2;i*i<=n;++i) {
if(n%i!=0) {
continue;
}
for(int j=0;j<2;++j) {
final int cur=j==0?i:n/i;
final int nxt=n/cur;
long t=pow(p[id],cur-1);
if(t>INF/dfs(id+1,nxt)) {
t=INF+1;
}
else {
t*=dfs(id+1,nxt);
}
if(f[id][n]>t&&t!=INF+1) {
f[id][n]=t;
}
}
}
return f[id][n];
} long pow(long n,long m) {
long result=1;
while(m>0) {
if(1==(m&1)) {
if(result>INF/n) {
return INF+1;
}
result*=n;
if(m==1) {
break;
}
}
if(n>INF/n) {
return INF+1;
}
n=n*n;
m>>=1;
}
return result;
} boolean isPrime(int x) {
for(int i=2;i*i<=x;++i) {
if(x%i==0) {
return false;
}
}
return true;
}
}