Codeforces ラウンド #279 (ディビジョン 2) 問題解決 report_html/css_WEB-ITnose

A - チームオリンピアード

貪欲な質問。 。最初のものから始めてください。

コードは次のとおりです:

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64int a[6000], b[6000];int main(){    int n, x, y, z, ans, i, j;    while(scanf("%d",&n)!=EOF)    {        x=y=z=0;        for(i=0;i<n;i++)        {            scanf("%d",&a[i]);        }        memset(b,0,sizeof(b));        for(i=0;i<n;i++)        {            if(a[i]==1)            {                x++;                b[i]=x;            }            else if(a[i]==2)            {                y++;                b[i]=y;            }            else if(a[i]==3)            {                z++;                b[i]=z;            }        }        ans=min(x,min(y,z));        printf("%d\n",ans);        for(i=1;i<=ans;i++)        {            for(j=0;j<n;j++)            {                if(b[j]==i)                {                    printf("%d ",j+1);                }            }            puts("");        }    }    return 0;}

B - Queue

次の位置を配列で記録することで、偶数と奇数の位置をそれぞれ埋めます。

偶数番号の位置は 0 から開始する必要があり、奇数番号の位置は出力次数がなく入力次数のみの数値から開始する必要があります。

コードは次のとおりです:

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64int next[1100000], a[1100000], out[1100000];struct node{    int u, v;}fei[1100000];int main(){    int n, i, j, u, v, cnt, pos;    while(scanf("%d",&n)!=EOF)    {        memset(next,-1,sizeof(next));        memset(out,0,sizeof(out));        for(i=0;i<n;i++)        {            scanf("%d%d",&fei[i].u, &fei[i].v);            next[fei[i].u]=fei[i].v;            out[fei[i].v]++;        }        cnt=1;        for(i=0;i!=-1;i=next[i])        {            if(cnt!=1&&!i) break;            a[cnt]=next[i];            cnt+=2;        }        cnt=0;        for(i=0;i<n;i++)        {            if(!out[fei[i].u])            {                pos=fei[i].u;                break;            }        }        a[0]=pos;        cnt=2;        for(i=pos;i!=-1;i=next[i])        {            a[cnt]=next[i];            cnt+=2;        }        for(i=0;i<n;i++)        {            printf("%d ",a[i]);        }    }    return 0;}

C - Hacking Cypher

前後からスキャンして分割可能な位置を記録します。フロントからリアまでハンドリングが非常に優れています。

k 番目の桁については、最初に 10^k の余りの合計を b に、最初の k 桁の余りを b に前処理してから、最後の数桁 = 合計数 - 最初の k で表されます。桁数*10^k。したがって、合計数 %b==(最初の k 桁で表される数 %b)*(10^k%b)%b が満たされる限り、最後の数桁で表される数は割り算できることを意味します。 bによる。

これは O(n) の複雑さ内で完了できます。

それは私が本当に弱いということです。 。他の人が短期間でそれを達成したのを見てきました。 。しかし、それを理解するのに30分かかりました。 。 。

コードは次のとおりです:

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64int a[1100000], b[1100000], c[1100000], d[1100000];char s[1100000];int main(){    int aa, bb, i, x, len, pos, flag=0, y;    gets(s);    scanf("%d%d",&aa,&bb);    memset(a,0,sizeof(a));    memset(d,0,sizeof(d));    x=1;    c[1]=1%bb;    for(i=2;i<=1000000;i++)    {        x=x*10%bb;        c[i]=x;    }    len=strlen(s);    x=0;    y=0;    for(i=0;i<len;i++)    {        x=x*10+s[i]-'0';        x%=aa;        //printf("%d\n",x);        if(x==0)            a[i]=1;        y=y*10+s[i]-'0';        y%=bb;        b[i]=y;    }    //printf("%d\n",y);    for(i=0;i<len;i++)    {        if((LL)b[i]*c[len-i]%bb==(LL)y)        {            d[i]=1;        }    }    for(i=0;i<len-1;i++)    {        if(a[i]&&d[i]&&s[i+1]!='0')        {            pos=i;            flag=1;            break;        }    }    if(!flag)        puts("NO");    else    {        puts("YES");        for(i=0;i<=pos;i++)        {            printf("%c",s[i]);        }        puts("");        for(i=pos+1;i<len;i++)        {            printf("%c",s[i]);        }    }    return 0;}

D - Chocolate

最終的な面積が等しい場合、2 の因数の数と 3 の因数の数は等しくなければなりません。したがって、まず 2 の因数の数と 3 の因数の数を求めることができます。このとき、2 を消去するか、3 を 2 に変えるという 2 つの操作が可能です。したがって、この時点では、最初に 3 の大きい方を 2 に変更して残りの 3 を等しくしてから、大きい方の因数 2 を消去します。大きい方の辺が等しくなります。そして、このときの両辺の面積は等しいと判断します。

コードは次のとおりです:

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64int main(){    int a1, b1, a2, b2, x2, x3, y2, y3, ans, m1, m2, n1, n2;    while(scanf("%d%d%d%d",&a1,&b1,&a2,&b2)!=EOF)    {        m1=a1;        m2=a2;        n1=b1;        n2=b2;        x2=x3=y2=y3=0;        while(!(a1%2)||!(a1%3))        {            if(a1%2==0)            {                x2++;                a1/=2;            }            if(a1%3==0)            {                x3++;                a1/=3;            }        }        while(!(b1%2)||!(b1%3))        {            if(b1%2==0)            {                x2++;                b1/=2;            }            if(b1%3==0)            {                x3++;                b1/=3;            }        }        while(!(a2%2)||!(a2%3))        {            if(a2%2==0)            {                y2++;                a2/=2;            }            if(a2%3==0)            {                y3++;                a2/=3;            }        }        while(!(b2%2)||!(b2%3))        {            if(b2%2==0)            {                y2++;                b2/=2;            }            if(b2%3==0)            {                y3++;                b2/=3;            }        }        if(x3>=y3)        {            x2+=x3-y3;            ans=x3-y3;            for(int i=0; i<x3-y3; i++)            {                if(m1%3==0)  m1=m1/3*2;                else  n1=n1/3*2;            }        }        else        {            y2+=y3-x3;            ans=y3-x3;            for(int i=0; i<y3-x3; i++)            {                if(m2%3==0) m2=m2/3*2;                else n2=n2/3*2;            }        }        ans+=abs(x2-y2);        if(x2>=y2)        {            for(int i=0; i<x2-y2; i++)            {                if(m1%2==0) m1/=2;                else n1/=2;            }        }        else        {            for(int i=0; i<y2-x2; i++)            {                if(m2%2==0) m2/=2;                else n2/=2;            }        }        if((LL)m1*n1!=(LL)m2*n2)            puts("-1");        else        {            printf("%d\n",ans);            printf("%d %d\n%d %d\n",m1,n1,m2,n2);        }    }    return 0;}