题意  共有n条蚯蚓，切割m次，每次切当前所有蚯蚓中最长的一条，切割比例为p=u/v，即对于长x的蚯蚓，切成px(向下取整)和x-px两段 特别的，长度为0也会被保留 同时每次切割后，除了被切割的那一条，其它蚯蚓增长q的长度 每切t次输出当前要切的这条蚯蚓的长度，最后输出长度从大到小排名t的整数倍的蚯蚓长度  思路  最开始先读入所有蚯蚓，从大到小排序 对于切割这件事，满足对切出来的两段中的任意一段，总有先切出来的比后切出来的更长，所以可以开两个队列维护切出来的两段，再加上没切的一共三个队列 每次比较三个队列中的队首，找到最大的那个，切一半 对于生长这件事，有两个思路处理，一个是开结构体，既存...

可以访问和修改队首队尾的支持sort的容器  STL   deque<类型>名称   方法： clear()：清空 front()：返回队首值 back()：返回队尾值 push_fornt(val)：队首插入值 push_back(val)：队尾插入值 pop_front()：移除队首值 pop_back()：移除队尾值 size()：返回容器中元素个数 empty()：判断容器是否为空 begin()：返回其实迭代器（指针） end()：返回末尾迭代器 insert(pos,val)：在迭代器位置插入值 erase(pos)：去除迭代器位置 支持sort，cmp，也可以在结构体...

STL   queue<类型>名称   方法 front():队首 back():队尾 pop():移除队首，不返回任何东西 push():写入队尾 empty():判空 不支持sort   常用于bfs   附一道队列小题   合并果子   #include<bits/stdc++.h> using namespace std; int a[202020]; int main(){ int n,pt=0; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&a[i]); } sort(a,a+n);...

牛客小白月赛112 A  给定三个数a,b,c,a放在天平一侧，判断有没有方法使得天平平衡  思路  瞪眼题 能平衡的无非5种情况，a=b,a=c,a=b+c,a+b=c,a+c=b,判断即可  代码 #include<bits/stdc++.h> using namespace std; int main(){ long long a,b,w; scanf("%lld%lld%lld",&a,&b,&w); if(a==w||b==w||a+b==w||a+w==b||b+w==a){ printf("Yes\n"); }else{ printf("No\...

