hai200103-CSDN博客

原创 AcWing 第九周周赛题解

AcWing 第九周周赛题解3780. 构造数组3781. 给定一个长度为 n 的整数数组 m1,m2,…,mn。现在，请你构造一个数组 a1,a2,…,an。对于构造的数组，有以下三点要求：∀i∈[1,n]，1≤ai≤mi 成立。∀i∈[1,n], 不存在数对 j,k 同时满足 j<i<k 且 aj>ai<ak。数组中所有元素之和尽可能大。请输出任意合理方案。输入格式第一行包含整数 n。第二行包含 n 个整数 m1,m2,…,mn。输出格式输出 n 个整

2021-08-09 16:31:02 140

原创 Acwing第七周周赛第三题

AcWing 第七周第三题题解3760. 最大剩余油量一个国家由 n 个城市组成，这 n 个城市由 n−1 条双向道路连接，呈一个树形结构。每个城市都设有加油站，在第 i 个城市可以购买 wi 升汽油。汽车在道路上行驶，毫无疑问也会消耗汽油，每条道路的具体耗油量也会给出。现在，需要制定一条汽车的行进路线，从任意城市 s 出发，经过一条简单路径，到达任意城市 e 结束。注意，行进路线也可以只包含一个城市（也就是哪都没去）。汽车初始时油箱是空的，但是可以在路线中经过的每个城市购买汽油，包括开始城

2021-08-09 10:09:48 130

原创牛客多校第3场 24点

2021年杭电多校1008————南昌理工学院acm集训队链接：https://ac.nowcoder.com/acm/contest/11254/F来源：牛客网24dian is a famous game. You are given a set of n cards, each card contains an integer between 1 to 13. You can put the cards in arbitrary order, add + or - or * or / betw

2021-07-25 12:59:53 174

原创树形dp入门题目最大独立子集最简版

树形dp入门题目最大独立子集最简版。——出自南昌理工学院集训队没有上司的舞会Ural 大学有 N 名职员，编号为 1∼N。他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。每个职员有一个快乐指数，用整数 Hi 给出，其中 1≤i≤N。现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。输入格式第一行一个整数 N。接下来 N 行，第 i 行表示 i 号职员的

2021-07-18 10:57:05 92

原创扫描线+线段树简介 AcWing 248窗内的星星题解

————出自南昌理工学院ACM集训队这周学习了线段树和扫描线的解题方法，下面由小菜鸡简介一下：一般扫描线的题目最简单的便是扫描线裸模板（一般来说的话：数据范围小），其次的话便是进行拓展成线段树+扫描线（数据范围增大），再难一点的话就是扫描线+线段树+加上离散化操作了。扫描线什么是扫描线呢：给你一堆的矩形求这些矩形再重叠的情况下的面积？便需要用到扫描线按照x排序从小到大 xi(1~8)，这样处理之后我们可以看到每两的相邻的 xi的值把矩形分成了若干个矩形，这是我们记录一下上...

2021-07-11 10:59:18 208

原创 1234. 倍数问题题解（余数dp线性）——南昌理工学院

倍数问题题解（余数dp线性）众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。现在小葱给了你 n 个数，希望你从这 n 个数中找到三个数，使得这三个数的和是 K 的倍数，且这个和最大。数据保证一定有解。输入格式第一行包括 2 个正整数 n, K。第二行 n 个正整数，代表给定的 n 个数。输出格式输出一行一个整数代表所求的和。数据范围1≤n≤105,1≤K≤103,给定的 n 个数均不超过 108输.

2021-01-30 16:18:47 450

原创区间问题+简单版线段树+ST表

对于某些区间问题：一. 每组操作次数很大10^5且查询范围广的情况下可以考虑该区间的最大值和最小值，要求达到每个操作只进行一步就可以出结果。二. 有些可以利用前缀和与结构体进行维护，在结构体内维护一个最大最小值...

2021-01-24 11:31:40 204 1

原创矩阵快速幂补充+6470hdu题解

矩阵快速幂补充——南昌理工学院ACM集训队我们知道f[n]=f[n-1]+f[n-2]是一个斐波那契数列递推公式。而对应的矩阵如下：从中我们可以看出一些规律：下面让我们一起来看看f[n]=f[n-1]+i^4的基础矩阵;从图中那个我们可以看出其 i^4 对应的矩阵一个是五阶矩阵。因为 i^4！=(i+1) ^4，所以这时我们一个先把其（i+1)^4=1* i^4+ 4* i^3+6* i^2+ 4*i+1;其基础矩阵为竖线的里面那些数是基础矩阵其中如果方程变换的成 f[n]=a f

2021-01-17 21:47:15 98

原创二进制枚举

