双指针、bfs与图论

1238. 日志统计 - AcWing题库 

import java.util.*;class PII implements Comparable<PII>{int x, y;public PII(int x, int y){this.x = x;this.y = y;}public int compareTo(PII o){return Integer.compare(x, o.x);}
}public class Main{static int N = 100010, D, K;static int[] cnt = new int[N];static PII[] a = new PII[N];static boolean[] st = new boolean[N];public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();D = sc.nextInt();K = sc.nextInt();for(int i = 0; i < n; i ++){int ts = sc.nextInt();int id = sc.nextInt();a[i] = new PII(ts, id);}Arrays.sort(a, 0, n);for(int i = 0, j = 0; i < n; i ++){//i比j快int id = a[i].y;cnt[id] ++;while(a[i].x - a[j].x >= D){cnt[a[j].y] --;j ++;}if(cnt[id] >= K) st[id] = true;}for(int i = 0; i <= 100000; i ++){if(st[i]) System.out.println(i);}}
}

1101. 献给阿尔吉侬的花束 - AcWing题库 

import java.util.*;class PII{int x, y;public PII(int x, int y){this.x = x;this.y = y;}
}public class Main{static int N = 210;static int r, c;static char[][] g = new char[N][N];static int[][] dist = new int[N][N];static int[] dx = {-1, 0, 1, 0};static int[] dy = {0, 1, 0, -1};static PII start, end;public static int bfs(PII start, PII end){Queue<PII> q = new LinkedList<>();for(int i = 0; i < r; i ++){Arrays.fill(dist[i], -1);}q.offer(start);dist[start.x][start.y] = 0;while(!q.isEmpty()){PII t = q.poll();for(int i = 0; i < 4; i ++){int x = t.x + dx[i];int y = t.y + dy[i];if(x < 0 || x >= r || y < 0 || y >= c) continue;if(g[x][y] == '#') continue;if(dist[x][y] != -1) continue;dist[x][y] = dist[t.x][t.y] + 1;if(end.x == x && end.y == y) return dist[x][y];q.offer(new PII(x, y));}}return -1;}public static void main(String[] args){Scanner sc = new Scanner(System.in);int T = sc.nextInt();while(T -- > 0){r = sc.nextInt();c = sc.nextInt();for(int i = 0; i < r; i ++){char[] s = sc.next().toCharArray();for(int j = 0; j < c; j ++){g[i][j] = s[j];if(g[i][j] == 'S') start = new PII(i, j);if(g[i][j] == 'E') end = new PII(i, j);}}int res = bfs(start, end);if(res == -1) System.out.println("oop!");else System.out.println(res);}}
}

1113. 红与黑 - AcWing题库 

import java.util.*;public class Main{static int N = 25;static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};static int n, m, res;static char[][] g = new char[N][N];static boolean[][] st = new boolean[N][N];public static void dfs(int x, int y){res ++;st[x][y] = true;for(int i = 0; i < 4; i ++){int a = x + dx[i];int b = y + dy[i];if(a < 0 || b < 0 || a >= n || b >= m) continue;if(st[a][b]) continue;if(g[a][b] == '#') continue;dfs(a, b);}}public static void main(String[] args){Scanner sc = new Scanner(System.in);while(true){m = sc.nextInt();n = sc.nextInt();//这里是先行后列if(n == 0 && m == 0) break;res = 0;int x = -1, y = -1;for(int i = 0; i < n; i ++){String s = sc.next();for(int j = 0; j < m; j ++){g[i][j] = s.charAt(j);st[i][j] = false;if(g[i][j] == '@'){x = i;y = j;}}}dfs(x, y);System.out.println(res);}}
}

1224. 交换瓶子 - AcWing题库

import java.util.*;public class Main{static int N = 10010;static int[] a = new int[N];static boolean[] st = new boolean[N];public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();for(int i = 1; i <= n; i ++){a[i] = sc.nextInt();}int res = 0;for(int i = 1; i <= n; i ++){if(!st[i]){res ++;for(int j = i; !st[j]; j = a[j]){st[j] = true;}}}System.out.print(n - res);}
}

 

1240. 完全二叉树的权值 - AcWing题库

import java.util.*;public class Main{static int N = 100010;static int[] w = new int[N];public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();for(int i = 1; i <= n; i ++) w[i] = sc.nextInt();int depth = 0;long max = -0x3f3f3f3f;for(int i = 1, k = 1; i <= n; i *= 2, k ++){long sum = 0;for(int j = i; j < i + (1 << (k - 1)) && j <= n; j ++){sum += w[j];}if(sum > max){max = sum;depth = k;}}System.out.print(depth);}
}

 

1096. 地牢大师 - AcWing题库

