- 博客(423)
- 收藏
- 关注
RSS订阅
原创 [Vjudge]Radar Installation
贪心好题题目大意海里有一些岛，你可以在岸边放雷达，用最少的雷达覆盖所有岛解题思路我们可以先将题目从二维降维至一维，显然能够覆盖岛的条件是雷达位于坐标区间[x0,x1]，其中x0x1分别是能够覆盖这个岛的两个极限点，在这两点之间的点都可以覆盖这个岛，所以我们可以将小岛投影到岸上，问题就变成了用最少的点，使得每个区间内都有至少一个点这就是一个比较经典的贪心思路了，我们将点设在一个区间的右端点一定优于设在左端点，因为左端点之前的点都被覆盖过，而不设在右端点那么会有一段区间是浪费掉的。我们先对所有区间.
2021-12-08 20:57:50
230
原创 [学习笔记]粒子群-TSP问题
题外话数模原因，导致最近一直需要用到随机化算法，之前也更新过模拟退火算法的学习笔记，一些常见的问题的解在模拟退火算法的优化之下大范围内较为准确，直到遇到了无人机集群问题，我不会了相关的论文中提到了需要用到粒子群（PSO）算法，所以记录一下学习笔记概念引入粒子群优化（Particle Swarm Optimization, PSO），又称微粒群算法，是由J. Kennedy 和R. C. Eberhart 等于1995年开发的一种演化计算技术，来源于对一个简化社会模型的模拟。其模型的建立基于自然界中
2021-11-27 13:58:05
1180
原创 [Vjudge]卡片游戏
题目描述如图贪心+STL应用基本思路最直观的想法，从第一位开始取，比较他和当前已经排好序的部分开头的数字比较，若比这个数字小，那么一定是放到左边作为新的开头，若是比这个数字大，那么一定放在右边进一步来讲，得到的最终序列的开头一定是整个原序列中，从右往左数除0以外的最小的数，而这个数后面的数因为都大于这个最小的数，所以一定是顺序插入的，不会再改变顺序，他之前的数还是按照开始直观的想法插入即可，到这个数就放到开头这里我用了STL中deque，双端队列，他是一个可以从头或者尾插入的队列，可以看做是一个.
2021-11-26 21:58:58
2796
原创 [Vjudge]Safe Or Unsafe
题目描述如图哈夫曼树模板题哈夫曼树几个定义两点路径： 树上两个点之间的最短路经过点的数量+1，若是节点到根节点，则可以看做节点的深度点权： 树上节点所具有的权重加权路径长： 节点到根节点的路径长乘节点的权重 wi=Li∗viw_i=L_i*v_iwi=Li∗vi哈夫曼树定义将n个带权重的节点构成一棵树，若这棵树所有叶节点到根节点的加权路径长最短，则这棵树为哈夫曼树如何构建显然，若加权路径长最短，那么权值最大的点就要深度最浅，相应的权值最小的点要深度最深那我我们不难想到，可以自叶.
2021-11-26 20:00:59
213
原创 [Vjudge]红色病毒
问题描述如图解题思路首先易得这应该是一道公式递推题通过观察样例，结合数据范围，我们不难想到，也许这道题的结果有循环分析题目，假设当前序列长n，那么前n-1个字符有什么情况1.A、C均出现了偶数次 f[n-1][0]2.只有A出现偶数次 f[n-1][1]3.只有C出现偶数次 f[n-1][2]4.A、C均出现奇数次 f[n-1][3]（记好这是前n-1个）针对每种情况我们当前位置可以进行的操作有1、前n个字符AC出现偶数次：f[n][0]=2*f[n.
2021-11-25 15:13:02
367
原创 [Vjudge]find your present (2)
题目简介给你n个数，有且仅有一个数出现了奇数次，你需要输出这个数思路这题的思路比较奇特，用到了一个位运算的特殊性质：异或运算的自反性即 x ^ y ^ y=x用到这道题里，我们只需要每次输进来一个数就异或他一下，这样出现偶数次的数就被异或掉了，剩下的就是出现奇数次的数代码//By AcerMo#include<set>#include<cmath>#include<cstdio>#include<cstring>#include<i
2021-11-20 16:13:22
660
原创 【学习笔记】排序算法
0 前言 排序使我们在算法竞赛以及数据结构中常用的一类基础算法，大体上分为插入排序、选择排序、交换排序、分配排序、归并排序几大种，每种下面又存在着细化的不同排序方式。不同方式可以应用于不同的数据规模以及不同的场景。 稳定：重复数字排序后相对于排序前的顺序不变，则算法是稳定的。1 插入排序1.1 基本思想我们从直观含以上理解，插入即将数据插入到某个位置，应用到排序中，我们将直接把数据插入到适当位置的排序方式称为插入排序。1.2直接插入排序1.2.1 基本原理这是最符合我们人直观排序方式的
2021-11-13 13:21:12
369
原创 [学习笔记]模拟退火
随便说说终究还是没能绕开这个随机化坎最近搞ACM的同时也被同学拉着去搞建模了，发现建模的时候一些初始最优解或者说近似最优解的求解可以利用模拟退火、蚁群以及遗传算法来解决，本文只介绍模拟退火算法，其他的随机化算法后续学完同样会更新。算法由来模拟退火原理来源于物理上的退火，在物理上，我们将固体加温至充分高，再让其缓慢冷却，温度升高，固体内部粒子随温升变为无序状，内能增大，冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。并且在物理退火中，发生一次能量差为dE的温度突变的概
2021-11-13 09:29:29
786
原创 [Vjudge]一个人的旅行
题目描述如图单源最短路裸题，只需要在所有节点之外建一个起点，让它指向草儿家附近的城市且路长为0，然后以这个点为起点跑一边最短路就可以了代码//By AcerMo#include<queue>#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define lli long long intusi.
2021-11-11 09:17:48
142
原创 [Vjudge]过山车
题目描述如图一道基本上是二分图匹配的裸题回忆二分图匹配的特点：两个内部相互独立的集合之间存在一些边，从连边的元素中取两两配对，看最多能取多少对放到这道题里，男生女生为内部独立的集合，且两个集合之间存在一些边，则我们用二分图匹配，找出最多的男女组合即可这里利用了匈牙利算法注意每次循环要清空各个数组代码//By AcerMo#include<cmath>#include<cstdio>#include<cstring>#include<iostr.
2021-11-10 23:48:00
377
原创 [Vjudge]龟兔赛跑
题目描述如图经典动态规划题依据题意，我们将起点，终点也看做两个加油站，只不过不需要加油，将输入的站点数据从小到大排列状态定义： f[i]表示从起点到第i个加油站所需的最短时间我们考虑如何转移，不考虑其他情况，从一个站点到另一个站点若时间最短，那么必然是充满电再走的，所以我们令f[i]=min(f[j]+w+t)，也就是从它之前的任意一个站点充满电出发，中间不再充电，能得到的最小时间，也许你疑惑为什么中间不需要充电，因为我们定义是在目标站点之前的站点中取最小，而这些站点已经得到了最优值，在前面的站点.
2021-11-10 21:11:05
589
原创 [Vjudge]复习时间
题目如图经典的动态规划问题状态定义： f[i][k]表示第i次复习第k门课能获得的最大价值不难发现，题目要求每次复习的课的难度要低于上次，所以我们现将难度从大到小排序，保证状态转移时能够符合题意初始状态： 我们将f[1][k]初始化，表示从第k门课开始复习的最大价值状态转移： f[i][k]=max(f[i][k],f[i-1][j]+w)，j<k，w=上次复习第j门课，本次复习第k门课的利益结果： 最终结果即为max(f[m][k])，第m次复习第k门课的价值取最大即为答案代码//.
2021-11-10 20:23:47
102
原创 [Vjudge]叠筐
题目描述如图题目比较好理解，只是需要一些细节处理这题的基本思路为，逐层给字符串数组赋值，定义一个0/1变量，取值不同时赋值不同，从最外层开始向内循环即可处理的特殊情况为：1.n=1，直接输出，而不是输出为空2.行末没有多余空行代码//By AcerMo#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>u.
2021-11-10 20:15:20
144
原创 [学习笔记]链表
最近接触最多的数据结构就是链表，链表实现的栈、队列等等，虽然鸡肋，但是还算好用，留个低存一下半裸代码1.1 链表是什么链表是一个链状的数据表，与传统数组不同，链表的每一个元素是一个独立的数据单元，整体是一个在内存中离散的数据结构，相邻两个数据单元通过指针连接，这样所有的数据就组成了一条链。链表分为单向链表和双向链表，区别在于一个只能单向遍历，一个可以正反双向遍历。1.2 链表的优缺点链表由于每个数据单元都是独立的，所以便于我们插入和删除；但是链表的...
2021-10-23 10:48:17
135
原创 Python入门--列表
Python的列表是真的强list=[] :相当于一个可以存储任意类型变量的数组[“1”,2,False]python内置了好多函数list.append(a):向list末尾添加一个元素alist.insert(i,a):把a添加到下表为i的位置，后面元素顺移del list[i]:删除下标为i的元素list.pop(i)删除下标为i的元素并返回该元素，默认为最后一个list.remove(a)删除list中出现的第一个元素alist1[1]+list2[2]=[1,2]a in li
2020-10-26 21:12:00
368
1
原创 大学python入门2
python入门第二节课零智商学编程/再次狗头主要内容条件分支语句 if/else/elifwhile 循环没啥好学的elif缩写了else if 挺好用的QWQand or 没了符号表达挺难受的break continue基本用法相较于c++无变化没了+=，差评冒号不能忘了打就像你被分号支配的恐惧#By AcerMo#0 IQ to codeif (true): #代码块elif (true): #代码块else : #代码块while (true): #代码块
2020-10-26 09:56:25
107
原创 大学python入门作业一
智障儿童欢乐多零智商学编程 / 手动狗头留了两道题习题1 摄氏度华氏度转换输入摄氏度C，输出其对应的华氏度FF=5/9*C+32没有任何含量#By AcerMo#0 IQ to codeC = eval(input())F = 9/5 * C +32print(F)习题二 验证等式logαMn\log_\alpha M^nlogαMn=nlogαM\log_\alpha MlogαM输入 a m n，输出上面两个式子各自的值学习内容为整行数据读入log函数 log
2020-10-21 20:08:03
397
原创 2018纪中集训游记
DAY 0从家出发的时候，阴天了，开始祈祷不要下雨(之后貌似起飞的时候下了大雨，不过当时在云层里只感觉到了一丢丢颠簸？)飞机给咕咕了半个小时，期间一直在被老头子呵斥不要奶飞机，我一直在叨叨：飞机不要坠机！！不要遭到雷击！！不要撞鸟！！(我不是毒奶，真的)到中山后，没有吃午饭，因为飞机上的盒饭40/份(万恶的资本主义)(juner大爷后来得知这么便宜竟说当时应该买一份，够资本！)...
2020-10-21 09:53:48
249
原创 大学python入门
python第一节课零智商学编程 /手动狗头失踪人口回归print 输出 任意类型input 输入 一个字符串eval 将input进的字符串转成字符串内容相应的类型import 引入第三方函数库运算符 + - * / //(整除) % (整除非常有意思多重赋值 a=1 b=2 --> a,b=1,2#By AcerMo#0 IQ to code'''print('Hello World!')print(1 + 1)print(2.2 **
2020-10-21 09:52:31
253
原创 NOIP2018游记&&AFO后记
DAY0早上难得和同学们跑了个早操，一个多月没动的老骨头快散架了给高一学长讲图论，与老头争执一番，原因是我给学长讲图的遍历时，讲了一下vector可以排序，举了个栗子，我问学长说：我要求你优先遍历编号小的点，咋办？老头儿非得说要求遍历最近的点，碰巧被路过的教导主任看见，diss了一波不务正业，(可恶的人类)mmp高铁上补了一下点双边双补了一下海贼&amp;&amp;尸兄秦皇岛比SJZ还要...
2018-11-11 22:40:18
505
1
原创 BZOJ1131&&洛谷 P3478 [POI2008]STA-Station
树形DP思路我们考虑暴力，从每个点dfsdfsdfs，然后累加每个点的depdepdep，然后取maxmaxmax就好如何优化我们不难发现无论哪个点做根，对于他的一个子节点vvv，若将vvv转化为树的根，造成的影响是什么？发现对于v的子树，所有点的dep−1dep-1dep−1，对于vvv子树外的点，dep+1dep+1dep+1，所以我们令f[rt]f[rt]f[rt]表示vvv的父节点...
2018-11-02 17:50:43
278
原创 洛谷P3500 [POI2010]TES-Intelligence Test
二分思路记录每个数出现的位置，然后二分。代码//By AcerMo#include<cmath>#include<cstdio>#include<vector>#include<cstring>#include<iostream>#include<algorithm>using namespace std...
2018-11-02 16:06:52
267
原创 Codeforces896C Willem, Chtholly and Seniorious
这题我不会，，存个代码，，，珂朵莉树真神奇//By AcerMo#include<set>#include<cmath>#include<cstdio>#include<vector>#include<cstring>#include<iostream>#include<algorithm>#
2018-10-29 20:15:19
343
原创 ST表[学习笔记]
模拟赛求最值，要用二维ST表，可是我连一维都不会所以我写了个树状数组，然后跪了30分QAQ赶紧滚过来学一学，网上讲的好复杂QWQ概念ST表是用来求解区间最大值的一种优秀的离线算法，它可以 O(nlogn)O(nlogn)O(nlogn)预处理，，然后O(1)查询，如何实现呢？思想运用了近似于区间DP的方法，一个大区间有小区间转移得到，不同的是，我们定义ST[i][k]ST[i][k]S...
2018-10-26 20:23:26
383
原创 BZOJ1539&&洛谷P3462 [POI2007]ODW-Weights
神奇的思路题其它博客讲的太emmm了！！我尽量讲清QWQ思路我们把在同一行的两个数所在列建一条长度为1的边，不在同一列的建一条长度为0的边，然后对这张新建出来的图染色，我们要保证权值为0的两边的点颜色必然相同，为1则不同，为什么这么做？对于一条边权为1的边，它两端的元素是相同且在一行的，我们必须要交换这两列其中的一列，也就是1 12 3第一列和第二列一定有一列要交换，但是我们不能确定...
2018-10-25 15:42:25
359
2
原创 BZOJ2815&&洛谷P2597 [ZJOI2012]灾难
拓扑+LCA思路清奇的一道好题这个题真的不毒瘤！！吐槽一下出题人如何同时吓死草原上的羊？？先考虑一下暴力反向建图跑个拓扑就完事了考虑一些特殊的情况假如输入的是一棵树，那么一个点的贡献就是他的子树大小-1，也就是子树中除他以外的所有点，但是大多数情况输入是一个DAG，那我们是不是可以找到一种方法，把它转化成一棵树呢？我们考虑样例的情况不难发现，若是4号点凉了，当且仅当2,3都凉了...
2018-10-25 11:02:51
276
原创 BZOJ1084&&洛谷P2331 [SCOI2005]最大子矩阵
DP+思维思路这道题的切入点是mmm，发现mmm只有两种取值，那么我们就可以尝试对mmm分类讨论m=1发现在m=1m=1m=1时就是在一个一维序列上做k个最大子段和，我们定义f[i][j]f[i][j]f[i][j]表示处理到第iii位，共jjj个矩阵的最大和，咋转移？1.1.1. 假设这一位不选，那就是f[i][j]=f[i−1][j]f[i][j]=f[i-1][j]f[i][j]=...
2018-10-24 21:46:57
395
2
原创 BZOJ1202&&洛谷P2294 [HNOI2005]狡猾的商人
差分约束 or 带权并查集思路假如我们给定了a−&gt;b，a−&gt;ca-&gt;b，a-&gt;ca−>b，a−>c现在又给你b−&gt;cb-&gt;cb−>c你是不是就可以直接判断这条句子是不是假的了？我们用带权并查集维护两个元素之间的距离，然后每次发现有俩元素在同一个集合 ，就判断一下是不是满足d[x]−d[y−1]...
2018-10-24 19:29:15
272
原创 BZOJ1415&&洛谷P4206 [NOI2005]聪聪与可可
期望+BFS+记搜这题很神奇思路可可会跑，所以我们肯定不能每次动态求聪聪要咋走，然后发现总点数很少？我们对每个点BFS一遍，求出dis[x][y]dis[x][y]dis[x][y]也就是图中每两个点之间的路径长，然后根据这个长度，我们可以求出来一个go[x][y]go[x][y]go[x][y]表示当聪聪在xxx，可可在yyy时，聪聪会怎么走，判断就是dis[x][y]=dis[to[i...
2018-10-24 11:12:57
267
原创 洛谷P4316 绿豆蛙的归宿
拓扑+期望思路因为每条边等概率，那么就很轻松了，我们先跑个拓扑，确定拓扑序之后，从最后一个点向前更新，初始是f[n]=0f[n]=0f[n]=0，能到n的点会获得(w[i]+f[n])deg[u\frac{(w[i]+f[n])}{deg[u}deg[u(w[i]+f[n])的期望长度，因为u的度数是deg[u]deg[u]deg[u]所以有1deg[u]\frac{1}{deg[u]}de...
2018-10-24 09:55:33
232
原创 BZOJ1264&&洛谷P4303 [AHOI2006]基因匹配
树状数组优化DP毒瘤题暴力60分！讲讲思路最暴力的思路就是n2n^2n2求LCS，能拿到60分得好成绩，如何AC？我也不会，这道题中每个元素都出现了5次，这是个很好的性质，也就是说两个序列的元素是一样的所以我们不妨存下第一个串中每个元素都在哪个地方出现过，那么我们在用第二个串匹配时，直接找到当前元素在a串中出现的位置，因为只有在这些位置才可能有贡献，然后我们用树状数组维护一下每个位置上的L...
2018-10-23 20:56:08
240
原创 BZOJ3594&&洛谷P3287 [SCOI2014]方伯伯的玉米田
二维树状数组优化DP手动再见大毒瘤这样的出题人就是丧病n2n^2n2只有10分！！！讲一下思路不难发现，每次拔高，必定是从序列中某个地方直接拔高到序列末尾，为啥？我们假设没有拔到末尾，那么有以下几种情况1.拔高区间有一些比左侧低的，现在不低于左侧了2.拔高区间有一些比左侧高的，现在还是高于左侧3.拔高区间有一些不高于右侧的，现在高于右侧了也就是说拔高某一段，会造成1.在它左...
2018-10-23 19:50:31
275
1
原创 Codeforces 611B New Year and Old Property
思维题题目大意给定你l和r，问你在这个区间内，有多少数满足化成二进制后，只有一个0思路我们发现最多也就60位，所以我们可以枚举0在哪一位，然后在补1，然后统计个数就好了，如何枚举0呢？我们先预处理二进制下的2i2^i2i，然后当我们要枚举0在第i-1位时，就可以让num=2i+2i−1−1num=2^i+2^{i-1}-1num=2i+2i−1−1，就会发生1000000+100000−...
2018-10-19 21:15:30
220
原创 BZOJ1260&&洛谷P4170[CQOI2007]涂色
区间DP思路我们定义f[i][k]f[i][k]f[i][k]表示从i涂到k，使得和原序列相同的最少步骤，显然f[i][i]=1f[i][i]=1f[i][i]=1，因为这是最暴力的涂法QWQ，然后如何转移？考虑两个端点i，k，若s[i]=s[k]s[i]=s[k]s[i]=s[k]，那么显然我们可以在涂这两个端点中间之前，先把i到k涂一遍，再涂中间，所以f[i][k]=min(f[i+1][...
2018-10-18 21:17:19
294
原创 BZOJ1106[POI2007]TET-Tetris Attack立方体大作战
树状数组思路不难发现对于1…2…2…1这种情况来说，先删除2比先删除1更优，也就是说有匹配就删掉肯定比先删掉一个后来的匹配要优，对于12…12先删除哪个对答案的贡献是相通的…1…2…1…2…这样先删除1是最优的，所以思路就明朗了，维护一个点到他上次出现的位置有多少还没被删除的点就好了，然后我们就可以用树状数组维护一下洛谷还要输出方案，真毒瘤代码//By AcerMo#include&...
2018-10-18 14:42:04
291
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人