Educational Codeforces Round 171 (Rated for Div. 2)(A~D) 题解

Problem - A - Codeforces--PerpendicularSegments

思路:正方形对角线最长,并且相互垂直.直接输出即可.

int x,y,k;
void solve(){       //Acin>>x>>y>>k;int res=min(x,y);cout<<"0 0"<<" "<<res<<" "<<res<<endl;cout<<"0 "<<res<<" "<<res<<" 0"<<endl;
}

Problem - B - Codeforces--BlaceCells

思路:读错题了..简单贪心，偶数个直接算即可；奇数个枚举哪一个不要，然后再相邻两两配对即可。

int n;
//读错题了cao,爽扣80分.
//https://codeforces.com/contest/2026/problem/B
void solve(){     //Bcin>>n;vector<int> vct;for(int i=1;i<=n;i++){int x; cin>>x;vct.emplace_back(x);}int ans=LONG_LONG_MAX,fuck=1;       //LONG_LONG_MAX!!if(n%2==0) {for(int i=1;i<(int)vct.size();i+=2) {  //wrong:i+=2!!fuck=max(fuck,vct[i]-vct[i-1]);}cout<<fuck<<endl;}else{for(int i=0;i<(int)vct.size();i++){vector<int> temp;for(int j=0;j<(int)vct.size();j++){if(i==j) continue;temp.emplace_back(vct[j]);}int res=1;for(int j=1;j<(int)temp.size();j+=2) res=max(res,temp[j]-temp[j-1]); //wrong:j+=2!!ans=min(ans,res);}cout<<ans<<endl;}
}

Problem - C - Codeforces--ActionFigures

思路:仍然是简单贪心，从后往前贪即可。把0和1分开存，优先使用0(注意把无效的弹出)，没有0了就最优先弹出最前面的1。用双端队列即可。

int n;
string str;
从后往前贪心,秒了
void solve(){       //Ccin>>n>>str;str="?"+str;deque<int> zero,one;for(int i=1;i<=n;i++) str[i]=='0'?zero.emplace_back(i):one.emplace_back(i);int ans=n*(1+n)/2;while(!one.empty()){int cur=one.back();one.pop_back();while(!zero.empty()&&zero.back()>cur) zero.pop_back();if(!zero.empty()) zero.pop_back(),ans-=cur;else if(!one.empty()) one.pop_front(),ans-=cur;}cout<<ans<<endl;
}

Problem - D - Codeforces--SumsOfSegments

思路:不知不觉推了一天..推导这方面还是太晕了..

题解:我们必须能够计算以下值：
①给定数据块b的一个索引,以及该数据块中元素l和r的索引,计算从该数据块中第l个元素到第r个元素的和;
这个是最核心的功能,看下面例子..
②给定图块l和r的两个索引，计算从图块l到图块r的和; 可以o(1)实现.整出pre3即可,这个很好推导.

题解:key:b数组分块处理,以第i个数字开头到n的为一块,共有n块.
那么可以记录每一块的长度和总和.然后可以维护全部块的前缀和.
可以o(logn)算出l,r在哪一块中,那么ans=(pre3[idxR]-pre3[idxL-1]) 减 (l块和r块中选上的数字的和);

以arr=1,2,5,10; 为例.
pre1:1,3,8,18; arr数组的前缀和.
pre2:1,4,12,30; 原数组的前缀和的前缀和.
key!!!!:
但是怎么求任意块内任意区间和???究极核心推导如下:
b为所求区间[l,r]所在的块编号(从1开始编号).
那么对应原数组,计算[l,r]所在的区间贡献为:pre1[b+l-1]+pre1[b+l]+pre1[b+l+1]+pre1[b+r] - (r-l+1)pre1[b-1];
即在求pre1的区间和,直接用pre2即可!!,那么任意块b区间[l,r]的和为:
pre2[b+r-1]-pre2[b+l-1]-(r-l+1)*pre1[b-1];
key!!!:一切的一切,都衍生于原数组,下标都是换成跟原数组对应的,这样就可以使用原数组衍生的各个前缀和.
pre3:30,56,76,86; 每一块的总和的前缀和.
每一块的总和:30,26(30-4*1),20(30-4*1-3*2),10(30-4*1-3*2-2*5);

