20230819 模拟赛总结

lzx

2023 年 08 月 19 日

173 次浏览

暂无评论

298字数

OI 总结

情况

$100+100+0+10=210pts$

$\texttt{rk1}$

T3 由于写错变量导致 $0$ 分

T1

需要正好吃饱

对于小 X 和小 Y 枚举

小 Z 排序后二分

code

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0,w=1;char ch=0;while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}return x*w;}
void write(int x){static int sta[35];int top=0;do{sta[top++]=x%10,x/=10;}while(x);while(top)putchar(sta[--top]+48);}
const int MAXN=2000+10;
int n,m,a[MAXN],b[MAXN],c[MAXN];
int ans;
int main()
{
    freopen("fishing.in","r",stdin);
    freopen("fishing.out","w",stdout);
    n=read();
    m=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
    }
    for(int i=1;i<=n;i++)
    {
        b[i]=read();
    }
    for(int i=1;i<=n;i++)
    {
        c[i]=read();
    }
    sort(c+1,c+1+n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int pr=m-a[i]-b[j];
            int l=lower_bound(c+1,c+1+n,pr)-c;
            int ll=lower_bound(c+1,c+1+n,pr+1)-c;
            if(a[i]+b[j]+c[l]==m) ans+=ll-l;
        }
    }
    write(ans);
    return 0;
}

T2

六维 DP，类似乌龟棋

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){int x=0,w=1;char ch=0;while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}return x*w;}
void write(int x){static int sta[35];int top=0;do{sta[top++]=x%10,x/=10;}while(x);while(top)putchar(sta[--top]+48);}
const int MOD=100000007;
const int MAXN=6,MAXM=1e5+10;
int n,m,f[13][13][13][13][13][13],a[MAXN],b[MAXN],c[MAXM];
int calc(int s1,int s2,int s3,int s4,int s5,int s6)
{
    return s1*a[1]+s2*a[2]+s3*a[3]+s4*a[4]+s5*a[5]+s6*a[6];
}
signed main()
{
    freopen("traveller.in","r",stdin);
    freopen("traveller.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        b[i]=read();
    }
    m=read();
    for(int i=1;i<=m;i++)
    {
        c[i]=read();
    }
    sort(c+1,c+1+m);
    f[0][0][0][0][0][0]=1;
    for(int i1=0;i1<=b[1];i1++)
    {
        for(int i2=0;i2<=b[2];i2++)
        {
            for(int i3=0;i3<=b[3];i3++)
            {
                for(int i4=0;i4<=b[4];i4++)
                {
                    for(int i5=0;i5<=b[5];i5++)
                    {
                        for(int i6=0;i6<=b[6];i6++)
                        {
                            if(i1==0 && i2==0 && i3==0 && i4==0 && i5==0 && i6==0) continue;
                            int pos=calc(i1,i2,i3,i4,i5,i6);
                            int l=lower_bound(c+1,c+1+m,pos)-c;
                            if(c[l]==pos)
                            {
                                continue;
                            }
                            if(i1!=0) f[i1][i2][i3][i4][i5][i6]=(f[i1][i2][i3][i4][i5][i6]+f[i1-1][i2][i3][i4][i5][i6])%MOD;
                            if(i2!=0) f[i1][i2][i3][i4][i5][i6]=(f[i1][i2][i3][i4][i5][i6]+f[i1][i2-1][i3][i4][i5][i6])%MOD;
                            if(i3!=0) f[i1][i2][i3][i4][i5][i6]=(f[i1][i2][i3][i4][i5][i6]+f[i1][i2][i3-1][i4][i5][i6])%MOD;
                            if(i4!=0) f[i1][i2][i3][i4][i5][i6]=(f[i1][i2][i3][i4][i5][i6]+f[i1][i2][i3][i4-1][i5][i6])%MOD;
                            if(i5!=0) f[i1][i2][i3][i4][i5][i6]=(f[i1][i2][i3][i4][i5][i6]+f[i1][i2][i3][i4][i5-1][i6])%MOD;
                            if(i6!=0) f[i1][i2][i3][i4][i5][i6]=(f[i1][i2][i3][i4][i5][i6]+f[i1][i2][i3][i4][i5][i6-1])%MOD;
                        }
                    }
                }
            }
        }
    }
    write(f[b[1]][b[2]][b[3]][b[4]][b[5]][b[6]]%MOD);
    return 0;
}

T3

两个显然的规律