import java.util.*;class PII{int x, y, z;public PII(int x, int y, int z){this.x = x;this.y = y;this.z = z;}
}public class Main{static int N = 110;static int L, R, C;static char[][][] g = new char[N][N][N];static int[][][] dist = new int[N][N][N];static boolean[][][] st = new boolean[N][N][N];static PII start, end;static int[] dx = {0, 0, -1, 0, 1, 0}, dy = {0, 0, 0, 1, 0, -1}, dz = {-1, 1, 0, 0, 0, 0};public static int bfs(){for(int i = 0; i < L; i ++){for(int j = 0; j < R; j ++){Arrays.fill(dist[i][j], -1);}}Queue<PII> q = new LinkedList<>();q.offer(start);dist[start.x][start.y][start.z] = 0;while(!q.isEmpty()){PII t = q.poll();for(int i = 0; i < 6; i ++){int a = t.x + dx[i];int b = t.y + dy[i];int c = t.z + dz[i];if(a < 0 || b < 0 || c < 0 || a >= L || b >= R || c >= C) continue;if(dist[a][b][c] != -1) continue;if(g[a][b][c] == '#') continue;dist[a][b][c] = dist[t.x][t.y][t.z] + 1;if(a == end.x && b == end.y && c == end.z) return dist[a][b][c];q.offer(new PII(a, b, c));}}return -1;}public static void main(String[] args){Scanner sc = new Scanner(System.in);while(true){L = sc.nextInt();R = sc.nextInt();C = sc.nextInt();if(L == 0 && R == 0 && C == 0) break;for(int i = 0; i < L; i ++){for(int j = 0; j < R; j ++){String s = sc.next();for(int k = 0; k < C; k ++){g[i][j][k] = s.charAt(k);if(g[i][j][k] == 'S') start = new PII(i, j, k);if(g[i][j][k] == 'E') end = new PII(i, j, k);}}}int res = bfs();if(res == -1) System.out.println("Trapped!");else System.out.printf("Escaped in %d minute(s).\n", res);}}
}

1233. 全球变暖 - AcWing题库

import java.util.*;class PII{int x, y;public PII(int x, int y){this.x = x;this.y = y;}
}public class Main{static int N = 1010;static int n;static char[][] g = new char[N][N];static boolean[][] st = new boolean[N][N];static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};public static boolean bfs(int x, int y){Queue<PII> q = new LinkedList<>();q.offer(new PII(x, y));st[x][y] = true;int max = 0;while(!q.isEmpty()){PII t = q.poll();int cnt = 0;//记录周围#的个数for(int i = 0; i < 4; i ++){int a = t.x + dx[i];int b = t.y + dy[i];if(a < 0 || b < 0 || a >= n || b >= n) continue;if(g[a][b] == '.') continue;cnt ++;if(!st[a][b]){st[a][b] = true;q.offer(new PII(a, b));}}max = Math.max(max, cnt);}if(max == 4) return true;else return false;}public static void main(String[] args){Scanner sc = new Scanner(System.in);n = sc.nextInt();for(int i = 0; i < n; i ++){String s = sc.next();for(int j = 0; j < n; j ++){g[i][j] = s.charAt(j);}}int res = 0;for(int i = 0; i < n; i ++){for(int j = 0; j < n; j ++){if(!st[i][j] && g[i][j] == '#'){if(!bfs(i, j)) res ++;}}}System.out.print(res);}
}

 1207. 大臣的旅费 - AcWing题库

import java.util.*;public class Main{static int N = 100010, M = 2 * N;static int[] h = new int[N], e = new int[M], ne = new int[M], w = new int[M];static int[] dist = new int[N];static boolean[] st = new boolean[N];static int n, idx;public static void add(int a, int b, int c){e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx ++;}public static void bfs(int u){Arrays.fill(st, false);Queue<Integer> q = new LinkedList<>();dist[u] = 0;q.offer(u);st[u] = true;while(!q.isEmpty()){int t = q.poll();for(int i = h[t]; i != -1; i = ne[i]){int j = e[i];if(st[j]) continue;dist[j] = dist[t] + w[i];st[j] = true;q.offer(j);}}}public static void main(String[] args){Scanner sc = new Scanner(System.in);n = sc.nextInt();Arrays.fill(h, -1);for(int i = 1; i < n; i ++){int a = sc.nextInt();int b = sc.nextInt();int c = sc.nextInt();add(a, b, c);add(b, a, c);}bfs(1);int u = 1;for(int i = 2; i <= n; i ++){if(dist[i] > dist[u]) u = i;}bfs(u);int maxv = dist[1];for(int i = 2; i <= n; i ++){if(dist[i] > maxv) maxv = dist[i];}System.out.println(maxv * 10 + ((long)(maxv + 1) * maxv) / 2);}
}