//题解:我们必须能够计算以下值：
//①给定数据块b的一个索引，以及该数据块中元素l和r的索引，计算从该数据块中第l个元素到第r个元素的和;
//这个是最核心的功能,看下面例子..
//②给定图块l和r的两个索引，计算从图块l到图块r的和; 可以o(1)实现.整出pre3即可,这个很好推导.
int n,q;
int arr[300005];
int pre1[300005];
int pre2[300005];
int pre3[300005];
int getBlock(int pos){    //二分出pos在哪个block.int l=1,r=n,res=-1;while(l<=r){int mid=(l+r)>>1;if( mid*(n+n-mid+1)/2 < pos ){res=mid-1;l=mid+1;}else r=mid-1;}return res;
}
//完整的b数组很大,大概9e10.
//ai的范围很小,只有[-10,10],但是有什么用呢?--没有什么用,只是总和不会爆long long
//不懂...
//看题解:key:b数组分块处理,以第i个数字开头到n的为一块,共有n块.
//那么可以记录每一块的长度和总和.然后可以维护全部块的前缀和.
//可以o(logn)算出l,r在哪一块中,那么ans=(pre3[idxR]-pre3[idxL-1]) 减 (l块和r块中选上的数字的和);//以arr=1,2,5,10; 为例.
//pre1:1,3,8,18; arr数组的前缀和.
//pre2:1,4,12,30; 原数组的前缀和的前缀和.
key!!!!:
但是怎么求任意块内任意区间和???究极核心推导如下:
b为所求区间[l,r]所在的块编号(从1开始编号).
那么对应原数组,计算[l,r]所在的区间贡献为:pre1[b+l-1]+pre1[b+l]+pre1[b+l+1]+pre1[b+r] - (r-l+1)pre1[b-1];
即在求pre1的区间和,直接用pre2即可!!,那么任意块b区间[l,r]的和为:
pre2[b+r-1]-pre2[b+l-1]-(r-l+1)*pre1[b-1];
key!!!:一切的一切,都衍生于原数组,下标都是换成跟原数组对应的,这样就可以使用原数组衍生的各个前缀和.
//pre3:30,56,76,86; 每一块的总和的前缀和.
//每一块的总和:30,26(30-4*1),20(30-4*1-3*2),10(30-4*1-3*2-2*5);
//https://codeforces.com/contest/2026/problem/D
void solve(){       //补D 分块,,细细推导...下标对应好...细节多多啊..给写了一天。。cin>>n;for(int i=1;i<=n;i++) {cin>>arr[i];pre1[i]=pre1[i-1]+arr[i];pre2[i]=pre2[i-1]+pre1[i];}int sum=pre2[n];for(int i=1;i<=n;i++){pre3[i]=pre3[i-1]+sum;sum-=(n-i+1)*arr[i];}cin>>q;while(q--){int x,y; cin>>x>>y;int bl=getBlock(x)+1,br=getBlock(y)+1;int posl=x-(bl*(n+n-bl+1)/2); //在块内的位置posl.int posr=y-(br*(n+n-br+1)/2); //在块内的位置posr.bl++,br++;if(bl==br){ cout<<pre2[bl+posr-1]-pre2[bl+posl-1-1]-(posr-posl+1)*pre1[bl-1]<<endl; }else{int resL=pre2[bl+(n-bl+1)-1]-pre2[bl+posl-1-1]-( (n-bl+1)-posl+1 )*pre1[bl-1];int resMid=pre3[br-1]-pre3[bl];int resR=pre2[br+posr-1]-pre2[br-1]-posr*pre1[br-1];cout<<resL+resMid+resR<<endl;}}
}