COGS 2685. 迷妹
2024-08-31 03:59:28
★ 输入文件:fans.in
输出文件:fans.out
简单对比
时间限制:1 s 内存限制:256 MB
【题目描述】
小钟、小皓和小曦都是著名偶像派OI选手,他们都有很多迷妹。
现在,有n个妹子排成了一行,从左到右编号为1到n。这些妹子中,任意一个都是其中一个人的迷妹。
现在,蒟蒻wyz有Q个问题,第i个问题为:编号在l[i]到r[i]范围内的妹子中,分别有几个小钟的迷妹、小皓的迷妹、和小曦的迷妹。
【输入格式】
输入到fans.in
第一行2个正整数n,Q。
第2行到第n+1行每行一个正整数a[i],描述了第i个妹子是谁的迷妹。a[i]=1表示小钟的迷妹,a[i]=2表示小皓的迷妹,a[i]=3表示小曦的迷妹。
第n+2行到第n+Q+1行,每行2个整数,表示第i个问题。
【输出格式】
输出到fans.out
共Q行,每行3个用空格分开的整数,分别表示对于第i个问题,有多少小钟、小皓、小曦的迷妹。
【样例输入】
6 3
2
1
1
3
2
1
1 6
3 3
2 4
【样例输出】
3 2 1
1 0 0
2 0 1
【提示】
【数据范围】
对于10%的数据,保证1<=n<=10,Q<=10,
对于25%的数据,保证1<=n<=100,Q<=100,
对于45%的数据,保证1<=n<=1000,Q<=1000,
对于100%的数据,保证1<=n<=100,000,Q<=100,000。
保证1<=a[i]<=3,1<=l[i]<=r[i]<=n。
【来源】
QBXT2017春令营第一次测试T1
做法1
很水的前缀和
#include <ctype.h>
#include <cstdio> void read(int &x)
{
x=;bool f=;
register char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=;
for(; isdigit(ch);ch=getchar()) x=x*+ch-'';
x=f?(~x)+:x;
}
int n,q,sum[][];
int main()
{
freopen("fans.in","r",stdin);freopen("fans.out","w",stdout);
read(n);read(q);
for(int opt,i=;i<=n;i++)
{
read(opt);
if(opt==)
{
sum[i][]=sum[i-][]+;
sum[i][]=sum[i-][];
sum[i][]=sum[i-][];
}
else if(opt==)
{
sum[i][]=sum[i-][];
sum[i][]=sum[i-][]+;
sum[i][]=sum[i-][];
}
else
{
sum[i][]=sum[i-][];
sum[i][]=sum[i-][];
sum[i][]=sum[i-][]+;
}
}
for(int x,y;q--;)
{
read(x);read(y);
printf("%d %d %d\n",sum[y][]-sum[x-][],sum[y][]-sum[x-][],sum[y][]-sum[x-][]);
}
return ;
}
改掉我前缀和的脑残求和 竟然慢了 !。。
#include <ctype.h>
#include <cstdio>
void read(int &x)
{
x=;bool f=;
register char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=;
for(; isdigit(ch);ch=getchar()) x=x*+ch-'';
x=f?(~x)+:x;
}
int n,q,sum[][];
int main()
{
freopen("fans.in","r",stdin);freopen("fans.out","w",stdout);
read(n);read(q);
for(int opt,i=;i<=n;i++)
{
read(opt);
sum[i][opt]=;
sum[i][]+=sum[i-][];
sum[i][]+=sum[i-][];
sum[i][]+=sum[i-][];
}
for(int x,y;q--;)
{
read(x);read(y);
printf("%d %d %d\n",sum[y][]-sum[x-][],sum[y][]-sum[x-][],sum[y][]-sum[x-][]);
}
return ;
}
做法2
很水的树状数组
#include <ctype.h>
#include <cstdio> void read(int &x)
{
x=;
bool f=;
register char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=;
for(; isdigit(ch);ch=getchar()) x=x*+ch-'';
x=f?(~x)+:x;
}
int n,q;
struct bit
{
int sum[];
int lowbit(int x) {return x&((~x)+);}
int query(int x)
{
int ans=;
for(;x;x-=lowbit(x)) ans+=sum[x];
return ans;
}
void plus(int x,int y)
{
for(;x<=n;x+=lowbit(x)) sum[x]+=y;
}
}a[];
int main()
{
freopen("fans.in","r",stdin);
freopen("fans.out","w",stdout);
read(n);read(q);
for(int opt,i=;i<=n;i++)
{
scanf("%d",&opt);
a[opt].plus(i,);
}
for(int x,y;q--;)
{
read(x);read(y);
printf("%d %d %d\n",a[].query(y)-a[].query(x-),a[].query(y)-a[].query(x-),a[].query(y)-a[].query(x-));
}
return ;
}
最新文章
- windows上如何搭建Git Server
- java中创建字符串的两种方式(“”与new String())及区别
- java删除文件
- 2.一起来学hibernate之配置文件1与持久化对象
- UStore-添加自定义工作流(JDF)到产品
- 禁止apache显示目录索引的常见方法(apache禁止列目录)
- mybatis 如何查找表里的某一个字段,然后返回它们的结果集list ?
- Label &; TextBlock
- 异常getaddrinfo enotfound
- C++容器类对象函数參数问题
- Rsync和FastDFS
- 「Poetize4」玉蟾宫
- 最全的TV视频应用合集,包含50多款客户端,有丰富直播点播
- sqlite 查询数据 不用回调
- IE7下浮动元素的内容自动换行的BUG解决方法
- cglib应用
- Hadoop记录-切换NN
- 翻译:delete语句(已提交到MariaDB官方手册)
- 使用Intellij IDEA将web项目导出为war包
- 4. API之打印函数
热门文章
- POJ - 2115 C Looooops(扩展欧几里德求解模线性方程(线性同余方程))
- MyBatis学习 之 七、mybatis各种数据库的批量修改
- Android应用开发完全退出程序的通用方法
- Android之APP模块编译
- PCB 线路铜皮面积(残铜率)计算的实现方法
- [原]Windows下openssl的下载安装和使用
- 北京师范大学第十四届ACM决赛-重现赛 F:Training Plan(DP)
- “玲珑杯”线上赛 Round #17 河南专场 B:震惊,99%+的中国人都会算错的问题(容斥计算)
- Android中R.java丢失不见的解决方案
- 关于${pageContext.request.contextPath}的理解(转载)