Greedy & Violent

贪心可不是件简单事儿.

有趣的贪心

依据与思想

  1. 贪心既然是一个方向的dp,往往相邻交换法可以得到优先级
  2. 真正不要脑洞的贪心还是很少的(比如例题11,UVA11520) ​ 贪心法是每步选择局部最优解,然后一步一步向目标迈进。这个“目标”两字很关键,说明贪心法是目标导向的,每一步的方向一定是目标。那么我上面两种方法其实只是在模仿那个经典问题的模式,但是却没有时刻注意到这个问题最终目标是实现从1到n每一位都能放上满足条件的车,比如第二个反例最后一个格最后都无法放车了,就是因为前面没有按照对最终目标的影响效果去选择局部最优解,单纯的选最左边一个是毫无道理的,因为本题已经不是那个经典的选最少点的问题了。(UVA11134题解摘录)

热身训练

sort大法好==.

  1. HEllo World (2 ^ ans > n)
  2. CF363A最小碰撞时间
  3. Building designing sort两个指针扫
  4. Ancient Cipher sort计数
  5. DNA Consensus String 枚举
  6. Big Chocolate 找规律==
  7. All in All 两个指针扫
  8. Children’s Game(UVA10905) 字符串最大==sort by a + b > b + a
  9. UVA11389 给出两个数组,使得搭配后所有超出S的值 超出部分和最小
  10. 例题1 UVA11292 勇者斗恶龙,两个指针往后扫 加上这两句话(if)才能过??? 1 2if(n) sort(dg, dg + n); if(m) sort(hero, hero + m);
    • 进阶 LA3266 田忌赛马
    • (这个我CSDN博客有详细题解==
    • 当初放弃ACM Steps题目..现在看来脸皮厚多了)
  11. UVA11100 (进阶)个数尽量少严格递增…等差(距)数列
  12. LA4094(进阶) 梦之队 这道题网上题解分析很贪心hhh
  13. LA4636(进阶) 给出主视图和左视图,求最小立体…(每次找max,相等加到ans,不相等舍弃大的那个)
  14. LA3303 相邻交换法 a1b2 < a2b1
  15. LA2757 从后向前

区间问题

最早完成

  1. 例题2 UVA11729 Bi时间交代任务,Ji时间完成. ==> (交换法证明)完成时间长的先交代
  2. 例题10 UVA11384 用最少次数全部变成0 =>> 保持平衡 ,每次把大的一半减去(n/2)+1 递归/二分(每次减大的数的一半)

最少区间选择

  1. UVA10382 sort by zuo when equal by you

最多区间选点

  1. UVA11134 二维的..等价于两个一维,紫书P237
  2. Priest John’s Busiest Day 至少出席区间一半时间 因为左右等价,sort by middle

