problem1 link
记录一个模$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 link
最朴素的方法应该是令$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<Double> list=new ArrayList<>();
for(int i=0;i<n;++i) {
double cur=0;
for(int j=i;j<n;++j) {
cur+=boardLength[j];
for(int k=0;k<m;++k) {
list.add(cur/painterSpeed[k]);
}
}
}
Collections.sort(list);
int low=0,high=list.size()-1;
int result=high;
while(low<=high) {
int mid=(low+high)>>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<m;++i) {
final double s=mid*painter[i]+1e-10;
for(int j=0;j<n;++j){
double x=0;
int y=j;
while(y<n&&x+board[y]<=s) {
x+=board[y++];
}
p[i][j]=y;
}
}
int[] f=new int[1<<m];
for(int i=1;i<(1<<m);++i) {
for(int j=0;j<m;++j) {
if((i&(1<<j))!=0) {
if(f[i^(1<<j)]==n) {
f[i]=n;
break;
}
f[i]=Math.max(f[i],p[j][f[i^(1<<j)]]);
}
}
}
return f[(1<<m)-1]==n;
}
}
problem3 link
分两步：
第一步，计算使用$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<List<Rational>> 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<Rational,Integer> 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<List<Rational>> 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<Rational,Integer> map2=new HashMap<>();
map2.put(need,0);
for(int i=1;i<=10;++i) {
for(int x=0;x<i;++x) {
final int y=i-x;
for(Rational xx:unall.get(x)) {
for(Rational yy:all.get(y)) {
mark(map2,Rational.unparallel(xx,yy),i,unall.get(i));
mark(map2,Rational.unserial(xx,yy),i,unall.get(i));
}
}
}
}
int result=17;
for(int i=0;i<=10;++i) {
for(Rational x:unall.get(i)) {
if(map1.containsKey(x)) {
result=Math.min(result,i+map1.get(x));
}
}
}
if(result==17) {
return -1;
}
return result;
}
void mark(Map<Rational,Integer> map,Rational object,int num,
List<Rational> list) {
if(object==null) {
return;
}
if(map.containsKey(object)) {
return;
}
map.put(object,num);
list.add(object);
}
}