Educational Codeforces Round 19 A+B+C+E!

题意：将n分解成k个大于1的数相乘的形式。如果无法分解输出-1。

思路：先打个素因子表，然后暴力判，注意最后跳出的条件。

int len,a[N],b[N];

void init()

{

    memset(a,-1,sizeof(a));

    a[0]=a[1]=0;

    memset(b,0,sizeof(b));

    len=0;

    for(int i=2; i<N; i++)

        if(a[i])

        {

            b[len++]=i;

            if(N/i<i) continue;

            for(int j=i*i; j<N; j+=i) a[j]=0;

        }

}

int main()

{

    init();

    int n,k;

    while(~scanf("%d%d",&n,&k))

    {

        if(k==1)

        {

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

            continue;

        }

        if(a[n])

        {

            puts("-1");

            continue;

        }

        int num=0,l=0;

        int tmp[35];

        while(k>1&&n>=b[num])

        {

           while(k>1&&n>=b[num]&&n%b[num]==0)

           {

               tmp[l++]=b[num];

//                printf("%d ",b[num]);

                k--;

                n/=b[num];

           }

           num++;

        }

        if(k>1||n==1) puts("-1");

        else

        {

           tmp[l++]=n;

          for(int i=0;i<l;i++)

            printf("%d ",tmp[i]);

          puts("");

        }

    }

    return 0;

}

B.
Odd sum

题意：给出n个数，求最大的奇数和是多大。

思路：注意：偶数=奇数+奇数。先将所有大于0的数加起来，如果是奇数直接输出，否则需要减去一个正奇数或者负奇数。于是输入的时候需要求出一个最大的负奇数和一个最小的正奇数。

int len,a[N],b[N];

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

        int mi=-INF,ma=INF,sum=0,x;

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

        {

            scanf("%d",&x);

            if(x>=0)

            {

               sum+=x;

               if(x&1) ma=min(ma,x);

            }

            else

            {

                x=-x;

                if(x&1) mi=max(mi,-x);

            }

        }

        if((sum&1)==0)

        {

            int sum1=0,sum2=0;

//            printf("%d %d\n",mi,ma);

             sum1=sum-ma;

             sum2=sum+mi;

             sum=max(sum1,sum2);

        }

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

    }

    return 0;

}

C.
Minimal string

对这题至今仍存在未解之谜。

题意：最开始给出一个串s,和两个空串t，u。每次操作可以将s的首字符加入t的尾部，也可以将t的尾字符加入u的尾部。输出字典序最小的串u。

贪心思想，只要当前字符的后面有比当前小的先将当前字符入栈，如果后面没有比当前字符更小的则将栈顶比当前字符小的输出来，再输出当前字符。思想貌似很正确，然后第25组数据死活过不去。看了一下别人的代码，感觉没什么区别，只是实现方式不同，真是玄学。。

代码一：WA 20:

char s[N],b[N];

int main()

{

    while(~scanf("%s",s))

    {

        int len=strlen(s);

        b[len-1]=s[len-1];

        for(int i=len-2; i>=0; i--) b[i]=min(s[i],b[i+1]);

        b[len]='\0';

        stack<char>q;

        while(!q.empty()) q.pop();

        for(int i=0; i<len; i++)

        {

            q.push(s[i]);

            while(!q.empty()&&q.top()<=b[i])

            {

                printf("%c",q.top());

                q.pop();

            }

        }

        while(!q.empty())

        {

            printf("%c",q.top());

            q.pop();

        }

        puts("");

    }

    return 0;

}

代码二：AC：

char s[N],b[N];

int main()

{

    while(~scanf("%s",s))

    {

        int len=strlen(s);

        b[len-1]=s[len-1];

        for(int i=len-2; i>=0; i--) b[i]=min(s[i],b[i+1]);

        b[len]='z';

        stack<char>q;

        while(!q.empty()) q.pop();

        for(int i=0; i<len; i++)

        {

            q.push(s[i]);

            while(!q.empty()&&q.top()<=b[i+1])//这里改成b[i+1]就过了

            {

                printf("%c",q.top());

                q.pop();

            }

        }

        while(!q.empty())

        {

            printf("%c",q.top());

            q.pop();

        }

        puts("");

    }

    return 0;

}

代码三：WA 25:

char s[N],b[N];

int main()

{

    while(~scanf("%s",s))

    {

        int len=strlen(s);

        b[len-1]=s[len-1];

        for(int i=len-2; i>=0; i--) b[i]=min(s[i],b[i+1]);

        b[len]='z';

        stack<char>q;

        while(!q.empty()) q.pop();

        for(int i=0; i<len; i++)

        {

            if(b[i]==s[i])//后面的没有比当前更小的；

            {

                while(!q.empty()&&q.top()<=b[i])

                {

                    printf("%c",q.top());

                    q.pop();

                }

                printf("%c",s[i]);

            }

            else q.push(s[i]);

        }

        while(!q.empty())

        {

            printf("%c",q.top());

            q.pop();

        }

        puts("");

    }

    return 0;

}

如果有路过的大牛，请帮忙指点迷津。

E.
Array Queries

题意：给出n个数的数列a[]（a[i]>=1&&a[i]<=n）,然后q次查询，每次输入一个p,k，每次操作可以将p变换成p+a[p]+k。求需要变换多少次才能使p大于n。

思路：暴力。注意到数据只有1e5。用一个数组b[p][k]表示输出数据为p,k的时候需要变换的次数。但第一维可达1e5，所以第二维能开到300到400的样子，这样先预处理出k在400一下的，至于k在400以上的，我们发现，p的变换是递增的，k越大递增越快，所以如果k为400，最坏也就在260左右次就可以达到条件，这样暴力判就行。

int a[N],b[N][321];

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

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

        memset(b,0,sizeof(b));

        for(int i=n;i>=1;i--)

            for(int j=1;j<=320;j++)

            if(j+a[i]>n) b[i][j]=1;

            else b[i][j]=b[a[i]+j][j]+1;

        int q,p,k;

        scanf("%d",&q);

        while(q--)

        {

            scanf("%d%d",&p,&k);

            if(k<=320)

            {

                printf("%d\n",b[p][k]);

                continue;

            }

            int ans=0;

            while(p<=n) p=a[p]+k,ans++;

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

        }

    }

    return 0;

}

E题挺有意思，奥，为什么D题不做，嘿嘿，不（我）告（好）诉（菜）你（a）。

巴特西

Educational Codeforces Round 19 A+B+C+E!

最新文章

热门文章