世界上最详细的题解
2026-11-07 16:45:38
发布于:广东
22阅读
0回复
0点赞
先读题,得知答案范围在longlong,所以要开longlong
这道题明显不能用字符串储存,所以我们要把它变成一个个区间
然后分成左区间和右区间
最后利用双指针累加
先定义
//n是区间个数,sum是字符串总长度,ans是储存答案的
long long n,sum,ans;
//lnum和lchar是左段的区间,lsize是左段区间个数
long long lnum[200001],lsize;
char lchar[200001];
//与左段同理
long long rnum[200001],rsize;
char rchar[200001];
然后处理输入
void input(){
cin>>n;
for(int i=1;i<=n;i++){
//这里lnum和lchar暂时用来储存全部区间
cin>>lnum[i]>>lchar[i];
//累加sum
sum+=lnum[i];
}
return;
}
然后处理左右分段
void segment(){
long long cnt=0;
//cnt在这里表示从第1个到第i-1个的和
for(int i=1;i<=n;i++){
//如果到第i个区间已经大于一半,说明左右两端的分界线就在i
if(lnum[i]+cnt>=sum/2){
//处理右段从n到i+1个区间
for(int j=n;j>i;j--){
rnum[++rsize]=lnum[j];
rchar[rsize]=lchar[j];
}
//如果中间那段能在右段增加一个区间,就增加一个
if(lnum[i]+cnt>sum/2){
rnum[++rsize]=lnum[i]+cnt-sum/2;
rchar[rsize]=lchar[i];
}
//如果sum是单数,那么就会有一个中间的,要减去
//看不懂为什么这么写的可以分类讨论一下单数和双数时sum%2都是什么
rnum[rsize]-=sum%2;
//如果中间那段能在左段还有剩余,就留下
if(sum/2>cnt){
lnum[i]=sum/2-cnt;
//此时有i个区间
lsize=i;
}
//不然就没有,此时有i-1个区间
else lsize=i-1;
break;
}
//让cnt累加
cnt+=lnum[i];
}
return;
}
写一个check检查一下
void check(){
//输出所有信息,用来检查
cout<<lsize<<"\n";
for(int i=1;i<=lsize+1;i++)cout<<lnum[i]<<" "<<lchar[i]<<"\n";
cout<<rsize<<"\n";
for(int i=1;i<=rsize+1;i++)cout<<rnum[i]<<" "<<rchar[i]<<"\n";
return;
}
接下来先改一下格式,我认为这样比较好写
void prefix(){
//让num[i]都累加,含义变为第i个区间的结尾位置
for(int i=1;i<=lsize;i++)lnum[i]+=lnum[i-1];
for(int i=1;i<=rsize;i++)rnum[i]+=rnum[i-1];
//让num[i]变成num[i-1]+1,含义变成第i个区间的开始位置
for(int i=lsize;i>=1;i--)lnum[i]=lnum[i-1]+1;
for(int i=rsize;i>=1;i--)rnum[i]=rnum[i-1]+1;
//设置尾部哨兵
lnum[lsize+1]=rnum[rsize+1]=sum/2+1;
return;
}
最后在分段处理
void segmented_search(){
//代表第i个区间的开头
long long cnt;
for(int i=1,j;i<=lsize;i++){
cnt=lnum[i];
//只要cnt没有超过这个区间就一直循环
while(cnt<lnum[i+1]){
//用j代表包含cnt的右段区间
j=upper_bound(rnum+1,rnum+rsize+1,cnt)-rnum-1;
//如果这个右段区间没有完全包含了从cnt到第i个区间的结尾
if(lnum[i+1]>rnum[j+1]){
//判断颜色是否相同
if(lchar[i]!=rchar[j])
//不同就加上从这个cnt到右段区间的结尾
ans+=rnum[j+1]-cnt;
cnt=rnum[j+1];
}
//不然就是完全包含
else{
//判断颜色是否相同
if(lchar[i]!=rchar[j])
//不同就加上从这个cnt到左段区间的结尾
ans+=lnum[i+1]-cnt;
//因为已经包含了cnt到左段区间的结尾,所以这个左段区间已经遍历完了,退出循环
break;
}
}
}
return;
}
最后在主函数中把所有函数一遍
int main(){
input(); //输入
segment(); //分段
//check() //检查
prefix(); //前缀
//check() //检查
segmented_search(); //分段处理
cout<<ans; //输出答案
return 0;
}
将所有代码写在一起,就能得到答案了
#include<iostream>
#include<algorithm>
using namespace std;
//n是区间个数,sum是字符串总长度,ans是储存答案的
long long n,sum,ans;
//lnum和lchar是左段的区间,lsize是左段区间个数
long long lnum[200001],lsize;
char lchar[200001];
//与左段同理
long long rnum[200001],rsize;
char rchar[200001];
void input(){
cin>>n;
for(int i=1;i<=n;i++){
//这里lnum和lchar暂时用来储存全部区间
cin>>lnum[i]>>lchar[i];
//累加sum
sum+=lnum[i];
}
return;
}
void segment(){
long long cnt=0;
//cnt在这里表示从第1个到第i-1个的和
for(int i=1;i<=n;i++){
//如果到第i个区间已经大于一半,说明左右两端的分界线就在i
if(lnum[i]+cnt>=sum/2){
//处理右段从n到i+1个区间
for(int j=n;j>i;j--){
rnum[++rsize]=lnum[j];
rchar[rsize]=lchar[j];
}
//如果中间那段能在右段增加一个区间,就增加一个
if(lnum[i]+cnt>sum/2){
rnum[++rsize]=lnum[i]+cnt-sum/2;
rchar[rsize]=lchar[i];
}
//如果sum是单数,那么就会有一个中间的,要减去
//看不懂为什么这么写的可以分类讨论一下单数和双数时sum%2都是什么
rnum[rsize]-=sum%2;
//如果中间那段能在左段还有剩余,就留下
if(sum/2>cnt){
lnum[i]=sum/2-cnt;
//此时有i个区间
lsize=i;
}
//不然就没有,此时有i-1个区间
else lsize=i-1;
break;
}
//让cnt累加
cnt+=lnum[i];
}
return;
}
void check(){
//输出所有信息,用来检查
cout<<lsize<<"\n";
for(int i=1;i<=lsize+1;i++)cout<<lnum[i]<<" "<<lchar[i]<<"\n";
cout<<rsize<<"\n";
for(int i=1;i<=rsize+1;i++)cout<<rnum[i]<<" "<<rchar[i]<<"\n";
return;
}
void prefix(){
//让num[i]都累加,含义变为第i个区间的结尾位置
for(int i=1;i<=lsize;i++)lnum[i]+=lnum[i-1];
for(int i=1;i<=rsize;i++)rnum[i]+=rnum[i-1];
//让num[i]变成num[i-1]+1,含义变成第i个区间的开始位置
for(int i=lsize;i>=1;i--)lnum[i]=lnum[i-1]+1;
for(int i=rsize;i>=1;i--)rnum[i]=rnum[i-1]+1;
//设置尾部哨兵
lnum[lsize+1]=rnum[rsize+1]=sum/2+1;
return;
}
void segmented_search(){
//代表第i个区间的开头
long long cnt;
for(int i=1,j;i<=lsize;i++){
cnt=lnum[i];
//只要cnt没有超过这个区间就一直循环
while(cnt<lnum[i+1]){
//用j代表包含cnt的右段区间
j=upper_bound(rnum+1,rnum+rsize+1,cnt)-rnum-1;
//如果这个右段区间没有完全包含了从cnt到第i个区间的结尾
if(lnum[i+1]>rnum[j+1]){
//判断颜色是否相同
if(lchar[i]!=rchar[j])
//不同就加上从这个cnt到右段区间的结尾
ans+=rnum[j+1]-cnt;
cnt=rnum[j+1];
}
//不然就是完全包含
else{
//判断颜色是否相同
if(lchar[i]!=rchar[j])
//不同就加上从这个cnt到左段区间的结尾
ans+=lnum[i+1]-cnt;
//因为已经包含了cnt到左段区间的结尾,所以这个左段区间已经遍历完了,退出循环
break;
}
}
}
return;
}
int main(){
input(); //输入
segment(); //分段
//check() //检查
prefix(); //前缀
//check() //检查
segmented_search(); //分段处理
cout<<ans; //输出答案
return 0;
}
如果只有72分说明忘开longlong了
用了二分函数upper_bound,要用<algorithm>头文件,或者用万能头
注释和代码都是纯手写的,只有查单词(函数名)时用了百度,点个赞吧,求求了。
互关
全部评论 1
互关
2026-11-07 来自 广东
0


有帮助,赞一个