曾任职于阿里巴巴,现就职于美图,专业搬砖100年~
暂时未有相关通用技术能力~
阿里云技能认证
详细说明点击打开链接uva 536 思路: 二叉树 分析: 1 题目给定前序序列和中序序列,要求二叉树的后序序列 2 建好二叉树之和直接遍历输出即可,裸题 代码: #include #include #include #include usi...
点击打开链接uva 548 思路: 二叉树 分析: 1 题目给定一棵二叉树的中序序列和后序序列求这个二叉树里面,根节点到叶子节点的最短路径的叶子节点的值,如果有多条路径输出最小的叶子节点 2 题目说最多有10000个节点,但是由于题目所说...
点击打开链接uva 11988 思路: deque模拟 分析: 1 题目给定一个字符串要求通过一序列的模拟输出最后的字符串 2 根据题目的意思[],分别表示的是键盘上的home和end键,home键的作用是跳到起始位置,end的作用是到最后一个位置。
点击打开链接uva 1329 思路: 带权并查集 分析: 1 看懂题目就是切菜了 代码: #include #include #include #include using namespace std; const int MAXN...
点击打开链接uva 1160 思路: 并查集 分析: 1 看懂题目之和就是切菜了 代码: #include #include #include #include using namespace std; const int MAXN...
点击打开链接uva 1203 思路: 优先队列 分析: 1 题目要求前k个事件的编号,我们利用优先队列来维护即可 2 优先队列保存的是一个struct,因此我们需要重载 s.
hdu 4602 点击打开链接hdu4602 思路: 数学 分析: 我们可以特判出 n = 1; m = (m*m)%mod; } return ans%mod; } ll getAns(){ ...
点击打开链接uva 11991 思路: STL 分析: 1 题目要求的是第k个v的下标 2 题目的规模是10^6如果用暴力的话那么超时是肯定的,所以这里应该考虑用vector数组,每一个值作为一个vector,,然后把这个值出现在第几个位...
点击打开链接uva 11995 思路: STL模拟 分析: 1 分别用三种STL去模拟这些操作,然后进行判断输出 2 比较简单 代码: #include #include #include #include #include #i...
思路: 完全背包 分析: 1 有n种战舰和敌人的总的血量L,每一种战舰的创建时间为ti,每秒钟对敌人的伤害的血量为li 2 当敌人的血量为0的时候玩家赢了,求玩家最少的时间赢了游戏 3 这边如果我们用血量去做背包dp[j]表示伤害血量为j...
思路: 多重背包 分析: 1 题目给定的数据明显就是多重背包,但是题目有个难点就是输出路径,0/1背包里面有输出路经的方法,做法做法是通过记录前面的状态 2 这一题还要求输出每种硬币的个数,那么这边利用mark数组,mark[i][0] ...
闲来无事,制定个不可能完成的计划来玩玩吧 考试结束7.3 1 7.
点击打开链接hdu 1963 思路: 完全背包 分析: 1 根据题目很容易分析出题目是裸的完全背包,但是经过题目的条件我们发现dp数组开不下(怒RE不解释) 2 然后发现题目说了所有的bonds的value都是1000的整数倍,因此这边我...
点击打开链接poj 3181 思路: 完全背包+高精度 分析: 1 题目是裸的完全背包,但是要注意的一个地方是要用高精度 代码: #include #include #include #include using namespa...
点击打开链接hdu1114 思路: 裸完全背包 代码: #include #include #include #include using namespace std; const int INF = 0x3f3f3f3f; cons...
点击打开链接uva 147 思路: 完全背包 分析: 1 很明显裸的完全背包,注意一个地方就是输入的值不一定是小数点只有2位,这边我们应该分成两部分输入,最后注意输出即可 代码: #include #include #inclu...
点击打开链接uva 674 思路: 完全背包 分析: 裸题 代码: #include #include #include #include using namespace std; const int MAXN = 8000; ...
点击打开链接hdu2126 思路: 二维0/1背包 分析: 1 题目给定n个物品的价钱和m的钱,问最多能买到的物品数有几种方案。 2 很明显就可以写出状态转移方程dp[i][j][k]表示的是前i个物品选j个总价钱为k的方案数 那么dp[i][j][k] = dp[i-1][j][k]+dp[i-1][j-1][k-v[i]]。
点击打开链接poj 1948 思路: 二维0/1背包 分析: 1 题目要求从n个木棒里面选出m个组成一个三角形,使得三角形的面积最大 2 对于三角形来说知道了两条边和周长就可以求面积,按照0/1背包的思想dp[i][j][k]表示前i个木棒能否组成第一条边为长度j,第二条长度为k。
点击打开链接poj 1976 思路: 0/1背包 分析: 1 题目给定n个数,要求三段连续的m个数之和最大 2 假设n个数是num[1],num[2],num[3].
点击打开链接poj 1745 思路: dp 分析: 1 又是一道看了题解还不懂怎么个回事的题,然后各种YY之后有点感觉 2 题目要求的是在n个数中间插入n-1个的+或-使得结果能否被k整除 3 看一个数学的公式(a+b)%k = a%k...
点击打开链接poj 3211 思路: 0/1背包 分析: 1 题目要求洗完n件衣服所需的最少的时间,并且必须洗完一种颜色才能跳到下一种 2 仔细想想这一题和uva上面的一道分金币非常的相似,由于要求必须洗完一种颜色才能跳到下一种,那么我们...
点击打开链接poj 2642 思路: 0/1背包 分析: 1 题目给定n个物品,并且每个物品只有两种的选择很明显就是0/1背包的特性。 2 题目给定c个客户的要求,每一个客户都要求最后金子的平均浓度在min~max这个区间,并且每个客户要...
点击打开链接hdu 3466 思路: 0/1背包 分析: 1 这一题和"hdu2546 饭卡"有点像,但是又有不同,不同的是这一题每一个物品都有一个限制的值Q[i],求最大的价值 2 题目明确提到每一种物品只能卖一次或这不卖,那这明显就是0/1的性质,但是现在多了一个条件钱不能少于Q[i]。
点击打开链接hdu 2639 思路: 0/1背包求第k优解 分析: 1 其基本思想是,将每个状态都表示成有序队列,将状态转移方程中的 max/min 转 化成有序队列的合并。
点击打开链接hdu 2955 思路: 0/1背包 分析: 1 按照题目的意思我们很容易知道这就是一个0/1背包问题,如果我们把概率当作是背包的容量,那么我们遇到一个问题就是浮点数的dp,因为题目没有告诉我们小数点具体几位,那么我们就不能够通...
点击打开链接hdu 2546 思路: 贪心+0/1背包 分析: 1 题目中收到只有当余额大于等以5的时候才可以买东西,那么我们利用m-5去买这样保证了于额不会小于5,那么这样就可以买东西了,因为最后可能还有点于额(为0)的时候也是可以买的,那么最后一次就买最贵的这样保证于额最少了。
点击打开链接hdu 2602 思路: 裸0/1背包 代码: #include #include #include #include using namespace std; const int N = 1010; const int MA...
点击打开链接uva 562 思路: 0/1背包 分析: 1 题目意思是有两个人分n个金币,要求最后两个人的金币差值最小 2 我们利用背包的思想即背包的总容量为金币总和的一半,去求出可以放入背包的最大的金币(这里其实就是某一个人能获得的最大...
点击打开链接uva 624 思路: 0/1背包 分析: 1 题目要求的是最大的时间,并且输出选择所选的磁带 2 要求最大的时间很容易,关键是怎么求所选的磁带。
点击打开链接poj 3628 思路: 0/1背包 分析: 1 题目抽象出来的话就是0/1背包 2 我们用dp[i][j]表示前i头牛放在高度为j的最小高度,那么我们只要求出 dp[n][B~s]中的最小值,然后减去B即可 代码: ...
点击打开链接 思路: dp 分析: 1 题目要求找到两条不同的路线使得和最大,那么我们可以换种思路就是看成是都是从(1,1)这个点出发的两条路线并且不相交,最后到达(n , m)这个点的和最大 2 题目说了从左上角往右下角传递的时候只能向...
点击打开链接 思路: 动态规划 分析: 1 题目要求找到最大的美学值,并且要求标识号大的必须在标识号小的右边,那么这就可以知道,如果花朵i在第i行的第j列那么第i+1朵必须在j+1后面 2 很明显的阶段就出来了,我们用dp[i][j]表示...
点击打开链接 思路: 线性动态规划 分析: 1 题目要求两个字符串的最小距离 2 假设dp[i][j]表示字符串1前i个字符和字符串2的前j个字符的最小距离,那么我们很容易知道。
点击打开链接 思路: 0/1背包 分析: 1 从题目可以知道本题肯定是0/1背包的变形,我们仔细分析不然发现其实这一题和普通的0/1背包的区别就是状态不同了 2 我们设dp[i][j]表示前i题用了j的时间,那么对于第i题来说就有三种情况...
点击打开链接 裸0/1背包 #include #include #include #include using namespace std; const int MAXN = 15000; int n , m; int w[MAXN]...
点击打开链接 思路: 最长上升子序列 分析: 1 题目要求最少的出队的人数,那么就是要求一个i使得满足的人数最多 2 很明显如果我们单独看i这个人,那么他就是中间点左边满足递增,右边满足递减。
点击打开链接 思路: 区间dp 分析: 1 很多人可能看到这一题首先想到的是贪心,但是很不幸的是这道题的贪心做法是错误的,因此正解是dp 2 不管怎么合并,总之最后总会归结为2堆,如果我们把最后的两堆分开,左边和右边无论怎么合并都必须满足最优合并方案,整个问题才能是最优的 3 题目是一个环,我们可以把环变成链那就是在后面在加上去,那么最后的ans一定是dp[1][n-1],dp[2][n]...中的最小值和最大值 4 我们dpMin[i][j]表示合并第i堆到第j堆石子所得的最小分数,dpMax[i][j]表示最大分数。
点击打开链接 思路:0/1背包 分析: 1 很明显的0/1背包 代码: // 一维 #include #include #include #include using namespace std; const int N = ...
1 题目标题:高斯日记(4分) 大数学家高斯有个好习惯:无论如何都要记日记。
点击打开链接cf 182 A /* 题目的真正意思是问能否由r-l+1个数组成和为0 */ #include #include #include #include using namespace std; const int MAXN ...
点击打开链接poj2377 思路: 并查集+排序+欧拉道路 分析: 1 题目要求的是,是否可以组成欧拉道路并且输出字典序最小的方案 2 和别的题目不一样的是这一题的输出是最小的字典序,所以这里面是一个难点,那么我们应该怎么做呢?其实我们只要对输入的n个单词进行从小到达排序即可 3 然后我们先去判断该有向图是否是单连通的 4 我们去判断是否最多只有两个点的入度不等与出度,其余所有点的出度等于入度 5 如果都满足的话,进行dfs。
点击打开链接poj2513 思路: hash+并查集+欧拉路 分析: 1 题目要求给定n个木棒是否可以组成一个满足要求的字符串 2 很明显的判断无向图是否是半欧拉图,首先先判断是否是单连通这一点可以利用并查集,然后在去判断是不是最多两个点...
点击打开链接hdu1116 思路: 欧拉回路 分析: 1 题目给定n个字符串,判断是否可以按照题目的要求可以组成一个长串 2 很明显题目是要求有向图是否有欧拉回路或者是欧拉道路 3 首先我们先判断有向图是否是单连通,那么这里面我们可以...
点击打开链接hdu 3018 题意: 给定一个n个点m条边的无向图求有几条欧拉道路或者欧拉回路 思路: 欧拉回路 分析: 1 给定一个图判断欧拉道路的条数,那么对于一个图有n个连通分支来说那么至少有n条欧拉道路或者欧拉回路 2 那么我们...
点击打开链接hdu 1878 思路: 欧拉回路 分析: 1 首先题目给定的是一个无向图,所以我们判断该图是欧拉图的条件是图是否是连通的并且所有点的度都是偶数 2 很明显度数很好判断,而图是否连通通过并查集 代码: #include...
点击打开链接uva 10054 思路: 欧拉回路 分析: 1 对于一个无向图来说如果这个图是一个欧拉图,那么必须满足该图是连通的并且每个点的度数都是偶数 2 题目给定n条边的无向图问我们是否是一个欧拉图,是的话输出欧拉图的一条路径 3 ...
点击打开链接uva 1394 思路: 数学递推 分析: 1 题目是一道变形的约瑟夫环变形问题 2 网上看到一篇很好的数学递推法 问题描述:n个人(编号0~(n-1)),从0开始报数,报到(m-1)的退出,剩下的人继续从0开始报数。
点击打开链接hdu 4424 题意: 有n个点n-1条边,现在规定i-j的路的最大负载量为i到j所经过的所有边的最小值,要求以某个点为中心然后求出这个中心点到所有点的负载量之和最大 思路: 并查集 分析: 1 n个点n-1条边很明显给...
点击打开链接 A #include #include #include #include using namespace std; char str[3][3]; bool isOk(){ for(int i = 0 ; ...