STL   stack<类型>名称   方法 top():栈顶 pop():移除，不返回任何东西 push():写入 empty():判空 不支持sort   注意  区分队列和栈的区别 附一个字符串转数字的题和代码 后缀表达式  class Solution { public: long long legalExp(string str) { // write code here stack<long long> st; int i = 0; while (i < str.size()) { if (isdigit(str[i])) { long long nu...

功能  在主串中查找子串，返回头位置(0开头索引)  复杂度   n,m为主串和子串长度  思路  把主串和子串拼接到一起，中间隔开，记为合并串s 对s中的每一个子串计算其最长匹配真前后缀长度，如果有某一个字串的最长匹配真前后缀长度等于子串长度，则说明查找到子串 对于每一个子串希望求他的最长匹配真前后缀长度，他的最长匹配前后缀长度等于他去掉末尾的子串s'匹配上的长度  代码 void kmp(string &s1,string &s2){ int m=s2.size(); s2=s2+'#'+s1; int n=s2.size(); vector<int>p(n);...

定义  有n个物品，每个物品有价值和消耗，从其中拿k个，希望使得 ∑价值/∑消耗 最大  方法  设最优解X=∑v/∑c，对式子做变形有∑v-X∑c=0，再变形有∑(v-Xc)=0 易发现这是一个单调式子，故考虑使用二分 二分X，每次计算当前X下的(v-Xc)，取前k个求∑(v-Xc)，如果小于0则没有意义，如果大于0，则说明可行，存下来答案   注意  如果变为实数域上二分循环条件就变为  while(r-l>eps){……}   同样的，二分对左右界的更新变为  l=mid r=mid   例题-AC代码 #include<bits/stdc++.h> using nam...

题意  两条传送带AB，CD，给出四个点坐标，在两条传送带和地面上的速度分别为P,Q,R,从A到D的最短时间是多少？  思路  从AB到CD某点花费满足凹函数，从AB某点到CD花费也满足凹函数，三分套三分  AC代码 #include<bits/stdc++.h> using namespace std; int P,Q,R; const double eps=1e-7; typedef struct{ double x,y; }dt; dt A,B,C,D,E,F; double dis(dt a,dt b){ return sqrt(eps+(a.x-b.x)*(a.x-b.x...

题意  n块小石头，1块大石头，大石头生命值m，撞碎每块小石头先扣除a滴血，然后再回复b滴血，能否使n块小石头在一定的顺序下被吃掉而不死（m<0）  思路   一个很贪的贪心   由于我们希望尽可能撞碎尽可能多的石头，所以第一步贪心是把所有小石头分为三类，先撞使稳定性提升的，再撞使稳定性不变的，最后处理使稳定性下降的   对于使稳定性提升的要先处理扣血少的，因为初始血量可能不够处理扣血多的   对于不改变稳定性的无所谓处理的先后顺序，只要遇到比总血量大的就直接死了   对于使稳定性下降的展开贪心的几次思考 1.先吃扣的多的： 但有可能啃了硬的不够硬的也啃不动了 2.先吃性价比高的： 有特...

题意  给定一个长为n的数组a，对于他的每个区间拿出他的第K大元素，将所有的第K大元素进行排序，请问其中的第M 大是多少  思路  转化1：第K大数比X小的区间个数不能超过M-1个 转化2：区间中大于等于X的元素超过K个的区间小于M个 转化3：二分M，按上述要求检查所有可能的区间 转化4：对于找区间这个事情，如果找到了一个说明这个区间右界往后的每一个区间超过X的数都多余K个——双指针  注意  第K大是一个神奇的概念，例如{1,1,1,2,2,2,2,2,3}，第3，4，5 大数都是2，所以当x=2，k=4时，不能只考虑大于的，等于的也得考虑，同理，在后面更新左界的时候，就不能取等  AC代码...

题意  第i天有Ri个教室可以借出，一共有m次操作，每次操作以（x,y,z）形式给出，代表从y天到z天要借出x个教室，判断教室够不够用，如果不够，输出第一次不够的操作的序号  思路  正常读入该读入的东西 二分第次天会出问题，将这一次前（包含这一次）的操作做完 检测有无教室不够  AC代码 #include<bits/stdc++.h> using namespace std; typedef struct{ int d,s,t; }L; int n,m,delta[1010101],R[1010101]; L lend[1010101]; int judge(int mid){ ...

题意  给定n块巧克力d天，第i块巧克力提供热量ai，每天热量会减半 请给出最大的最小热量，使得在d天中每天的热量值都大于等于最小热量  思路  观察可得，最小热量越大维持天数越小，满足单调性，二分最小热量，对每一个最小热量判断是否足够维持d天 注意各种细节  细节（狂WA9发，人已经麻啦）  虽然每一块巧克力都是2e5以内的范围，但加和可能超过int——不开long long见祖宗 左右界：在本题中左界似乎不影响，但是右界得设的足够大如1e16，所以建议以后考虑二分的时候把右界算出来，在这个题中右界为所有热量值的加和 特殊情况思考，维护最后的吃巧克力顺序时，有可能有的巧克力吃了也不会增加天数...

题意  给定每个点的消耗时间，查询在第t秒的时候位于哪个点  思路  对耗时做前缀和，查询第一个大于的位置(upper_bound)  AC代码 #include<bits/stdc++.h> using namespace std; long long sum[50505]; int main(){ int n,q; scanf("%d%d",&n,&q); for(int i=1;i<=n;i++){ long long tp; scanf("%lld",&tp); sum[i]=sum[i-1]+tp; } for(int i=0;i<q;...

如何写一个二分  标准格式  int l,r; //找第一个大于等于x的位置，所求答案为l（等价于r+1） while(l<=r){ int mid=(l+r)>>2; if(a[mid]>=x)r=mid-1; else l=mid+1; } //找第一个小于等于x的位置，所求答案为r（等价于l-1） while(l<=r){ int mid=(l+r)>>2; if(a[mid]<=x)l=mid+1; else r=mid-1; }  解释 第一段  对于每一次进入if：mid指向的都是大于等于x的元素，更新x为小于mid指向元素的第一个元...