题意  给定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指向元素的第一个元...

对于a^b，可以将b转化为二进制表示（10：1010），故a^b可拆分成a^b1*a^b2*…… 因此记录一个base=a，如果b的对应位为1，ans*=base 最后再给base倍增：base*=a，b位移：b>>=1  #include<bits/stdc++.h> using namespace std; long long qpow(long long a,long long b,long long p){ a%=p; long long ans=1; while(b){ if(b&1)ans*=a%p; a*=a%p; b>>=1; } r...

题意  给定若干个点，求最近的两个点的距离  思路   分治   对于所有点，总可以按照以下三种情况处理： 1.只剩下两个点：直接返回两点距离 2.只剩下三个点：返回三个距离的最小值 3.剩下的点超过三个，从中点分开，不断递归至情况一/情况二   由此，总能不断地把大区间二分成小区间，并算出区间内最近点对距离dis   此后，考虑将区间合并，找出可能的在跨区间的最小点对： 1.记录全部距离mid的距离小于等于dis的点 2.将这些点按纵坐标排序 3.二重循环遍历所有点，如果两个点的纵坐标差值大于dis，直接跳出循环，进行剪枝   最后将所有答案整合求最小即可得到答案   AC代码 #inclu...

题意  n个点，m次输入，每次输入左界，右界，存储的货物编号 求存储的货物种类最多的点  思路  因为一个点可能重复读入同一个货物，所以使用map并做前缀和 开一个map统计每个点存入的货物和次数，全部读入完后，开第二个前缀和map 遍历第一个map中的每一个点，对每一个点，将其中的货物存入前缀和map，如果计算到某一种货物的数量为0，就将这种货物从sum中erase掉，以保证sum的size始终为当前货物种类  AC代码 #include<bits/stdc++.h> using namespace std; map<int,int>mp[101010],num; i...

题意  给定一个树的先序遍历和后序遍历，求他的中序遍历，无法确定的时候，认为是左子树  思路  若没有规定左子树，则给定先序和后序是无法确定的，但规定后即可 对于先序遍历，第一个点总是当前的根，第二个点总是当前左子树的根 对于后序遍历，找到由先序确定的左子树的根的位置，由后续的头到该位置为左子树，由该位置加一到倒数第二位是右子树 在划分完后序里的左右子树后，可以确定两个子树的长度，因此可以找到先序遍历中左子树的屁股，左子树的屁股加一到先序序列的最后就是右子树 找到以后按照递归左子树-根-递归右子树的顺序存入中序序列中  AC代码 #include<bits/stdc++.h> us...

题意  对给定的数学表达式，求解其值（包含括号，加减乘除，幂）  思路  通过递归的方式，每次找到最后一个运算的运算符，然后递归处理该运算符的左边和右边，直到当前区间只有数字，然后将两个递归的结果按照符号处理即可  AC代码 #include<bits/stdc++.h> #define int long long using namespace std; string s; int digit(int l,int r){ int num=0; for(int i=l;i<=r;i++){ num=num*10+s[i]-'0'; } return num; } int ca...

题意  求gcd  证明 对于a和b的最大公因子d a=pd，b=qd 则有c=(p-q)d，使得d为b和c的公因子  代码 int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b); }

前言  通常对于一颗树有四种遍历方式，先序遍历，中序遍历，后序遍历，层序遍历，分别对应着：根左右，左根右，左右根，层（类bfs队列实现）  题意  存一颗树，输出他的前中后层遍历  思路  由题意，给定一个节点的父亲和该节点的左右位置，可以使用一个结构体数组来存储 对于前三种遍历方式，使用递归即可实现 对于最后一种方式，维护一个队列，pop的同时把该节点的两个儿子加入队列，直到队列为空  AC代码 #include<bits/stdc++.h> using namespace std; typedef struct{ int l,r; }TREE; TREE a[505050]; ...

Codeforces Round 1006 div.3 A 题意  给定n,k,p,能否在判断np和k的关系  思路  就简单签到  AC代码 #include<bits/stdc++.h> using namespace std; int main(){ int t; scanf("%d",&t); while(t--){ int n,k,p; scanf("%d%d%d",&n,&k,&p); if(abs(k)>n*p)printf("-1\n"); else{ int rst=abs(k)/p; if(k%p!=0)rst++; pri...

思路  类似于二分的操作，把每一段空间分成两半，直到空间长度等于一（递归实现） 合并过程，则对两个区间分别分配一个pointer，比较两个pointer指向的元素，然后存入数组 对于每一个片段需要的合并，一共有的层次，所以复杂度为  实现代码 #include<bits/stdc++.h> using namespace std; int a[505050],b[505050]; long long ans=0; void merge(int l,int r,int mid){ int p1=l,p2=mid+1; for(int i=l;i<=r;i++){ if((p2&...

题意  给定若干点和每个点的权值，查询若干次，每次查询输出将给定区间所有点移动到给定点的代价，代价为权值*距离  思路   肉眼可见的题目数据范围很大，暴力必T就别抱有幻想了   差分的给出了坐标，可以求前缀和得到每个点的真实坐标    让我们算代价，对代价的公式进行推导：  此时，此时我们试图消去绝对值，讨论a[i]和a[x]的大小，也就是x和l,r的关系   最终可以得到，总代价%%和以及有关   维护三个前缀和就可以在的复杂度内获得答案   记得取模   AC代码 #include<bits/stdc++.h> using namespace std; long long p...