Rem_Inory的博客

原创 萌彩T1

原创 【题解】洛谷P2354 [NOI2014] 随机数生成器(贪心 模拟)

题面很长 但这道题最大的难度在于贪心和卡常前面一大堆随机数怎么搞出来完全可以直接模拟，注意该long long该取模的地方要做到。然后我们就到了字典序最小的那一部分。这里我们可以设两个数组L[x]与R[x]，代表第x行最左边能取第几列、最右边能取第几列。初始化为1和m。然后我们从小到大枚举矩阵里的数，如果这个数所在的列满足它在所在的行内的L[x]到R[x]区间范围内，那么这个数就可以被选择，然...

原创 【题解】洛谷P2323 公路修建问题(生成树)

概括一下 就是最小生成树问题对于连接两个点的一条边都可以选择两个权值(一级 二级)，一级权值>=二级，要求必须选至少k条一级公路（因为一级权值始终比二级全职大，所以我们就选k条一级公路)，求这样构建出来的最小生成树最长的一条大小与选择第几条公路和级别。这里我们需要写三个排序函数，第一个按照一级公路权值由小到大排序，选出k条公路。第二个按照二级公路权值由小到大排序，选出n-1-k条公路，记...

原创 【题解】洛谷P3388 割点(模板)

https://www.luogu.org/blog/user15232/solution-p3388mark一下noip复习时使用

原创 【题解】洛谷P2731 骑马修栅栏(欧拉回路)

https://www.luogu.org/blog/zbzhz111/ou-la-hui-lu-yu-ou-la-lu-jing这里有详细的欧拉回路解释 mark一下 noip复习用。 

原创 【题解】洛谷P1435 回文子串(区间dp)

IOI 2000的题目 实际上是一道区间dp我们设dp[i][j]代表字符串中第i个字符到第j个字符得到回文串需要添加的字符数，初始化dp[i][i]为0。这里注意还应该初始化dp[i][i+1]，如果s[i]==s[i+1]那么dp[i][i+1]=0,否则=1。接着我们枚举不相邻的两个点，如果两个字符相同那么dp[i][j]就等价于dp[i+1][j-1]。否则就等于这一段去掉首字符在尾加...

原创 【题解】洛谷P1262 间谍网络(强联通分量 缩点)

强联通分量缩点的类似模板题(雾)观察题目我们可以用tarjan的缩点来解决，首先我们以每个受到贿赂且没被打上时间戳过的人为起点进行tarjan缩点操作，这里顺道记录下在这个缩点的强联通分量中的贿赂最小值(因为贿赂一个人就可以将这里一锅端)。操作过后遍历n个人，如果没有被打上时间戳那这个间谍就一定不会被抓到，所以输出NO并输出这个最小的序号。否则我们缩点后得到的就是一张有向无环图，需要贿赂的最小...

原创 【题解】洛谷P1886 滑动窗口(单调队列)

（之前从未听说过这道题目 来到qbxt后大佬们都早就切掉此题了 倍感惭愧qwq）题目大意就是给定一个序列A与要求的长度k，让我们输出A中所有长度为k的区间的最大值和最小值。看到数据范围后我们发现暴力会炸掉，所以要考虑比较简洁的方法。这里我们维护一个元素单调递减的队列求区间内的最大值，最后单调队列队首的元素一定是最大值。进一步地，插入了第i个元素后的单调队列队首元素一定是前i个元素的最大值，...

原创 【题解】洛谷P3946 小鸟的点心(spfa)

稍微思考可以发现这道题目是最短路问题，但我们有一些特殊的情况需要考虑。当积雪增长速度q=0时，我们设每个点雪涨到无法通行的位置的时间（因为南小鸟的速度是1m/s 实际上路程在数值上就是时间了）是最大值INF（因为雪不能涨了嘛），否则用(l[i]-h[i])/q（注意这里的差和除数都是double类型，最后转化成int类型）计算出时间来。然后我们建图跑spfa，这里更新最短路的条件有两个:1.下...

原创 【题解】洛谷P3879 阅读理解(trie树)

新学了字典树算法，这个可以算是一个模板吧在有n个单词的字典中 对m个单词询问是否在此字典里。对于这个问题，我们可以通过构建字典树来解决。trie树的思路就是对于n个单词，我们开一个数组to[maxn][26]，代表编号为maxn、字母编号为x的编号（我在说啥。。。）；具体思路就是构建一棵长成这样的树并记录其编号然后对于读入的每个单词，我们对于其末尾编号开一个b数组记录下来代表一个单...

