2024年12月18日下午测试

skimlight · 2024-12-18 22:40:23 · 个人记录

T2

没想到前缀和了，考试的时候算时间复杂的算错了，其实就是吧遍历求和的部分替换成前缀和就好了。

错误代码：

#include<bits/stdc++.h>//100 

#define int long long

using namespace std;

int n,q;
int a[200005];
int x,y;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//  freopen("b.in","r",stdin);
//  freopen("b.out","w",stdout);
    cin >> n >> q;
    for(int i=1;i<=n;++i)cin >> a[i];
    sort(a+1,a+n+1);
    while(q--)
    {
        cin >> x >> y;
        int ans=0;
        for(int i=n-x+1;i<=n-x+y;++i)
        {
            ans+=a[i];
        }
        cout << ans << "\n"; 
    } 
    return 0;
}

正确代码：

#include<bits/stdc++.h>//100 

#define int long long

using namespace std;

int n,q;
int a[200005],cnt[200005];
int x,y;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//  freopen("b.in","r",stdin);
//  freopen("b.out","w",stdout);
    cin >> n >> q;
    for(int i=1;i<=n;++i)cin >> a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;++i)cnt[i]=cnt[i-1]+a[i]; 
    while(q--)
    {
        cin >> x >> y;
        int l=n-x+1,r=n-x+y;
        cout << cnt[r]-cnt[l-1] << "\n"; 
    } 
    return 0;
}

T3

全排列的搜索加去重，去重可以用map做，全排列函数next_permutation。

#include<bits/stdc++.h>

#define int long long

using namespace std;

int n,k,ans=0;
string s;
bool hw(string s)
{
    for(int i=0;i<s.size();++i)if(s[i]!=s[s.size()-i-1])return 0;
    return 1;
} 

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//  freopen("c.in","r",stdin);
//  freopen("c.out","w",stdout);
    cin >> n >> k >> s;
    sort(s.begin(),s.end());
    do
    {
        bool f=1;
        for(int i=0;i<s.size()-k+1;++i) 
        {
            string tmp;
            for(int j=i;j<i+k;++j)tmp.push_back(s[j]);
            if(hw(tmp)==1)
            {
                f=0;
                break;
            } 
        }
        if(f==1)ans++; 
    }while(next_permutation(s.begin(),s.end()));
    cout << ans;
    return 0;
}

T5

动态规划的10背包变形问题，dp[j]=max(dp[j],dp[j-c]+p);

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int dp[50005];
int main(){
    int t;
    cin>>t;
    while(t--){
        memset(dp,0,sizeof dp);
        int n,P,Q;
        cin>>n>>P>>Q;
        int p[105],c[105];
        for(int i=1; i<=n; i++){
            cin>>p[i]>>c[i];
        }
        for(int i=1; i<=n; i++){
            for(int j=Q; j>=c[i];j--){
                dp[j]=max(dp[j],dp[j-c[i]]+p[i]);
            }
        }
        int flag=1;
        for(int i=1; i<=Q; i++){
            if(dp[i]>=P){
                cout<<i<<"\n";
                flag=0;
                break;
            }
        }
        if(flag==1) cout<<"-1\n";
    }
    return 0;
}