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. (因为第一个和最后一个都是奇数位)看最后一个是否会拿左边的.

• 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 三维最大子空间

二分

二分模板= =

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墙外服务器是在是慢啊…)
   • 1-1
   • 1-2-1
   • 1-2-2
   • 1-3
3. 求LA5704 Yummy Triangular Pizza传统题解,oeis是个好地方