二进制转十进制和二进制转十进制#include<iostream>using namespace std;int a[32];void turnToTwo(int number){ for(int i=1;i<=31;i++){ a[i-1]=number>>(i-1)&1; cout<<a[i-1]<<' '<<i<<endl; }}int turnToten(

2020-09-21 16:15:44 187

原创 SPFA算法

每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值d[v]变小。所以算法的执行会使d越来越小。SPFA核心思想：如果一个点上次没有被松弛过，那么下次就不会从这个点开始松弛。每次把被松弛过的点加入到队列中，就可以忽略掉没有被松弛过的点。而且SPFA相比Dijkstra算法还有个优势：可以处理负权图和判负环，判负环只需要再加一个if和统计入队次数的num数组即可（注释部分）void spfa(int s) { memset(dis, 0x3f3f, siz.

2020-08-23 09:54:18 122

原创高精度+素数判断小优化（6N+1）

——————出自南昌理工学院ACM高精其实理解了就很好解决，下面让我们一起来看看高精度算法的新萌小模板，如有不足还望指教。高精加法：这里有些学长喜欢用二维数组的去处理，新萌在这里用的是三个一位数组处理。#include<cstdio>#include<iostream>#include<cstdlib>#include<cstring>using namespace std;int main(){ int n,m,pd=0;

2020-08-15 14:40:00 638

原创 HDU 2102 A计划题解（BFS算法）+数据

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 40040 Accepted Submission(s): 9926Problem Description可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后，而今，不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主，因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急

2020-08-15 14:11:31 176

原创 BFS算法小结

BFS算法小结----出自南昌理工学院ACM集训队算法的基本思路广度优先搜索类似于树的层次遍历过程。它需要借助一个队列来实现。如图2-1-1所示，要想遍历从v0到v6的每一个顶点，我们可以设v0为第一层，v1、v2、v3为第二层，v4、v5为第三层，v6为第四层，再逐个遍历每一层的每个顶点。具体过程如下：1.准备工作：创建一个visited数组（标记数组），用来记录已被访问过的顶点；创建一个队列，用来存放每一层的顶点；初始化图G。2.从图中的v0开始访问，将的visited[v0]数组的值设置为t

2020-08-08 15:22:52 294 2

原创最小生成树Prim算法和样例POJ287（文夕）

#最小生成树算法: (Prim)和样例POJ287简单的说(Prim) 算法就是一一个模板，记住它的意思还是很容易实现的。简介一下Prim算法:int dp[maxn][maxn],dismin[maxn],vis[maxn];int n,ans;//这里的n，有必要放在这里，而不是int main（）中，要不然prim（）中无法操作，会报错void prim(){ ans=0; int i,j,k; memset(vis,0,sizeof(vis));/*这个步骤对应的是多组数据输入时

2020-08-02 10:51:48 218

原创第二周总结ACM

小周总结这周是对上周所学的两个算法加以巩固的一周，上周我学习了两个算法分别是（最小生成树和并查集），这两个算法的简单使用还是没有问题的，并查集提升中包含了一个种类并查集，对于它我并没有很好地掌握，下周之前争取拿下。这周在做题中时常碰到别的算法与该算法结合的综合性题目，比如洛谷中的一道蓝色题目货车运输是真不知道怎么写，生成树的架构打好了，但是别的算法架构却不够清晰。这提醒这我要加紧步伐，追赶心中的梦。“山重水复疑无路，柳暗花明又一村。”当遇到困难时，你若持之以恒努力面对，终点将属于你。下周先把种类并

2020-08-02 10:42:28 108

原创最小生成树Kruskal算法和POJ1287样例

最小生成树Kruskal算法和POJ1287样例先把所有的边和其边权存下来，在按照边权进行排序。其次便是利用并查集的基本算法进行操作。这里你可以注意一下，和并查集不同的是这里要判断你现在操作的边对应的两个点是否已经在fat[maxn]中了，如果是的话这条边舍弃，不保存其边权。建议先看看并查集算法在来理解这个算法，可以说这个算法只是在并查集上面进行小改动的。https://blog.csdn.net/hai200103/article/details/107590515模板为这几个函数加上int

2020-07-26 18:32:22 87

原创并查集算法和例样P1551亲戚（文夕）

并查集算法和例题P1551亲戚并查集主要采用类似递归的方法，开一个数组用来查看点是否相连。如果（X1，X2）相连则更新一下X2点的存储内容，改为存X1的下标。并查集的模板基本相似，且适用性也比较广。以下便是模板：用来找祖宗，采用路径压缩防止一字长蛇多次。eg：（1，2）（2，3）（3，4）（4，5）防止出现1->2->3->4->5而是1->5;2->5;3->5;4->5;int father(int x){ if(fat[x]!=

2020-07-26 11:02:46 284

hai200103的博客