本文主要是介绍CCF CSP认证 题解:201709-5 除法(Java语言原创),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
问题描述
小葱喜欢除法,所以他给了你 N个数 a 1, a 2, ⋯, aN,并且希望你执行 M次操作,每次操作可能有以下两种:
给你三个数 l, r, v,你需要将 al, al +1, ⋯, ar之间所有 v的倍数除以 v。
给你两个数 l, r,你需要回答 al + al +1 + ⋯ + ar的值是多少。
给你三个数 l, r, v,你需要将 al, al +1, ⋯, ar之间所有 v的倍数除以 v。
给你两个数 l, r,你需要回答 al + al +1 + ⋯ + ar的值是多少。
输入格式
第一行两个整数 N, M,代表数的个数和操作的次数。
接下来一行 N个整数,代表 N个数一开始的值。
接下来 M行,每行代表依次操作。每行开始有一个整数 opt。如果 opt=1,那么接下来有三个数 l, r, v,代表这次操作需要将第 l个数到第 r个数中 v的倍数除以 v;如果 opt = 2,那么接下来有两个数 l, r,代表你需要回答第 l个数到第 r个数的和。
接下来一行 N个整数,代表 N个数一开始的值。
接下来 M行,每行代表依次操作。每行开始有一个整数 opt。如果 opt=1,那么接下来有三个数 l, r, v,代表这次操作需要将第 l个数到第 r个数中 v的倍数除以 v;如果 opt = 2,那么接下来有两个数 l, r,代表你需要回答第 l个数到第 r个数的和。
输出格式
对于每一次的第二种操作,输出一行代表这次操作所询问的值。
样例输入
5 3
1 2 3 4 5
2 1 5
1 1 3 2
2 1 5
1 2 3 4 5
2 1 5
1 1 3 2
2 1 5
样例输出
15
14
14
这题用java很轻松AC,除了要加if(b3==1)continue;之类的小优化外没用到啥就蜜汁AC了。但是用c++的话要用数状数组之类的数据结构,应对大量的增删操作,才能不超时。
public class Main{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
int i,n=in.nextInt();
int m=in.nextInt();
int a[]=new int [n];
for(i=0;i<n;i++){
a[i]=in.nextInt();
}
int a1,b1,b2,b3;
long sum;
for(i=0;i<m;i++){
a1=in.nextInt();
if(a1==1){
b1=in.nextInt();
b2=in.nextInt();
b3=in.nextInt();
if(b3==1)continue;
for(int j=b1-1;j<=b2-1;j++)
if(a[j]>=b3&&a[j]%b3==0)
a[j]=a[j]/b3;
}else if(a1==2){
b1=in.nextInt();
b2=in.nextInt();
sum=0;
for(int j=b1-1;j<=b2-1;j++)
sum+=a[j];
System.out.println(sum);
}
}
in.close();
}
}
这篇关于CCF CSP认证 题解:201709-5 除法(Java语言原创)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!