未来重要-CSDN博客

原创 2021 牛客第三场 G

行不行不行不行……比赛的时候队友给我说了一说题意，想了一下没有想出来，主要是前边的简单题目都不会…做法：把给定的区间都当成限制，我们考虑区间的限制肯定越少越好。给定两个结论，我们来证一下结论一：对于两个区间a,ba, ba,b, 假如bbb完全包括aaa，对于bbb区间，对于最优解我们有两种选择：第一种：和aaa区间放到一个组。第二种：单独放到一个组中。第一种选择很好理解，我们怎样理解第二种选择呢，我们前边说过一句话，把区间都当成限制，假如bbb区间没有单独放到一个组中，我们可以将bbb区

2021-07-25 22:04:09 142

原创 2021牛客多校 I 期望dp

题意AliceAliceAlice和 BobBobBob 玩游戏，规定每轮每个人在序列中选一个数字，要求是选择的数字的大小一定是比之前两人选过的数字都要大，选择数字在序列中的下标要比该选手选过的数字下标要大。题解我们发现该选手选择序列的限制有两条，我们想到是否可以使用dp来表示限制然后转台转移模拟选择的数字，然后我们开始设置状态，f[i][j]f[i][j]f[i][j]表示Alice选手前一次选择了数字jjj，iii则表示BobBobBob选手上一次选择的数字的期望次数g[i][j]g[i][j..

2021-07-23 18:07:25 168

原创 2021 年牛客多校第1场 G

题目描述：题意给你一个两个序列，要求你交换的一个序列K次使得值最大。题解我们首先思考绝对值对于两个数的含义是两个数之间的绝对距离，然后我们思考如果我们交换第一个序列我们的答案会如何改变，我们将两个序列相对应的位置抽象成一个个的区间，a[i],b[i]a[i],b[i]a[i],b[i] 形成区间[a[i],b[i]][a[i], b[i]][a[i],b[i]]（这里假设a[i]a[i]a[i]比较大）交换第一个序列无非就是改变两个区间，我们首先想到如果两个区间是有交集的，那么我们无需交换，因为

2021-07-23 16:54:05 157

原创蓝桥杯 I: 翻转括号序列（满分做法）

本质上是线段树加二分最近忙着考试，等有时间再来详细写写做法。不知道在哪里提交，反正我大数据对拍了5分钟都是通过的，小数据也对拍了很久。#include <iostream>#include <cstring>#include <algorithm>#include <ctime>#include <vector>#include <set>#include <map>using namespace s

2021-07-05 20:51:53 629 5

原创 Kill Anton

小前置知识前置题目这里简单的讲解一下：答案为什么是逆序对的个数，因为我们每次只能交换相邻的元素，对于我们的每次操作，我们可以将我们整个序列的逆序对加一或者减一，因为我们最终序列的逆序对数为0，所以我们每次操作一定是将逆对数减一，这样我们逆序对数的个数就是答案的个数。大前置知识传送门题目含义：给你一个字符串，每次只能交换相邻的元素，问将整个字符串翻转的最小步数是多少。题解：首先我们先注意到只能交换相邻的元素，这时候我们就应该开始往逆序对的方面上想，我们可以发现这道题目与前边的有些许不同，首先对于

2021-06-02 23:36:36 259

原创 ~_~

为什么要写题解！！！！！（bushi）查询Description给出一个长度为nnn的序列aaa给出qqq组询问，每组询问形如(x,y)(x,y)(x,y)，求aaa序列的所有区间中，数字xxx的出现次数与数字yyy的出现次数相同的区间有多少个。Data Constraint1<=n<=8∗103，11<=x,y,ai<=1091<=n<=8∗10^3，11<=x,y,a_i<=10^91<=n<=8∗103，11<=x,y,ai

2021-03-19 17:16:44 93

原创 Alex and Julian

慢慢来嘛。昨天做了一道题目，被一个地方卡住了。（想想自己真的是好蠢呀）。先不说其他的，首先我在错误的题意上已经走了好远，后来实在是不会了，看了一看题解（对不起我实在是不会了），对不起我没忍住把题解给看完了，但是我还是没有看懂题解，我好蠢啊。网上的题解都很多，那个主要的部分我就不写了，我写一下当时我疑惑的地方吧，当时在证明完两个数的情况的时候，如何扩展成多个数的情况。最后证明多个数的时候的感觉是不对呢，我们需要证明的是它不会形成奇数环，而不是证明我们可以形成偶数环，这里我有一种比较好的方式：我们可以将

2020-11-25 21:36:24 116 1

原创 Moving Points

别灰心，我一直相信着你呢。题目链接题目大意：给你一些点的位置，并且每个点都有一个速度，定义一个最短距离是在任何时间两点之间之间的最短距离，然后要求我们求出所有点对的最短距离的和。这题老数据结构了。首先我们先想到每两个点对之间的最短距离该怎样计算，由于我们每个点都有一个速度，所以我们我们两个点对之间会有一个速度差，假如这个速度差不是000，由于时间是无限制的，这个速度差会将两点之间的距离无限缩小或者放大，我们就可以想到两点之间的最小距离不是000就是他们一开始本来之间的距离，如果这个速度差是000 的

2020-11-09 13:40:23 241

原创 Cow and Fields

先写一下这周发生的事情吧，这周我们是劳动周，我被分配到了站岗排车子的保卫组，虽然倒是没有什么活干，但是由于是在户外，天气太冷了有没有，真的是手都要冻掉了，但是我可以偷懒来实验室打代码（嘿嘿这倒是还不错），但是还是有查岗的，所以还是小心翼翼的，这周注定是艰苦的一周，这周天好像还有比赛要打，加油！昨天和前天就做了一道1900 的图论题，现在想出来倒是没啥了，但是没有想出来之前是真的难啊有没有，真的是折磨，痛并快乐着。少点压力，不要看的太重。本来就一无所有，所以变成什么样子都无所谓吧。题目地址首先我们明

2020-10-21 18:33:14 135

原创 pbds!

今天在做题的时候发现了这个数据结构有点意思，但是我还没有完全的搞明白，因为我感觉可能会有更厉害的功能。这个主要的功能就是维护一个动态的有序数组，可以根据下标来求值，还可以利用值来求下标。在这里记录一下学习网址...

2020-10-19 20:52:03 286

原创 TediousLee

这是一道好题，一开始我以为这道题目数学组合数的题目呢，但是没想到是个dp，我还是太菜了，慢慢加油！题目地址做这道题目首先我们必须发现这道题目的一个特点，就是假设我们有一颗水平是iii的树，如果他有三个儿子的话，那么这三个儿子的水平一定是i−2,i−1,i−2i - 2,i - 1,i - 2i−2,i−1,i−2，那么我们就可以利用dp的思想来求最大值，首先我们对于水平是iii的子树来说，我们可以选择是否选择以根节点为首的爪，但是对于我们保存的子树i−1i - 1i−1这个状态来说，有可能子树i−1i

2020-10-10 16:41:48 98

原创 Lonely Numbers

还看不见绿洲呢，绿洲的存在是来安慰迷失者的吗。现在的我就像是沙漠中迷失的人，只能奔着我认为对的方向一直前进，向着我认为存在的绿洲前进，虽然过程是困难的，但是只要结果是好的我就已经心满意足了，天多给我点运气吧！昨天晚上评奖学金我居然评上了有没有，虽然只有600块，但是也是非常开心有没有！出去吃饭！今天上午在实验室打印东西，发现打印机没有反应，还以为是电脑的问题，搞了好长时间，结果旁边的学长按了下打印机的开关，打印机正常运转了，原来是没有开机，我真的好蠢啊啊啊。然后就是这几天做题做的比较少了，因为感冒了

2020-10-09 09:35:21 190

原创 E1 - Asterism (Easy Version)

人菜就要多努力，今天实验室去教室里边去宣讲（虽然我只是一个打杂的），我预感这届新生会有强的选手，带带学长们吧！今天一天的课，并且上午极困（并且上午上完课感觉那个困劲小了一半有没有，我果然还是适合自己自学），没有什么时间去想这道题目，感觉自己静不下心来呢，还是稳住吧，感觉要想拿牌子还是不能幻想着队友的爆发，我还是先爆发吧。思路：我们首先有nnn个糖果，题目中要求我们每次对决都不能输，所以我们在对决中的糖果数量已经是一定的了，就是 x,x+1,x+2……x,x + 1, x + 2……x,x+1,x+2…

2020-09-28 21:24:50 151

原创 A. String Transformation 1

做好当前吧，抱怨和祈求怜悯没有任何作用，你不是来作秀的！题目地址又是一道好的题目（其实是因为我菜。。），cf 真的是个好东西。思路：首先先判断无解的情况：这个很好的判断。然后是有解的思路：看成一个图论的问题，我们将字符串aaa和字符串bbb不相同的点之间建一条边，我们可以想一下假设我们需要a[i]−>b[i],a[j]−>b[j]a[i] ->b[i], a[j] -> b[j]a[i]−>b[i],a[j]−>b[j]，并且我们如果b[j]==b[i]b[

2020-09-24 11:02:27 181

原创 B. Stairs

在这道题目上我充分的认识到了专注的重要性，下午做题心思一直不在线，一直想着各种事情，想要把各种事情做好，除非是能力特别高的，不然到头来大概率是所有的事情都做不好，专注下啊啊啊啊啊啊，所有的决策不一定都是最优的，也不一定是最坏的，慢慢的看着来吧。题目地址题目大意：我还是写的详细点吧，毕竟折磨了我好久的。上图是题目中的楼梯的样式，都是由一个一个的小正方形组成的，并且都是第一行1个，第二行2个……等等。题目的问题是给你这些小正方形的数目个数，求利用这些小正方形组成的nice型阶梯的数目是多少（小正方形可以

2020-09-22 20:03:58 225

原创 Cyclic Permutations

就差一点点了，再坚持下吧，保持热心，稳住心态。题目地址思路：题目给的还是比较绕的，但是代码就一点点，需要思考下，我们根据题意发现相邻的两点之间一定会连边，因为边是无向边，所以我们发现我们只要存在一条横跨多个点的边就可以完成一个环，我们经过思考发现，只有点之间的权值‘’凹‘’形状才会出现这样的情况，所以我们需要求出序列形成“凹”的序列数目，我们发现正向求很难求，所以我们反向求。求出没有形成“凹”点的序列的数目，题目中说过，每个点的权值是不同的，所以我们只能有三种不合法情况，即一直上升，一直下降，先上升后

2020-09-10 16:29:13 98

原创 D. Decrease the Sum of Digits

题目地址垃圾如我。题目含义：给你两个数a,ba, ba,b，求大于等于a 的某数的各位加起来小于b最小是多少。思路：我们在加的时候发现只有进位的时候才会存在数字相加和减少的情况，所以我们只考虑进位的情况，当然我们不可能在个位一位一位的加一再进行判断，所以我们需要跳过某些不可能的数字，我们发现当存在xxxx00xxxx00xxxx00这种末尾几位是零情况的时候，若这种情况不合法，那么我们没有必要在后边几位上继续加，因为这样一定是不合法的，所以我们只能寄希望于更高位的进位，，这样造成的结果一定是后边的0越

2020-09-07 19:50:06 98

原创 Stoned Game

努力也成功不了的话也太心酸了啊题目地址题目挺好的，就是想不出来。这道题目有点博弈论的意思，一般没有学过博弈论的话是很难想出来博弈论的题目的，基本上是不可能的。但是这道题目好像没有博弈论那种味，仔细分析下还是可以的。题目大意，给你n堆石子，每轮玩家可以选择某一堆石子然后拿走其中一个石子，其中在每轮游戏中玩家不能选择同一堆石子，到最后那位玩家动不了就是失败。思路：我们首先想假设有一堆石子数量特别多，其余的堆石子的数量特别少，那么先手拿的人肯定是赢的（因为它可以死赖在这堆石子上），那么剩下的情况呢，我

2020-09-03 09:09:49 120

原创 Multiples of Length

蠢蠢蠢死了，啊啊啊啊我真的要被自己蠢死了我也不知道总结这样的题目有没有用。。今天下午做的题我的智商真的直接降到5。题目的大概含义就是你有三次操作，每次操作选一个区间，然后可以选择在区间上每一个数字加上一个区间长度的整数倍（后边补充了可以是0），只有三次操作，问怎样才能将所有的数字变成0。真的看到这种构造的题目智商直接变成了 5，这种题目的思路真的好宽啊啊啊，做的还是少，看到直接到处想，进行毫无目的的想。感觉我的思路还是被束缚了，一开始想着这根本不可能啊，但是看到大佬的榜单的代码，我真的是瞬间醒

2020-09-02 18:48:49 180

原创关于代替动态的向数组中插入数据有效的方式

今天遇到了一个题目感觉有点意思，我开始直接想着拿链表过掉的，发现链表无法完成这个题目，然后后边我又想着并查集可不可以，但是并查集好像也是复杂度有点高，后边一直在找优化的方式，怎么想感觉复杂度都会是在平方的级别。问题抽象成的模型也是非常的简单，要求就是想数组中不断的插入数据，然后最后会问你每个数据的排名情况，当然这道题目直接vectorvectorvector是不可以的，因为时间复杂度太高了，会被卡掉，想用链表？那我们就需要维护一个点的排名的逆向，而维护这个排名我们需要线性的时间复杂度，并查集怎么样呢？这也

2020-08-23 23:43:15 100 1

原创第五套题目的总结

这第五套有些题目还是可以想出来的，但还是有难的题目想不出来，这大概就是我的天花板了吧，以后还需要更加的努力啊。首先第一道就是一个简单的kmp字符串匹配算法，由于在做的时候kmp算法已经好久都没有用了，居然下手写的时候有点懵？？第二道第二道题目是最小生成树加上最近公共祖先的变形，比这道题目稍微简单点，但是可惜没有一次写过，忘了写一小行代码。第三道是。。。第三道！！这道题目好像是最折磨我的了，这道题目我本来想着可以贪心过掉的，但是奈何我的思路不够缜密，最后还是老老实的用数组记录下过的，这也算是dp

2020-08-22 22:14:50 82

原创带邻域的并查集的理解andFloyd

关系是有向的，但是集合是无向的。一般来说带邻域的并查集都可以用带权的并查集来解决，虽然说带权的并查集也不是很难，但是闫学灿老师讲的带邻域的理解方式感觉比较好，感觉还是记录下来比较好。一般用到这样的算法的题目是：给你几个种类，然后告诉你这几个种类的关系，然后给出几个条件让判断是否产生了矛盾。这样的题目首先要具备两个点，一个是每两个种类的关系必须要知道，邻域并查集的目的：在一个集合里边的元素我们应该知道每两对之间的关系带邻域的并查集首先最主要的思想上是枚举的思想，对于每个元素我们分成若干个条件，

2020-08-18 23:44:25 340 1

原创欧拉回路

写一下欧拉回路，欧拉回路在小学数奥里边简称一笔画问题，意思是用一笔将所有的边全部走一遍且不能重复。欧拉回路的结论：在无向图中，存在欧拉路径的充要条件是：1、所有的点的度是二的倍数或者是2、只有两个点的度数不是二的倍数，其余所有的点都是二的倍数。存在欧拉回路（起点和终点相同）的重要条件是：所有的点的度数是二的倍数。在有向图中，存在欧拉路径的充要条件是：1、所有的点的出度和入度是相同的。或者是2、只有两个点的初度和入度不相同，且这两点其中某点的出度比入度多一，另外一个入度比出度多一。存在欧

2020-08-15 23:47:15 674

原创二分图

用感性来感知世界。最小点覆盖选择最少的点，将所有的边都覆盖到，这样就叫做最小点覆盖，正常的图的最小点覆盖我不会！但是二分图的最小点覆盖还是有结论的。结论：最小点覆盖 = 最大匹配数。证明：第一步：证明最小点覆盖 >=>=>= 最大匹配数。证明：我们每条匹配边两边都有两条匹配点，而且每条匹配边两边的匹配点都不相同，是相互独立的，即点如果是匹配点，那么只属于一条匹配边。那么我们至少在每条匹配边两端上取一点才能将所有的匹配边覆盖掉，更何况还有非匹配边。第二步：选择一种方法得出在这

2020-08-13 15:00:41 86

原创棋盘覆盖

题目地址只有在深入的去思考一些东西的时候才能有所收获，加油！在开始看到这道题目的时候没有想到这是一道二分图的题目，当时听完老师讲的感觉恍然大悟，但是过了两个月之后在看这道题目的时候，虽然知道这是二分图的题目，但是推理的过程已经记不清了，还是写一下吧。问：这道题目为什么可以看成是二分图？可以利用二染色法，首先我们对每个格子隔着一个染一个色：就像这样，我们发现白色的格子和白色的格子不存在边，绿色的格子和绿色的格子不存在边，这个就是一个二分图，而题目中要求覆盖点不可以重复，那就直接可以匈牙利算法解

2020-08-12 15:24:29 93 1

原创无向图的强连通分量拓扑

首先先讲一下拓扑排序的递归做法。看似有点玄学，讲一下为什么是正确的，在一张拓扑图，我们如果能够保证每一条边 a−−−>ba ---> ba−−−>b，在序列中aaa 始终保证在bbb 的前边，那么这个序列一定是拓扑序。贴一下dfsdfsdfs求拓扑的代码：bool dfs(int x){ vis[x] = true, st[x]= true; //st 数组表示的是点是否遍历到，vis数组则表达的是点是否在正在搜索 dfs 路径上。seq 倒序输出就是答案 for (

2020-08-09 22:23:48 574

原创树上差分

首先对于最简单的线性差分，我感觉还是可以用状态来表示，对于每个点的真实值是dp[i]=a[1]+a[2]+a[3]+.....a[n]dp[i] = a[1] + a[2] +a[3] + ..... a[n]dp[i]=a[1]+a[2]+a[3]+.....a[n]，也就是说，无论何种差分的时候，我们需要先明确aaa数组。首先我们在dfsdfsdfs遍历树的时候，一般都是在节点上标记或者记录东西，只是因为我们在dfsdfsdfs的时候是在点之间进行转移，边只是一个通道，我们在储存图的方式也多是邻接表

2020-08-09 14:19:42 72

原创分层图

做了三个分层图的题目，感觉自己又行了，写一下技巧吧，第一道题目是有k条免费的边，然后求最短路。这种简单的分层图其实是不用真实的建边的，因为我们在做的时候发现每层之间的边都是有规律的，且层中的边都是有相同的，且权值都是0，利用这种特殊性，我们可以用 dp 来解决这个题目，在求最短路的时候我对每个点设置kkk个状态，每个状态对应着该点所在的层数，在每次进行状态转移的时候，我么可以选择下一个点是否转移到下个一层。这样我们就可以不用真实的建立kkk层图来解决这个问题了。题目地址：最短网格接下来的题目变得就有点

2020-08-06 21:51:44 188

原创差分约束和dp和最短路

继上一篇有感我发现学的越深入，各个知识点之间的关系真的就是越紧密，我希望有一天我能学习完所有的算法，站在算法的顶端俯瞰各个算法之间的联系，感受算法之美，感受逻辑之美，想想那时候是多么的骄傲和自豪啊。很久之前做过的一道题目，当时做的时候是跟着老师的思路来做的，当时并没有多大的启发，但是后边我在看一遍的时候发现题目不是那么理所当然，也怪当时没有深入的思考，以后不能想着这是对的就完事了，要问为什么，不能做那种看见题目就没有思路，一看题解代码就都懂的人，真的不要这样，这很重要。谁让这道题目是一个差分约束 +

2020-08-02 01:12:28 147

原创差分约束条件

之前学的差分约束也没怎么总结下，写一下吧。差分约束其实主要的还是需要将条件给列举完整，感觉这是一个有点难的点，怎样将条件进行列举完整呢，我想写一下这个点，以后遇到新的再来补充。确定点的所表达的含义，这是极为重要的。先从普通的来讲，假设点没有任何实际的含义，就是点与点之间距离，那么这就是最短路了，正常的列举完条件作图就完事了，剩下的就交给spfa，假设我们每个点表达的是某个状态，那么就需要注意了，看下每个状态的取值又没有什么限制，状态和状态之间的大小关系有没有什么关系。题目：给定 nnn 个区间

2020-08-01 02:19:48 177

原创点和边之间关系的负环

写一下这道题目，题目是之前做过的，但是现在再做一遍感觉有点陌生，说明之前做的时候没有认真思考和总结，现在做完这道题目感觉还挺重要的，还是写一下这道题吧。自认为可以将这种的题目抽象成：首先是一个环，其次是环内点和边都有权值，然后让我们求一些东西，比如点的权值和边的权值和之间的比值的最大值之类的，像这样的题目我们一般会发现答案是具有单调性的，我们进行二分，然后判断是否有满足这样的环即可。写一下判断的方法是 ∑point∑edgs>=mid\frac{\sum point}{\sum edgs}

2020-07-30 22:26:31 190

原创无向图的最小环问题

板子题目地址夜深人静最适合静下心来写博客了哈哈。写一下最小环问题的Floyd解法吧，时间复杂度在立方的水平（还行吧），做法和Floyd一样，只不过是在作Floyd的时候，多了点操作，我们的想法是将每次Floyd做法枚举的中间点k，作为环的最大点，为什么要这样做呢，因为这样做枚举的环中一定不会存在重复点，那么我们只需要做下边的操作 res=dist[i]j]+map[j][k]+map[k][i]res = dist[i]j] + map[j][k] + map[k][i]res=dist[i]j]+m

