4.29 京东笔试 题解
两个题 都AC了 尝试发一下题解
1、就是一个尝试的模型。我这里让n 表示较大的，k表示较小的。
考虑1-n 每一个位置
边界：n-k+1 此时可以竖着放，可以横着放，放完之后没有别的选择，返回2
大于边界位置 只能竖着 所以1
其他 就是尝试每一个位置 如果竖着放 那可以去 下一个位置
横着放 长度是k 意味着下面的全是横着 所以去i+k
这样写只能82% 超时 于是 dp优化一下
package jd.c01;
import java.util.HashMap;
import java.util.Scanner;
/*
题目描述：
Alice需要用n块相同的大小为1*k的方形地砖铺满一块大小为n*k的地板。她数学不是很好，所以希望你帮她计算有多少种不同的铺法。
如下图，使用5块大小为1*3的方形地砖铺满一块大小为5*3的地板总共有四种铺法。
输入仅包含一行，这行仅包含两个数n(1<=n<=10000)，k(1<=k<=1000)，代表题目中的参数。
输出所求的答案。因为答案可能很大，你只需要输出答案除以998244353所得的余数。
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), k = in.nextInt();
int max = Math.max(n, k);
int min = max==n ? k: n;
System.out.println(prcoessdp(max, min));
//System.out.println(process(max, min, 1, new HashMap<>()));
}
//n > k
public static long process(int n, int k, int index, HashMap<Integer, Long> map){
if(map.containsKey(index)){
return map.get(index);
}
if(index > n) return -1;
long ans = 0;
if(index == n-k+1){
// ans = process(n, k, index+1, map) + 1;
ans = 2;
}else if(index > n-k+1){
ans= 1;
}else{
long p1= process(n,k,index+1, map);
long p2 = process(n,k,index+k, map);
p1 = p1 % 998244353;
p2 = p2 % 998244353;
if(p1 == -1) p1=0;
if(p2 == -1) p2=0;
ans = p1+p2;
}
ans = ans % 998244353;
map.put(index, ans);
return ans;
}
public static long prcoessdp(int n, int k){
long[] dp = new long[n+1];
for(int i = n; i > n-k+1;i--)
dp[i] = 1;
dp[n-k+1] = 2;
for(int i = n-k+1-1; i >= 1; i--){
long p1 = 0, p2 = 0;
if(i+k <= n){
p1 = dp[i+k];
}
p2 = dp[i+1];
dp[i] = (p1+p2)% 998244353;
}
return dp[1];
}
} 2、最开始想法 一个一个试 好复杂
最后：构建一张图，每一个点计算 他们的距离 认为是图的一个边
prim最小生成树 求最小生成树的 最大边 是多长 就可以了
代码里那个max min啥的 没用哈 都是自己的最开始想法 不对（最开始以为求所有距离的 最大值 ）
package jd.c02;
import java.util.Scanner;
/*
Alice和Bob需要采购会议场馆内的无线路由器。每一种路由器有一个参数k用于度量其通信距离。将场馆视为一个二维平面并将路由器视为该平面上的点，两台参数为k的路由器只能在他们所在位置的曼哈顿距离不超过k的前提下直接通信。两个点(x1,y1)和(x2,y2)之间的曼哈顿距离被定义为|x1-x2|+|y1-y2|。
给出场馆内需要安装无线路由器的所有位置的坐标，请你计算出若他们只采购一种路由器，则其参数k至少需要为多少才能使得任意两个路由器之间都能够互相通信。
能够互相通信的定义如下：存在一个路由器序列v1,v2,…,vc，该序列中任意两个相邻路由器之间可以直接连接，则v1和vc之间可以互相通信。
*/
/*
第一行有一个正整数n(1<=n<=1000)，代表需要安装路由器的位置数量。
第二行有n个整数，第i个代表编号为i的位置的x坐标。
第三行有n个整数，第i个代表编号为i的位置的y坐标。
坐标的绝对值不超过1000000000。
输出一个正整数，代表能够使得任意两个路由器在允许中继的前提下能够互相通信的参数的最小值。
*/
public class Main {
static long[] x;
static long[] y;
static int n;
public static void main(String[] args) {
//System.out.println(Long.MAX_VALUE);
Scanner in= new Scanner(System.in);
n = in.nextInt();
x = new long[n];
y = new long[n];
long xmax=Long.MIN_VALUE, xmin=Long.MAX_VALUE, ymax=Long.MIN_VALUE, ymin=Long.MAX_VALUE;
for(int i=0; i < n;i++){
x[i] = in.nextLong();
xmax = Math.max(xmax, x[i]);
xmin = Math.min(xmin, x[i]);
}
for(int i=0; i < n;i++){
y[i] = in.nextLong();
ymax = Math.max(ymax, y[i]);
ymin = Math.min(ymin, y[i]);
}
Long max = Long.MIN_VALUE;
Long min = Long.MAX_VALUE;
long[][] graph = new long[n][n];
for(int i = 0; i < n; i++)
for(int j = 0; j <n; j++)
graph[i][j] = Long.MAX_VALUE;
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
long dis = distance(i, j);
graph[i][j] = dis;
graph[j][i] = dis;
max = Math.max(max, dis);
min = Math.min(min, dis);
}
}
//左下角的点 右上角的点
long ans = prim(graph);
if(ans == -1)
System.out.println(max);
else
System.out.println(ans);
}
public static long distance(int i, int j){
long x1 = Math.abs(x[i]-x[j]);
long y1 = Math.abs(y[i] - y[j]);
return x1 + y1;
}
public static long prim(long[][] graph){
long[] dis = new long[n];
boolean[] isVisit = new boolean[n];
isVisit[0] = true;
long ans = Long.MIN_VALUE;
for(int i = 0; i < n; i++){
dis[i] = graph[0][i];
}
for(int i = 1; i < n; i++){
long minPath = Long.MAX_VALUE;
int index = -1;
for(int j = 0; j < n; j++){
if(!isVisit[j] && dis[j] < minPath){
minPath = dis[j];
index = j;
}
}
if(index == -1){
return -1;
}
isVisit[index] =true;
ans = Math.max(ans, minPath);
for(int j = 0; j < n; j++){
if(!isVisit[j] && dis[j] > graph[index][j]){
dis[j] = graph[index][j];
}
}
}
return ans;
}
} 
