@CQUPTacm
2018-11-14T14:01:46.000000Z
字数 9003
阅读 3044
题解
按照题意的描述把数列的每个数的平方加起来就行了。善良的出题人保证了答案在int的表示范围之内。
时间复杂度o(T*N),空间复杂度o(N)。
代码
//C++
#include<iostream>
#include<cstdio>
using namespace std;
int num[1005];
int main()
{
int t,n,ans;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
ans=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&num[i]);
ans+=num[i]*num[i];
}
printf("%d\n",ans);
}
return 0;
}
//Java
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
int t=cin.nextInt();
int n,ans;
int[] num=new int[1005];
while(t>0){
t--;
n=cin.nextInt();
ans=0;
for(int i=1;i<=n;i++){
num[i]=cin.nextInt();
ans+=num[i]*num[i];
}
System.out.println(ans);
}
}
}
根据中位数的定义,如果我们先把数列排序,那么当N为奇数时,中位数就是数列中间位置的那个数,当N为偶数时,中位数就是数列中间位置的那两个数的平均值。
对于N<=1000的数据规模,我们可以采取冒泡排序或者选择排序等时间复杂度为o(N^2)的方法。这里提供的是选择排序的版本。
时间复杂度o(T*N^2),空间复杂度o(N)。
代码
//C++
#include<iostream>
#include<cstdio>
using namespace std;
int num[1005];
int main()
{
int t,n,temp;
double ans;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
{
if(num[j]<num[i])
{
temp=num[i];
num[i]=num[j];
num[j]=temp;
}
}
if(n%2==1)
ans=num[(n+1)/2];
else
ans=(num[n/2]+num[n/2+1])*0.5;
printf("%.2f\n",ans);
}
return 0;
}
//Java
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
int t=cin.nextInt();
int n,temp;
double ans;
int[] num=new int[1005];
while(t>0){
t--;
n=cin.nextInt();
for(int i=1;i<=n;i++)
num[i]=cin.nextInt();
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++){
if(num[j]<num[i]){
temp=num[i];
num[i]=num[j];
num[j]=temp;
}
}
if(n%2==1)
ans=num[(n+1)/2];
else
ans=(num[n/2]+num[n/2+1])*0.5;
System.out.println(String.format("%.2f", ans));
}
}
}
枚举从(a,b]中的每个数,如果这个数满足题目的两个条件,那么安排数的个数加一。最后输出有多少个安排数即可。
时间复杂度o(T*(b-a)),空间复杂度o(1)。
代码
//C++
#include<iostream>
#include<cstdio>
using namespace std;
bool have7(int x)
{
while(x!=0)
{
if(x%10==7)
return 1;
x=x/10;
}
return 0;
}
int main()
{
int t,a,b,ans;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&a,&b);
ans=0;
for(int i=a+1;i<=b;i++)
{
if(i%7==0 && have7(i))
ans++;
}
printf("%d\n",ans);
}
return 0;
}
//Java
import java.util.*;
import java.io.*;
public class Main {
public static boolean have7(int x){
while(x!=0){
if(x%10==7)
return true;
x=x/10;
}
return false;
}
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
int t=cin.nextInt();
int a,b,ans;
while(t>0){
t--;
ans=0;
a=cin.nextInt();
b=cin.nextInt();
for(int i=a+1;i<=b;i++){
if(i%7==0 && have7(i))
ans++;
}
System.out.println(ans);
}
}
}
题目和B几乎相同,区别在于数据范围。
对于N<=100000而且ai<=1000000000的数据规模,我们可以采取快速排序、归并排序或者堆排序等时间复杂度为o(N*log(N))的方法。这里提供的是库函数排序的版本。
这里给出一个三种常见o(N*log(N))排序方法的伪代码版本(java),有兴趣的同学可以查看,并自行进行更深入的了解。blog.csdn.net/wkyworkuno/article/details/66091709
时间复杂度o(T*N*log(N)),空间复杂度o(N)。
代码
//C++
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int num[100005];
int main()
{
int t,n,temp;
double ans;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
ans=0;
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
sort(num+1,num+1+n);
if(n%2==1)
ans=num[(n+1)/2];
else
ans=(num[n/2]+num[n/2+1])*0.5;
printf("%.2f\n",ans);
}
return 0;
}
//Java
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
int t=cin.nextInt();
int n,temp;
double ans;
int[] num=new int[100005];
while(t>0){
t--;
n=cin.nextInt();
for(int i=1;i<=n;i++)
num[i]=cin.nextInt();
Arrays.sort(num,1,1+n);
if(n%2==1)
ans=num[(n+1)/2];
else
ans=(num[n/2]+num[n/2+1])*0.5;
System.out.println(String.format("%.2f", ans));
}
}
}
题目和C几乎相同,区别在于数据范围。
对于T<=100000的数据范围,如果时间复杂度还是o(T*(b-a)),那么肯定会超时。
这里我们要用到一个小技巧:区间和等于两个前缀和的差。
具体来说,如果S[i]表示a[1]+a[2]+……+a[i]的和,那么a[l+1]+a[l+2]+……+a[r]就可以用S[r]-S[l]来表示。所以我们只需要求出S数组即可。
时间复杂度o(max(b)+T),空间复杂度o(max(b)+T)。
代码
//C++
#include<iostream>
#include<cstdio>
using namespace std;
int ans[1000005];
bool have7(int x)
{
while(x!=0)
{
if(x%10==7)
return 1;
x=x/10;
}
return 0;
}
int main()
{
int t,a,b;
scanf("%d",&t);
for(int i=1;i<=1000000;i++)
{
ans[i]=ans[i-1];
if(i%7==0 && have7(i))
ans[i]++;
}
while(t--)
{
scanf("%d%d",&a,&b);
printf("%d\n",ans[b]-ans[a]);
}
return 0;
}
//Java
import java.util.*;
import java.io.*;
public class Main {
public static boolean have7(int x){
while(x!=0){
if(x%10==7)
return true;
x=x/10;
}
return false;
}
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
int t=cin.nextInt();
int[] ans=new int[1000005];
int a,b;
for(int i=1;i<=1000000;i++){
ans[i]=ans[i-1];
if(i%7==0 && have7(i))
ans[i]++;
}
while(t>0){
t--;
a=cin.nextInt();
b=cin.nextInt();
System.out.println(ans[b]-ans[a]);
}
}
}
朴素的想法是枚举数列中的任何一对数,求出他们的最大公因数加到答案中。这样计算一组数据的时间复杂度o(f*N^2),这里的f指的是求两个数的gcd所耗费的时间。即使这个f非常小,光是N^2已经很大了,而且还要乘上组数T,所以这样肯定会超时。
我们换个思路:如果x和y都是z的倍数,那么gcd(x,y)肯定是z的倍数。如果有k个数都是z的倍数,那么在这k个数中任意选择一对,他们的gcd肯定也是z的倍数,所以我们只需要求出对于每个z数列中有多少个数是z的倍数即可。如果对于每个z,我们知道数列中有多少对数字的gcd恰好等于z,那么我们把对数和z相乘,就是这个值对答案的贡献,枚举z把贡献算出来全加上,就是答案。
我们注意到,之前我们说的是gcd是z的倍数,但是我们要求的是gcd恰好为z的。所以我们要将gcd是z的倍数(包括z)的数字有多少对,减去gcd是z的倍数(不包括z)的数字有多少对,剩下的就是gcd恰好为z的。举个例子:我们用gcd=5的倍数对数减去gcd恰好为10、gcd恰好为15、……剩下的就是gcd恰好为5的。
关于如何计算每个z在数列中有多少个倍数,我们可以反过来,对于数列中每个数,把它的因数的出现次数加一。枚举x的因数的时间复杂度是o(sqrt(x))。
同样,我们也不必枚举每个z的倍数再减去。我们可以从大到小枚举z,当前z的每个因数(除了z本身),都要减去gcd恰好为z的,我们用另外一个数组储存。同样,对于每个z,枚举因数的时间复杂度是o(sqrt(z))。
这样我们可以从大到小算出gcd恰好等于每个z的数字的对数,乘上z再加起来,就是最终答案。因为两个正整数的gcd肯定小于等于他们当中较小的那个,所以z不会超过数列数字的上限。
时间复杂度o(T*(max(a)+N)*sqrt(max(a))),空间复杂度o(max(a)+N)。
代码
//C++
#include<iostream>
#include<cstdio>
using namespace std;
int a[10005];
long long del[10005];
long long nums[10005];
long long ans[10005];
int main()
{
int t,n;
long long sumans;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
sumans=0;
for(int i=1;i<=10000;i++)
nums[i]=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
for(int j=1;j*j<=a[i];j++)
{
if(a[i]%j==0)
{
nums[j]++;
if(a[i]/j!=j)
nums[a[i]/j]++;
}
}
}
for(int i=1;i<=10000;i++)
del[i]=0;
for(int i=10000;i>1;i--)
{
ans[i]=(nums[i]*(nums[i]-1))/2-del[i];
del[1]+=ans[i];
for(int j=2;j*j<=i;j++)
{
if(i%j==0)
{
del[j]+=ans[i];
if(j!=i/j)
del[i/j]+=ans[i];
}
}
}
ans[1]=(nums[1]*(nums[1]-1))/2-del[1];
for(int i=1;i<=10000;i++)
sumans+=i*ans[i];
printf("%lld\n",sumans);
}
return 0;
}
//Java
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
int t=cin.nextInt();
int[] a=new int[10005];
long [] nums=new long[10005];
long [] ans=new long[10005];
long [] del=new long[10005];
long sumans;
int n;
while(t>0){
t--;
sumans=0;
n=cin.nextInt();
for(int i=1;i<=10000;i++)
nums[i]=0;
for(int i=1;i<=n;i++){
a[i]=cin.nextInt();
for(int j=1;j*j<=a[i];j++){
if(a[i]%j==0){
nums[j]++;
if(a[i]/j!=j)
nums[a[i]/j]++;
}
}
}
for(int i=1;i<=10000;i++)
del[i]=0;
for(int i=10000;i>1;i--){
ans[i]=(nums[i]*(nums[i]-1))/2-del[i];
del[1]+=ans[i];
for(int j=2;j*j<=i;j++){
if(i%j==0){
del[j]+=ans[i];
if(j!=i/j)
del[i/j]+=ans[i];
}
}
}
ans[1]=(nums[1]*(nums[1]-1))/2-del[1];
for(int i=1;i<=10000;i++)
sumans+=i*ans[i];
System.out.println(sumans);
}
}
}
F(i+1)=F(i)+F(i-1)。
我们构造一个2*1的矩阵M[i]={{F(i-1)},{F(i)}},再构造一个2*2的矩阵A={{0,1},{1,1}},根据矩阵乘法如果M[i]左乘上A,结果是一个2*1的矩阵{{F[i]},{F[i]+F[i-1]}}即{{F[i]},{F[i+1]}},我们记为矩阵M[i+1]。很明显,M[i]左乘j次A,结果就是M[i+j]。
S1(i+1)=S1(i)+F(i+1)=S1(i)+F(i)+F(i-1)。
S2(i+1)=S2(i)+S1(i+1)=S2(i)+S1(i)+F(i+1)=S2(i)+S1(i)+F(i)+F(i-1)。
以此类推。
可以想象,如果我们构造一个10*1的矩阵M[i]={{F(i-1)},{F(i)},{S1(i)},{S2(i)},{S3(i)},{S4(i)},{S5(i)},{S6(i)},{S7(i)},{S8(i)}},也会存在一个10*10的矩阵A令A*M[i]=M[i+1]。
这样我们可以通过构造M[1]和A,让M[1]左乘N-1次A求得M[N],M[N]的最后一行就是S8(N)。这样做的时间复杂度是o(100*N),不用我说你们也知道会超时了,这甚至比暴力计算还满。
但是矩阵乘法是满足结合律的(圈起来,这个要考)。我们可以将A的N-1次方进行二进制分解,比如A^7=A^4*A^2*A,如果我们事先求得矩阵A的1次方(即A本身)、2次方、4次方、8次方、16次方……我们就可以通过将这些矩阵中的一部分相乘求出A^(N-1)。很容易看出来N最多分解为log2(N)项。所以时间复杂度就变成了o(1000*log2(N))。这里的1000表示的是10*10的两个方阵相乘的复杂度,而之前的100指的是10*1的矩阵左乘10*10的矩阵。
时间复杂度o(T*1000*log2(N)),空间复杂度o(100)。
代码
//C++
#include<iostream>
#include<cstdio>
using namespace std;
#define mod 1000000007
struct Node
{
long long num[10][10];
friend Node operator *(Node x1,Node x2)
{
Node x3;
for(int i=0;i<10;i++)
for(int j=0;j<10;j++)
x3.num[i][j]=0;
for(int i=0;i<10;i++)
for(int k=0;k<10;k++)
for(int j=0;j<10;j++)
x3.num[i][j]=(x3.num[i][j]+x1.num[i][k]*x2.num[k][j])%mod;
return x3;
}
}A,E;
Node ksm(long long y)
{
Node nowans=E,x=A;
while(y)
{
if(y%2)
nowans=x*nowans;
x=x*x;
y=y/2;
}
return nowans;
}
int main()
{
for(int i=0;i<10;i++)
E.num[i][i]=1;
A.num[0][1]=1;
for(int i=1;i<10;i++)
for(int j=0;j<=i;j++)
A.num[i][j]=1;
int t;
long long n,ans;
scanf("%d",&t);
while(t--)
{
scanf("%lld",&n);
ans=0;
Node now=ksm(n-1);
for(int i=1;i<10;i++)
ans=(ans+now.num[9][i])%mod;
printf("%lld\n",ans);
}
return 0;
}
//Java
import java.util.*;
import java.io.*;
class Node{
long[][] num=new long[10][10];
Node mul(Node x2){
Node x3=new Node();
for(int i=0;i<10;i++)
for(int k=0;k<10;k++)
for(int j=0;j<10;j++)
x3.num[i][j]=(x3.num[i][j]+num[i][k]*x2.num[k][j])%1000000007;
return x3;
}
}
public class Main {
static Node E=new Node(),A=new Node();
static Node ksm(long y){
Node nowans=E,x=A;
while(y!=0){
if(y%2==1)
nowans=nowans.mul(x);
x=x.mul(x);
y=y/2;
}
return nowans;
}
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
for(int i=0;i<10;i++)
E.num[i][i]=1;
A.num[0][1]=1;
for(int i=1;i<10;i++)
for(int j=0;j<=i;j++)
A.num[i][j]=1;
int t;
long n,ans;
t=cin.nextInt();
while(t>0)
{
t--;
n=cin.nextLong();
ans=0;
Node now=ksm(n-1);
for(int i=1;i<10;i++)
ans=(ans+now.num[9][i])%1000000007;
System.out.println(ans);
}
}
}