原创 【题解】洛谷P2678 跳石头(二分)

1-1e9二分答案，设其为最短距离。判断如果该距离可以就向上二分（单调递增，求最大值），注意判断mid+1可以避免边界问题。判断函数统计移走石头个数，如果相邻石头之间距离比要的最短距离还小就移走。移走石头个数小于M就返回true#include<cstdio>#include<iostream>#include<algorithm>using n...

原创 【题解】codevs P1403 新三国争霸(最小生成树 dp)

联动：https://blog.csdn.net/Rem_Inory/article/details/81139322这道题和一道叫物流运输的题非常相似，只不过变成了求最小生成树。根据这种思路我们求出w数组代表第i天到第j天没有灾害会消耗的军粮数，然后还要设一个判断数组记录在某一段时间内出现了灾害，记录下每一段时间内的最小值，然后进行dp操作就好了#include<cstdio&g...

原创 【题解】51NOD 1105 第k大的数（二分）

n^2的时间复杂度肯定会爆炸，所以我们要考虑更优的做法。这里可以写一个check函数，记录c数组里大于等于x的数的个数。而统计这个需要枚举i来得到a[i]，然后进行二分查找b数组，方法就是寻找最小的大于等于某个数的数。注意到达边界条件时要特判，来决定这一段区间的长度。处理完check函数后我们就可以枚举1-a[n]*b[n]（a、b数组已经从小到大排好序了），再次二分，如果某个数(mid+1)...

原创 【题解】洛谷P3958 奶酪（并查集 搜索）

想了半天写了一个搜索，不过里面用到了并查集的思想。。。结果很显然我TLE了6个点。看了题解之后发现自己傻了。。所以就把搜索去掉，单用并查集解决不就完事儿了qaq#include<cstdio>#include<iostream>#include<algorithm>#include<cstdlib>#include<cstri...

原创 【题解】洛谷P1491 集合位置（次短路）

解决k短路问题有很多思路，不过因为这道题目是次短路，所以我们考虑的可以简单一些。先跑一遍spfa，记录下最短路的路径和在这条路上每个点的前驱，然后枚举最短路的路径删边，再重复跑最短路，取最小值。这样求得的就是次短路了。#include<cstdio>#include<iostream>#include<algorithm>#include<...

原创 【题解】洛谷P3959 宝藏（生成树 随机化）

一开始可能大部分人的想法是这是个最小生成树问题，用prim就能解决，然而实际上可以发现由于有倍数与深度的限制，这种算法是不一定正确的。那该怎么办呢？我们只需要在找最小点之前做一下判断，用随机数取模，保证其有很小的概率取出来的是次小、更小的概率取出来的是次次小……的点，这个过程重复1000次（差不多吧），基本上就能通过了。#include<cstdio>#include<i...

原创 【题解】洛谷P1027 Hankson的趣味题(gcd 枚举 数学)

纯粹的数学推理题。。。找到思路后代码实现还是不难的。注意不要开long long。。。不然会TLE一个点思路：https://zzlzk.blog.luogu.org/solution-p1072#include<cstdio>#include<iostream>#include<algorithm>#include<cstdlib&g...

原创 【题解】洛谷P2118 比例简化（gcd 数学）

https://www.luogu.org/blog/18993/solution-p2118暴力就行 l不大#include<cstdio>#include<iostream>#include<algorithm>#include<cmath>using namespace std;int gcd(int x,int y){...

原创 【题解】洛谷P2651 添加括号III（gcd 数学）

看到是入门难度结果看了半天也不知道啥做法。。kkk大神给出了答案，a1肯定在分子上，a2肯定在分母上，如果我们想让这个式子更有可能化成整数，那么a1、a3、a4……an都应该在分子上，所以我们只需要枚举求其与a2的gcd，a2/=gcd(a2,ai)，如果a2化成1了，证明可以约分成功化为整数。否则就不能#include<cstdio>#include<iostrea...

原创 【题解】洛谷P1029 最大公约数和最小公倍数问题（gcd 暴力）

郁闷。。这题交了三遍才过 果然我太菜了qaq就是个枚举，我说一下我的简化思路。首先循环从x0到sqrt(x0*y0)，因为这后面的数都和前面相反了，所以枚举到这里就可以停下，乘二就是结果。如果枚举到一个数恰好为sqrt(x0*y0)就在乘二的基础上给结果加1.然后gcd和lcm乘积就是x0*y0，利用这个性质写一个gcd函数，然后判断一下他们的最大公约数是不是想要的那个，然后再判断一下能不能整...

