卓越盃發生的常見問題

DP 時狀態不足

這題應該需要兩種狀態

1. 這一天有超過
2. 這一天沒有超過

#include <bits/stdc++.h>
using namespace std;
int dp[100005];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,t;
    cin>>n>>t;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    if(a[0]>t&&a[0]>a[1]) dp[0]=a[0];
    else if(a[0]>t) dp[0]=t;
    else dp[0]=a[0];
    for(int i=1;i<n;i++){
        if(i==n-1) dp[i]=dp[i-1]+a[i];
        else if(a[i]>t&&a[i]>a[i+1]) dp[i]=dp[i-1]+a[i];
        else if(a[0]>t) dp[i]=dp[i-1]+t;
        else dp[i]=dp[i-1]+a[i];
    }
    cout<<dp[n-1]<<'\n';
    return 0;
}

或是合併

#include<iostream>
using namespace std;
int main(){
    int a,b,arr[100010],dp[100010];
    cin>>a>>b;
    for (int i=0;i<a;i++) cin>>arr[i];
    dp[0]=arr[0];
    if (arr[0]>b) dp[1]=max(dp[0],arr[1]);
    else dp[1]=dp[0]+arr[1];
    for (int i=0;i<a;i++){
        if (arr[i-1]>b) dp[i]=max(dp[i-1],dp[i-2]+arr[i]);
        else dp[i]=dp[i-1]+arr[i];
    }
    cout<<dp[a-1];
    return 0;
}

嘗試用浮點數做高精度計算

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    long long n;
    cin >> n;
    
    long long k = 54*pow(2,n);
    long long t = pow(10,9) + 7; 
    cout << (long long)(k%t); 
}

時間複雜度(想偷分阿)

\(O(n)\) ，題目預設要求 \(O(\log(n))\)

#include<iostream>
using namespace std;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    long long a,b=2;
    long long r=54;
    cin>>a;
    for (int i=0;i<a;i++){
        r*=2;
        r%=1000000007;
    }
    cout<<r;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n;
    cin>>n;
    int t=1;
    if(n==0) cout<<54<<'\n';
    else{
        for(int i=0;i<n;i++){
            t=t*2%1000000007;
        }
        cout<<54*t;
    }
    return 0;
}
//我來亂的

我們的 judge 真口黏

常數優化同學 XxRoyxX

40 分，有想法耶同學

#include<bits/stdc++.h>
 
using namespace std;
 
long long a,b=54;
 
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	
	cin>>a;
	for(int i=0;i<a;i++)
	{
		b=b*2;
		if(b>1000000007) b-=1000000007;
	}
	cout<<b;
}

幫你做到極限(有AC)

#include<bits/stdc++.h>
using namespace std;
 
long long a,b=54;
 
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	
	cin>>a;
	int i;
	for(i=0;i+30<a;i+=30)
	{
		b<<=30;
		b%=1000000007;
	}
	b=(b<<(a-i))%1000000007;
	cout<<b;
}

索引值

除此之外還有其他問題，大家來找找

#include<bits/stdc++.h>
using namespace std;
vector<string> v;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int n,q,a[1005];
    cin>>n>>q;
    for(int i=0;i<q;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>v[i];
    for(int i=0;i<q;i++){
        cout<<v[a[i]]<<'\n';
    }
    return 0;
}

字串沒有用 getline

#include<bits/stdc++.h>
#define eb emplace_back
using namespace std;
vector<string> v;
int main(){
    string s;
    int a,b,c;
    cin>>a>>b; cin.ignore();
    for (int i=0;i<b;i++){
        cin>>s;
        v.eb(s);
    }
    for (int i=0;i<a;i++){
        cin>>b>>c;
        cout<<v[b-1][c-1];
    }
    return 0;
}