双指针、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);
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/462593.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Android 面试题及答案整理，最新面试题

Android 面试题及答案整理，最新面试题

Android中Intent的作用及分类 Intent在Android中用作组件之间传递信息&#xff0c;它可以用于启动活动(activity)、服务(service)和发送广播(broadcast)。Intent主要分为显式Intent和隐式Intent两大类。 1、显式Intent&#xff1a; 直接指定了要启动的组件名称&#xff08;比如…
阅读更多...
Lua中文语言编程源码-第一节，更改llex.c词法分析器模块, 使Lua支持中文关键词。

Lua中文语言编程源码-第一节，更改llex.c词法分析器模块, 使Lua支持中文关键词。

源码已经更新在CSDN的码库里&#xff1a; git clone https://gitcode.com/funsion/CLua.git 在src文件夹下的llex.c&#xff0c;是Lua的词法分析器模块。 增加中文保留字标识符列表&#xff0c;保留英文保留字标识符列表。 搜索“ORDER RESERVED”&#xff0c;将原始代码 …
阅读更多...
嵌入式硬件设计（一）|利用 NodeMCU-ESP8266 开发板和继电器结合APP“点灯•blinker”制作Wi-Fi智能开关（附有关硬件详细资料）

嵌入式硬件设计（一）|利用 NodeMCU-ESP8266 开发板和继电器结合APP“点灯•blinker”制作Wi-Fi智能开关（附有关硬件详细资料）

概述 本文主要讲述利用 NodeMCU-ESP8266 开发板和继电器通过手机 APP “ 点灯 • Blinker ” 制作一款能够由手机控制的WiFi 智能开关&#xff0c;从而实现智能物联。NodeMCU 是基于 Lua 的开源固件&#xff0c;ESP8266-NodeMCU是一个开源硬件开发板&#xff0c;支持WiFi功能&a…
阅读更多...
IDEA创建Sping项目只能勾选17和21，没有Java8？

IDEA创建Sping项目只能勾选17和21，没有Java8？

解决办法: 替换创建项目的源 我们只知道IDEA页面创建Spring项目&#xff0c;其实是访问spring initializr去创建项目。故我们可以通过阿里云国服去间接创建Spring项目。将https://start.spring.io/或者http://start.springboot.io/替换为 https://start.aliyun.com/
阅读更多...
OpenCV系列文章目录（持续更新中......）

OpenCV系列文章目录（持续更新中......）

引言&#xff1a; OpenCV是一个开源的计算机视觉库&#xff0c;由英特尔公司开发并开源的一组跨平台的C函数和少量的C函数组成&#xff0c;用于实时图像处理、计算机视觉和机器学习等应用领域。OpenCV可以在包括Windows、Linux、macOS等各种操作系统平台上使用&#xff0c;具…
阅读更多...
Github Copilot 工具，无需账号，一键激活

Github Copilot 工具，无需账号，一键激活

① 无需账号&#xff0c;100%认证成功&#xff01;0风险&#xff0c;可联网可更新&#xff0c;&#xff0c;支持copilot版本升级&#xff0c;支持chat ② 支持windows、mac、linux系统等设备 ③一号通用&#xff0c;支持所有IDE(AppCode,CLion,DataGrip,GoLand,IntelliJ IDEA …
阅读更多...
面向对象（C# ）

面向对象（C# ）

面向对象&#xff08;C# &#xff09; 文章目录 面向对象&#xff08;C# &#xff09;ref 和 out传值调用和引用调用ref 和 out 的使用ref 和 out 的区别 结构体垃圾回收GC封装成员属性索引器静态成员静态类静态构造函数拓展方法运算符重载内部类和分布类 继承里氏替换继承中的…
阅读更多...
图像处理ASIC设计方法 笔记11 像素误差与字长优化

图像处理ASIC设计方法 笔记11 像素误差与字长优化

P108 P105 定点误差分析与字长优化 1 像素误差是什么原因导致的？ 在本书所说的算法中，像素误差是由几次定点运算累加导致的： 首先由行（列）号与定点正弦／正切值计算出该行（列）的小数平移量，然后将这些小数平移量截取一定字长用来计算插值核，再将这些插值核也截取一…
阅读更多...
python统计分析——单变量分布之量化变异度

python统计分析——单变量分布之量化变异度

参考资料&#xff1a;python统计分析【托马斯】 1、极差 极差仅仅是最高值和最低值之间的差异。使用函数为&#xff1a;numpy.ptp()。代码如下&#xff1a; import numpy as npxnp.arange(1,11) np.ptp(x) ptp代表“峰值到峰值”&#xff0c;唯一应该注意的异常值&#xff0c…
阅读更多...
LCD屏的应用

LCD屏的应用

一、LCD屏应用 Linux下一切皆文件&#xff0c;我们的LCD屏再系统中也是一个文件&#xff0c;设备文件&#xff1a;/dev/fb0。 如果要在LCD屏显示数据&#xff0c;那我们就可以把数据写入LCD屏的设备文件。 1.显示颜色块 LCD屏分辨&#xff1a;800*480 像素 32位:说明一个像…
阅读更多...
HarmonyOS NEXT应用开发—发布图片评论

