1. 给个数组，需要移除k个数使得这个数组的最大公因数为1，求k，不存在输出-1。AC
看整个序列的最大公约数是不是1，是1 返回0，不是1返回-1。
import java.util.*;
public class Main20200811001 {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int i=0;i<T;i++){
int N = sc.nextInt();
int[] arr = new int[N];
for(int ii=0;ii<N;ii++){
arr[ii] = sc.nextInt();
}
int g = arr[0];
for(int ii=1;ii<N;ii++){
g = gcd(arr[ii], g);
if(g==1){
break;
}
}
if(g==1){
System.out.println(0);
}else{
System.out.println(-1);
}
}
}
public static int gcd(int a, int b){
if(b==0){
return a;
}
return gcd(b, a%b);
}
}
2. 求a mod x = b的解的个数。90%
不知道哪里错了。。。
import java.util.*;
public class Main20200811002 {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
long a = sc.nextLong();
long b = sc.nextLong();
if(a==b){
System.out.println("inf");
return ;
}
long t;
if(a-b>0){
t = a-b;
}else{
t = b-a;
}
int ans = 0;
long k = 1;
for(;t>k*b && t/k>=1;k++){ // 保证 x>b,x>=1 k越来越大，x越来越小
if(k>100000000){
System.out.println("inf");
return ;
}
if(t%k!=0){ // x不是整数
continue;
}
ans++; // x=t/k
}
System.out.println(ans);
}
}
3. 给定矩阵地图，有不可行点。自己选择起点或终点，问最短路径的最大值为多少。AC
遍历起点，对每个起点BFS
import java.util.*;
public class Main20200811003 {
static int H;
static int M;
static int[][] next = {{0,-1}, {-1,0}, {1,0}, {0,1}};
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
H = sc.nextInt();
M = sc.nextInt();
sc.nextLine();
char[][] table = new char[H][M];
for(int i=0;i<H;i++){
String line = sc.nextLine();
table[i] = line.toCharArray();
}
int ans = 0;
for(int x=0;x<H;x++){
for(int y=0;y<M;y++){
if(table[x][y]=='.'){
int tmp = bfs(x*100+y, table);
ans = Math.max(ans, tmp);
}
}
}
System.out.println(ans);
}
public static int bfs(int start, char[][] table){
int[][] isVis = new int[H][M];
LinkedList<Integer> pre = new LinkedList<>();
LinkedList<Integer> cur = new LinkedList<>();
cur.add(start);
isVis[start/100][start%100] = 1;
int ans = -1;
while(cur.size()>0){
ans++;
pre = cur;
cur = new LinkedList<>();
for(int pos: pre){
int x = pos/100;
int y = pos%100;
for(int i=0;i<4;i++){
int nx = x+next[i][0];
int ny = y+next[i][1];
if(nx>=0&&nx<H && ny>=0&&ny<M && isVis[nx][ny]==0 && table[nx][ny]=='.'){
cur.add(nx*100+ny);
isVis[nx][ny]=1;
}
}
}
}
return ans;
}
}
4. 4个人，每个人有一些音乐，给定所有音乐长度，选择若干首播放，并行播放时，最长结束时间和最短结束时间的差最小为多少。AC
暴力，首先得到每个人的所有播放时间长度，然后4个for循环，可过60%，加剪枝（如果当前时间差大于ans,就跳过）可过100%
import java.util.*;
public class Main20200811004 {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] a = new int[4][n];
for(int i=0;i<4;i++){
for(int j=0;j<n;j++) {
a[i][j] = sc.nextInt();
}
}
int[] s0 = gen(a[0],n);
int[] s1 = gen(a[1],n);
int[] s2 = gen(a[2],n);
int[] s3 = gen(a[3],n);
int ans = Integer.MAX_VALUE;
int[] d = new int[4];
for(int i0=0;i0<s0.length;i0++){
d[0] = s0[i0];
for(int i1=0;i1<s1.length;i1++){
d[1] = s1[i1];
if(Math.abs(d[0]-d[1])>ans){
continue;
}
for(int i2=0;i2<s2.length;i2++){
d[2]= s2[i2];
if(Math.abs(d[0]-d[2])>ans){
continue;
}
if(Math.abs(d[1]-d[2])>ans){
continue;
}
for(int i3=0;i3<s3.length;i3++){
d[3] = s3[i3];
if(Math.abs(d[0]-d[3])>ans){
continue;
}
if(Math.abs(d[1]-d[3])>ans){
continue;
}
if(Math.abs(d[2]-d[3])>ans){
continue;
}
int minD = d[0], maxD = d[0];
for(int tt=0;tt<4;tt++){
if(d[tt]<minD) minD = d[tt];
if(d[tt]>maxD) maxD = d[tt];
}
int curAns = maxD - minD ;
ans = Math.min(ans, curAns);
}
}
}
}
System.out.println(ans);
}
public static int[] gen(int[] arr, int n){
ArrayList<Integer> ansl = new ArrayList<>();
for(int idx=0;idx<n;idx++){
int curn = ansl.size();
for(int i=0;i<curn;i++){
ansl.add(ansl.get(i)+arr[idx]);
}
ansl.add(arr[idx]);
}
ansl.sort((a,b)->(a-b));
int[] rst = new int[ansl.size()];
int len = 0;
int pre = -1;
for(int i=0;i<ansl.size();i++){
int cur = ansl.get(i);
if(pre==cur){
continue;
}else{
rst[len] = cur;
pre = cur;
len++;
}
}
return Arrays.copyOfRange(rst, 0, len);
}
}
全部评论
(18) 回帖