Codeforces Round #256 (Div. 2) A/B/C/D_html/css_WEB-ITnose

A. Rewards

Water Question

#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. Suffix Structures

Question: Given two strings, you need to change string a into string b. If you only need to delete certain characters to achieve the goal, output automaticon

If you only need to exchange For certain characters, an array is output. If both operations are required to achieve the purpose, both are output. If both operations

are not possible when used at the same time, a need tree is output.

Algorithm:

This situation is actually very complicated. You must keep your mind clear and clear~

1. First, if the two strings are the same The output array.

2. If the length of string a is less than the length of string b or the corresponding letters in string b are not enough in number or type in string a, it is a need tree.

3. If the length of string a is Equal to the length of string b, and if the corresponding letters in string b can be found in string a, the array will be output.

4. If the length of string a is greater than the length of string b, the letters in string b will appear in sequence in string a. Then output automaton. If both appear but

are in different order, output both.

#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. Painting Fence

Question: Yes n wooden strips of length ai. Then there is a paint brush, the width of the wooden strips and the width of the paint brush are both 1, and the

wooden strips should be painted. And there should be wood blocks wherever the paint brush touches. Ask how many times it needs to be refreshed at least.

Algorithm: memorized search

1. The horizontal brush must be horizontal brush below.

2. After painting the common length below, the wooden strips will be divided into several broken sections. Each section is composed of several unpainted upper parts of the wooden strips.

Each part is brushed either vertically or horizontally. At this time, compare the number of times of the two brushing methods, whichever is smaller. When brushing the [l, r] part vertically, brush

r-l 1 time. When brushing horizontally, brush the common part first, and then look at how many sections it is divided into, so the same sub-problem appeared again. Solve it recursively with 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. Multiplication Table

Question: A multiplication table with n rows and m columns is the Which number is larger than k?

For example: the multiplication table of 2*3 is 1 2 3

                      2 4 6

Algorithm: binary search.

Since the largest number is n*m=25*10^10, think of two points. The kth largest number means that there are k numbers less than or equal to it (this statement is also inaccurate).

is the first such smallest number found anyway.

Make full use of the features of the multiplication table, each row is the number of rows multiplied by 1-m. So finding a number less than or equal to x is min(m,x/i).

P.S. . . Anyway, I didn't think of this solution. . . o(?□?)o. . . Learned. . .

#include<cstdio>#include<iostream>#include<cstring>#include<queue>using namespace std;typedef long long ll;ll k,n,m;ll min(ll x,ll y){    return x<y?x:y;}ll check(ll x){    ll sum = 0;    for(int i=1;i<=n;i++)        sum += min(m,x/i);    return sum;}int main(){    ll ans;    while(scanf("%I64d%I64d%I64d",&n,&m,&k)!=EOF)    {        ll l = 1,r = n*m;        while(l<=r)        {            ll mid = (l+r)>>1;            if(check(mid)>=k)            {                ans = mid;                r = mid-1;            }            else l = mid+1;        }        printf("%I64d\n",ans);    }    return 0;}