楼下的线段树写的都太过麻烦，这是因为楼下的线段树均为及时更新答案。 但是，询问只有一次，我们不需要费力对每次询问维护答案。 对于第一问，留下的树苗数等于：留下的（树与树苗）总数减去留下的（树）的总数。 对于v第二问，种上又被拔掉的树苗数等于：被砍掉的（树与树苗）总数减去被砍掉的（树）的总数。 那么我们只需要维护有多少（树）被砍掉和有多少（树与树苗）被砍掉就好了。 对于前者，我们只需建立一颗线段树，无视种树苗操作，每次统计被砍掉多少即可。 对于后者，我们也建立一颗线段树，同时维护种树与砍树，每次统计成功砍掉多少（树与树苗）即可。 #include<iostream> #include...

本题细节错的较多。 #include<algorithm> #include<iostream> #include<cmath> #define inf 20000000 #define rep(i,a,b) for(int i=(a);i<=(b);i++) using namespace std; const int maxn=250; int miin(int a,int b){return a<b?a:b;} struct Bk{ int h,d; bool operator < (const Bk &b)const{ re...

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define dwn(i,a,b) for(int i=(a);i>=(b);i--) using namespace std; const int maxn=50050; int maxx(int a,int b){return a<b?b:a;} int n,Ans,a[2*maxn],b...

f[n] =0,n=0 else =f[n-1],s[n]=0 else =2^n-1,s[i]=0,1<=i<=n-1 else =f[k-1]+2^n-2^k,k为1到n-1中最后一个一位数 #include<iostream> #include<cstring> #include<cstdio> #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define dwn(i,a,b) for(int i=(a);i>=(b);i--) using namespace std; const i...

本题的解法实在神奇。 7不存在，那么可能的数位就有： 1,2,3,4,5,6,8,9,0 九种情况。 那么就可以看作是0-8，也就是九进制数。 然后将输入的数看作九进制数转成十进制就好了。 #include<iostream> #define ll long long int #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define dwn(i,a,b) for(int i=(a);i>=(b);i--) using namespace std; ll a[320]; int main(){ int n; cin>&...

对于出题人大大的证法表示太高深。 这里用高考范围内的知识给出更为简洁，严谨的证明。 为了方便起见，一下中的按理解。 首先，我们要证的命题是 若对于任意的正整数及任意的自然数， 有， 则对任意的自然数， . 现对用数学归纳法证明命题。 当时，显然. 假设时命题成立，即对任意的自然数, 有. 则当时，对任意的自然数, 有      故命题对也成立。 综上命题得证。 #include<iostream> #include<cstdio> void read(int &s); #define rep(i,a,b) for(int i=(a);i<=(b);i++)...

求每个固定长度区间最值 顾名思义,单调队列即是一个单调的队列. 这里只考虑求区间最小值. 建立一个单调递增的队列,队首是最小值. 开始队列为空,每次添元素的时候,从队尾向前比较, 直到找到最靠前的比自己小的数,将待添加元素添加到这个数后面, 舍弃后面的所以数.(这是因为新添加的数一定比后面的数更优) 每次取最小值时,因为区间左端点在变, 故对于队列中的每一个元素,记录它在原数列中的位置. 当当前所求区间中不含队首元素时,将队首舍弃. 直到队首在所求区间时,输出队首即可. 由于每个元素最多进出队一次,故复杂度为O(n). struct dddl{ int queue[maxn],t[maxn],...

算法: 记为以结尾的最长上升子序列长度, 对于每个更新  for(int i=1;i<=n;i++)f[i]=1; for(int j=2;j<=n;j++) for(int i=1;i<j;i++) if(a[i]<a[j]) f[j]=max(f[j],f[i]+1); for(int i=1;i<=n;i++) Ans=max(Ans,f[i]); 算法: 记为当前长度为结尾的上升子序列的末尾元素中最小的一个.可以保证序列单调. 从左到右扫一遍,为当前正常上升子序列长度. 对于新的,若,则更新 否则二分查找最后一个小于的后一个位置,设为, 则.则可以将替换为...

对于本题而言,记为前面的人的左手乘积, 比优等价于:  等价于 可以推出 故按照排序即可.

最长公共子序列 #include<iostream> #define maxn 100010 using namespace std; int A[maxn],B[maxn],C[maxn],f[maxn],f1[2333][2333]; int main(){ 将A序列一一映射成1,2,3...n,便等价于求B序列的最长上升子序列长度. int n;cin>>n; for(int i=1;i<=n;i++)cin>>A[i]; for(int i=1;i<=n;i++)cin>>B[i]; O(n^2)求一般情况 for(int i...

看了题解发现自己想的十分复杂。 现在来说一下不一样的方法。 题目要求放倒后可以重合的竹竿的对数， 自然会想到去研究：两个什么样的竹竿可以重合。 设第个竹竿是的高度为， 那么对于任意的， 它们倒地重合有三种情况：  一起倒在中间:，这等价于。 一起倒在左边:，这等价于。 一起倒在左边:，这等价于。  以上等价转化用到了大家在高中学习中做导数题经常用到的构造函数思想。 对于，我们可以将存进,数组， 若有个满足或相等， 则显然对应着对优秀的竹竿。 扫一遍即可算出答案。这里是的。 而对于，我们可以将存进数组， 再遍历一遍的数组， 对于每个，二分查找在数组中出现的左界与右界 那么就对应了对优秀的竹竿。 ...

首先依次加边，直到整个图联通为止，之前均输出， 图刚连通时跑一遍正常的克鲁斯卡尔。 然后将用到的边存起来（只有条）， 之后每加一条边，就对将这条边排序， 再跑就可以了。 复杂度（快排） （插入排序）  #include<algorithm> #include<iostream> #include<cstdio> #define rep(i,a,b) for(int i=(a);i<=(b);i++) using namespace std; const int maxn=25000; struct Bian{ int a,b,v; bool opera...

观察下题目的状态，可设计出一个较为直接的方程。 对于，代表当前时间，代表机器人即将走第几步， 表示从第几个工厂出发。则有:  时，  时, （一开始写的时候把时的方程写错了，丑） 边界就是 然后空间是不够的，易见第一维可以滚掉。 然后优化下就可以卡过此题。 #include<iostream> #include<cstdio> void read(int &s); #define inf 1000000000 #define rep(i,a,b) for(int i=(a);i<=(b);i++) using namespace std; const in...

首先可以数学地证明：可对所有人按吃饭时间从大到小排序 然后会想到表示前个人,一队用时间打饭，另一队用时间打饭的最小用时。 思想就是知道，就可以保证没有后效性。 但数组开不下，这时发现,便可以去掉以为一维。 还有要注意的就是初始化的问题了。 #include<algorithm> #include<iostream> #include<cstdio> int read(); #define inf 2000000000 #define rep(i,a,b) for(int i=(a);i<=(b);i++) using namespace std; co...