problem1 link
这个的结论是只需要考虑坐标是整数或者是整数.5，比如(2.5,3),(4,3.5),(1.5,4.5)这样的时候。这个详细证明起来应该挺麻烦的。这里有一些讨论。
problem2 link
首先，可以暴力看下$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）当$kleq 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 link
可以把问题转化为可以构造多少种不同的长度为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<x.length;++t) {
a[t]=Math.abs(xx-x[t])+Math.abs(yy-y[t]);
}
Arrays.sort(a);
if(a[k-1]<min) {
min=a[k-1];
}
}
}
return min;
}
}
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<Long,Integer> 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<msg.length();++i) {
int u=get(msg.charAt(i));
int v=get(encMsg.charAt(i));
if(u%26==v%26) {
return 0;
}
if(p[u]!=-1&&p[u]!=v||q[v]!=-1&&q[v]!=u) {
return 0;
}
p[u]=v;
q[v]=u;
}
int[][] c=new int[3][3];
for(int i=0;i<26;++i) {
int x=0,y=0;
if(p[i]==-1) {
++x;
}
if(p[i+26]==-1) {
++x;
}
if(q[i]==-1) {
++y;
}
if(q[i+26]==-1) {
++y;
}
++c[x][y];
}
return dfs(c);
}
int dfs(int[][] c){
final long h=hash(c);
if(map.containsKey(h)) {
return map.get(h);
}
int c1=-1,c2=0;
for(int i=2;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;
}
}