蒟蒟独行

贪心

01分数规划(1) AC自动机(2) bbp(1) cf(8) dp(35) FFT(4) fleury(1) floyd(1) k-d树(1) kmp(1) kruskal重构树(1) lca(4) main(1) manacher(2) markdown(1) st表(1) trie(1) 一中(4) 主席树(1) 二分(2) 前缀和(1) 单调队列(1) 博弈论(3) 卡常(1) 双联通分量(5) 图论(1) 左偏树(1) 并查集(1) 强联通(2) 思维(11) 感想(6) 扫描线(1) 找规律(1) 技巧(1) 拓扑排序(2) 搜索(7) 数位dp(3) 数学(25) 斜率优化dp(1) 暴力(1) 最小树形图(1) 最短路(2) 未归档(1) 杂(15) 树(5) 树套树(2) 树形dp(4) 树状数组(5) 概率dp(1) 模拟(14) 模拟赛(2) 模板(30) 欧拉函数(1) 点分治(1) 状压dp(1) 生成树计数(1) 离散化(1) 算法复习(14) 线段树(20) 线段树合并(1) 网络流(2) 置换群(1) 虚树(1) 计算几何(1) 轮廓线dp(1) 高斯消元(1) 高精度(2)

/ 注册

全部文章 / 贪心（共12篇）

bzoj1217: [HNOI2003]消防局的设立

题目题解：贪心。因为每个点都要被覆盖，所以每次取最深的一个点k，取t为k的爷爷，然后覆盖所有与t距离为1、2的点标程： #include<bits/stdc++.h> using namespace std; int n,i,j,k,mx,p,t,fa[1003],x,de...

2020-01-21

0 524

51nod1125 交换机器的最小代价

题目题解标程： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=50003; struct kk{ int x,id; }a[N]; ll ans,mn; in...

2020-01-21

0 473

51nod1328 比赛往事

题目题解 #include<bits/stdc++.h> using namespace std; const int N=1002; int P[N],C[N],c[N],p[N],cnt,cnt1,x,y,tag,i,n,tmp; void ins(int *A,int k,i...

2020-01-21

0 418

51nod 1380 夹克老爷的逢三抽一

题目题解设最大值为b，左边为a，右边为c 解释一下为什么要把a+c-b放回去因为b不一定是最优的，说不定a、c和b差不多大，同时选a、c可能比b更优，把a+c-b放回去，若再次取出，则相当于用两次选了a和c，满足题意，也满足贪心 #include<bits/stdc++.h...

2020-01-21

0 454

51nod 1299 监狱逃离

题目题解按我的理解对题解改了一些 Description 给出一个n+1个点n条边的树，其中每一个度数为1的点为出口。现在有一些点有逃犯，你需要在一些没有逃犯的点放置警卫，有警卫的点逃犯无法经过。求若使所有逃犯均无法到达出口，最少需要多少个警卫。 n<=10^5 Sol...

2020-01-21

0 483

bzoj2525: [Poi2011]Dynamite

题目思路出处感觉这题就是消防局的设立+ n n 开大 300 300 倍+距离为任意数+二分答案显然，这题就是二分答案后，把当前最深的点向上 now ...

2020-01-21

0 426

51nod1385 凑数字

题目题解 Solution 这个题，其实就是和数位 dp 相似，分为满状态和非满状态来考虑，什么叫满状态呢？就拿 21 21 来说吧，当最高位为 0 0 、 ...

2020-01-21

0 332

Codeforces 1042F. Leaf Sets

题目题解 Solution 把子树拆成几条链，每次合并短的几条链 Code #include<bits/stdc++.h> using namespace std; const int N=1000001; struct node{ int to,ne; }e[N<&l...

2020-01-21

0 441

poj1456 Supermarket

题目每次尽可能选大的，不知道怎么证正确性，但感觉是对的 #include<cstdio> #include<algorithm> using namespace std; const int N=10002; int n,i,pos,fa[N],ans; struct n...

2020-01-21

0 408

51nod 2206 低买高卖&codeforces867E Buy Low Sell High

题目 Solution 用堆保存最小值，遇到大于堆顶的元素就把ans加上差值，然后这个元素入队两次，入队两次是为了有一次“后悔”的机会，也就是先选着，遇到更好的就替换掉 Code #include<bits/stdc++.h> using namespace std; int i...

2020-01-21

0 543