题解 - Wqh R13 - A

wenqinghua1001 · 2025-10-20 09:59:20 · 题解

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

0 分的可能

• 没开 long long。
• 没特判 n=1。
• 输出空格写成换行。
• 没写代码或乱写代码。
• 脑残。

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

暴力递推求出每次答案。

#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 分做法上加上预处理，避免重复计算。

#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_i(i \bmod 2 = 0)=A_{i-1}+1，所以：

#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;
}