8.22错题总结

· · 个人记录

T3(T657860 小仓鼠西行记)

考试思路：直接暴搜

考试代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,d[1005],c[1005],ans=1e9;
void dfs(int num,int sx,int sum)
{
    if(num>n)
        return ;
    if(sx>m&&num!=n)
        return ;
    if(num==n)
    {
        ans=min(ans,sum);
        return ;
    }
    dfs(num,sx+1,sum);
    dfs(num+1,sx+1,sum+d[num+1]*c[sx]);
    return ;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>d[i];
    for(int i=1;i<=m;i++)
        cin>>c[i];
    dfs(0,1,0);
    cout<<ans;
    return 0;
}

正确思路：dp[i][j]表示第j天走到第i个城市，花的疲劳值，跟dfs差不多，分第j天走或不走

正确代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,d[1005],c[1005],ans=1e9,dp[1005][1005];
int main()
{
    cin>>n>>m;
    memset(dp,0x3f,sizeof dp);
    for(int i=1;i<=n;i++)
        cin>>d[i];
    for(int i=1;i<=m;i++)
        cin>>c[i];
    dp[0][0]=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            dp[i][j+1]=min(dp[i][j+1],dp[i][j]);
            dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+d[i+1]*c[j+1]);
        }
    }
    for(int i=0;i<=m;i++)
        ans=min(ans,dp[n][i]);
    cout<<ans;
    return 0;
}

T4(P11005 [蓝桥杯 2024 省 Python B] 缴纳过路费)

考试思路：骗分

考试代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    cout<<3;
    return 0;
}

正确思路：要求满足条件的对数，所以求一个连通块的点数。因此选用并查集，满足性质。求最小的线路费用，所以再跑kruskal即可。

正确代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1;
int ans,fa[N],s[N];
struct node
{
    int x,y,w;
}a[N];
bool comp(node a1,node a2)
{
    return a1.w<a2.w;
}
int Father(int x)
{
    if(fa[x]!=x)
        return fa[x]=Father(fa[x]);
    return x;
}
void unionn(int x,int y)
{
    if (x!=y)
        fa[x]=y,s[y]+=s[x];
}
int main()
{
    int n,m,l,r;
    cin>>n>>m>>l>>r;
    for(int i=1;i<=n;i++)
        fa[i]=i,s[i]=1;
    for(int i=1;i<=m;i++)
        cin>>a[i].x>>a[i].y>>a[i].w;
    sort(a+1,a+1+m,comp);
    for(int i=1;i<=m;i++)
    {
        if(a[i].w>r)
            break;
        int x=Father(a[i].x),y=Father(a[i].y);
        if(x==y)
            continue;
        if(a[i].w>=l)
            ans+=s[x]*s[y];
        unionn(x,y);
    }
    cout<<ans;
    return 0;
}

T5(T657862 2038年问题)

考试思路：直接模拟

考试代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int yl[25]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool rn(int nf)
{
    if((nf%4==0&&nf%100!=0)||nf%400==0)
        return 1;
    return 0;
}
void solve()
{
    int cd,nf,yf,rq,h,m,s;
    cin>>cd>>nf>>yf>>rq>>h>>m>>s;
    int ms=pow(2,cd-1);
    ms--;
    s+=ms;
    if(s<60)
    {
        cout<<nf<<' '<<yf<<' '<<rq<<' '<<h<<' '<<m<<' '<<s<<'\n';
        return ;
    }
    m+=(s-(s%60))/60;
    s%=60;
    if(m<60)
    {
        cout<<nf<<' '<<yf<<' '<<rq<<' '<<h<<' '<<m<<' '<<s<<'\n';
        return ;
    }
    h+=(m-(m%60))/60;
    m%=60;
    if(h<60)
    {
        cout<<nf<<' '<<yf<<' '<<rq<<' '<<h<<' '<<m<<' '<<s<<'\n';
        return ;
    }
    rq+=(h-(h%24))/24;
    h%=24;
    if(rq<=yl[yf])
    {
        cout<<nf<<' '<<yf<<' '<<rq<<' '<<h<<' '<<m<<' '<<s<<'\n';
        return ;
    }
    while(rq>yl[yf])
    {
        if(yf!=2)
        {
            rq-=yl[yf];
            yf++;
        }
        else
        {
            if(rn(nf))
                rq-=29;
            else
                rq-=28;
            yf++;
        }
        if(yf>12)
            yf=1,nf++;
    }
    cout<<nf<<' '<<yf<<' '<<rq<<' '<<h<<' '<<m<<' '<<s<<'\n';
    return ;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

正确思路：直接模拟

正确代码：

#include<bits/stdc++.h>
using namespace std;
long long T,jz,ye,mo,da,ho,mi,se;
int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
void change()
{
    if(ye%400==0)
        month[2]=29;
    else if(ye%100!=0 && ye%4==0)
        month[2]=29;
    else
        month[2]=28;
}
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>jz>>ye>>mo>>da>>ho>>mi>>se;
        long long tot=(1<<(jz-1))-1;
        se+=tot;
        mi+=se/60, se%=60;
        ho+=mi/60, mi%=60;
        da+=ho/24, ho%=24;
        if(mo==2)
            change();
        while(da>month[mo])
        {
            da-=month[mo];
            mo++;
            if(mo>12)
                ye++,mo=1;
            if(mo==2)
                change();
        }
        printf("%lld %lld %lld %lld %lld %lld\n",ye,mo,da,ho,mi,se);
    }
    return 0;
}