考试总结

· · 个人记录

考试总结

本人反思了一下爆零没考好的原因，可能是因为最近太颓废不细心。

第一题 寻找朋友

题目分析：将字符串和数字排序后依次输出即可。

为什么我会错呢？因为我输入时是从1开始，排序却是从0开始，最后一个没排进去样例也太水了。

代码

#include<bits/stdc++.h>
using namespace std;
string a[200001];
int b[200001];
int main(){
    int n;
    freopen("find.in","r",stdin);
    freopen("find.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    for(int i=1;i<=n;++i)
        cin>>b[i];
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    for(int i=1;i<=n;++i)
        cout<<a[i]<<' '<<b[i]<<endl;
    return 0;
}

第二题 摆放棋子

题目分析：用递推的算法，得出公式f[i][j]=f[i-1][j]+f[i][j-1]，如果i=1或者j等于1时，f[i][j]=i+j。

错误原因：在初始化边际时错了。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll f[10000][10000];
int main(){
    int h,l;
    freopen("chessman.in","r",stdin);
    freopen("chessman.out","w",stdout);
    cin>>h>>l;
    for(ll i=1;i<=h;++i)
        for(ll j=1;j<=l;++j)
            if(i==1||j==1)
                f[i][j]=i+j;
            else
                f[i][j]=f[i-1][j]+f[i][j-1];
    cout<<f[h][l];
    return 0;
}

第三题

一个二维前缀和搞定。

核心代码

    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+z[i][j];
    for(int i=r;i<=n;++i)
        for(int j=c;j<=m;++j){
            f[i][j]=b[i][j]-b[i-r][j]-b[i][j-c]+b[i-r][j-c];
            ans=max(ans,f[i][j]);
        }

第四题

用dp即可解决。前提得排序。动态转移方程为：当j<i &&r[j]<l[i]时f[i]=f[j]+sum[i]还要初始化f[i]=sum[i]。

核心代码

    for(int i=r;i<=n;++i){
        f[i]=t[i].sum;
        for(int j=c;j<i;++j)
            if(t[j].r<t[i].l)
                f[i]=max(f[i],f[j]+t[i].sum);
        ans=max(ans,f[i]);
    }