最小惩罚

  1. LA4850 求两个最大惩罚之和,end排序贪心扫一遍后,枚举 做法一: 枚举一个任务以及调动位置 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38struct seg { int f,e; bool operator<(const seg & b)const{ return e < b.e; } }cs[500 + 5]; /* in main sort(cs, cs + n); > int ans = gao(-1,10000,n); > for(int i = 0;i < n;i++)//枚举一个任务调动 > for(int j = 0;j < n;j++)//枚举调动位置 > ans = min(ans,gao(i,j,n)); > printf("%d\n", ans); */ int gao(int cur,int to,int n) { int sum = 0, cnt = 0; int max1 = 0,max2 = 0; for(int i = 0; i <= n; i++) { if(cnt == to) { sum += cs[cur].f; max2 = max(max2,sum - cs[cur].e); if(max2 > max1) swap(max2,max1); }//调动位置 if(i != cur && i < n) { sum += cs[i].f; max2 = max(max2,sum - cs[i].e); if(max2 > max1) swap(max1,max2); cnt++; }//未调动位置 } return max1 + max2; }

剪枝

牺牲的任务只能在两个最大惩罚值中的最后一个任务的前面,只有牺牲前面的任务才能使最大惩罚值的值减小,注意这里是牺牲,就表示有可能牺牲这个任务后,该任务的惩罚值变成了最大惩罚值的其中一个。

方法2 二分套二分

半边界

优先队列维护

  • LA3507 知道DDL和花费,用优先队列维护最优值 1 2 3 4 5 6 7 8 9int ans = 0; for (int i = 0; i < n; i++) { ans += af[i].q; dd.push(af[i].q); while (ans > af[i].d) { ans -= dd.top(); dd.pop(); } } ​

路径最小

  1. 例题3 UVA11300 所有人转手金币之和最小
    1. (少一个方程的线性方程组=>)单变量极值不等式
    2. 数轴上一串点距离和,中位数是极小值点.
  2. 例题4 LA3708 加入m个雕塑到n个等距中,求最小移动距离
    1. 变换坐标系为len = 1;
    2. tot最小,一定移动到最接近的位置
    3. 随机选一个坐标原点不动

    1 2 3//坐标缩小后就可以更方便的选择 double pos = (double)i / n * (n + m);//原来雕像的位置 ans += fabs(pos - floor(pos + 0.5))/(n + m);//*n+m后就选四舍五入最近的

相对不变问题

  1. 例题5 UVA10881 蚂蚁爬.求每个蚂蚁最后的位置和方向 每个蚂蚁的相对顺序不会改变=>记录id,最后对应回去 1 2 3 4sort(before, before + n); for (int i = 0; i < n; i++) { order[before[i].id] = i; }// 之后i := 0->n, a = order[i]就是从小到大的顺上去

树形贪心

  1. 例题15 LA3902 每个叶节点不超过k有个站 求站的最小数 ​ 每次取最深的 通过node表flood fill. (node[dis]表示深度为dis的叶子)) ​ 1 2 3for(int i = 0;i < k;i++) v = fa[v];//第k级祖先 if (e[u].size() == 1 && d > k) node[d].push_back(u);//node表构建
  2. CF363c 完全二叉树..每次找最近公共祖先还是很简单的==

左右互搏法

  1. 例题16 LA3177

围成一个圈每个人拿r[i]个礼物,相邻不相同

  1. n == 1,特殊情况总共r[1]个
  2. ​n % 2 == 0 => max(r[i] + r[i+1])个
  3. n % 2 == 1
    1. 二分答案
    2. 以r[1]为界限循环一圈,(除了第一个)奇数尽量拿右边的,偶数尽量拿左边的,
    3. (因为第一个和最后一个都是奇数位)看最后一个是否会拿左边的.

123456789101112131415161718

bool check(int p){ int x = a[1], y = p - a[1];//bound left[1] = x,right[1] = 0; for (int i = 2; i <= n; i++) { if (i & 1) { right[i] = min(a[i],y - right[i-1]);//奇数尽量拿右边的 left[i] = a[i] - right[i]; } else { left[i] = min(a[i], x - left[i-1]);//偶数尽量拿左边的 right[i] = a[i] - left[i]; } } return left[n] == 0;}

  • UVA11627(数据有毒) 过障碍维护当前最左和最右
  • LA4725 两个飞机一个入口,问最小编码..维护当前飞机,ab能飞和tot能飞 维护当前机场的飞机数目,机场可以供起飞的数目还有可以起飞的总数。 超过数目后,判断可供起飞的数目是否为0就行了。 其实也就是因为a起飞数和b起飞数不是完全相干的 所以要多个变量定义. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34inline int min(int a,int &b,int &c) { if (a > b) { if (b > c) return c; return b; } if (a > c) return c; return a; } bool ok(int m){//high cnt = m int ap = 0,bp = 0;//当前飞机场数目 int af = 0,bf = 0,tf = 0;//a可以起飞数,b,总 for (int i = 0; i < n; i++) { if(a[i] > m || b[i] > m) return false; ap += a[i];//时间i降落 bp += b[i]; if(ap > m)//之前起飞 { int dec = min(ap - m, af,tf); ap -= dec,af -= dec,tf -= dec; } if(bp > m) { int dec = min(bp - m, bf,tf); bp -= dec,bf -= dec,tf -= dec; } if(ap > m || bp > m) return false; if(af < ap) af++;//主要是这个if限制了状态定义 if(bf < bp) bf++; if(tf < ap + bp) tf++; } return true; }
  • LA3403 (紫书例题)天平难题…二进制枚举二叉树,记录左右最大值

滑动窗口/单调队列

  1. 例题18 UVA11078 找Ai和Aj使得Ai - Aj尽量大 维护小于j的最大i值 MaxAi = max(Aj,MaxAi)
  2. 例题21 LA2678 正整数序列,求最短子序列和>S
    • 重点在于随后加一个if (ans == maxn) ans = 0

    尺取法 1 2 3 4 5 6 7 8 9for (ptr1 = ptr2 = 0; ptr2 < N; ptr2++) { sum += a[ptr2];//每次后面的指针后移 while (ptr1 <= ptr2 && sum - a[ptr1] >= S) { sum -= a[ptr1]; ptr1++; } if (sum >= S)update(ans, ptr2 - ptr1 + 1); } 1 2 3 4 5 6 7 8 9 10 11for (ptr1 = ptr2 = 0; ptr2 < N; ) { while (sum < S && ptr2 < N ) { sum += a[ptr2]; ptr2++; } while (sum >= S && ptr1 < ptr2) { update(ans, ptr2 - ptr1); sum -= a[ptr1]; ptr1++; } }

可怕的暴力

三维问题

  1. 例题6 LA2995 (最大立体)三维坐标系转换 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15void get(int k, int i, int j, int len, int &x, int &y, int &z) { if (k == 0) { x = len; y = j; z = i; } if (k == 1) { x = n - 1 - j; y = len; z = i; } if (k == 2) { x = n - 1 - len; y = n - 1 - j; z = i; } if (k == 3) { x = j; y = n - 1 - len; z = i; } if (k == 4) { x = n - 1 - i; y = j; z = len; } if (k == 5) { x = i; y = j; z = n - 1 - len; } } /* 给出六个面 k: 前 左 后 右 顶 底 i j 枚举位置 len是深入的长度 x y z从上往下看的坐标系 */
  2. 例题8 LA3401 修改最少的面使得立方体相同
    1. 写个小程序枚举”姿态”
    2. 枚举每个立方体每种姿态最少涂色数

套路

  1. 例题7 UVA11464 01矩阵枚举第一行
  2. 例题11 UVA10795 汉诺塔的扩展 汉诺塔变形,给出始态终态,求移动步数 赋予中间态定义f(P,i,final)表示把1…i全部移动到final所需要的步数 ans = f(start,k-1,6-start[k]-finish[k]) + f(finish,k-1,6-start[k]-finish[k])+1 (k 是最大编号要移动的盘子) f(P,i,final) = (P[i] == final) ? f(P , i-1, final): f(P,i-1,6-P[i]-final) + (1LL<<(i-1));
  3. 例题17 计数排序
  4. 例题19 UVa11549 Floyd判圈法 1 2 3 4 5 6long long a = k,b = k; do{ a = next_num(a); b = next_num(b); if(b > ans) ans = b; b = next_num(b); if(b > ans) ans = b; }while (a != b);
  5. 例题24 三维最大子空间

二分

二分模板= =

1234567891011121314151617181920

//整数while(l < r){ int m = l + (r - l + 1) / 2; if(check(m)) l = m; else r = m - 1;}l is answer //浮点数while (r - l > 0.000001) { double m = (r + l )/2; if (check(m)) { l = m; }else r = m;}//单调时最小位置i = lower_bound(a,a + n,val) - a;

  1. 例题12 最小品质因子最大值最小a值最大b
  2. LA4254 白书手写题解==
  3. LA4253 返回值有意义的二分(判存在性,极角维护左右)

二维降,扫描线

  1. 例题20 LA3905 流星最多的时间
    1. 扫描线计数法(碰到起点+1)
    2. 抽象为起点和终点,由于是直线,二维= 一维∩一维
    3. 整数计算
  2. 例题23 LA3695 找一个矩形边上包括尽量多的点 求平行坐标轴的矩形边上最多点覆盖 扫描线,对所有点依据x排序,对所有y排序,unique 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20for (int a = 0; a < m; a++) { for (int b = a + 1; b < m; b++) { int low = y[a], high = y[b];//枚举平行于x轴的两条边 int k = 0,M = 0; for (int i = 0; i < n; i++) {//扫描平行于y轴的边 if (i == 0 || p[i].x != p[i-1].x) { k++;//统计x坐标个数 on[k] = on2[k] = 0; left[k] = k == 0 ? 0 : on2[k-1] - on[k-1] + left[k-1];//y = low (+) high 上已经有多少点 } if(p[i].y > low && p[i].y < high) on[k]++;//左记录线记录low,high之间的边(不含端点) if(p[i].y >= low && p[i].y <= high) on2[k]++;//右记录线记录low,high之间的边(含端点) } if(k <= 2) return n;//总共只有两个坐标(这里不用再对x排序- -) for (int j = 1; j <= k; j++) { ans = max(ans,on2[j] + M + left[j]);//ans = max(on2[j] + on2[j-1] + left[j] - left[j-1]) M = max(M,on[j] - left[j]);//维护on[i] - left[j]的最大值 } } }

悬线法

  1. 例题22 LA3029 最大子矩阵. 把每个格子向上延伸的连续空格看成一条悬线 有障碍物的区域中的最大子矩阵 (USACO用一个height数组过的(USACO6.1)) 训练指南是维护up,l,r三个数组,l,r标记以up为高度的矩形最左和最右的位置

01 GUY

  1. 例题25 LA2965 尽量多的串使得大写字母都出现偶数次
    • =>用二进制位表示字母
  • =>xor == 0
  • =>枚举前一半,而后枚举后一半中途相遇

码农题

  1. 例题9 UVA11210 麻将(判断”听牌”)
  2. Ugly Windows 代码量不大但是有坑
  3. LA3667 最少刻度 二进制bfs扩展参考 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18for (i = 0; i < N; i++) { if (cur.found & (1<<i)) continue;//当前存在 int v = *iter + arr[i];//扩展节点 if(cur.st.find(v) != cur.st.end()) continue; if(v > MAX) continue; next = cur; next.st.insert(v); for (set<int>::iterator iter2 = cur.st.begin();//进一步扩展 iter2 != cur.st.end(); iter2++) { int x = abs(v - *iter2); if (idx[x] != -1) { next.found |= (1<<idx[x]); } } if (next.found != cur.found) { q.push(next); } } ​
  4. UVA10825 乘2..m后所有位数字还是那些…..枚举最后一位生成所有位数
  5. LA3621 最少几次乘除得到${X}^{n}$.迭代加深搜索+剪枝

trick

  1. writein & readin 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31inline int readint() { char c = getchar(); while(!isdigit(c)) c = getchar(); int x = 0; while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); } return x; } int buf[10];//global varible inline void writeint(int i) { int p = 0; if(i == 0)p++; else while(i) { buf[p++] = i % 10; i /= 10; } for(int j = p - 1;j >= 0;j--) putchar('0' + j); }

  1. 例题及习题指 <<算法竞赛入门经典(训练指南)>>对应例题
  2. 私在vjudge中开题集(因为uva墙外服务器是在是慢啊…)
  3. 求LA5704 Yummy Triangular Pizza传统题解,oeis是个好地方

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据小魔方

R语言可视化——箱线图及其美化技巧

今天跟大家分享如何在R语言中利用ggplot函数制作箱线图及其美化。 箱线图也是经常会用到的用于呈现数据分布形态的重要的图表类型。 还是以ggplot2包内置的...

4776
来自专栏数据结构与算法

洛谷P2251 质量检测

题目背景 无 题目描述 为了检测生产流水线上总共N件产品的质量,我们首先给每一件产品打一个分数A表示其品质,然后统计前M件产品中质量最差的产品的分值Q[m] =...

3323
来自专栏ACM算法日常

算法合集 | 无限的路(递推) - HDU 2073

递推和递归有着很多的相似之处,甚至可以看做是递归的反向。递归的目的性很强,只解需要解的问题,递推有点“步步为营”的味道,不断的利用已有的信息推导...

1001
来自专栏Vamei实验室

概率论02 概率公理

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢!

961
来自专栏数说戏聊

09.交叉&结构&相关分析1.交叉分析2.结构分析3.相关分析

用于分析两个或两个以上,分组变量之间的联系,以交叉表形式进行变量间关系的对比分析。

4071
来自专栏数据结构与算法

P1403 [AHOI2005]约数研究

题目描述 科学家们在Samuel星球上的探险得到了丰富的能源储备,这使得空间站中大型计算机“Samuel II”的长时间运算成为了可能。由于在去年一年的辛苦工作...

3865
来自专栏小樱的经验随笔

2017"百度之星"程序设计大赛 - 复赛1003&&HDU 6146 Pokémon GO【数学,递推,dp】

Pokémon GO Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 32768/32768 K...

3457
来自专栏小樱的经验随笔

ACM训练计划

看完人家的博客,发现任重道远。。。 一位高手对我的建议: 一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功.acm主要是考算法的,主要时间...

49210
来自专栏大数据文摘

你真的懂TensorFlow吗?Tensor是神马?为什么还会Flow?

6017
来自专栏懒人开发

(7.7)James Stewart Calculus 5th Edition:Approximate Integration

黎曼求和,我们把对应的[a, b]分成n份,每份大概为 Δx = (b - a)/n 这个时候,有:

1813

扫码关注云+社区

领取腾讯云代金券