NOIP模拟1

期望得分：100+100+100=300

实际得分：94+96+97=287

T1 #6090. 「Codeforces Round #418」尘封思绪

#include<cstdio>

#define N 102

using namespace std;

int a[N],b[N];

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    if(m>) { printf("Yes"); return ; }

    if(!m)

    {

        for(int i=;i<=n;i++)

        if(a[i]<a[i-]) { printf("Yes"); return ; }

        printf("No"); return ;

    }

    int pos;

    for(int i=;i<=n;i++)

    {

        scanf("%d",&a[i]);

        if(!a[i]) { pos=i; continue;}

        if(a[i]<a[i-]) { printf("Yes"); return ; }

    }

    scanf("%d",&m);

    a[n+]=;

    if(m<a[pos-] || m>a[pos+]) { printf("Yes"); return ; }

    printf("No");

}

T1 #6091. 「Codeforces Round #418」幻想特快

#include<cstdio>

#define N 1001

using namespace std;

int a[N],b[N];

int p[],fa,fb;

int v[N];

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    {

        scanf("%d",&a[i]);

        if(!v[a[i]]) v[a[i]]=i;

        else fa=i;

    }

    for(int i=;i<=n;i++)

    {

        scanf("%d",&b[i]);

        if(a[i]!=b[i]) p[++p[]]=i;

    }

    int k;

    for(int i=;i<=n;i++)

            if(!v[i]) { k=i; break; }

    if(p[]==)

    {

        a[p[]]=k;

        for(int i=;i<=n;i++) printf("%d ",a[i]);

        return ;

    }

    if(b[fa]==k) a[fa]=k;

    else a[v[a[fa]]]=k;

    for(int i=;i<=n;i++) printf("%d ",a[i]);

}

T3 LOJ #6092. 「Codeforces Round #418」恋爱循环


法一： 尺取法

#include<cstdio>

#include<algorithm>

#define N 1501

using namespace std;

char s[N];

int main()

{

    int n,q;

    scanf("%d",&n);

    scanf("%s",s+);

    scanf("%d",&q);

    int l,r,now,ans,m;

    char c[];

    while(q--)

    {

        scanf("%d%s",&m,c);

        now=ans=;

        r=,l=;

        while()

        {

            while(r<=n && now<=m)

                if(s[++r]!=c[])  now++;

            ans=max(ans,r-l);

            if(r>=n) break;

            while(l<=n && now>m)

                if(s[l++]!=c[]) now--;

        }

        printf("%d\n",ans);

    }

}

法二：动态规划

#include<cstdio>

#include<cstring>

#include<algorithm>

#define N 1501

using namespace std;

char s[N];

int ans[][N];

int main()

{

    int n,sum;

    scanf("%d",&n);

    scanf("%s",s+);

    for(int k=;k<;k++)

    {

        for(int i=;i<=n;i++)

        {

            sum=;

            for(int j=i;j<=n;j++)

            {

                if(s[j]-'a'!=k) sum++;

                ans[k][sum]=max(ans[k][sum],j-i+);

            }

        }

        for(int i=;i<=n;i++) ans[k][i]=max(ans[k][i],ans[k][i-]);

    }

    int q;

    scanf("%d",&q);

    int m; char c[];

    while(q--)

    {

        scanf("%d%s",&m,c);

        printf("%d\n",ans[c[]-'a'][m]);

    }

}

考场做法：二分 TLE1个点

#include<cstdio>

#include<iostream>

#define N 1501

using namespace std;

char s[N],c[];

int n,m;

inline bool check(int mid)

{

    int now=;

    for(int i=;i<=mid;i++)

        if(s[i]!=c[]) now++;

    if(now<=m) return true;

    for(int i=mid+;i<=n;i++)

    {

        if(s[i-mid]!=c[]) now--;

        if(s[i]!=c[]) now++;

        if(now<=m) return true;

    }

    return false;

}

inline void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

int main()

{

    read(n);

    scanf("%s",s+);

    int q,l,r,mid,ans;

    read(q);

    while(q--)

    {

        read(m);

        scanf("%s",c);

        ans=;

        l=m,r=n;

        while(l<=r)

        {

            mid=l+r>>;

            if(check(mid)) ans=mid,l=mid+;

            else r=mid-;

        }

        printf("%d\n",ans);

    }

}

巴特西

NOIP模拟1

期望得分：100+100+100=300

T1 #6090. 「Codeforces Round #418」尘封思绪

T1 #6091. 「Codeforces Round #418」幻想特快

T3 LOJ #6092. 「Codeforces Round #418」恋爱循环

最新文章

热门文章