题解 - Wqh R13 - A - 洛谷仓库

如果没有代码出现的话，请刷新。

0 分的可能

没开 long long。
$k$ 可能为负数。
没特判 $n=1$ 。
输出空格写成换行。
没写代码或乱写代码。
脑残。

30 分做法 - O( $Q \times n$ )

暴力递推求出每次答案。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[10000005];
signed main(){
	int q,k;
	cin>>q>>k;
	while(q--){
		int n;
		cin>>n;
		a[1]=5;
		for(int i=2;i<=n;i++){
			if(i%2==0) a[i]=a[i-1]+1;
			else a[i]=a[i-2]+k;
		}
		cout<<a[n]<<" ";
	}
	return 0;
}

60 分做法 - O( $Q + \max(n)$ )

在 30 分做法上加上预处理，避免重复计算。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e7+5;
int a[10000005];
signed main(){
	int q,k;
	cin>>q>>k;
	a[1]=5;
	for(int i=2;i<=maxn;i++){
		if(i%2==0) a[i]=a[i-1]+1;
		else a[i]=a[i-2]+k;
	}
	while(q--){
		int n;
		cin>>n;
		cout<<a[n]<<" ";
	}
	return 0;
}

100 分做法 - O( $Q$ )

直接找规律，第

1,3,5,7

个数分别是

5,5+k \times 1,5+k \times 2,5+k \times 3 \cdots

，推出：

A_n=5+(n-2) \div 2 \times k (n \bmod 2 = 1)

因为

A_i(i \bmod 2 = 0)=A_{i-1}+1

，所以：

A_n=6+(n-2) \div 2 \times k (n \bmod 2 = 0)

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
	int q,k;
	cin>>q>>k;
	while(q--){
		int n;
		cin>>n;
		if(n%2==0) cout<<6+(n-2)/2*k<<" ";
		else cout<<5+(n-1)/2*k<<" ";
	}
	return 0;
}

题解 - Wqh R13 - A

文章操作

0 分的可能

30 分做法 - O( $Q \times n$ )

60 分做法 - O( $Q + \max(n)$ )

100 分做法 - O( $Q$ )

相关推荐

评论

题解 - Wqh R13 - A

文章操作

0 分的可能

30 分做法 - O(Q×nQ \times nQ×n)

60 分做法 - O(Q+max⁡(n)Q + \max(n)Q+max(n))

100 分做法 - O(QQQ)

相关推荐

评论

30 分做法 - O( $Q \times n$ )

60 分做法 - O( $Q + \max(n)$ )

100 分做法 - O( $Q$ )