Ver
  • 2024-11-04【笔记/模板】割点和桥
    割点对于一张无向图\(G=(V,E)\),使得H是G的连通子图,且不存在\(F\)满足\(H\subsetneqF\inG\)且\(F\)为连通图,则称\(H\)是\(G\)的一个连通块/连通分量(connectedcomponent),又叫极大连通子图。由此,我们可以对割点做出如下定义:对于一个无向图,如果把一个点删除后
  • 2024-11-04【笔记/模板】无向图的双连通分量
    边双连通分量定义在一张联通的无向图中,对于任意两点\(u\)和\(v\)​,删去两点之间任意一条边,都无法使其不连通(即连通数不变),我们就说这两点是边双连通。对于一个无向图中的极大边双连通的子图,我们称这个子图为一个边双连通分量。根据【笔记/模板】割点和桥中可知,如果
  • 2024-11-04【笔记/模板】树链剖分
    树链剖分树链剖分的基本思想通过将树分割成链的形式,从而把树形变为线性结构,减少处理难度。树链剖分(树剖/链剖)有多种形式,如重链剖分,长链剖分和用于Link/cutTree的剖分(有时被称作「实链剖分」),大多数情况下(没有特别说明时),「树链剖分」都指「重链剖分」。树链有如下几个特
  • 2024-11-03【模板】图的存储与遍历
    图的存储与遍历直接存边法做法建立三个数组u[N],v[N],w[N],对于每一次读入的起点,出点和权值存储即可。初始化structEdge{intu,v,w;};vector<Edge>graph;存储voidadd(inta,intb,intc){ graph.push_back({a,b,c});}遍历voiddfs(intver){ if(vis[v
  • 2024-11-03【笔记/模板】Bellman-Ford
    Bellman-Ford求最短路和负环时间复杂度:\(O(nm)\)【模板/笔记】Johnson算法boolBellman_Ford(){memset(dist,0x3f,sizeofdist);for(intk=1;k<n;k++)for(intver=1;ver<=n;ver++)for(inti=h[ver];~i;i=ne[i])
  • 2024-11-01C. DS循环链表—约瑟夫环 (Ver. I - B)
    题目描述N个人坐成一个圆环(编号为1-N),从第S个人开始报数,数到K的人出列,后面的人重新从1开始报数。问最后剩下的人的编号。例如:N=3,K=2,S=1。2号先出列,然后是1号,最后剩下的是3号。测试数据有多组,每组包括3个数N、K、S,表示有N个人,从编号为S的人开始,数到K出列。输入测
  • 2024-10-21abc375_G
    G-RoadBlocked2思路只有当一条边是从\(1\)到\(n\)的所有最短路构成的图的桥时,去掉这条边,最短路才会变大怎么判断一条边是否可以构成最短路呢,比如求\(1\)到\(n\)的最短路,分别求出dist1(源点为1)和distn(源点为n),当一条边(端点分别为a,b,边长为w)包含再最短路之中时,它满足如下
  • 2024-10-14题解:P10370 「LAOI-4」Mex Tower (Hard ver.)
    ProblemLink「LAOI-4」MexTower(Hardver.)题意给定一个长度为$n$的序列$a$,求序列的$\operatorname{Mex}$值是否大于等于其他所有长度为$n$的自然数序列的$\operatorname{Mex}$值。Solution不难发现,两个数或一个序列的$\operatorname{Mex}$一定是
  • 2024-10-10Day3 备战CCF-CSP练习
    Day3题目描述目前在一个很大的平面房间里有\(n\)个无线路由器,每个无线路由器都固定在某个点上。任何两个无线路由器只要距离不超过\(r\)就能互相建立网络连接。除此以外,另有\(m\)个可以摆放无线路由器的位置。你可以在这些位置中选择至多\(k\)个增设新的路由器。你的
  • 2024-10-06P11059 [入门赛 #27] 数字 (Hard Ver.)题解
    Solution先读题:在给定x的位数\(n\)和模数\(p\)后,要求构造一个\(x\)在满足\(x\modp\)的余数尽可能小的前提下使\(x\)的数字尽可能小。我们假设\(x\)的各位数字之和为\(m\),有\(1\lem\le9n\)。.(当\(x\)仅在最高位有1时\(m=1\),称为情况一,当x每位为9时\(m=9n\),称为情况二
  • 2024-10-01题解 P2726 【[SHOI2005]树的双中心】
    首先,我们会有一个很简单的想法,枚举断边,产生两棵子树,然后在两棵树内分别求带权重心,计算贡献,这样的话复杂度是\(O(n^2)\)的。那么我们要好好利用$h\leq100$的性质。考虑\(sze[u]\)为带权重量,\(g[u]\)为以\(u\)为根的树,所有点都到\(u\)的代价。所以\(g[u]=\sum\l
  • 2024-10-01P3369 【模板】普通平衡树
    直接抄WIDA的pbds板子#include<bits/stdc++.h>#include<ext/pb_ds/assoc_container.hpp>usingnamespace__gnu_pbds;usingnamespacestd;typedefpair<int,int>V;tree<V,null_type,less<V>,rb_tree_tag,tree_order_statistics_node_updat
  • 2024-09-282024 Autumn Training #2 CG (by hzy)
    C.Black-WhiteCubicLattice(网络流)大意:三维空间\(n*m*l\)格点黑白染色,已有初始色,每个点有翻转的代价\(w\),要求以最小的代价构造\((1,1,1)\)为黑,\((n,m,l)\)为白,且不存在内白外黑的点对。禁止内白外黑,考虑最小割,每个点向内连边\(inf\),白点流出\(w\),黑点流入\(w\),则最
  • 2024-09-25P3311 [SDOI2014] 数数
    参考题解做法。题目思路数位dp+AC自动机好题。直接往下递归,dfs(u,ver,limit,st)表示目前在数字\(n\)的第\(u\)位进行讨论,\(ver\)表示当前在AC自动机上的节点,\(limit\)是是否步步紧逼\(n\),只要位数不足\(n\)的位数或者有一位小于\(n\)的那一位就不叫步步
  • 2024-09-13A*算法.
    A算法*保证一定有解,不然算法不如dfs;无解会很慢,只能先写写去试试179.八数码在一个3×3的网格中,1∼8这8个数字和一个x恰好不重不漏地分布在这3×3的网格中。例如:123x46758在游戏过程中,可以把x与其上、下、左、右四个方向之一的数字交换(如果存在)。我们
  • 2024-09-059月做题纪要
    9.3/9.4P3376【模板】网络最大流因为Dinic对于求最大流是比较优的算法,考虑对Dinic进行一个复习Dinic属于Ford-Fulkerson增广路算法,每次增广前我们都先用BFS将图分层,每个点的层数都是其距离源点的最短距离求解思路如下:对原图进行BFS构建分层图考虑EK算法的
  • 2024-09-04洛谷 P5340 大中锋的游乐场
    洛谷P5340大中锋的游乐场题意给出一张\(n\)个点\(m\)条边的图,每个点有一个点权\(1\)或\(-1\)。给出点\(s,t\),求出\((s,t)\)间满足以下条件的最短路。任意时刻,走过的路径上点权和均\(\in[-k,k]\)。思路分层图最短路。\(dis_{i,j}\)表示走到\(i\),点权和为\(j
  • 2024-08-24解决Qt creator5..中文乱码问题
    1.工具->选项2.两种方案供选择    a.头文件(或目标文件)添加预编译指令:                #ifdefined(_MSC_VER)&&(_MSC_VER>=1600)#pragmaexecution_character_set("utf-8")#endif    b.编辑->SelectEncoding...->savewithE
  • 2024-08-09CF379F New Year Tree
    题意给定图:每次在叶子结点加入两个点,并实时输出树的直径长度。思路每次增加两个点,直径至多变化一个点,长度最多加1,所以对加入的点处理lca,并且更新长度和点即可。代码#include<bits/stdc++.h>usingnamespacestd;constintN=1000010;intfa[30][N],dep[N];vo
  • 2024-08-02最短路计数
    //最短路计数.cpp:此文件包含"main"函数。程序执行将在此处开始并结束。///**https://loj.ac/p/10077【题目描述】给出一个N个顶点M条边的无向无权图,顶点编号为1∼N。问从顶点1开始,到其他每个点的最短路有几条。输入格式第一行包含2个正整数N,M,为图的顶
  • 2024-07-28C++自学笔记30(类型双关)
    上栗子#include<iostream>intmian(){inta=50;doublever=a;std::cout<<ver<<std::endl;std::cin.get();}a是一个占据4字节的数据,将a复制给ver并转换为double8个字节。这其中就是隐式的类型转换。第一个是int类型的50,第二个是类型转换后的
  • 2024-07-28CF843E Maximum Flow
    考虑到最小割一定是满流,此时最小割边数就是答案。对于\(g_i=0\),连接\((u_i,v_i,inf)\),没有流量则一定可以走到,还需要防止隔断;对于\(g_i=1\),连接\((u_i,v_i,1),(v_i,u_i,inf)\),该边有流量则反向边一定有残余容量,且如果没满流,那么\(u_i\)可以到达\(v_i\),否则就选择它假如最
  • 2024-07-28CF1416F Showing Off
    网格图先黑白染色,由于格子无法向边界外连边,且为正数,所以最后一定是一个基环树森林,并且一定是偶环,那么就可以把一个环拆分成多个二元环,更加方便;每个格子前往的点一定比它自己小,所以一个格子周围的数都比它大,那么无解,如果等于,那么就在同一个环上,否则一定会先经过一些树边,然后到达一
  • 2024-07-10VisualStudio各版本_MSC_VER和_MSC_FULL_VER宏定义值列表
        这些值可以用于在C++中判断版本和C++特性支持情况。   大版本产品名VC++版本号_MSC_VER定义_MSC_FULL_VER定义2022VisualStudio2022version17.9.214.3919391939335212022VisualStudio2022version17.8.314.381938193833133202
  • 2024-07-01Windows11家庭版如何使用远程桌面
     下载、安装从本文最上面的依赖下载RDPwrapv1.6.2文件(压缩包),并解压,文件构成大致如下:–install.bat安装RDPWrap–RDPCheck.exe在本地测试远程连接情况–RDPConf.exe设置远程桌面(也用于检查运行情况)–uninstall.bat卸载RDPWrap–update.bat在Github上检查更新