当前位置: 首页> 文旅> 艺术 > 写作文网站_支付网站搭建_最新实时大数据_友情链接论坛

写作文网站_支付网站搭建_最新实时大数据_友情链接论坛

时间:2025/7/12 2:13:50来源:https://blog.csdn.net/Lindsey_feiren/article/details/146027531 浏览次数:0次
写作文网站_支付网站搭建_最新实时大数据_友情链接论坛

蓝桥杯每日一题:第一周周四哞叫时间

在这里插入图片描述

疑惑:如何把复杂度控制在Q(n),怎么枚举a和b,longlong的形式又该怎么输入(考虑用string)

思路:枚举倒数第二个b前面有多少个a

这是一种经典的实现方法,需要掌握,用数的值做数的下标,其实就和用字母序号做下标一样,left[x]表示当前数左边值等于x的数的个数,right[x]则相反

注意特别的含义,left[x]=0,当前就是从右往左遍历到的最后一个x了,

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e6 + 5;
typedef long long int LL;
LL res;//因为res最大为N的平方,超int了
int l[N],r[N],w[N],cnt;//cnt表示一共有多少个不同的数
int main(){int n;cin>>n;for(int i=1;i<=n;++i){cin>>w[i];if(++l[w[i]]==1) cnt++;}for(int i=n;i>=1;--i){int x=w[i];r[x]++;l[x]--;if(l[x]==0) cnt--;//即不一样的数就减少了一个if(r[x]==2) {res+=cnt;if(l[x]>0) res-=1;}//剪掉的1就是左边剩下的一个b,因为只有不一样的数字才会被记到cnt里,左边无论有几个b,在cnt里左边不同的数都只有1}cout<<res<<endl;
}
关键字:写作文网站_支付网站搭建_最新实时大数据_友情链接论坛

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: