problem1

枚举每一种大于等于$n$的计算其概率即可。

problem2

首先二分答案，然后计算。令$f[i][j]$表示移动完前$i$最后一个在位置$j$的最小代价。

problem3

假如一个数质因子分解为$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

　　

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
     
      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
     
      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;	}}