HarmonyOS NEXT应用开发—发布图片评论

介绍 本示例将通过发布图片评论场景&#xff0c;介绍如何使用startAbilityForResult接口拉起相机拍照&#xff0c;并获取相机返回的数据。 效果图预览 使用说明 通过startAbilityForResult接口拉起相机&#xff0c;拍照后获取图片地址。 实现思路 创建CommentData类&#…
阅读更多...
CSS中如何设置单行或多行内容超出后，显示省略号

CSS中如何设置单行或多行内容超出后，显示省略号

1. 设置超出显示省略号 css设置超出显示省略号可分两种情况&#xff1a; 单行文本溢出显示省略号…多行文本溢出显示省略号… 但使用的核心代码是一样的&#xff1a;需要先使用 overflow:hidden;来把超出的部分隐藏&#xff0c;然后使用text-overflow:ellipsis;当文本超出时…
阅读更多...
在react中使用tailwindcss

在react中使用tailwindcss

安装tailwind css npm i -D tailwindcssnpm:tailwindcss/postcss7-compat postcss^7 autoprefixer^9安装 CRACO 由于 Create React App 不能让您覆盖原生的 PostCSS 配置&#xff0c;所以我们还需要安装 CRACO 才能配置 Tailwind。 npm install craco/craco配置CRACO 在项目根…
阅读更多...
贪心算法（算法竞赛、蓝桥杯）--糖果传递

贪心算法（算法竞赛、蓝桥杯）--糖果传递

1、B站视频链接&#xff1a;A31 贪心算法 P2512 [HAOI2008] 糖果传递_哔哩哔哩_bilibili 题目链接&#xff1a;[HAOI2008] 糖果传递 - 洛谷 #include <bits/stdc.h> using namespace std; const int N1000005; int n,a[N],c[N]; long long b,ans;int main(){scanf(&quo…
阅读更多...
游戏引擎中的动画基础

游戏引擎中的动画基础

一、动画技术简介 视觉残留理论 - 影像在我们的视网膜上残留1/24s。 游戏中动画面临的挑战&#xff1a; 交互&#xff1a;游戏中的玩家动画需要和场景中的物体进行交互。实时&#xff1a;最慢需要在1/30秒内算完所有的场景渲染和动画数据。&#xff08;可以用动画压缩解决&am…
阅读更多...
【C语言初阶（五）】数组

【C语言初阶（五）】数组

❣博主主页: 33的博客❣ ▶文章专栏分类: C语言从入门到精通◀ &#x1f69a;我的代码仓库: 33的代码仓库&#x1f69a; 目录 1. 前言2.一维数组的概念3.一维数组的创建和初始化3.1数组的创建3.2数组的初始化3.3数组的类型 4.一维数组的使用4.1数组下标4.2数组元素打印4.4数组元…
阅读更多...
算法——前缀和之除自身以外数组的乘积、和为K的子数组、和可被K整除的子数组、连续数组、矩阵区域和

算法——前缀和之除自身以外数组的乘积、和为K的子数组、和可被K整除的子数组、连续数组、矩阵区域和

这几道题对于我们前面讲过的一维、二维前缀和进行了运用,包含了面对特殊情况的反操作 目录 4.除自身以外数组的乘积 4.1解析 4.2题解 5.和为K的子数组 5.1解析 5.2题解 6.和可被K整除的子数组 6.1解析 6.2题解 7.连续数组 7.1题解 7.2题解 8.矩阵区域和 8.1解析 …
阅读更多...
Ubuntu 20.04 系统如何优雅地安装NCL？

Ubuntu 20.04 系统如何优雅地安装NCL？

一、什么是NCL&#xff1f; NCAR Command Language&#xff08;NCL&#xff09;是由美国大气研究中心&#xff08;NCAR&#xff09;推出的一款用于科学数据计算和可视化的免费软件。 它有着非常强大的文件输入和输出功能&#xff0c;可读写netCDF-3、netCDF-4 classic、HDF4、b…
阅读更多...
使用PWM实现呼吸灯功能

使用PWM实现呼吸灯功能

CC表示的意思位捕获比较&#xff0c;CCR表示的是捕获比较寄存器 占空比等效于PWM模拟出来的电压的多少&#xff0c;占空比越大等效出的模拟电压越趋近于高电平&#xff0c;占空比越小等效出来的模拟电压越趋近于低电平&#xff0c;分辨率表示的是占空比变化的精细程度&#xf…
阅读更多...
MATLAB：拟合与插值

MATLAB：拟合与插值

一、关于多项式的基本操作 若要求非线性方程的根&#xff0c;则采用fzero, fminbnd函数 二、多项式拟合 clc, clear x0:0.2:10; y0.25*x20*sin(x); plot(x,y,k.,MarkerSize,15) grid on; hold on [p1,s1,mu1]polyfit(x,y,3); %3阶多项式拟合 y1polyval(p1,x,s1,mu1); [p2,s…
阅读更多...
最新文章

Copyright @ 2022~2023