2024常州day3(8.14

Posted on By 林 珂涵 2024常州day3(8.14无评论

今天是非常不GOOD的一天

刷到一个奇怪的一言：王只有一个！那就是我！

以及另一个奇怪的一言： 我要AK！IOI！

今天早上zmx因为昨天迟到，负责叫人起床
他十分的尽职尽责，特别的“善良”
他提早了12分钟叫我们，实在是太"人性化”了
原本6：50起床，他™6：38就把我们叫起来了
沙县小吃实在是太“美味”了:grin:

1.算法及其评价和计算时间

算法及其评价就是优化算法，计算时间复杂度和空间复杂度

（然后就没有然后了
计算时间就是写一个（忘记是什么的）东西，然后在写一个bat就可以了

1.最大子序列和

  • 贪心方法
#include<bits/stdc++.h>//最大子序列（贪心） 
using namespace std;
/*从小到大扫描j（可以同时读入a[j]）：
如果s[j]变大，则min值不变、max变大；
如果s[j]再创新低，应该让s[j]作为今后的min值;*/
//6 -1 5 4 -7 4 3 -1
//3 1 -6 1 7 5 -2 5 -100 10
int s,minn,maxn,n,a,x,y; 
int main()
{
    s=0;minn=0;maxn=-0x7f7f7f7f;
    cin>>n;
    x=1;y=1;
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        s+=a;
        if(s-minn>maxn) maxn=s-minn;
        if(s<minn) minn=s;
    }
    cout<<maxn<<endl;
    return 0;
}

2.DP

#include<bits/stdc++.h>//最大子序列（dp） 
using namespace std;
int n,a[50000005],maxn,x,y,qj,dp[50000005]; 
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],dp[i]=a[i];
    x=1;y=1;maxn=a[1];
    for(int i=2;i<=n;i++)
    {
        if(dp[i-1]+a[i]>dp[i])
           dp[i]=dp[i-1]+a[i];
        else qj=i;
        if(dp[i]>maxn)
        {
            maxn=dp[i];
            x=qj;
            y=i;
        }
    } 
    cout<<maxn<<" "<<x<<" "<<y;
    return 0;
}

2.比赛

怎么说，还挺简单的

赛时：
1.2.4都AC了，3拿了30分，然后超时了（我打的暴力枚举
赛后都改出来了
今天的比赛wwq直接AK，拿了400分，实在是太有实力了
怎么说，大家比赛的错误千奇百怪
lft他把文件名后面多加了个cpp，直接爆0了
zyc和zyf都把文件读写注释掉了，真的无话可说

1.mistake

#include
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while((ch'9')&&ch!='-') ch=getchar();
    if(ch=='-') f=-1,ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int n,a[110][110],ch,cz,sum_h,sum_z,x,y;
int main()
{
    freopen("mistake.in","r",stdin);
    freopen("mistake.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) 
            a[i][j]=read();
    for(int i=1;i<=n;i++)
    {
        ch=0;cz=0;
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]==1) ch++;
            if(a[j][i]==1) cz++;
        }
        if(ch%2==0) sum_h++;
        else x=i;
        if(cz%2==0) sum_z++;
        else y=i;
    }
    if(sum_h==n && sum_z==n) cout<<"OK";
    else if(sum_h==n-1 && sum_z==n-1) cout<<x<<" "<<y;
    else cout<<"Corrupt"; 
    return 0;
}

2.dis

貌似以前打过

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while((ch<&#039;0&#039;||ch>&#039;9&#039;)&&ch!=&#039;-&#039;) ch=getchar();
    if(ch==&#039;-&#039;) f=-1,ch=getchar();
    while(ch>=&#039;0&#039;&&ch<=&#039;9&#039;)
    {
        x=x*10+ch-&#039;0&#039;;
        ch=getchar();
    }
    return x*f;
}
int a,b,ans;
int main()
{
    freopen("dis.in","r",stdin);
    freopen("dis.out","w",stdout);
    a=read();
    b=read();
    if(a==b)
    {
        cout<<"0";
        return 0;
    } 
    while(a!=b)
    {
        if(b%2==0 && b/2>=a) b/=2,ans++;
        else b-=1,ans++;
    }
    cout<<ans; 
    return 0;
}

3.sum

#include
using namespace std;
const int N=1e6+5;
int n,a[N],ans,b[N];
int main()
{
    freopen("sum.in","r",stdin);
    freopen("sum.out","w",stdout);
    cin>>n;
    ans=0x7f7f7f7f;
    for(int i=1;i>a[i];
    sort(a+1,a+n+1);
    int right=n,left=1;
    while(right>left)
    {
        ans=min(ans,abs(a[left]+a[right]));
        if((a[left]+a[right])<0) left++;
        else right--;   
    }
    cout<<ans;
    return 0;
}

4.flu

zmx说以前打过，但我一点印象都没有

#include
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while((ch'9')&&ch!='-') ch=getchar();
    if(ch=='-') f=-1,ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int n,m,sum,b[110][110];
char a[110][110];
int main()
{
    freopen("flu.in","r",stdin);
    freopen("flu.out","w",stdout);
    n=read();
    for(int i=1;ia[i][j];
            if(a[i][j]=='@') b[i][j]=1;
        }
    m=read();
    for(int k=1;k<m;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(b[i][j]==1)
                {
                    if(a[i+1][j]=='.')a[i+1][j]='@';
                    if(a[i][j+1]=='.')a[i][j+1]='@';
                    if(a[i-1][j]=='.')a[i-1][j]='@';
                    if(a[i][j-1]=='.')a[i][j-1]='@'; 
                }
            }
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(a[i][j]=='@') b[i][j]=1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]=='@') sum++;
        }
    }
    cout<<sum;  
    return 0;
}

S组

1.Star

  • #### 一言：一起去看星星吧
    我觉得提别符合这道题目（bushi
#include<bits/stdc++.h>//star
//一言 一起去看星星吧 
using namespace std;
const int N=2e4+5; 
long long n,t,k,a[N],b[N],c[N],d[N];
long long dp1[4*N],dp2[4*N];
int main()
{
    freopen("star.in","r",stdin);
    freopen("star.out","w",stdout);
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        for(int i=1;i<=n;i++)
            cin>>a[i]>>b[i]>>c[i]>>d[i];
        for(int i=1;i<=k;i++) dp1[i]=dp2[i]=1e17;
        dp1[0]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=k;j++) dp1[j]=1e17;
            for(int j=k;j>=0;--j)
            {
                dp1[j]=min(dp1[j],dp2[j]);
                if(j>=1) dp1[j]=min(dp2[j-1]+a[i],dp1[j]);
                if(j>=2) dp1[j]=min(dp2[j-2]+b[i],dp1[j]);
                if(j>=3) dp1[j]=min(dp2[j-3]+c[i],dp1[j]);
                if(j>=4) dp1[j]=min(dp2[j-4]+d[i],dp1[j]);
            }
            for(int j=1;j<=k;++j) dp2[j]=dp1[j];
        }
        cout<<dp2[k]<<endl;
    }
    return 0;
}
训练日志

发表回复