223847比赛总结

LIUHAOYU2013 · 2025-01-08 22:09:50 · 个人记录

开篇语

比赛网址

在寒假模拟赛总结（2025年1月8日）

加油努力，最后没考好！

T1

其实就是一道模板题直接AC，这是代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, a, f[35];
signed main()
{
    cin >> n;
    while(n --)
    {
        cin >> a;
        f[1] = 1;
        f[2] = 1;
        if(a == 1 || a == 2)
        {
            cout << 1 << "\n";
            continue;
        }
        for(int i = 3; i <= a; i ++)
        {
            f[i] = f[i - 1] + f[i - 2];
            if(i == a)
            {
                cout << f[a] << "\n";
            }
        }
    }
    return 0;
}

T2

这一道题也是模板题（但因为我模板不熟练）所以WA了，错误原因：模板错误，错误代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2000005;
int n, a[N];
int f[N];
signed main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];

    int ans = 0;
    f[1] = 1;
    f[2] = 1;
    for(int i = 3; i <= n; i ++)
    {
        for(int j = 1; j < i; j ++)
        {
            if(a[i] > a[j])
                f[i] = max(a[i], f[j] + a[i]);
        }
    }
    for(int i = 1; i <= n; i ++)
        ans = max(ans, f[i]);
    cout << ans << "\n";
    return 0;
}

正确思路动态dp：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200005;
int n, a[N], maxi = -1e9, dp[N];
signed main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i) cin >> a[i];
    dp[1] = a[1];
    for(int i = 2; i <= n;++ i) dp[i] = max(dp[i - 1] + a[i], a[i]);
    for(int i = 1; i <= n; ++ i) maxi = max(dp[i], maxi);
    cout << maxi << "\n";   
    return 0;
}

T3

最长上升子序列，这一道题纯属脑袋一热一通乱写，0分代码（错误点最后ans的赋值和for循环中的赋值其实就是模板）：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5005;
int n, a[N], f[N], ans;
signed main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    f[1] = 1;
    f[2] = 1;
    for(int i = 2; i <= n; i ++)
    {
        for(int j = 1; j < j; j ++)
        {
            if(a[i] > a[j])
                f[i] = max(a[i], a[j] + 1);
        }
    }
    for(int i = 1; i <= n; i ++)
        ans = max(a[i], f[i]);
    cout << ans << "\n";
    return 0;
}

AC更改代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[5005],f[5005];
signed main()
{
    int n,maxx=-1e9;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        f[i]=1;
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i])
            {
                f[i]=max(f[i],f[j]+1);
            }
        }
        maxx=max(maxx,f[i]);
    }
    cout<<maxx;
    return 0;
} 

T4

这道题考研数学思维，可是我数学不错过于自大所以AC，代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, ans = 1000000;
signed main()
{
    cin >> n;
    for(int i = 0; i <= n; i ++)
    {
        for(int j = 0 ; j <= n; j ++)
        {
            if(i * 5 + j * 3 == n)
            {
                if(i + j < ans)
                {
                    ans = i + j;
                }
            }
        }
    }
    if(ans == 1000000)
    {
        cout << -1 << "\n"; 
    }
    else
    {
        cout << ans;
    }
    return 0;
}

T5

这道题是根本不会做，只能骗骗分。其实就是用f数组去判断，找规律。这里就没必要看骗分代码了，直接看AC的。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 55;
int f[N][N];
int n, m;
signed main()
{
    cin >> n >> m;
    f[1][2] = f[1][n] = 1;
    for(int i = 2; i <= m; i ++)
    {
        for(int j = 1; j <= n; j ++)
        {
            if(j == 1) f[i][j] = f[i - 1][n] + f[i - 1][2];
            else if(j == n) f[i][j] = f[i - 1][n - 1] + f[i - 1][1];
            else f[i][j] = f[i - 1][j - 1] + f[i - 1][j + 1];
        }
    }
    cout << f[m][1] << "\n";
    return 0;
}

T5

这道题我用结构体排序，结果

18分代码说错误，听取WA声一片。

然后再老师的指导后改了亿下。

#include <bits/stdc++.h>
using namespace std; 
#define int long long
const int N = 5005;
int n;
int sum;
struct node{
    int c, k, ch;
}a[N];
bool cmp(node x, node y)
{
    return x.ch > y.ch;
}
signed main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> a[i].c >> a[i].k;
    sort(a + 1, a + 1 + n, cmp);
    for(int i = 1; i <= n; i ++)
    {
        if(a[i].c > a[i - 1].k)
            sum ++;
    }
    cout << sum << "\n";
    return 0;
}

AC代码：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int l,r;
} a[10005];
int n;
int dp[10005],ans;
bool cmp(node x,node y){ 
    if(x.l==y.l){
        return x.r<y.r;
    }
    return x.l<y.l;
}
int main() 
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].l>>a[i].r;
    } 
    sort(a+1,a+1+n,cmp);
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<i;j++) 
        {
            if(a[j].r>a[i].r) 
            {
                dp[i]=max(dp[j]+1,dp[i]);
            }
        }
        ans=max(dp[i],ans); 
    }
    cout<<ans+1; 
    return 0; 
}

总结到此结束endl

这次没发挥好，下次努力！

加油！奥里给！