点分治 今天学的算法，呀。其实之前打比赛时做到过类似的题目。当时没有去补题，感觉怪难的。现在学学。 点分治主要是用于求解树上路径类的问题。这题如果能想到点分治的话，思路其实还是挺清晰的。但是，刚学，我板子写错了哦 #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=1e5+100; const int inf=1e9; struct edge{ int to,cost,next; }E[N<<1]; int head[N];...

大体方向上是正确的。但是，代码处理时我做的不好。我也意识到了，老老实实地枚举的话，时间复杂度一定是10^9级别的。如何优化呢？我也注意到了，在枚举向右地次数的时候是有一个单调性的。对于每一个robot，能够检测到他的点一定是越来越少。我们只用先对监视器和robot排序，就可以利用这个单调性了。但是，即使如此，我仍然tle了。我的做法其实已经和正确答案差不多了，思想史类似的。但是我的常数太大了，所以被卡。然后，我看了正确答案。正确做法是，先筛选出所有的监控监视robot的情况。然后再进行排序，执行上面的类似的操作。常数很小。跑得很快。 #include<iostream> #incl...

今天的一场虚拟竞赛就是一道贪心+模拟不难，但是wa了好多发。果然还是没有适应这个难度的题目啊 题目让我们求最大可以带走的军队数量。很显然，我们能够想到二分。我们从属性值最高的兵开始带走，可以只考虑带的兵中属性值最低的那个人。所以，我们只需要排个序就行了。关键是二分中如何二分呢？如何判断，这个属性值可以在规定时间内度过呢？check()函数是关键！我们想想哈，假设我的军队走到了1出，发现2处有陷阱，且可以杀死我的军队中最弱的那个人。那么，身为司令官的我肯定要先去拆除那个陷阱。假设我需要走到5处才能拆除那个陷阱，那么自然在从2到5这一路，我会把我能拆的陷阱都给拆了。然后我再跑回来带领军队前进 ok...

动态规划 并不是很难，就是情况稍显复杂。我峨嵋你要分两种情况1.x为正数2.x为负数 如果为正数，那么我们直接求出这个数组初始的最大的美丽数然后乘x就可以了。注意这里的初始最大美丽数最小为0，因为如果全部是负数，那么我们一个也不取 如果为负数，那么很有可能被会出现这样的一种情况[L,R]为答案区间 [L,ML]初始美丽值为正，[ML,MR]初始美丽值为负，[MR,R]初始美丽值为正然后我们对[ML,MR]乘x之后得到了最大的美丽值 我们怎么得到这个呢？首先我峨嵋你可以两个指针O(n^2)的枚举。但是这肯定是不行的。那么我们动态规划。如何进行动态规划呢？我们可以分成两段。第一段[L,MR]第二段...

implement 贪心 老实说，思路并不是很难。但是，实现起来是很有难度的。其实就是如果两个元素冲突了，那么我们就增加那个代价比较小的就可以了。很简单，但是我的实现超时了。懊恼。个人感觉实现起来真的是有一定的难度。 推荐这个并查集实现的代码： #include <map> #include <iostream> #include <algorithm> using namespace std; #define sd(n) scanf("%d", &n) #define sdd(n, m) scanf("%d%d&quo...

dp 之前看了，雨神的关于dp优化的思路视频。感觉很神奇。就在cf上做了一做。磕磕碰碰。。但是，确实思路是雨神说的。首先对于这道题，我们要判断是否可以取出一些数其和能整除m直接设状态方程dp[i][j]即到第i个为止是否能够凑出符合要求的数。对于这种能否凑出来整除的题，我们往往有一个技巧就是先进行取模。这会方便许多，这样只要我们能凑出来0即dp[i][0]=true那么就能满足。那么怎么转移状态方程呢？dp[i][j] = dp[i-1][?]|dp[i-1][?]这里有一个技巧，我们这样写状态转移方程是十分困难的。所以，我们不妨这样dp[i][j] = true 那么dp[i+1][j]=t...

贪心 这一题个人感觉倒不是多难。主要靠直觉。首先，如果没有k这个条件的话，我们肯定是从大到小的取元素。这一题最开始，我们也应该从大到小地取元素。同时此刻的cur即元素值也在不断变化。一旦cur变为负数的时候，我们break一下。然后问题来了，我们对于接下来的每一步都必然是负数的元素，该如何使用这k次机会使得减少的值最小？若接下来还剩m个元素，那其实就是将m+1个元素分为k+1组，从小到大地取元素。为什么是这样。首先分组这个概念肯定没有问题。那么我们看分组会带给我们什么？最后一个人的影响为0！！！既然如此，我们当然要把最小的放在每组后面。也就是，前k+1个最小作为每组的最后面！！那么为什么是k+...

