汕头市队赛 SRM16
2024-09-04 15:08:35
T3
C-2 SRM 16
描述
给一个数列,给出两种数字, 询问在多少个非空区间中这两种数字出现次数相同。
输入格式
第一行:一个数字n,q,n表示数列长度,q表示q组询问
第二行n个数字表示数列A
接下来q行每行2个数字表示询问
输出格式
输出q行分别对应每个问题的答案
样例输入
2 1
1 2
1 2
样例输出
1
数据范围与约定
n <= 5000,q <= 10000 其他数字在int范围内
样例解释
只有区间[1,2]符合
——————————————————————————
因为 符合的状态就是 a.r-a.l=b.r-b.l
转换一下就是 a.r-b.r=a.l-b.l
然后我们记录一下差然后瞎jb搞就好了
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int M=1e4+,mod=;
int read(){
int ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
int n,q,k1,k2;
int s[M];
int f[*M];
int main()
{
n=read(); q=read();
for(int i=;i<=n;i++) s[i]=read();
for(int i=;i<=q;i++){
for(int i=;i<=*n;i++) f[i]=; f[n]=;
k1=read(); k2=read();
int cnt1=,cnt2=;
LL ans=;
for(int i=;i<=n;i++){
if(s[i]==k1) cnt1++;
if(s[i]==k2) cnt2++;
int now=cnt1-cnt2+n;
ans+=f[now];
f[now]++;
}
printf("%lld\n",ans);
}
return ;
}
C-3 SRM 16
描述
给一个数列, 询问对于在数列中出现过的数字种类集合S。对于所有的x属于S,y属于S,询问在数列中有多少个区间,x,y这两种数字出现次数相同,对于所有的询问求和后输出。
输入格式
第一行:一个数字n
第二行n个数字表示数列A
输出格式
输出1行表示问题的答案
样例输入
2
1 2
样例输出
7
数据范围与约定
n <= 8000, 其他数字在int范围内
样例解释
一共有三种不同的询问
A 询问1,1 共有3个区间
B 询问1, 2共有1个区间
C 询问2,2共有3个区间
—————————————————————————————
这道题就n^2枚举区间 然后记录每个点的出现次数 以及每种出现次数的
就好了
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define LL long long
using namespace std;
int read(){
int ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
const int M=1e4+;
int n,s[M],sq,ss[M];
LL h[M],f[M],ans,sum;
int main()
{
n=read();
for(int i=;i<=n;i++) s[i]=read(),ss[i]=s[i];
sort(ss+,ss++n);
sq=unique(ss+,ss++n)-ss-;
for(int i=;i<=n;i++) s[i]=lower_bound(ss+,ss++n,s[i])-ss;
for(int i=;i<=n;i++){
memset(h,,sizeof(h));
memset(f,,sizeof(f));
sum=sq*(sq+)/;
h[]=sq;
for(int j=i;j<=n;j++){
sum=sum-h[f[s[j]]]+h[f[s[j]]+]+;
ans+=sum;
h[f[s[j]]]--; h[f[s[j]]+]++;
f[s[j]]++;
}
}printf("%lld\n",ans);
return ;
}
最新文章
- 爱上MVC3系列~Html.BeginForm与Ajax.BeginForm
- 【HDU】1536 S-Nim
- sign in和sign up区别
- CentOS6.4下安装TeamViewer8
- IOS网络开发概述
- JavaWeb项目开发案例精粹-第4章博客网站系统-005action层
- KVM虚拟化技术简介
- 浅谈C#浅拷贝和深拷贝
- codility上的问题 (22)
- HUD 4473 Exam
- doT.js实例详解
- Spring的IOC分析(一)
- 微软推出了Cloud Native Application Bundles和开源ONNX Runtime
- md5加密utils
- 分页控件 AspNetPager的使用
- python第四十九课——对象序列化与反序列化
- css postion 属性区别【原】
- 重写equals()方法也要重写hashcode()方法
- 模仿std::vector写线性表的几点感想
- Service Fabric 用 Powershell 部署应用到本地
热门文章
- 2、Java并发编程:如何创建线程
- 从浏览器或者Webview 中唤醒APP
- vux用法
- lua优化
- tomcat8编码设置和gc异常解决
- 《鸟哥的Linux私房菜》读书笔记
- 【tips】【词频统计】中可能用到的资源,以C++为例
- Android之ViewPager 第二课
- java课程设计——2048
- SQLErrorCodes loaded: [DB2, Derby, H2, HSQL, Informix, MS-SQL, MySQL, Oracle, PostgreSQL, Sybase