2020-07-27 23:53:00 180

原创 Mysterious Code （状态机 + dp + kmp）

题目链接哈哈哈今天晚上ig VS tes， ig 居然赢了，作为極粉的我真的很开心，写一下今天下午做的题目吧，是一个kmp + 状态机的题目，之前做过一个这样的题目，但是奈何做题数量真的不多，一开始还是不清楚做题方向，还在向贪心的方向上想了一会（指半小时），后来知道是dp之后自己也是独立的做出来了，想想自己还是有一点实力，就是要自信点，大胆的去猜和做，就像小ig一样冲冲冲，这几天没有ig的比赛了，那就潜心研究下算法！！首先先想一下这道题目为什么可以利用dp来做呢，其实这道题目也是在进行枚举，对

2020-07-27 00:44:12 652

原创回文串（DP）

天下人类一家亲，望人类停止斗争！题目描述Friday is Polycarpus’ favourite day of the week. Not because it is followed by the weekend, but because the lessons on Friday are 2 IT lessons, 2 math lessons and 2 literature lessons. Of course, Polycarpus has prepared to all of them

2020-07-25 00:50:46 189 1

原创传递闭包

好段时间没有更新我的博客了，之前一段时间在考试复习，复习了一个月，复习了一个月发现之前的算法学的太快有点遗忘了，于是重新学了一遍，虽然说过程有点艰难，但是在重新复习了一遍后还是发现不少我可以学习的地方，机油吧！写一下Floyd 算法的一个用途：传递闭包。思想也很简单，例如：A<B,B<CA < B, B < CA<B,B<C, 那么我们就可以得出A<CA < CA<C ，代码的思路很简单，首先先枚举所有比AAA小的CCC，然后再枚举所有比

