贪心思路是解决很多思维题的利器。然而这种题没有固定模板，纯看赛时脑子零不灵活。能否快速切出思维题往往是取胜的关键。本文将收录一些常用的解题思路，持续更新中。 直接排序法这种题一般排个序，按照要求每步选择最优解就可以。 P1803 线段覆盖P1803 线段覆盖 因为要参加更多的比赛，所以要优先选择结束更早的比赛，才能为后来的比赛创造更多的时间。直接按结束时间排序即可。 12345678910111213141516171819202122232425262728bool cmp(const pii&a,const pii&b){ return a.second<b.second;}void solve(){ int n; cin>>n; vecpi a(n); mpi h; int idx=1; for(auto&p:a) { cin>>p.first>>p.second; } sort(a.be ...

别看他简单，但是代码打起来特别容易红温，而且容易想不到漏洞。特别是大模拟题…… 本文简要总结一下常用的搜索算法： 二分搜索使用二分搜索的前提条件是每种情况的答案具有二分性————即大于某一点符合某一性质，小于等于某一点则不符合某一性质。一般常和排序一起用。 例题：2020 ICPC Shanghai Site D.Walker 首先把特殊情况处理一下：一个人走完全程、两人相对走到终点。 其次列举某点，某一人走完1到某点的距离，另外人走剩下部分。某点向用时较长的人方向偏移。 代码： 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768#ifndef VLSMB_VS#include <bits/stdc++.h>#else#include <iostream>#include <iomanip>#include <set>#include ...

给你一个排列，要求你每次操作任选4个数字交换位置，最小需要多少次操作才能变成有序排列。 思路：考虑使用并查集，将i和a[i]所在的集合并。这样合并后的每个集内部元素是可以自由排列形成最终答案的。对于长度为1的集，说明i与a[i]在一个位置上，不需要操作；对于长度为2的集，两个可以组成一对进行操作；对于长度为3的集，需要用一个辅助元素与之组合；对于长度为4的集，肯定是选择它自己了；对于长度大于4的集，我们任选其中4个元素，只能使3个定序，另一个必定还是不对位的，因此操作次数是集的大小/3，此外集的大小%3还要讨论一下。 有位佬跟我说可以用基环树，但我还没有学过。等我学了，我再更新这篇blog…… 代码： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990#ifndef VLSMB_VS# ...

线段树是一个处理区间问题常用的数据结构。但是码线段树的时候总是会有很多很多小错误导致RE…… 线段树模板题：区间查询、区间修改仅涉及线段树的代码： 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364int a[N];struct node{ int l,r,v,tag;}tr[4*N];void build(int l,int r,int i){ tr[i].l=l; tr[i].r=r; tr[i].tag=0; if(l==r) { tr[i].v=a[l]; return; } int mid=(l+r)>>1; build(l,mid,2*i); build(mid+1,r,2*i+1); tr[i].v=tr[2*i].v+tr[2* ...

利用两个优先队列，可以求出数组中第k小的数字 解题思路利用两个优先队列当大根堆和小根堆，将前k个数字放入大根堆中，再将剩下的数字放入小根堆中，大根堆的堆顶就是所求。 【POJ3784】Running Median题意：有n个数字（n为奇数）组成的数组，当遍历到奇数索引时，中位数是多少。 思路：用一个大根堆维护较小部分数字，小根堆维护较大部分的数字。插入时根据插入的元素与两个优先队列堆顶元素的大小关系插入指定序列。插入之后维护两个堆，使大根堆的大小为小根堆+1. 注意：STL的优先队列的greater模式，堆顶是最小值；less模式，堆顶是最大值。不要用反！！ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293#ifndef VLSMB_VS#include <bits/stdc ...

问每次询问，Y与X，是否满足X是自Y以来最大降雨量的一年。 这题可以用ST表做。首先对年份进行离散化处理，数字相邻的离散化后的数字也相邻，但是中间有数字空白的，离散化时要差1位。 之后初始化st表，建立stmax和stmin两部分，某个区间的最小值为0，说明这个区间存在不确定的年份，这个是判maybe的一个关键条件。 之后只需要判断X与Y的关系，以及X与[Y+1, X-1]区间的最大值的关系。 注意：X需要小于等于Y，[Y+1, X-1]的每一个数也要满足这个条件，题干虽然没说但根据不等式也能推导出来 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171 ...

ST表（Sparse Table，稀疏表）是用于解决可重复贡献问题的数据结构。 常用于区间问题，如区间最值、区间最大公因数。 ST表的模板ST表模板题 ST表 Oi Wiki ST表可以用于解决可重复贡献问题，例如区间最值、区间最大公因数、区间按位与、区间按位或。核心思想是倍增法，覆盖的区间不会因为被覆盖而影响答案。 核心代码： 12345678910111213141516171819const int N = 1e5;int st[N][20]; // j层为指数// j==0即区间长度为2**0，则为数字本身for(int i=1;i<=n;i++)cin>>st[i][0];for(int j=1;j<20;j++){ // 先枚举区间长度 for(int i=1;i<=n&&(i+(1<<(j-1)))<=n;i++) { st[i][j] = opt(st[i][j-1], st[i+(1<<(j-1))][j-1]); }& ...

利用树状数组记录小于a[i]数字的个数 树状数组的模板123456789101112131415161718192021222324int lowbit(int x){ return x&(-x);}int tr[N];int n;void update(int x,int i){ while(i<=n) { tr[i]+=x; i+=lowbit(i); }}int getval(int i){ int ans=0; while(i) { ans+=tr[i]; i-=lowbit(i); } return ans;} 树状数组的一个应用——记录数字出现的情况比如说数字a[i]，出现的时候将其在树状数组的位置+1，之后的a[j]，就可以取树状数组的记录值，来得出有几个大于a[j]的数字。 题目链接：P10589 题目大意：有n个数字组成的排列，问能组成机组V ...

给你n个商品，每个商品有销售利润和保质期，问如何安排利润最大。 并查集模板1234567891011121314151617int a[N];int parent(int x){ if(x==a[x])return x; a[x]=parent(a[x]); return a[x];}void merg(int x,int y){ x=parent(x); y=parent(y); a[x]=y; // a[x]-> y}void init(){ for(int i=1;i<N;i++)a[i]=i;} 本题思路首先根据价格由高到低，其次保质期由低到高排序。 并查集初始化为每一天都可用的状态，先安排利润高的商品，安排最后一天再销售。若这一天不可用，用并查集找到下一个可用天数；若并查集父节点为0，代表没有可用天数，放弃安排这个商品。 123456789101112131415161718192021222324252627282930313233343536373839 ...