巅峰赛#25 T1~T5题解
2025-09-14 23:30:56
发布于：浙江
24阅读
0回复
0点赞
总体来说这次巅峰赛难度好像略高于上次，也可能是换了出题老师的缘故
T1
T2
T3
T4
T5
方便大家观看与自己书写，我就是用超链接进行跳转了
这真的都是我辛苦写完的题解
（其实是不知道要合并发）
胡乱解T6，喜提4分高分
#include<bits/stdc++.h>
using namespace std;
//巅峰赛最后一题一看就惹不起，上次即便使用AI也无法战胜
//所以这次浅尝即止
//数据范围给的非常普通，没有突破点
//唯一值得注意的是q，也就是说我们需要以最高O(logn)的时间复杂度查询
//所以Alice大概率是赢的，所以只要求出子段数？
//根据样例来说，不可能（不然怎么都没人做出来）
//综上，Alice和Bob两个cs就不应该玩这个sm小游戏
//666,数学+RMQ+模拟？
//很明显我找不到数学规律
//诶？通过观察样例,与分析，好像我们可以得出
//当存在多个盘子时，盘子时，盘子中个数相同则Alice必输？
//仔细打了两遍表,似乎该情况仅仅出现于偶数个盘子中
//我们只要寻找该字段中连续相同的个数；
//看数字范围可以知道我们还要预处理
int idx=0;
struct ikun{
long long l,cnt;
}d[200010];//用D数组保存每段连续子段
int fd(long long x){
int l=1,r=idx;
int ans=0;
while(l<=r){
int mid=l+r>>1;
if(d[mid].l<=x&&x<=d[mid].l+d[mid].cnt-1){
ans=mid;
break;
}
else if(x<d[mid].l)r=mid-1;
else l=mid+1;
}
return ans;
}
int main(){
int a[200010];
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]==a[i-1]){
d[idx].cnt++;
}
else{
d[++idx].l=i;
d[idx].cnt=1;
}
}
//查询bob的胜局时不能是O(n);
//所以我们用二分（不完整字段），和前缀和优化（完整子段）
long long pre[200010]={};
for(int i=1;i<=idx;i++){
pre[i]=pre[i-1]+d[i].cnt/2*(d[i].cnt/2+1)/2;
}
int q;
cin>>q;
while(q--){
int l,r;
cin>>l>>r;
long long lenth=r-l+1;
long long sum=(1+lenth)*lenth/2;
int ld=fd(l),rd=fd(r);
long long cnt=0;
//左不完整子段
int lf=d[ld].cnt-(l-d[ld].l);
//右
int rf=r-d[rd].l+1;
if(ld==rd){
rf=0;
ld=lenth;
}
cnt=lf/2*(lf/2+1)/2+rf/2*(rf/2+1)/2+(pre[ld+1]-pre[rd]);
//O(n)查找
//for(int i=l+1;i<=r;i++){
//if(a[i]==a[i-1]){
//k++;
//}
//else{
//k/=2;
//cnt+=k*(k+1)/2;
//k=1;
//}
//}
cout<<sum-cnt<<endl;
}//喜提4分完结撒花
}
@AC君求精
有帮助，赞一个