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);
}
}