产生贡献的只能是二进制下有单数个 $1$ 和二进制下有双数个 $1$
每 $4$ 个数中，各有 $2$ 个二进制下有单数个 $1$ 和二进制下有双数个 $1$ 的数

对于合并，我们可以离散化

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){int x=0,w=1;char ch=0;while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}return x*w;}
void write(int x){static int sta[35];int top=0;do{sta[top++]=x%10,x/=10;}while(x);while(top)putchar(sta[--top]+48);}
const int MAXN=100000+10;
int n,l[MAXN],r[MAXN],c[MAXN*4],m,s1[MAXN],s0[MAXN];
int f[MAXN*4];
signed main()
{
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++)
    {
        l[i]=read()-1;
        r[i]=read();
        c[++m]=l[i];
        c[++m]=r[i];
    }
    sort(c+1,c+1+m);
    m=unique(c+1,c+1+m)-c-1;
    for(int i=1;i<=n;i++)
    {
        int x=lower_bound(c+1,c+1+m,l[i])-c;
        int y=lower_bound(c+1,c+1+m,r[i])-c;
        for(int j=x;j<y;j++)
        {
            if(f[j]) continue;
            f[j]=i;
        }
    }
    for(int i=1;i<m;i++)
    {
        if(!f[i]) continue;
        c[i]++;
        while(c[i]%4!=0 && c[i]<=c[i+1])
        {
            int xxx=__builtin_popcount(c[i]);
            if(xxx%2==1) s1[f[i]]++;
            else s0[f[i]]++;
            c[i]++;
        }
        int pr=c[i+1];
        while(pr%4!=3 && pr>=c[i])
        {
            int xxx=__builtin_popcount(pr);
            if(xxx%2==1) s1[f[i]]++;
            else s0[f[i]]++;
            pr--;
        }
        c[i]--;
        int xxx=(pr-c[i])/4;
        s1[f[i]]+=xxx*2;
        s0[f[i]]+=xxx*2;
    }
    for(int i=1;i<=n;i++)
    {
        s1[i]+=s1[i-1];
        s0[i]+=s0[i-1];
        //cout<<s1[i]<<" "<<s0[i];
        write(s1[i]*s0[i]);
        puts("");
    }
    return 0;
}

T4

数据范围不大，考虑 DP。我们设 $f_i$ 表示匹配到 $i$ 位修改的最小数，转移也不难想，直接暴力对于 $i+1$ 位开始和 $n$ 个数字串暴力匹配出最少修改数，更新 DP 值，答案就是 $f_S$。时间复杂度 $\Theta(S \times$ 数字串总长度 $)$ ——solution.docx

code

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0,w=1;char ch=0;while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}return x*w;}
void write(int x){static int sta[35];int top=0;do{sta[top++]=x%10,x/=10;}while(x);while(top)putchar(sta[--top]+48);}
const int MAXN=100+10,MAXS=1000+10;
string s,ss[MAXN];
int n,lens,lenss[MAXN],h[MAXN][MAXS],f[MAXS],fr[MAXS];
vector <string> ans;
int main()
{
    freopen("pianist.in","r",stdin);
    freopen("pianist.out","w",stdout);
    cin>>s;
    lens=s.size();
    n=read();
    for(int i=1;i<=n;i++)
    {
        cin>>ss[i];
        lenss[i]=ss[i].size();
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=lens-lenss[i];j++)
        {
            for(int k=0;k<lenss[i];k++)
            {
                if(ss[i][k]!=s[j+k])
                {
                    h[i][j]++;
                }
            }
        }
    }
    memset(f,0x3f,sizeof f);
    f[0]=0;
    for(int i=0;i<lens;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i+lenss[j]>lens) continue;
            if(f[i]+h[j][i]<f[i+lenss[j]])
            {
                f[i+lenss[j]]=f[i]+h[j][i];
                fr[i+lenss[j]]=j;
            }
        }
    }
    for(int i=lens;i;i-=lenss[fr[i]])
    {
        ans.push_back(ss[fr[i]]);
    }
    for(int i=ans.size()-1;i>=0;i--)
    {
        cout<<ans[i]<<"\n";
    }
    return 0;
}

后记

其实这套题去年暑假做过

当初的得分是 $0+100+0+0=100pts$

这么看来，一年间进步了一题

20230819 模拟赛总结

lzx • 2023 年 08 月 19 日

情况

T1

T2

T3

T4

后记

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

20230819 模拟赛总结

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款