clearove__0520

分类

未归档(1) 题解(14)

/ 注册

全部文章（共15篇）

balalala

刚开始做这个题目以为是贪心？？？唉，一直没思路，后来看了题解，原来是二分。。。。我们假设第x天为当前最优解,小于x的都不是最优解，如果小于x的话那么就会与当前得到的最优解矛盾，如果冲突的话我们应该更新当前最小值，大于x的都不是最优解，符合二分的条件------具有某种神秘性质（单调性）。长到第x天的...

2020-05-09

0 593

排序

快速排序模板 void quick_sort(int q[],int l,int r) { if(l>=r)return; int i = l - 1, j = r + 1,x=q[l + r >> 1]; while(i < j) { ...

2020-04-13

0 518

复习位运算

for(int i = 1;i<1<<20;i++) { for(int j = 0 ;j < n ;j++) { if(i>>j&1){ for(int k ...

2020-04-13

0 482

DP计数问题

背包dp问题 dp[i][j] 是在前i个背包内选择价值j的方案数状态转移方程是dp[i][j] += dp[i - 1 ][j - a[i][j]]dp[0][0] = 1 代表的意义是在前 0 个背包价值为 0的方案数是1 #include <iostream> #include ...

2020-04-11

1 720

每日一题

自己看的别人的题解才看懂的！#*这个题的题意是让我们把一颗树，分为两个部分，每个部分内部之间的路权值最小。首先我们来看任一个节点，如果这个节点下面的子树(包含当前节点)是奇数的话，那么我们就应该把这个节点与他的父节点之间的边连接，因为我们如果不添加的话，我们这颗子树下面必然要有一个匹配不成功。比如我...

2020-04-04

0 490

每日一题

第一眼看见这个题以为是KMP问题，后来发现自己错了，子串和子序列不同！#……&（）……#相比于KMP问题有很多相似之处，如果我们用一个一个比较字符的话，时间复杂度是N * N我们用一个 ne 数组来记录位置关系， ne[i][j]代表在第 i 个字符下一个 i + 1 字符最近的位置，...

2020-04-03

0 539

每日一题

从题目来看这就是个树啊从题目来看这就是个树啊从题目来看这就是个树啊我真的好菜。。。看的好多人的题解才会&%！&%￥#……&度为1的节点就是叶子节点度为1的节点就是叶子节点度为1的节点就是叶子节点首先我们从 s 出发，那么我们不能让叶子节点走到 s 的话，我们现在有两种选择，设...

2020-04-02

0 563

括号模拟

首先在这里检讨下自己，今天实在是好堕落啊@……%……&~判断括号是否匹配成功，肯定要用到栈这个数据结构，当我们匹配到 c 字符时，我们判断和栈顶元素是否匹配，如果匹配的话，我们就把这个栈顶元素删掉，当栈顶元素不匹配时我们让 c 字符进栈。 if(stk.size())res = max(r...

2020-04-02

0 662

哈夫曼树

对于任意的 1≤i,j≤n，i≠j，都有：si 不是 sj 的前缀这就是说要用到哈夫曼树题目还要保证最长的字符串长度最小，那么如果现在有两个权值相同的节点，我们应该优先选择深度较小的节点，因为我们如果选择了深度大的节点那么这个树的深度就会变长，我们选中深度较小的节点，那么我们深度较大的节点会在后面...

2020-04-01

0 562

树上倍增问题

原图是这样的当我们输入 4 2 1 时我们就是要找从4 到 2 比 1 大的节点数，我们可以转换成这样的树，红色代表我们新加入的节点，显而易见，4号节点比 1大， 2号节点比 1大答案为2 那我们就可以转换为把要查询的路径用这样的方式插入，实力太弱的我还是对数据结构掌握不好。~~我们用f[...

2020-04-01

1 675