problem1

记录一个模$k$之后的值是否出现过，出现过则出现循环，无解；否则最多$k$ 次一定能出现0.

import java.util.*;import java.math.*;import static java.lang.Math.*;public class ConcatenateNumber {		public int getSmallest(int number, int k) {		if(k==1) {			return 1;		}		boolean[] f=new boolean[k];		final long b=getbase(number);		int cur=0;		for(int i=1;;++i) {			cur=(int)((cur*b+number)%k);			if(cur==0) {				return i;			}			if(f[cur]) {				return -1;			}			f[cur]=true;		}	}	long getbase(int x) {		long result=1;		while(x>0) {			result*=10;			x/=10;		}		return result;	}}

　　

problem2

最朴素的方法应该是令$f[i][mask]$表示处理前$i$块板子使用的painter的集合是$mask$的最小值，但是这样会超时。

时间上可以接受的方法是二分。首先列举所有可能的时间，然后对时间进行二分。二分之后，令$p[i][j]$表示第$i$个painter从第$j$个board开始能涂到的板子的编号。然后进行动态规划。令$dp[mask]$表示$mask$集合的painter可以涂到的板子的最大编号。

import java.util.*;import java.math.*;import static java.lang.Math.*;public class PaintingBoards {	public double minimalTime(int[] boardLength, int[] painterSpeed) {		final int n=boardLength.length;		final int m=painterSpeed.length;		List
     
       list=new ArrayList<>();		for(int i=0;i
      
       >1;			if(check(list.get(mid),boardLength,painterSpeed)) {				result=Math.min(result,mid);				high=mid-1;			}			else {				low=mid+1;			}		}		return list.get(result);	}	boolean check(double mid,int[] board,int[] painter) {		final int n=board.length;		final int m=painter.length;		int[][] p=new int[m][n];		for(int i=0;i
      
     

　　

problem3

分两步：

第一步，计算使用$i$个可以拼成的集合$all[i]$,$1 \leq i \leq 10$；

第二步，从$\frac{a}{b}$开始进行逆向搜索，令集合$unall[i]$中的每个元素$x$表示$x$可以和某个$all[i]$中的元素$y$可以组装成$\frac{a}{b}$。

import com.sun.imageio.spi.RAFImageInputStreamSpi;import java.util.*;import java.math.*;import static java.lang.Math.*;public class BuildCircuit {	static long gcd(long x,long y) {		return y==0?x:gcd(y,x%y);	}	static class Rational {		public long p;		public long q;		public Rational() {}		public Rational(long x,long y) {			long t=gcd(x,y);			this.p=x/t;			this.q=y/t;		}		public static Rational parallel(Rational r1,Rational r2) {			return new Rational(r1.p*r2.p, r1.p*r2.q+r1.q*r2.p);		}		public static Rational unparallel(Rational r1,Rational r2)		{			long t=r1.q*r2.p-r1.p*r2.q;			if(t<=0) {				return null;			}			return new Rational(r1.p*r2.p,t);		}		public static Rational serial(Rational r1,Rational r2)		{			return new Rational(r1.p*r2.q+r1.q*r2.p,r1.q*r2.q);		}		public static Rational unserial(Rational r1,Rational r2)		{			long t=r1.p*r2.q-r1.q*r2.p;			if(t<=0){				return null;			}			return new Rational(t,r1.q*r2.q);		}		public boolean equals(Object object) {			Rational t=(Rational)object;			return p==t.p&&q==t.q;		}		public int hashCode() {			return (int)((p*1007+q)%1000000007);		}	}		public int minimalCount(int a,int b) {		List
     
      
       > all=new ArrayList<>();		for(int i=0;i<11;++i) {			all.add(new ArrayList<>());		}		Rational one=new Rational(1,1);		Rational two=new Rational(2,1);		all.get(1).add(one);		all.get(1).add(two);		Map
       
         map1=new HashMap<>();		map1.put(one,1);		map1.put(two,1);		for(int i=2;i<=10;++i) {			for(int x=1;x<=i-x;++x) {				final int y=i-x;				for(Rational xx:all.get(x)) {					for(Rational yy:all.get(y)) {						mark(map1,Rational.parallel(xx,yy),i,all.get(i));						mark(map1,Rational.serial(xx,yy),i,all.get(i));					}				}			}		}		List
        
         
          > unall=new ArrayList<>();		for(int i=0;i<11;++i) {			unall.add(new ArrayList<>());		}		Rational need=new Rational(a,b);		unall.get(0).add(need);		Map
          
            map2=new HashMap<>(); map2.put(need,0); for(int i=1;i<=10;++i) { for(int x=0;x
           
             map,Rational object,int num, List
            
              list) { if(object==null) { return; } if(map.containsKey(object)) { return; } map.put(object,num); list.add(object); }}