思维题 这题有个小陷阱，比赛时掉进去了。过了pretest但是没能Accept首先，最小的次数肯定就是1既然是异或，那么我们很容易就会按照位进行思考。我们想想，如果最高位为i的数字，总数超过3个。那么我们是不是一定能在1此操作中干掉这个数组。能的，对后两个进行异或，然后与前面的一个比较，一定小于前面的一个。 这是关键，因为通过这个方法，我们排除了大量的数据。也就是说，经过这一步的筛选，最终剩下来的最多也只有64个数。这就允许我们使用一些相对暴力的算法去解决了。下面有一个结论：如果我们操作了k此，那么这k次一定都是合并一个连续的区间。为什么这样说呢？假设k == 4 数组：[a1,a2,a3,a...

找规律 我在打表后发现，这一题可以进行二分答案，来做。虽然整体并不呈现单调性但是偶数和奇数却呈现单调性。这就很方便了。我们可以分别在偶数和奇数上进行二分答案，然后取大即可。 但是，有一个困难，那就是如何求解每次这个数出现的集合数如何求解呢？刚开始我是使用暴力的，因为我隐隐约约的感觉复杂度应该不算很高吧。。。但是，我错了，这个复杂度是很高的，甚至可以达到O(n)级别。而远非我们所想的O(logn)那么我该怎么办呢？苦恼啊苦恼 看了题解。发现其实题解也是在找规律。这不过他是从公式中找规律。他发现对于一个数x，假设是奇数。那么根据函数，2x,2x+1 肯定出现他4x,4x+1,4x+2,4x+3肯定...

dp 我在一开始的时候也想要用dp去做，但是发现，对于占据一个节点我们可以在当前位置占据他，也可以在之后占据他。这一就意味着我峨嵋你的dp具有后效性，那么就不能dp了 苦恼啊苦恼。后来发现，这里其实是一个简单的贪心。 对于占据一个节点，很明显我们在能占据他的节点中的最后面占据他就好了！这个贪心至关重要，他帮助了我们解决了dp的后效性问题。那么我们就可以利用dp了。dp[i][j]到第i个位置上，拥有j个士兵(还没在当前节点招募士兵)从这之后的最大收益。 很明显，我们可以不去防守节点，直接去占据下一个节点。当饭我们也可以去占据节点。如何占据呢？我们从大到小的占据，优先占据性价比最高的嘛。 如此，...

区间dp 虚拟比赛时没有做出来，看题解时，第一句话就让我反应过来了！可恶！！！！ 最终的答案假如[a1,a2,a3]那么a1,a2,a3一定是三个区间合并出来的也就是，我们给数组划分几个区间，这些区间都可以合并成一个数。找到划分区间的最小数。 问题一下子就简化了！！定义dp[i][j]，如果[i,j]不可以合并成一个数那么dp[i][j]=inf否则dp[i][j] = 最终合并的这个数转移dp[i][j]=dp[i][k]+1 if dp[i][k]!=inf&&dp[k+1][j]!=inf&&dp[i][k]==dp[k+1][j]其实就是划分更两个区间看...

斜率dp 斜率dp都不大好写啊，细节的边界处理感觉好麻烦啊。这里我们很容易就总结出状态和状态转移方程了。我们首先从小到大排序(在斜率dp中排序很重要，有利于保持决策的单调性)dp[i] 表示到第i个点为止的最小花费。dp[i] = min(dp[j-1]+sum[i]-sum[j]-(i-j+1)a[j])注意范围t+1<=j<=i-t+1那么我们就对这个公式进行斜率dp的优化就行了，把他变为O(n)但是要注意的是起始的初始状态。如果i<t的时候怎么办，很显然这时是不可能的。那么当i<2t时怎么办？很显然这时我们必须一起打包买走的。处理好初始情况，我们就可以解题了 #i...

论文题，再度认识了数形结合！！！所谓斜率判断时，可以划分阴影区域的，有助于判断 #include<iostream> #include<algorithm> #include<queue> #include<deque> #include<vector> #include<functional> using namespace std; inline int read(){ char c=getchar(); int x=0,f=1; while(!isdigit(c)){if(c=='-')f=-1;c=getchar(...

tarjan，找环 比赛时先看错了题，然后，想出来方案再到编码没赶上。coding还是太慢了。要刻意练习。 关键信息在于n个节点n条边。我们注意到了，这其实就是一棵树再加上一条边。树中形成了一个环。我们把这个环单独拿出来，将其他节点视作有这个环上的节点向外的延申。也就是以这个环的每一个节点为根生成了一个又一个的树。我们可以统计每个树的简单路径，然后再统计经过了这个环后的简单路径。如何统计经过了这个环后的简单路径呢？我们注意到经过这个环，那么这条路径的两个端点一定是在不同的树中，而因为是环所以对于同样的起点终点我们有两条不同的路径。故，算法完毕。 但是，麻烦的事来了。我们如何找到这个环呢？利用类...