- 2024-08-232024.8.23 模拟赛总结
A.distStatement:给定一棵\(n(n\le10^6)\)个节点带边权的树,定义\(\mathrm{Min}(x,y)\)是\((x,y)\)路径上的边权最小值。求\(\max_{r=1}^n{\sum_{v\nei}\mathrm{Min}(r,v)}\)。Solution:经典套路题。首先注意到一条路径上的只有最小值才会产生贡献,于是对于
- 2024-08-17树链剖分
具体见OI-wiki,下面是一些补充重链要求是极大的每个点都在某一个重链中,如果一个点是重子节点,那么其在与其父亲所连的边的重链中,否则在与其重子节点所连的边的重链中这一段的原因:我们走重链是不用关心的,因为同一重链的dfs序是连续的,我们可以用其他数据结构维护,我们只用关心这条
- 2024-08-15【NOIP2016普及组复赛模拟赛】侦察兵
题目描述mxy沉迷于一个辣鸡游戏不可自拔。游戏地图是一个n*n的矩形,在每个单位格子上有一个数字,代表当前位置的生命体个数,作为一个侦察兵,mxy的任务是计算出她所在位置的左上角和右下角的总人数(不包括她所在的行列)。注意作为一个侦察兵,mxy是不包括在地图上的生命体个数中的
- 2024-08-14并查集
并查集(递归写法)#include<bits/stdc++.h>usingnamespacestd;constintX=10010;intf[X];intn,m; //初始化voidinit(){ for(inti=0;i<X;i++){ f[i]=i; }}//查找上级是谁intfind(intx){ if(x!=f[x]){ returnf[x]=find(f[x]);//路径
- 2024-08-08【无人机】纯定向被动定位视角下的无人机群定位调度方法(Matlab代码实现)
- 2024-07-21线段树分治
线段树分治线段树分治可以解决这样的问题:对于一些操作,每个操作只在\(l\)~\(r\)的的时间内有效。对于一些操作,询问某个时间点所有操作的贡献。经典例题算法思路对于这道题,因为二分图的充要条件是不存在奇环,所以可以使用扩展域并查集解决。我们考虑离线优化:对于每
- 2024-07-08P3043 [USACO12JAN] Bovine Alliance G
P3043[USACO12JAN]BovineAllianceG并查集每个连通块方案数独立。考虑一个连通块的情况,显然如果\(m>n\)一定无解,那么就只有\(m=n\)和\(m=n-1\)两种情况,前者是基环树,后者是树。基环树的环上,第一条边选择的端点确定,其他也就确定,共有两种情况。环下的树选择固定。所有总
- 2024-06-22迷宫Ⅱ
题目描述一天Extense在森林里探险的时候不小心走入了一个迷宫,迷宫可以看成是由n×n 的格点组成,每个格点只有 22 种状态:. 和 #,前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时,他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上,Extense想要从
- 2024-06-16「杂题乱刷」AT_abc358_g
代码恢复训练2024.6.15(补)链接(luogu)链接(atcoder)abc最水的G了吧。你发现,你最后肯定全在在同一个点上不动,而且你一定可以在\(n\timesm\)回合内走到这个点,因此我们直接\(dp_{i,x,y}\)表示走\(i\)步到\((x,y)\)这个格子所能得到的最大值即可。时间复杂度\(O(
- 2024-05-20C语言-文件读写
C语言文件读写文件分类:二进制文件:把数据的补码直接写入文件,这种文件叫二进制文件。优点:读写和写入时不需要进行转换,所以读写速度快,数据安全性高。缺点:不能使用文本编译器打开,无法阅读。文本文件:把数据转换成字符串写入文件,也就是把字符的二进制写入文件,这种文件
- 2024-05-10[ARC069F] Flags
题意有\(n\)个旗子。你需要将她们插在数轴上。第\(i\)个旗子只能放在\(x_i\)或\(y_i\)处。你需要求所有旗子的最小距离\(d\)的最大值。Sol二分个答案先。考虑\(\text{check}\),注意到这是个\(\text{2-sat}\)的经典模型。具体地,设\(S=x\cupy\)若\(|S_i
- 2024-05-08并查集
并查集并查集模板包含路径压缩+小挂大constintMAXN=1e5+1;intfather[MAXN];//存父亲节点father[1]=2指的是1节点的父亲为2intsize[MAXN]; //存每个集合的大小intstack[MAXN];//intn;//建立并查集voidbuild(){ for(inti=0;i<=n;i++)
- 2024-05-05标准C语言5
进制转换: 现在的CPU只能识别高低两种电流,只能对二进制数据进行计算。 二进制数据虽然可以直接CPU计算识别,但不方便书写、记录,把二进制数据转换成八进制是为了方便记录在文档中。随着CPU的不断发展位数不断增加,由早期的8位逐渐发展成现在的64位,因此八进制就不能满
- 2024-05-03P2024 [NOI2001] 食物链
原题链接题解带权并查集的应用,普通的并查集只能表示结点间的一种关系(如同一集合中的都是朋友)。而带权并查集的结点权值表示该结点与根结点的关系。相对应,带权并查集的路径压缩也复杂了一点。code #include<bits/stdc++.h>usingnamespacestd;constintN=5e4+5;intn,k
- 2024-04-25树链剖分
link1link2前言:树链剖分实际上就是一种将树形结构剖分成一条条链状结构,并用线性数据结构来快速维护信息。重链剖分:一些定义:重儿子:一个节点的重儿子定义为它的子节点中子树节点最大的节点。轻儿子:一个节点除重儿子外的所有儿子重边:一个节点到它的重儿子的边即为重边
- 2024-04-20如何将图片上的像素坐标(u, v)投影到世界坐标系中
如何将图片上的像素坐标(u,v)投影到世界坐标系中,即得到\((x_w,y_w,z_w)\).数学表达如下\[\begin{align*}s\begin{bmatrix}u\\v\\1\end{bmatrix}&=\begin{bmatrix}f_x&0&c_x&0\\0&f_y&c_y&0\\0&0&1&0\end
- 2024-04-17达梦数据库-初步学习
达梦数据库-初步学习sql连接方式su-dmdbacd/data//data/dm/bin/disqlSYSDBA/
[email protected]:5236数据库信息查看查看当前数据库中存在的模式select*fromSYSOBJECTStwheret."TYPE$"='SCH';查看所有表空间SELECT*FROMV$TABLESPACE;表空间信息
- 2024-04-08并查集(水题)
A.是不是亲戚题目描述若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。规定:x 和 y 是亲戚,y 和 z 是亲戚,那么 x 和 z 也是亲戚。如果 x,y 是亲戚,那么 x 的亲戚都是 y 的亲戚,y 的亲戚
- 2024-04-08高级数据结构-并查集plus(更新中。。。
格子游戏题目链接:格子游戏思路:首先围成一个闭环的时候,两个点一定有边相连,那么可以把这两个点通过并查集连在一个连通块里面,如果两个点的父亲相同,那么就形成闭环。同时,为了方便可以将二维的图转化成一维的进行计算,k=x*n+y,x,y要从0开始统计。代码附上:#include<bits/stdc++.h
- 2024-03-16并查集
模板题:https://www.luogu.com.cn/problem/P1551题解:#include<bits/stdc++.h>usingnamespacestd;intn,m,p;intfa[5050];intfind(intx){returnfa[x]==x?x:fa[x]=find(fa[x]);}intquery(intx,inty){intfx=find(x),fy=fi
- 2024-03-06Abbott的复仇 Abbott's Revenge
原题链接bfs的深度用法。这题最坑的我觉得是输入输出格式的处理(一不小心就容易格式错误)调了好几个小时.....这里放一组udebug数据SAMPLE31N3311WLNR*12WLNRERWF*13NLER*21SLWRNF*22SLWFELF*23SFREL*0NOSOLUTION31N3211WLNR
- 2024-03-06洛谷题单指南-搜索-P1605 迷宫
原题链接:https://www.luogu.com.cn/problem/P1605题意解读:从起点走到终点的方案数,DFS可遍历所有情况。解题思路:在DFS过程中,有两种标记墙:不能访问已访问过的,不能重复访问定义数组inta[N][N]表示迷宫,1是墙或者已访问过的,0是可以通过的。100分代码:#include<bits/stdc++.h>
- 2024-02-14947. 移除最多的同行或同列石头
原题链接根据题意我们可以得到一个很有趣的结论:处于同一行或者同一列的石头是共处一个集合的,而一个集合最终可以消除到只剩一个石头。(可以实验一下)因此我们采取并查集实现。Code classSolution{public:intsum=0;intfather[1005];map<int,int>mapx;
- 2024-02-012024/1/29~2024/2/4
Wiki下象棋题目链接:https://ac.nowcoder.com/acm/contest/74679/Ebfs搜两下就行了#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;intfx[8]={-1,1,0,0,-1,1,-1,1};intfy[8]={0,0,-1,1,-1,-1,1,1};constintmod=1000000007
- 2024-01-27并查集
简介并查集是一种维护集合的数据结构。支持合并和查询元素所在集合。我们将所有元素用点表示,从属关系用边表示,那么每个集合构成了一棵有向树。每个点有且仅有一条出边,指向其父亲。其中根节点的出边指向自己。集合用根节点的编号代表。实现初始化一开始所有的元素指向自己。