Bellman-Ford算法，dijstra算法，循环dp问题 这题很好，让我重新认识到了最短路到底是为解决了一个什么样的问题！！！！ 题意： 分析： 首先，我不会分层图！！！！所以，这题我主要是围绕dp展开。我们必须要知道题中所给函数1/(1-x)是个周期为三的周期函数那么边权就为x,1/(x-1),(x-1)/x 这里是取过绝对值的这是前提，没有意识到这一点无从展开的。 这里我给一个dp状态dp[i][j]:点i在j状态时到达 状态为0的节点1 的最短路径j状态共有三种对应上面周期函数的每一种变化[x,1/(x-1),(x-1)/x] 那我们所求的答案就是min(dp[n][0...

分层图，建图，最短路 题意： 分析： 首先来看看我当时的思路吧！ 我们很容易发现这是个最短路问题，但线路的存在很棘手。雨神说过，图论的难点在于建图！如果成功建图接下来就只是套板子了。那来看看我们如何建图。我上来也没有思路，后是从实际生活入手的。想象一下，我们在站点i我们可以坐1,2,3三路高铁，登上1号高铁掏钱a1，登上2号高铁掏钱a2，登上3号高铁掏钱a3然后我们登上了高铁，假设我们登上了高铁1号线，我们向前开开了一站到达了j站的高铁上,这时我们要在花费b1然后我们从j站的高铁上下来，不用掏钱。 从i站到j站是不是就是这个过程。那我们就模仿这个过程建图就好了嘛。除了站点之外，我们再建立一...

题意： 分析： 正如“jxnu-19-软技一班-刘晟”所说的，按照kruskai算法的想法来看的话，出现多条最短路径的原因只可能是存在复数的最小权值边连接着两个集合以供选择。那我们其实只要在kruskai算法进行的同时动手脚就行了。我们先对权值进行从小到大的排序，然后将其分为一个个的相等权值的集合。对每一份的相等权值集合，我们看这里面有没有复数的连接两个集合的边，有的话我们实际上只需连一条，所以剩下的条数*权值就是我们要消去的。 代码： #include<iostream> #include<algorithm> #include<vector> #in...

最小路、枚举 题意： ##分析：版子题，枚举中间点，选两个最大的。注意图并不是连通图，选择的时候不能选自己。 代码： #include<iostream> #include<algorithm> #include<vector> #include<queue> #include<functional> using namespace std; typedef long long ll; struct edge { int to, cost; }; typedef pair<int, int> pii; const int ...

动态规划 题意： 分析： 这题和前面的Butterfly很相似，都是dp的组合。建议做完后去做做Butterfly 那么现在开始分析这题吧：假设我们选了i个savent，花费了d1的cost值，那么现在我们只有d-d1的cost值，我们用d-d1的cost值，到所有的概念礼装中去选最多i个概念礼装。在这个过程中我们要尽量使savent的atk和最大，也要尽量使概念礼装的atk和最大 也就是说我们要知道:花费d1选i个savent的最大atk花费d2最多选i个概念礼装的最大atk （d1+d2 = d）这便是我们真正的问题，这两个问题是相似的。 对于第一个问题，我们开一个动态规划数组dp1[...

线段树 题意： 分析： 以前没学线段树时，看一些题解总是会有这句话“这题可以用线段树做，当然不必这么麻烦。。。。。”总会产生兴趣，线段树是什么呀。上了雨神的课终于是清楚了。能够解决复杂问题的线段树也是起于简单的想法的呢。 不说了看着一题，很明显是区间求和问题。那么重点便为我们的lazy标记了！我们lazy标记应该为什么呢？标记这个区间最左端的元素值！而这个区间一定要应该从头到尾都是等差的即a1,a1+1,a1+2,a1+3......我们这样规定。这样就可以了。。。。。。 #include<iostream> #include<algorithm> using na...

树状数组 题意： 分析： 这两天一直在学习树状数组，但做题的时候总是有些摸不到头脑。不知道要在何处构造树状数组？又要用树状数组表示什么？ 通过这题，我来总结一下吧。这题中我们要求sum(l,r)[ai<=x]很明显直接去往区间里看是不行的，因为我们无法区分出ai<=x那我们简化一下问题吧。求sum(1,n)[ai<=x]这该怎么求呢？我们不可能每一次查询时都遍历整个数组吧。很简单我们就会想到，我们对数组从小到大排序，再对查询从小到大排序。然后遍历数组，并且计数，然后如果发现现在遍历的数组元素已经大于查询栈顶的查询值时，那么这次查询的结果就是计数数！这是很简单就能想到的。 ...

树状数组 题意： 分析： 我们很明显便能明白：对于妹子g1,如果没有其他妹子的细心程度和热心程度都大于他的话，就说明她是1级的。既然如此，我们不妨按照一个参数排一下序。按照细心程度排序：[g1,g2,g3,g4,g5,g6......]对于gi如果前面没有girl比的热心程度比她大，那么她就是一级的。如此判断了一级的再去掉她们，然后以同样的手法判断二级的。如此重复，最后将会得到答案。 那么接下来我们考虑如何在一次遍历中得到答案。我们遍历到gi时，去到前面的比大小。注意，我们此时前面的所有girl都已经确定了其重要程度。那么我们再比大小时，发现所有比当前女孩gi大的点，只有当这些女孩都在我们...

分块、树状数组 题意： 因为上次在月月面前丢人了，所以华华决定开始学信息学。十分钟后，他就开始学树状数组了。这是一道树状数组的入门题：华华很快就学会了树状数组并通过了这道题。月月也很喜欢树状数组，于是给华华出了一道进阶题：给定一个长度为N的序列A，所有元素初值为0。接下来有M次操作或询问：操作：输入格式：1 D K，对于所有满足i≡0(modD)的i，将加上K。询问：输入格式：2 L R，询问区间和，即sum(L,R)华华是个newbie，怎么可能会这样的题？不过你应该会吧。输入描述:第一行两个正整数N、M表示序列的长度和操作询问的总次数。接下来M行每行三个正整数，表示一个操作或询问。输出描述...

树状数组 题意： 情人节到了，小芳和小明手牵手，打算过一个完美的情人节，但是小刚偏偏也来了，当了一个明晃晃的电灯泡，小明很尴尬，就和小刚说，我交给你个任务，你完成了我俩就带你玩，否则你就回家吧。小刚很有当单身狗的觉悟，他坚决不想让小明过好情人节，同为单身狗的你能帮帮他吗？现在有一个n×n（1 <= n <= 1000）的格子，每一个格子都有一个电灯泡，可能是亮的，也可能是灭的（1代表亮， 0代表灭），现在有两种操作，一种是给你一个坐标，对于那个坐标上的灯泡，如果他是亮的，那么熄灭他，反之如果他是灭的，那么打开它。第二种操作是给你两个坐标，第一个坐标代表一个子矩阵的左上角，另一个坐标...

离散化，树状数组，大数简单输出 题意： 珂朵莉给了你一个序列，有 个子区间，求出她们各自的逆序对个数，然后加起来输出 输入描述:第一行一个数 n 表示这个序列 a 的长度 之后一行 n 个数，第i个数表示ai 输出描述:输出一行一个数表示答案 分析： 树状数组进阶中！！！！！！！！！这题大佬们已经分析的很清楚了。考虑贡献，对于一个逆序对(i,j)他在整个计算中的贡献为 ： i(n-j+1)当我们固定j，找到所有与j搭配的i(i1,j)、(i2,j)、(i3,j)。。。。。。那么总贡献便为：(i1+i2+i3+......)(n-j+1)sum(i)*(n-j+1)这里的这个i是在我们遍...

暴力枚举，剪枝 题意： 分析： 这题没什么，真的没什么。考虑数据范围，就真的只是单纯的枚举而已。最多再做一些剪枝优化，比如种类ti的没有装备就直接跳过，或者说发现即使接下来的装备都是理论上最好的也无法大于已经更新的ans。。。。。。。。 代码如下： #include<iostream> #include<algorithm> #include<vector> using namespace std; typedef long long ll; struct item { ll a, b, c, d; }; vector<item> items...

并查集、分析 题意： Problem DescriptionThere are n cities and m bidirectional roads in Byteland. These cities are labeled by 1,2,…,n, the brightness of the i-th city is bi. Magician Sunset wants to play a joke on Byteland by making a total eclipse such that the brightness of every city becomes zero. Sunset c...