- 博客(133)
- 收藏
- 关注
RSS订阅原创 洛谷P2607 骑士 树形dp
思路：首先我们想到可以对相互憎恶的俩个骑士连边，这样就得到了一个图，有多个连通块，并且每个连通块中最多只有一个环。如果每个连通块都是一颗树，那么这个问题就很简单~每个节点都是选或者不选。idea1：我想可不可以把这个比树多一条边的图，变成一棵树来处理，那么就是要删掉环上的一条边。考虑删掉这条边(u,v)的影响是什么，影响是u,v两点可能同时被选，产生错误的答案。我的解决办法是把边删了的同时...
2020-03-13 18:22:53
180
原创 CF596C 最多只用30次循环，一定能得到答案
/**/#include<bits/stdc++.h>using namespace std;#define maxn 300010#define ll long longmap<int,int> M;int a[maxn];int cal(ll x){ int cnt=0; while(x) { cnt+=(x%2); x/=2; }...
2019-12-13 18:57:21
209
原创 牛客练习49D(差分巧解区间+递归的处理)
思路：看到这题，我脑海中浮现了一颗树~每个叶子都是一个1类型的操作。。。想到了n^2的算法，记录下每个操作时，之前所有操作的操作次数。dp[i][j]:i操作时，j操作一共运行了多少次~然而并没有什么用。。。看到题解发现真厉害%%%；用后缀差分(tg[i])记录下第i次操作和第i+1次操作的操作数之差，每次遇到2的操作时，令tg[l-1]减去当前操作数(其实很好算当前操作数，都是当前次数+tg...
2019-07-07 10:40:00
216
原创 矿大G毕业生的礼物(贪心)
思路：离散化，之后贪心选取最多的三个种类的物品(注意每次要一个个选，因为要保证每个阶段的选择都是最优的，如果一下子拿，就可能导致某个阶段的选择不是最有选择)；例：161 1 2 2 3 3 4 4 4 4 5 5 5 5 6 6ans=5;代码如下：/**/#define LOCAL#include<cstdio>#include<algorit...
2019-07-06 17:37:15
311
原创 uva1598(大模拟+优先队列)
思路：照着模拟就行坑点：一个订单可能会被删除多次，还有一个点。。。优先队列的top函数，返回的是一个copy。。。代码如下：/**/#define LOCAL#include<cstdio>#include<algorithm>#include<cstring>#include<iostream>#include<...
2019-07-06 13:14:54
309
原创 uva11134(贪心)
/*按照区间长度排序,长度一样按照l从小到大排序如此贪心，错误：反例：[1,1],[2,3],[3,4],[1,3]；因为有包含关系的区间，不能保证大区间尽量选择小区间外的点，从而使得小区间能选的点变少正确的贪心思路是：按r从小到大排序，一样按l从小到大排序，每次从左端点开始选，选出的点一定是对接下来区间影响最小的 因为接下来的区间都被当前区间包含,先满足大区间,小区间才能有更多机...
2019-05-30 16:08:20
636
原创 关于莫队算法时间复杂度的分析
这两天看了莫队，对于莫队算法感觉实现还是很简单的，但是时间复杂度的理解好像网上的文章都没有讲的太明白(也可能是我理解能力有问题Orz)；莫队的时间复杂度的贡献主要来自于L,R指针的移动：L跨块转移的次数O(sqrt(n)),跨块转移的总距离为O(n);即不跨块转移的次数为O(n-sqrt(n)),每次的查询的复杂度是O(sqrt(n));所以L的时间复杂度为O(n)+O(n-sqrt(n...
2019-05-20 16:19:33
2466
1
原创 天梯赛 冰岛人（LCA）
思路：按照长辈的名是孩子的姓这个关系建树，建完树以后求LCA，但是细节居多。坑点巨多TT代码如下：/* 坑点： 存在孩子以女的长辈名作为后缀，这种情况孩子跟长辈其实没有关系，wa第三个点儿子有可能出现在父亲前面,wa最后一个点 3scj smxx scjsdottirxxx xxsson10xx scj xxx xx(应该yes) */#include<io...
2019-04-02 15:54:27
505
原创 uva1149(贪心入门)
/*贪心的选最轻的物品i+最重的j，如果放不下就剩下的只能单独一个背包 证明:如果这种方法不是最优的则i有两种情况:1.单独一个包，那么可以把j跟它放一起,这样可以得到一个可能更优的解2.跟k(k<j)放一起,那么把j,k换位,交换后:k所在的船不会超重,因为原本放的是j；j所在的船也不会超重,因为贪心策略,所以能得到一个不比之前差的新解综上：该策略为最优策略 */#defi...
2019-03-22 15:37:39
307
原创 uva 11093(思维题+对取余的思考)
/*以1作为出发点,如果遇到一个z加油站，到z+1时油不够了，则从2...z都不是正确出发点证明： 设中间节点k(1<k<=z),1->k时的剩余量为t则t必定>=0;否则肯定不能从k-1->k;那么k->z的路途中有sum(p[k]+...+p[z-1])+t的油量，并且这个值<sum(q[k]+...+q[z-1])如果直接从k出发，则剩...
2019-03-20 20:56:42
218
原创 牛客训练赛40 A,C
。。。谨以此篇，纪念我的爆0(wa~~~~TT!!!)A:思路：想到了应该用dp做，想用数位。可是状态转移方程写不出。。。其实简单的。。。d[i][j][k](//表示当前为第i位,最后两个是j,k)=can[l][j][k]*d[i-1][l][j],(l遍历1,49);代码如下：/**/#define LOCAL#include<cstdio>#in...
2019-02-16 14:34:24
273
原创 牛客训练赛36 B题(dp滚动数组)
2019年第一次比赛，遭逢大败。。。都不忍心看自己的排名，第一题一直在想该怎么去优化。发现并不用，直接暴力过。。。心态炸了，第二题是dp题，一开始想到了增加维度以获得更多信息，还好死不死的用疲劳度作为第二维。。。结果数组变成400*81000那么大。。。一直在推状态转移方程还推不出来。。。看了题解恍然大悟。。。哎，在推不出状态转移方程的时候应该改变思路，想办法减小每一维的大小，这样就比较容易想到正...
2019-01-05 14:19:13
228
1
原创 牛客练习赛35 B(简单dp,ORZ)
思路：想明白了发现真的简单dp。。。我还是太菜了代码如下：/*果不其然。简单dp...是我菜，不是题目难做这题首先我没想到dp(哭晕)看了题解半天。一脸懵逼既然dp解那么先考虑最优解的结构特征先想只用一维表示,dp[i]:在i这个位置上得到的最多的方案数上面是不行的，因为dp[i]没有记录i位置上是什么元素，导致下一步无法转移(条件中说了，不能有超过连续A个元音,只用dp[i...
2018-12-30 16:45:30
164
原创 大二第一次比赛(zcmu校赛)
体会：记得比赛前一个晚上，看无双（因为是偶像发哥演的）看到了2点多，比赛那天9点起床，起来人还挺迷糊的；开始比赛的时候，我写了第一题，因为人傻没烦恼，正好避过了坑，一发ac，然后我们队伍（其实就2个人）我跟学长，分别看b，d；学长看题出错，导致一直没a，我那题是博弈，我真不会，也没找到规律，很难受；后来我帮学长看，学长帮我看， 我发现了他的，他博弈出了我的；2a期间一起写了个dp的题。...
2018-12-25 14:08:13
232
原创 poj3666(dp逻辑的重要性)
思路：不知道为啥中间有一段时间没搞清楚状态时怎么转移的，想了好久，不过最后还是想明白了。在想状态转移的时候一定要牢牢抓住状态，通过状态来思考如何转移；第一次提交得到了完美的TLE，因为复杂度是n^3(其实当时也想到了，不过抱着侥幸的心理提交了)；上网查了查题解，别的都是一样的，就在判断最小dp值时，每次都历遍造成了重复计算，优化一下，每次都记录最小值minn，那么后面一个直接跟minn比，就得到了...
2018-12-20 17:14:30
570
1
原创 uva10003(有点迷糊的思考)
思路：这题跟矩阵链乘的思路一样，所以还是很好考虑的，只是有一点需要加两个切割点；代码如下：/*求最优的切割顺序最优子结构：dp[i][j]从i刀到j刀的最优切割顺序子问题：哪一刀最后切,dp[i][k]+dp[k][j]|i<k<j证明：因为最后一刀切的所有情况都被历遍到了，必定包含了最优解*/#include<cstdio>#include<...
2018-12-19 19:35:59
197
原创 uva 1625(dp)
代码如下：/*最优子结构：dp[i][j](1...i,1...j)合并后的minsum子问题：dp[i][j-1],dp[i-1,j](合并最后一个字符是来自哪个字符串)证明：最优解的最后一个元素必定来自两个字符串的末尾，如果子问题不包含最优解，那么说明dp[i][j-1],dp[i-1][j]不是最优解（矛盾）具体实现：滚动数组记录dp[i][j],并且记录这个状态下每个字符的最...
2018-12-19 13:34:24
153
原创 uva11400(对dp的进一步思考)
思路：这次比之前想到的会多一些，不过还不够，具体过程在代码中代码如下：/*条件:高v的灯可以替换低v的灯 思路1：dp[i]表示(1->i)号灯泡经过替换后得到的mincost，dp[i+1]为min(i替换成i+1...i+n)+dp[i];错误！ 因为该子结构不具有子问题独立性：之前的灯泡替换成之后的灯泡，那么对之后的灯泡能否替换就将产生影响思路2：(对上面的思路进行限...
2018-12-15 17:26:22
309
原创 牛客练习赛34C(对用差分进行区间更新的理解)
思路：这题我一开始想到了用前缀和来直接计算查询的区间中1的个数（即：失去这个线段后会不覆盖的点数），但是不知道怎么快速更新这个点被几个线段覆盖过。看了题解恍然大悟！用差分；差分记录的是每个元素跟前一个元素的差值，也是增量，那么区间更新[l.r]+x时，l的位置上的数与前一个数的差值大了x，r+1上的数小了x。。。求i位置上的值，就i位置的前缀和；代码如下：#include<bi...
2018-12-15 12:50:35
186
原创 uva12563(对于状态的理解)
思路：这题有两种状态都可以，具体的在代码中有写代码如下：/*其实这题的意思就是求在t时间内，选尽量多的歌曲最优子结构：在j时刻，能从i首歌中选择的最多歌曲数(注意这里是j时刻，不是<=j时刻)(因为是j时刻，所以答案，要判断每个时刻的能选择的最多歌曲数)证明：子问题是在j时刻从i-1首歌中选最多的歌曲数+【选这首歌(dp[i-1][j-num[i]]+1)，或者不选这首歌(...
2018-12-14 14:01:10
357
原创 uva 437(不用记忆化搜索解)
思路：放代码上了代码如下：/*最优解是max height最优子结构是以i方块作为最后一块的最大长度子问题的最优解是以前1，2，3...i-1个方块作为最后一块的最大长度显然：最优子结构包含了子问题的最优解 并且这些子问题的解之间相互独立(其中一个问题的解，不会影响另外一个)重叠子问题：每次都不用再计算子问题的解，因为这些解都已经保存在了表中 综上：用dp[i]保存以...
2018-12-10 17:04:33
226
2
原创 hdu1074(状压dp)
思路：先说什么是状压dp（一开始我也不知道，但是做了一次之后发现还挺简单的），一句话概括就是一种很暴力的dp方式；核心思想是：枚举所有的情况，用二进制记录状态这道题其实只要枚举所有状态，并且是根据前面的状态推导得到，如：用（111）表示三门课都完成，则这个状态有可能是从(110),(101),(011)这三种状态推出;代码如下：#include<cstdio>...
2018-12-03 18:58:06
320
原创 线段树位运算区间更新(牛客东信杯j题)
思路：其实就是区间更新的时候，不是加减数了，而是用或运算，具体看代码#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>using namespace std;typedef long long LL;const int maxn = 2...
2018-11-25 20:01:12
442
原创 牛客小白赛9A(求逆元)
思路：就是求个逆元会求了，这题也就会做了。代码如下：#include<cstdio>#define ll long longconst ll mod=1e9+7;ll quick_pow(ll a,ll b){ ll ans=1; while(b) { if(b&1) { ans=ans*a%mod; } a=a*a%mod; ...
2018-11-18 14:52:20
181
原创 poj3468(线段树区间查询+区间更新)
思路：很明显的线段树模板题，区间查询+区间更新但是小弟比较菜，并不会线段树，所以现学了一波，别的还是好理解的，就是lazy标记我觉得很难理解（应该是因为我比较菜），所以请教了大佬，大佬告诉我：lazy标记就是在访问这个节点时，并且要访问子节点时，向下传递lazy标记，以减少时间；访问操作包含了（查询与更新）；代码如下：#include<cstdio>#include&l...
2018-11-17 15:55:26
182
原创 最短路算法优化（dijkstra算法+邻接表+队列优化，bellman算法+邻接表+队列优化）
dijkstra算法+邻接表+队列优化（poj1511）：#include<iostream>#include<algorithm>#include<vector>#include<queue>#include<map>#include<string>#include<stdio.h>#defi
2018-11-03 14:13:34
310
原创 最短路（Floyd算法，Dijkstra算法，Belleman算法）
Floyd算法： 在两点之间插入节点，如果插入后能减少两点间的距离，则更新距离； 模板如下：void Floyd(){ for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) e[i][j]=min(e[i][k]+e[k]...
2018-10-30 15:31:02
326
原创 dancing links (精确覆盖+重复覆盖）
精确覆盖模板：(解决的问题是在01矩阵中选出最少的行，另每一列都有且只有一个1）#include <iostream>#include <stdio.h>#include <string.h>#include <iostream>using namespace std;const int MN = 1005;//最多的行数 cons...
2018-10-19 10:29:03
554
原创 hdu 1560 DNA sequence(IDDFS)
思路:IDDFS是每次按照限制的深度进行搜索，如果在k深度没有找到解，则进行k+1深度的搜索；这题的做法就是按照从max_size的深度开始增加深度，如果找到解直接return;代码如下：#include <iostream>#include <string>#include <vector>#include <set>#inc...
2018-09-29 15:05:59
123
原创 hdu 3567 EightⅡ（映射+bfs暴力打表）
思路：跟hdu 1043 其实差不多，只是最后的状态变成了非唯一情况；我们要做的就是把最后的状态变成唯一的或者唯几的情况；看了网上大佬的思路之后发现，不管最后的状态怎么变化，都可以映射成9种，也就是X放在其中的9个位置，然后按照映射关系把起始状态也映射一下，最后两个映射的达到路径跟要求的路径其实是一样的（虽然不知道为什么，但是事实如此）；因为有9种情况，那么就有9张表分别代表到达9个末位置...
2018-09-28 13:56:39
418
原创 hdu 1043 eight (bfs暴力打表+康托展开)
思路：1.首先要知道什么是康托展开，不会的自行百度吧，其实我个人感觉就是一种映射关系，将一种排列方式映射成一个数2.bfs打表得到到达每个点的路径，然后一直找点的父节点就行；代码如下：#include <iostream>#include <string>#include <vector>#include <set>#inc...
2018-09-27 17:09:37
211
原创 poj 3414 pots（bfs暴力+路径记录）
思路：这可真是我目前写过最长的题目了，虽然很多可以复制（学艺不精T-T）。。。其实思路还是很简单的，就是6种情况，各种倒来倒去，然后记录下路径，我的方法是用一张图来表示，有没有走到过，然后图上每个位置都存着父节点的位置，以及父节点怎么达到，如果找到了逆序输出，如果没找到impossible，具体的看代码吧；代码如下：#include <iostream>#include...
2018-09-24 14:54:39
179
原创 poj 3279 fliptile (翻转棋盘，枚举方法)
思路：翻转偶数次跟翻转0次是一样的，奇数次是跟1次是一样的，所以最后的结果中只可能有0，1；下一行的状态可以通过前二行的的状态得到，因为在求（i，j）是否要翻转的时候，(i-1,j)(i-1,j-1)(i-1,j+1)(i-2)(j)是否翻转都已经知道了，并且要(i-1,j)这个位置是0，那么就可以推出(i,j)这个位置是否要翻转，所以其实问题中只要枚举第一行的所有情况，就能推出所有的情况...
2018-09-22 16:15:49
1389
原创 poj 2251 三维迷宫（惨痛的bfs）
思路：正常的bfs，但是有坑代码如下：#include <iostream>#include <string>#include <vector>#include <set>#include <cstring>#include <climits>#include <algorithm>#inc
2018-09-21 17:08:27
669
原创 poj 1321 棋盘问题（八皇后变形）
思路：一开始直接暴力dfs，然后被t； 其实这题一个小改动就行了，用两个数组记录这行这列有没有放过棋子，这样就不用每次都进行判断了代码如下：#include <iostream>#include <string>#include <vector>#include <set>#include <cstring...
2018-09-21 15:56:36
240
原创 洛谷oj 1024 一元三次方程（二分）
思路：历遍-100~~~100每次递增1，因为题目说每个根起码相隔1；然后如果f(x)*f(x+1)<0说明x到x+1上存在着一个根，然后二分这个区间，需要主要的是，上下界，如果f(l)*f(m)<0说明上届还可以变小，所以r=mid代码如下：#include <iostream>#include <string>#include <vect...
2018-09-20 13:47:29
312
原创 hdu 1087 Super Jumping!（dp）
思路：动态规划的三个原则是：1.子问题重叠性2.无后效性3.子结构最优性如果这题把dp[i]当成前i个数的最长上升子序列的话，那第i+1个数会影响前i个数的选择，比如 5 6 1 2 3；第i+1个数加上去不一定使得和前i个数加起来就是最长子序列所以正确选择子问题的方法是：dp[i]代表以第i个元素结尾的最大上升子序列；代码如下：#include <iostream>...
2018-09-20 12:28:22
84
原创 hzau Little Red Riding Hood （入门级dp）
思路：很明显的dp，dp[i]代表在i鲜花处得到的最大值，那么久两种情况，i鲜花拿，i鲜花不拿拿：dp[i]=dp[i-k-1]+a[i] 因为如果拿了，那么前k朵都凋谢了，也就是要前第k+1朵才能采;不拿：dp[i]=dp[i-1] 不拿值跟前一个朵的值一样所以dp的动态转移方程就是dp[i]=max(dp[i-k-1]+a[i],dp[i-1]);代码如下：...
2018-09-18 11:16:53
194
原创 迷宫问题（bfs+路径记录）
思路：正常bfs搜索，然后记录每个点的父节点，最后找父节点，最后输出路径；代码如下：#include <iostream>#include <string>#include <vector>#include <set>#include <cstring>#include <climits>#include...
2018-09-14 13:56:36
4324
原创 hdu 2159 FATE（二维完全背包）
思路：观察题目，有两个约束条件，要在耐心的范围内，而且不能超过杀怪数；所以简单的一维背包问题解决不了。要用二维的完全背包来做；二维完全背包就是在有两个代价c1,c2的时候，求在这种状态下的最大收益；类比一维的完全背包：dp[j]=max(dp[j],dp[j-w[i]]+v[i]);j正序历遍二维的完全背包,只是多了一个维度:dp[j][k]=max(dp[j][k],dp[j-c1[...
2018-09-11 15:56:20
140
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人