2020-07-22 23:25:35 532

原创线性求逆元

我是真的不会。。太难了。。。。唯有被虐让我感觉还活着。。太惨了。。今天下午的题目怎么就这么刚猛呢，我居然一个都不会做，这样跨难度的题目真的不适合我，果断离场去学习基础！写一下线性求逆元的证明以及代码吧！首先对我我们求得的iii，ppp为模数，令 b=p% ib = p \%\ ib=p% i，k=pik = \frac{p}{i}k=ip ，我们可得到式子 p=k∗i+bp = k * i + bp=k∗i+b，可得到 k∗i+b=0(mod p)k * i

2020-05-10 14:55:43 168

原创牛站

有一段时间没有总结了，趁现在闲着没事干，写一下今天晚上做的一道多源最短路的题目的题解吧，这道题目真的有很多可以学习的地方呢！（02冲冲冲）。题目也是经典老题目了，名字叫牛站，由于我是在acwing上看做的这道题目，网站上已经将题目的剥离的非常干净了，只剩下题意了。。我猜这题目应该是有背景的，但是我也不去原题了，看到蓝皮书上的也是只给出了题意，蓝皮书上也给出了题目的出处PS：这道题目真的是好题，强烈建议去做一下。首先这道题目启发我的地方是，符合结合律的式子都可以用快速幂，我们平常的加法（两个数相乘~），乘

2020-05-10 00:22:24 1298 1

空空如也

空空如也