problem1

这个的结论是只需要考虑坐标是整数或者是整数.5，比如(2.5,3),(4,3.5),(1.5,4.5)这样的时候。这个详细证明起来应该挺麻烦的。有一些讨论。

problem2

首先，可以暴力看下$n=3,4$时的情况。

$n=3$,

000

001

011

010

110

100

101

111

$n=4$,

0000

0001

0011

0010

0110

0100

0101

0111

1111

1000

1001

1011

1010

1110

1100

1101

这时候可以发现，规律是最高位从0变到1的时候，后面的位数进行了一次shift。

而题目是求最大值，即getMax(n,k)。

（1）当$k\leq 2^{n-1}$时，getMax(n,k)="0"+getMax(n-1,k)

（2）当$k=1+ 2^{n-1}$时，getMax(n,k)="1"+get(n-1,$2^{n-1}$)

（3）当$k>1+ 2^{n-1}$时，getMax(n,k)="1"+max(get(n-1,$2^{n-1}$),getMax(n-1,k-m-1))

其中，get(n,k)表示得到长度为$n$的第$k$个串。

 

problem3

可以把问题转化为可以构造多少种不同的长度为52的(msg,encMsg)二元对（只是msg中是已经排序的）。现在$msg$中的某些位置已经确定。只需要考虑那些未确定的即可。

每次可以选择一个在原串中未确定的最小(防止重复)的，枚举它匹配加密串中未确定的每一个可合法匹配的。

另外，在原串中，一个字符可能使用了0次、1次、2次，也就是还可以使用2次、1次、0次，同样一个字符在加密串中还可以使用2次、1次、0次。所以搭配一下有3*3=9种情况，（x,y）表示在原串中还可以使用$x$次，在加密串中还可以使用$y$次的的字符种类数

那么每次需要从(2,*),(1,*)中选择一个匹配(*,1)或者(*,2)中的一个。

code for problem1

import java.util.*;import java.math.*;import static java.lang.Math.*;public class TheNewHouseDivOne {		public double distance(int[] x, int[] y, int k) {		double min=1e10;		double[] a=new double[x.length];		for(int i=0;i<=200;++i) {			for(int j=0;j<=200;++j) {				final double xx=-50+i*0.5;				final double yy=-50+j*0.5;				for(int t=0;t

　　

code for problem2

import java.util.*;import java.math.*;import static java.lang.Math.*;public class TheLockDivOne {	public String password(int n, long k) {		return getMax(n,k);	}	String getMax(int n,long k) {		if(n==1) {			return k==1?"0":"1";		}		long m=1l<<(n-1);		if(k<=m) {			return "0"+getMax(n-1,k);		}		else if(k==m+1) {			return "1"+get(n-1,m);		}		else {			String a=get(n-1,m);			String b=getMax(n-1,k-m-1);			if(a.compareTo(b)<0) {				return "1"+b;			}			return "1"+a;		}	}	String get(int n,long k) {		if(n==1) {			return k==1?"0":"1";		}		long m=1l<<(n-1);		if(k<=m) {			return "0"+get(n-1,k);		}		else if(k==m+1) {			return "1"+get(n-1,m);		}		else {			return "1"+get(n-1,k-m-1);		}	}}

　

code for problem3

import java.util.*;import java.math.*;import static java.lang.Math.*;public class TheEncryptionDivOne {	static final int MOD=1234567891;	Map
     
       map=new HashMap<>();	public int count(String msg, String encMsg) {		int[] p=new int[52];		int[] q=new int[52];		Arrays.fill(p,-1);		Arrays.fill(q,-1);		for(int i=0;i
      
       =1&&c1==-1;--i) {			for(int j=2;j>=0;--j) {				if(c[i][j]>0) {					c1=i;					c2=j;					break;				}			}		}		if(c1==-1) {			map.put(h,1);			return 1;		}		int result=0;		for(int i=2;i>=0;--i) {			for(int j=2;j>=1;--j) {				if(c[i][j]==0) {					continue;				}				long num=c[i][j]*j;				if(i==c1&&j==c2) {					num-=j;				}				if(num<=0) {					continue;				}				--c[i][j];				--c[c1][c2];				++c[i][j-1];				++c[c1-1][c2];				result=(int)((result+dfs(c)*num)%MOD);				++c[i][j];				++c[c1][c2];				--c[i][j-1];				--c[c1-1][c2];			}		}		map.put(h,result);		return result;	}	int get(char c) {		if(c>='A'&&c<='Z') {			return c-'A';		}		return c-'a'+26;	}	long hash(int[][] c) {		long ans=0;		for(int i=0;i<3;++i) {			for(int j=0;j<3;++j) {				ans=(ans<<5)|c[i][j];			}		}		return ans;	}}