首页 > 其他分享 >一点模板

一点模板

时间:2023-10-18 11:23:06浏览次数:42  
标签:遍历 prim 短路 素数 筛除 一点 模板 dis

线性素数筛:

欧拉筛:

  定义数组prim[i]表示第i大的素数,isprim[i]表示i是否为素数(是否被筛过)

  从2~n遍历,if(!isprim[i]) prim[++cnt]=i,如果遍历到i时i仍未被筛,则将i记录于prim数组中。接下来开始以i为基数筛除素数,我们发现:所有的合数都能被筛分割为若干数的积。所以无论i是否为素数,我们就从1~cnt依此将所有筛出的素数分别与i的乘积筛除,当i是prim[j]的倍数时,i的倍数必然也是prim[j]的倍数,显然在遍历prim[j]时已经将所有prim[j]的倍数都筛除,故没有必要再用i再筛一遍,break掉。

for(int i=2;i<=n;i++){
    if(!isprim[i]) prim[++cnt]=i;
    for(int j=1;prim[j]<=n/i&&j<=cnt;j++){
        isprim[i*prim[j]]=1;
        if(i%prim[j]==0) break;
    }
}

埃氏筛:

  定义数组prim[i]表示第i大的素数,isprim[i]表示i是否为素数(是否被筛过)

  从2~n依此遍历,若当前遍历的i未被筛除,将i加入prim数组,并将i的所有倍数筛除

  

for(int i=2;i<=n;i++){
    if(!isprim[i]){
        prim[++cnt]=i;
        for(int j=2;j*i<=n;j++){
            isprim[i*j]=1;
        }
    }
}

  埃氏筛相较于欧拉筛较慢,原因是埃氏筛可能会重复筛除同一合数,故欧拉筛的核心剪枝代码即 if(i%prim[j]==0) break;

 

最短路:

floyd:

  作为最短路算法中思路最为暴力,码量最少的算法,floyd也有与之相应的代价:n的三次方的时间复杂度令人难以接受。

  整体思路如下:1~n遍历中间点,再遍历起点,终点,最后更新起点到终点的最短路为起点至中间点的做短路加上中间点至终点的最短路之和。

  实现:定义数组dis[i][j]表示点i至点j的最短路径,初始化为 inf,dis[i][i]=0,在读入边权信息时记录dp[u][v]=w(u表示起点,v表示终点,w表示边权),最后套三层循环即可(注意:遍历顺序为kij)

//记得初始化
memset(dis,0x3f3f3f3f,sizeof(dis));
for(int i=1;i<=n;i++) dis[i][i]=0;
//读入边信息并记录()
for(int i=1;i<=m;i++){
    u=read(),v=read(),w=read();
    dis[u][v]=w;
    dis[v][u]=w;
}

for(int k=1;k<=n;k++){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
                        //取最小值
            dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
        }
    }
}    

 

spfa:

  spfa已死!!!(死不了一点)

  适用于有负权边的最短路,在最劣情况会被卡到O(nm),在没有负权边时建议使用dijkstra,正确性交给玄学组。

   思路:每次取出已经更新过最短路的点,并利用它去进行更新,属于一个贪心的思想

  实现:定义数组dis[i]表示从起始点s至点i的距离,初始时dis[s]=0,其余点dis[i]=inf。在spfa函数中利用STL自带的queue进行取出/放入,vis[i]记录i是否在queue中。

 

void spfa(){
  //初始化 for(int i=1;i<=n;i++) dis[i]=inf; queue<ll>dl; //将起始点s放入
   dl.push(s); dis[s]=0; while(!dl.empty()){ ll u=dl.front(); dl.pop(); vis[u]=0; for(ll i=head[u];i;i=e[i].nxt){ ll v=e[i].v; if(dis[v]>dis[u]+e[i].w){ //更新最短路
          dis[v]=dis[u]+e[i].w; //未在队中即放入
          if(!vis[v]){ dl.push(v); vis[v]=1; } } } } }

 

 

 