原创 【题解】洛谷P1062 数列（进制 数学）

拿到这道题非常懵，不过如果仔细看的话会发现有一句话（以十进制形式表示答案）为啥这么说呢。。我们不妨找找规律。首先我们将n转化成k进制的数，对于题目给的k=3就是转化成三进制：1,10,11,100,101,110,111……这些数和二进制数也许有点关系 所以我们再把它们转化为二进制：1,2,3,4,5,6,7……答案也就出来了。我们只需要把过程逆回去，将n转化为二进制，然后在其k进制的表示...

原创 对拍的方法

当我们写出一个解决某个问题的高端算法后不清楚自己写的是否正确，而我们又能想到一种暴力做法，这个时候我们可以让两个程序对拍，判断自己写的是否正确。这里我们以洛谷P2152 SuperGCD为例，当我们写出了高精的做法又不敢确定是否写对时，我们可以写一下long long类型的普通gcd（当然前提是你这个不能写错）。然后将两个程序进行对拍，这里给出对拍的代码@echo off:loopda...

原创 【题解】洛谷P2152 [SDOI2009] SuperGCD（高精 gcd）

10^10000，这个数据范围是一定得用高精度的。。不过如果用平常递归求最大公约数的算法肯定会栈溢出，除法的高精又麻烦，所以我们可以考虑减法（虽然有人说更相减损术在这道题里其实是不成立的 但可以通过）。我们读入字符串，将对应的位存到数组里，手写高精度减法、高精度比较函数（因为gcd里我要让较大的数在前面）、输出函数，然后就要写gcd了。在没有任何优化的情况下，更相减损术的意思就是gcd(a,b...

原创 【题解】vijos P1200 ganggang的烦恼（高精 素数判断）

看到数据范围就知道需要用高精度乘法。。不过是一个整型*一个高精类型的，我们可以重载运算符来计算，数据比较水。记录数字每一位数的数组开到5000左右就够了，我之前开到1000跑不出500以后的数，结果居然A了。。。这个数据真的水管他啥的数学规律，素数判断无脑欧拉筛。#include<iostream>#include<cstdio>#include<a...

原创 【题解】洛谷P2149 [SDOI2009]Elaxia的路线(记忆化搜索 最短路)

题目里已经明示了这道题的目的：具体地说，就是要求无向图中，两对点间最短路的最长公共路径。那么我们首先得把两对点的每一个点到其他点的最短路求出来，可以通过spfa来解决。这里我开了一个二维数组dis[s][v]，s范围从1-4，分别代表出发点为x1,y1,x2,y2的四种情况，v则是其他点的编号。存下这个信息后，我们就需要找到最短路的公共部分。我们首先让Elaxia从宿舍(x1)出发，然后求在她到达...

原创 【题解】洛谷P1726 上白泽慧音（tarjan缩点）

拿到这道题后，知道tarjan算法的应该第一反应就是用tarjan缩点来求。观察一下数据范围，其实我们可以将裸的缩点模板打上去。问题可能集中在第二问，我们只需记录下染色的数组，在第二问时从小到大遍历如果当前点染的是最大的那个颜色，就输出来即可。（代码下附题目背景人物 车万永不过气）#include<cstdio>#include<iostream>#inclu...

原创 【题解】洛谷P1993 小K的农场（差分约束 dfs 最短路）

做多了应该能一眼看出这道题使用差分约束解决。根据1/2/3三个序号所代表的含义建立不等式组，然后我们将符号统一成一个方向跑最短路或者最长路，这里我选择跑最短路。如果出现在图内出现负环就代表不行，而如果用bfs-spfa的话会T几个点，所以改用dfs-spfa来解决。卡着时间过去了#include<cstdio>#include<iostream>#include&...

原创 【题解】洛谷P3953 逛公园（最短路 动态规划）

NOIP2017最难的题目。。。这里给一种比较方便理解的做法。拿到这个题目，啥也不用想，首先得把最短路求出来。然而求最短路时我们要反着建图，也就是求出n到其他所有点的最短路。为什么这样做呢？因为这样可以避免正向某个点无法到达n点的情况。求出最短路后，我们可以利用动态规划解决这个问题。首先考虑没有0边的情况。我们开一个二维数组f[u][know]，代表在反向图中从u到n与从u到n的最短路径之...

转载 【题解】洛谷P3952 时间复杂度(栈 模拟 字符串)

https://www.luogu.org/blog/WYW-wys/solution-p3952没想到.jpg 

原创 【题解】洛谷P2216 理想的正方形（单调队列）

一般的暴力做法的时间复杂度为O(a*b*n*n),一定会超时。其中a*b是省不掉的，所以我们可以在对n*n的区间寻找最大值和最小值内进行优化。https://www.luogu.org/blog/denial/solution-p2216以上是本题的解题思路，但具体如何实现这个思路，我们就需要用到单调队列了。对于X（行内最大值）和Y（列最大值）我们维护一个从大到小的单调队列，然后对于读进来...

原创 【题解】洛谷P2331 最大子矩阵（dp 前缀和）

对于m=1与m=2的情况分开单独处理，m=2注意有4种不同的状态https://www.luogu.org/blog/ttt-ttt/solution-p2331#include<cstdio>#include<iostream>#include<algorithm>#include<cmath>#include<cstrin...

原创 【题解】洛谷P2467 地精部落（dp 滚动数组）

https://www.luogu.org/blog/user55639/solution-p2467思维难度挺大。。正解不容易想 由于原来数组两维可能比较浪费，我们注意到每次更新dp数组只需要前一位的状态，所以我们可以利用滚动数组优化。这里令偶数位存在0中，奇数位存在1中，两者之间的变化通过&1来实现，这样能节省很多时间。最后注意该方程只是考虑了开头为峰的情况，结果还应当×2才是...

原创 【题解】洛谷P3084 照片（差分约束）

https://www.luogu.org/blog/user9643/solution-p3084注意用优先队列。。还有判断负环

原创 【题解】codevs P2218 补丁vs错误（最短路 状压）

我们可以将b+、b-、f+、f-集合用0和1的二进制表示来进行状态压缩，然后枚举软件的所有状态，如果当前状态取反&补丁b+==0并且当前状态&b-==0说明软件包含了补丁中的所有错误，可以使用。然后对原来的软件我们让他|能修补的错误与不能修补的错误，最后减去能修补的错误，然后将当前状态与利用补丁后的最终状态连上权值为输入的单位时间的边。最后跑最短路求得当软件压缩后所代表的数为0时的...

原创 【题解】codevs P2594 解药还是毒药(bfs 状压)

https://blog.csdn.net/qq_36799943/article/details/76919180思路非常清晰。。

原创 【题解】codevs 1391 伊吹萃香（分层图 最短路）

对于这道题我们可以利用分层图来解决。我们首先设点1~n为白洞，点n+1~2n为黑洞。首先对于每一个点，由于可以留在原地，而且过了一秒之后路另一端会变色，所以我们将自己所代表的白点与自己所代表的黑点连边，边权为零，意思就是在某个点为白洞时选择留在原地，不消耗体力。同样的，我们将自己所代表的黑点也就是n+i与自己所代表的白点连边，边权为读入的是停留的点为黑洞时所要消耗的体力。然后我们将读入的点连边...

原创 【题解】洛谷P2324 骑士精神(A*算法 启发式搜索)

第一眼看到就可以枚举空白格子位置然后跑bfs，处理一些细节就可以，这样的话最优能30分。为了让程序跑的更快，我们可以在读入队列某个元素时记录其和目标状态对应位置不同的数量，因为交换一下最多能消去两个格子（第一次），其他情况最多能消去一个格子，所以当前的步数+数量>16或者当前步数>=15(这里可以为等于因为在其前面已经有循环保证如果步数为15就输出结果并return)。这样还有一个...

原创 【题解】洛谷P2831 愤怒的小鸟（搜索 状压）

#include<cstdio>#include<iostream>#include<algorithm>#include<cstdlib>#include<cstring>#include<cmath>using namespace std;int t;int m1,m2;struct pig{ do...

原创 【题解】洛谷P2939 改造路（最短路 分层图）

因为有k条道路可以将权值变成0，所以我们可以构建分层图，读入边后循环k，将自己与下一层到达自己的点相连，到达自己的点与下一层自己所在的点相连，下一层的到达自己的点与自己两个点之间互相相连（注意这个是双向的）。然后就可以跑最短路，从1到(k+1)*n。这道题队列的spfa会TLE，所以我们可以进行堆优化，然后卡过去。#include<cstdio>#include<iost...

原创 【题解】洛谷P3225 矿场搭建（割点 tarjan）

https://www.luogu.org/blog/cjyyb/solution-p3225思路还是比较好理解的，不过实现起来挺复杂。。。虽然数据水 但还是注意初始化别搞错了。。我的Cut数组初始化为0时sizeof写的是cut，看了半天没找出来。。。#include<cstdio>#include<iostream>#include<algori...