Codeforces ラウンド #256 (ディビジョン 2) A/B/C/D_html/css_WEB-ITnose

A. 報酬

水の質問

#include<cstdio>#include<iostream>#include<cstring>using namespace std;int main(){    int a1,a2,a3,b1,b2,b3,s,t1,t2,sum1,sum2;    while(scanf("%d%d%d",&a1,&a2,&a3)!=EOF)    {        scanf("%d%d%d",&b1,&b2,&b3);        scanf("%d",&s);        sum1 = a1+a2+a3;        sum2 = b1+b2+b3;        if(sum1>=5)        {            t1 = sum1/5;            if(sum1%5) t1++;        }        else if(sum1>0) t1 = 1;        else t1 = 0;        if(sum2>=10)        {            t2 = sum2/10;            if(sum2%10) t2++;        }        else if(sum2>0) t2 = 1;        else t2 = 0;        if(t1+t2>s) puts("NO");        else puts("YES");    }    return 0;}

B. サフィックス構造

ヒント: 一部の If 文字を削除する必要がある場合は、文字列 a を文字列 b に変更する必要があります。目的を達成できる場合は、automaticon を出力します

特定の文字を交換するだけの場合は配列を出力し、目的を達成するために両方の操作が必要な場合は両方を出力し、両方の操作

を同時に使用できない場合は、ツリーを出力する必要があります

アルゴリズム:

この状況は実際には非常に複雑です。心を明確に保つ必要があります~

1. まず、2 つの文字列が同じである場合、配列を出力します。

2. 文字列 a の長さが文字列 b の長さより短い場合、または文字列 b 内の対応する文字の数が足りない場合、または文字列 a に入力する場合、それは必要なツリーです。

3.文字列 a が文字列 b の長さに等しく、文字列 a の対応する文字が文字列 b 内で見つかる場合、文字列 a の長さが

の長さより大きい場合、配列が出力されます。文字列 b と、文字列 a の中に文字列 b の文字が次々に出現すると、automaticon が出力されますが、

順序が異なる場合は、両方が出力されます。

#include<cstdio>#include<iostream>#include<cstring>#include<vector>using namespace std;char s1[110],s2[110];vector<int> c;int cnt1[30],cnt2[30];int main(){    int flag1,flag2,d,flag;    while(scanf("%s%s",s1,s2)!=EOF)    {        if(strcmp(s1,s2)==0)        {            printf("array\n");            continue;        }        flag1 = flag2 = flag = 0;        c.clear();        memset(cnt1,0,sizeof(cnt1));        memset(cnt2,0,sizeof(cnt2));        int len1 = strlen(s1);        int len2 = strlen(s2);        if(len1>len2) flag1 = 1;        for(int i=0;i<len2;i++)            cnt2[s2[i]-'a']++;        for(int j=0;j<len1;j++)            cnt1[s1[j]-'a']++;        for(int i=0;i<len2;i++)        {            if(cnt2[s2[i]-'a'] > cnt1[s2[i]-'a'])            {                flag = 1;                break;            }        }        if(flag || len1<len2)        {            printf("need tree\n");            continue;        }        for(int i=0;i<len1;i++)        {            if(s1[i]==s2[0])                c.push_back(i);        }        for(int i=0;i<c.size();i++)        {            int t = 1;            for(int j=c[i]+1;j<len1;j++)            {                if(s1[j]==s2[t])                    t++;            }            if(t == len2)            {                flag2 = 1;                break;            }        }        if(flag1 && flag2)            printf("automaton\n");        else if(flag1 && !flag2)            printf("both\n");        else if(!flag1 && !flag2)            printf("array\n");    }    return 0;}

C. 絵画フェンス

質問: 長さ ai の木片が n 枚あります。次にペイント ブラシがあり、木片の幅とペイント ブラシの幅は両方とも 1 で、

木片がペイントされます。そして絵筆が触れるところには木のブロックがあるはずです。最低何回ブラッシングが必要かを尋ねてください。

アルゴリズム: 記憶された検索

1. 水平ブラッシングの下は水平ブラッシングでなければなりません。

2. 以下の共通の長さを塗装した後、木製ストリップはいくつかの分割されたセクションに分割されます。各セクションは、木製ストリップのいくつかの未塗装の部分で構成されます。

各部位を縦方向または横方向にブラッシングし、どちらか少ない回数を比較します。 [l,r]部分を縦方向にブラシする場合は

r-l+1を使用します。横方向にブラシをかける場合は、最初に共通部分をブラシしてから、それが何個のセクションに分割されているかを見ると、同じサブ問題が再び発生しました。 。 dfsで再帰的に解きます。

#include<cstdio>#include<iostream>#include<cstring>#define maxn 5010using namespace std;typedef long long ll;ll a[maxn];ll min(ll x,ll y){    return x<y?x:y;}ll work(int l,int r,int cen){    ll mi = a[l];    for(int i=l+1;i<=r;i++)        mi = min(mi,a[i]);    ll sum = mi-cen,s = r-l+1;    int last = l;    for(int i=l;i<=r;i++)    {        if(a[i]==mi)        {            if(last<i) sum+=work(last,i-1,mi);            last = i+1;        }    }    if(last<=r) sum+=work(last,r,mi);    return min(sum,s);}int main(){    int n;    while(scanf("%d",&n)!=EOF)    {        for(int i=1;i<=n;i++)            scanf("%I64d",&a[i]);        ll ans = work(1,n,0);        printf("%I64d\n",ans);    }    return 0;}

D. 九九

ヒント: n 行 m 列の九九で k 番目に大きい数はどれですか? 2、例: 2*3 乗算表は 1 2 3

2 4 6

アルゴリズム: 2 点探索。

最大の数はn*m=25*10^10なので、2つの点を考えます。 k 番目に大きい数値は、それ以下の数値が k 個あることを意味します (この記述も不正確です)

とにかく、それは最初に見つかった最小の数値です。

九九の機能を最大限に活用し、各行は行数を1-m倍したものになります。したがって、x 以下の数値を見つけることは min(m,x/i) です。

追伸。 。とにかく、この解決策は思いつきませんでした。 。 。 o(?□?)o。 。 。学んだ。 。 。

りー