dijkstra:

  

标签:遍历,prim,短路,素数,筛除,一点,模板,dis
From: https://www.cnblogs.com/shashadejianzhang/p/17771635.html

相关文章

  • Thymeleaf 模板引擎
    Thymeleaf简介Thymeleaf(https://www.thymeleaf.org/Thymeleaf3.0.15)是一个XML/XHTML/HTML5模板引擎,可用于Web与非Web环境中的应用开发。它是一个开源的Java库,基于ApacheLicense2.0许可。Thymeleaf提供了一个用于整合SpringMVC的可选模块,在应用开发中,你可以使用Thymeleaf......
  • 考前模板整理
    有用的板子常用技巧inlinellread(){ llx=0,w=1; charch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ x=(x......
  • laravel 中layout模板
    Blade布局是指具有多个公共部分的布局,可以在整个应用程序中使用,无需为此加载多个文件。公共区域包括页眉、页脚、侧边栏等。它包括Blade语法。我们也使用相同的文件夹结构/resources/views来存储布局。让我们创建一个简单的基本Blade布局。在/resources/views/layouts/app.blade.p......
  • 人工智能结合模板实现表格信息提取
    人工智能结合模板实现表格信息提取一、项目介绍本项目基于是OCR(文本识别)、表格识别的人工智能技术应用,通过表格识别,实现快速制作模板;模板单元格信息,结合OCR识别结果,将表格内容提取为结构化信息输出。与KIE(KeyInformationExtraction,关键信息抽取)模型对比,本项目准确率更高,效率......
  • Windows Server 2016 OVF, updated Oct 2023 (sysin) - VMware 虚拟机模板
    WindowsServer2016OVF,updatedOct2023(sysin)-VMware虚拟机模板2023年10月版本更新,现在自动运行sysprep,支持ESXiHostClient部署请访问原文链接:https://sysin.org/blog/windows-server-2016-ovf/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.org现在......
  • Windows Server 2019 OVF, updated Oct 2023 (sysin) - VMware 虚拟机模板
    WindowsServer2019OVF,updatedOct2023(sysin)-VMware虚拟机模板2023年10月版本更新,现在自动运行sysprep,支持ESXiHostClient部署请访问原文链接:https://sysin.org/blog/windows-server-2019-ovf/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.orgWind......
  • Modbus主机模板
    #ifndefMODBUS_MASTER_H#defineMODBUS_MASTER_H#include"main.h"#ifdefMODBUS_MASTER_C#include"stm32f10x_usart.h"#include"crc.h"#definePrioritySize3#defineMissionSize10#defineBps115200#defineRecSize......
  • React-Admin后台管理模板|react18+arco+zustand后台解决方案
    基于react18.x+vite4+arco-design自研中后台管理系统解决方案ReactAdmin。react-vite-admin基于vite4搭建react18.x后台管理项目。使用了react18hooks+arco.design+zustand+bizcharts等技术实现权限管理模板框架。支持暗黑/亮色主题、i18n国际化、动态权限鉴定、3种布局模板、t......
  • 互联网大厂面试一点都不难,邻居小孩都能过,是真的吗?
    前言最近正值“金九银十”时期,但由于就业形势并不乐观,大家对于面试的吐槽也多了几分...面试前期什么都没准备,导致错失了许多面试的机会...面试时太紧张了,想说的话都没说出来,发挥不好,很苦恼...空窗期太久,投简历800余份,都没有回应...准备了很久的一场面试,但由于候选者太多,最后的回复......
  • 麒麟KYLINOS2303上通过模板设置电源
    hello,大家好啊,今天给大家带来一篇在麒麟kylinOS2303上通过模板设置电源的文章,主要通过开机启动脚本实现,开机脚本内容主要为gsettings的设置,关于gestating的相关信息,请大家自行查阅相关资料获取。1、查看系统信息pdsyw@pdsyw-pc:~/桌面$cat/etc/.kyinfo[dist]name=Kylinmiles......