Codeforces ラウンド #256 (ディビジョン 2) 题解_html/css_WEB-ITnose

問題 A:

A. 報酬

テストごとの制限時間

テストごとのメモリ制限

入力

出力

Bizon the Champion がチャンピオンと呼ばれるのには理由があります。

Bizon the Champion は最近プレゼントをもらいましたか?棚がいくつかある新しいガラスの戸棚を作り、そこにプレゼントをすべて置くことにしました。すべてのプレゼントはメダルとカップの2種類に分かれます。ビゾン・ザ・チャンピオンには、a1 一等賞カップ、a2 二等賞カップ、および a3三等賞カップがあります。さらに、彼は b1 の 1 位メダル、b2 の 2 位のメダル、b3 の 3 位のメダルを持っています。

当然のことながら、食器棚の中の報酬は見栄えが良くなければなりません。だからこそ、Bizon ザ チャンピオンはルールに従うことにしました:

チャンピオンのビゾンがすべての条件を満たすようにすべての報酬を置くことができるかどうか調べるのを手伝ってください

入力

最初の行には、整数 a1、a2、および a3 (0?≤?a1,?a2,?a3?≤?100) が含まれています。 2 行目には、整数 b1、b2、b3 (0?≤?b1,?b2,?b3?≤?100) が含まれています。 3 行目には整数 n (1?≤?n?≤?100) が含まれています。

行内の数字は単一のスペースで区切られています。

出力

報酬は上記の方法で棚に置くことができます。それ以外の場合は、「NO」を出力します (引用符なし)。

サンプル テスト

入力

1 1 11 1 14

出力

YES

input

1 1 32 3 42

出力

YES

入力

1 0 01 0 01

出力

NO

解题思路：

すべての奖杯と奖牌が必要な最小フレーム子の数を求めるnum、そしてnは比較を実行します。 ：

#include <cstdio>#include <cmath>int main(){    int a1, a2, a3, b1, b2, b3, n;    scanf("%d%d%d%d%d%d%d", &a1, &a2, &a3, &b1, &b2, &b3, &n);    int num = ceil((a1 + a2 + a3) * 1.0 / 5) + ceil((b1 + b2 + b3) * 1.0 / 10);    printf("%s\n", num <= n ? "YES" : "NO");    return 0;}

B. サフィックス構造

テストごとの制限時間

あるコンテストで、「Bizons」は次の問題を受け取りました。「2 つの異なる単語 (英語の文字列)、s と t が与えられています。単語 s を変換する必要があります。」単語に変換します。」彼らはサフィックスのデータ構造をよく知っているため、このタスクは簡単に見えました。 Bizon先輩はサフィックスオートマトンが大好きです。これを文字列に 1 回適用すると、この文字列から任意の 1 文字を削除できます。 Bizon Middle はサフィックス配列をよく知っています。これを文字列に 1 回適用すると、この文字列の任意の 2 文字を交換できます。彼らはサフィックス ツリーについて何も知りませんが、それは彼らがもっと多くのことを行うのに役立ちます。

最初の行には空ではない単語が含まれています。 2 行目には空ではない単語 t が含まれています。単語 s と t は異なります。各単語は英小文字のみで構成されています。各単語には最大 100 文字が含まれます。

In the single line print the answer to the problem. Print "need tree" (without the quotes) if word s cannot be transformed into word teven with use of both suffix array and suffix automaton. Print "automaton" (without the quotes) if you need only the suffix automaton to solve the problem. Print "array" (without the quotes) if you need only the suffix array to solve the problem. Print "both" (without the quotes), if you need both data structures to solve the problem.

It's guaranteed that if you can solve the problem only with use of suffix array, then it is impossible to solve it only with use of suffix automaton. This is also true for suffix automaton.

Sample test(s)

input

automatontomat

output

automaton

input

arrayarary

output

array

input

bothhot

output

both

input

needtree

output

need tree

解题思路：

如果串A中包含串B的所有字母，并且这些字母在串A和串B中排列顺序相同，输出“automaton”，否则，如果串A中包含串B的所有字母，我们在这种情况下在进行讨论，如果A和B的长度相等，输出“array”，如果A比B长，输出“both”，否则输出“need tree”。

代码：

#include <cstring>#include <string>#include <iostream>using namespace std;const int MAXN = 105;int vis[MAXN];bool cmpa(string stra, string strb){    memset(vis, 0, sizeof(vis));    int lena = stra.length();    int lenb = strb.length();    int k = 0;    for(int i = 0; i < lenb; i++)    {        bool flag = true;        for(int j = k; j < lena; j++)        {            if(!vis[j] && strb[i] == stra[j])            {                vis[j] = 1;                k = j + 1;                flag = false;                break;            }        }        if(flag) return false;    }    return true;}bool cmpb(string stra, string strb){    memset(vis, 0, sizeof(vis));    int lena = stra.length();    int lenb = strb.length();    for(int i = 0; i < lenb; i++)    {        bool flag = true;        for(int j = 0; j < lena; j++)        {            if(!vis[j] && strb[i] == stra[j])            {                vis[j] = 1;                flag = false;                break;            }        }        if(flag) return false;    }    return true;}int main(){    string stra, strb;    cin >> stra >> strb;    int lena = stra.length();    int lenb = strb.length();    if(cmpa(stra, strb))    {        cout << "automaton" << endl;    }    else if(cmpb(stra, strb))    {        if(lena == lenb)        {            cout << "array" << endl;        }        else if(lena > lenb)        {            cout << "both" << endl;        }        else        {            cout << "need tree" << endl;        }    }    else    {        cout << "need tree" << endl;    }    return  0;}

Problem C:

C. Painting Fence

time limit per test

memory limit per test

input

output

Bizon the Champion isn't just attentive, he also is very hardworking.

Bizon the Champion decided to paint his old fence his favorite color, orange. The fence is represented as n vertical planks, put in a row. Adjacent planks have no gap between them. The planks are numbered from the left to the right starting from one, the i-th plank has the width of 1 meter and the height of ai meters.

Bizon the Champion bought a brush in the shop, the brush's width is 1 meter. He can make vertical and horizontal strokes with the brush. During a stroke the brush's full surface must touch the fence at all the time (see the samples for the better understanding). What minimum number of strokes should Bizon the Champion do to fully paint the fence? Note that you are allowed to paint the same area of the fence multiple times.

Input

The first line contains integer n (1?≤?n?≤?5000) ? the number of fence planks. The second line contains n space-separated integersa1,?a2,?...,?an (1?≤?ai?≤?109).

Output

Print a single integer ? the minimum number of strokes needed to paint the whole fence.

Sample test(s)

input

52 2 1 2 1

output

input

22 2

output

input

15

output

解题思路：

递归，贪心。粉刷篱笆，我们可以水平方向粉刷（只能刷到连续的部分），也可以竖直方向粉刷。按水平方向粉刷的话，刷的最少次数是min(a1,a2,a3,...,an-1)；按竖直方向刷的话最少次数是这段连续篱笆的长度n。按上述方式刷完之后，必然会产生高度为0的篱笆（被全部刷过了），我们把这样的篱笆作为分割点，分成左半部分，和右半部分，两部分各是一段连续的篱笆，依次类推。

一个错误的思路：每次刷的时候找所有篱笆高度的最大值h，和最长的连续篱笆的长度len，刷的时候取max（h，len），最多刷n次，算法复杂度O(n2)。这样做的话，可能会使得篱笆变得分散，导致最终粉刷的次数变多。

反例：

3
1 10 1

错误的代码：

  #include <cstdio>    #include <algorithm>    using namespace std;    const int MAXN = 5010;    int n, ans = 0, a[MAXN];    int main()    {        scanf("%d", &n);        for(int i = 0; i < n; i++)        {            scanf("%d", &a[i]);        }        while(true)        {            int maxv = *max_element(a, a + n);            int maxh = -1, tmp = 0, first = 1;            int s = 0, t = 0, ts = 0, tt = 0;            for(int i = 0; i < n; i++)            {                if(a[i])                {                    if(first)                    {                        ts = i;                        first = 0;                    }                    tt = i;                    tmp++;                    if(i == n - 1)                    {                        if(tmp > maxh)                        {                            maxh = tmp;                            s = ts;                            t = tt;                        }                    }                }                else                {                    if(tmp > maxh)                    {                        maxh = tmp;                        s = ts;                        t = tt;                    }                    tmp = 0;                    first = 1;                }            }            if(maxv > maxh)            {                *max_element(a, a + n) = 0;            }            else            {                for(int i = s; i <= t; i++)                {                    a[i]--;                }            }            ans++;            if(0 == *max_element(a, a + n)) break;        }        printf("%d\n", ans);        return 0;    }

代码：

#include <cstdio>#include <algorithm>using namespace std;const int MAXN = 5010;int n, a[MAXN];int solve(int l, int r){    if(l > r) return 0;    int minh = *min_element(a + l, a + r + 1);    int ret = r - l + 1, tot = minh;    if(ret < minh)    {        for(int i = l; i <= r; i++)            a[i] = 0;        return ret;    }    else    {        for(int i = l; i <= r; i++)            a[i] -= minh;        int t = min_element(a + l, a + r + 1) - a;        tot += solve(l, t - 1) + solve(t + 1, r);    }    return min(ret, tot);}int main(){    scanf("%d", &n);    for(int i = 0; i < n; i++)        scanf("%d", &a[i]);    printf("%d\n", solve(0, n - 1));    return 0;}

Problem D:

D. Multiplication Table

time limit per test

memory limit per test

input

output

Bizon the Champion isn't just charming, he also is very smart.

While some of us were learning the multiplication table, Bizon the Champion had fun in his own manner. Bizon the Champion painted ann?×?m multiplication table, where the element on the intersection of the i-th row and j-th column equals i·j (the rows and columns of the table are numbered starting from 1). Then he was asked: what number in the table is the k-th largest number? Bizon the Champion always answered correctly and immediately. Can you repeat his success?

Consider the given multiplication table. If you write out all n·m numbers from the table in the non-decreasing order, then the k-th number you write out is called the k-th largest number.

Input

The single line contains integers n, m and k (1?≤?n,?m?≤?5·105; 1?≤?k?≤?n·m).

Output

Print the k-th largest number in a n?×?m multiplication table.

Sample test(s)

input

2 2 2

output

input

2 3 4

output

input

1 10 5

output

解题思路:

二分。需要求的是n*m乘法表中第k大的数，我们可以对这个数ans进行二分查找，区间是[1, n * m]，对于每一个可能的ans，我们求出比他小的数的个数sum += min((mid - 1) / i, m);(i = 1,2,3,..,n)，记录下小于k的最大的mid，即为我们所求的ans。

代码：

#include <cstdio>inline long long min(long long a, int b){    if(a < b) return a;    return b;}int main(){    int n, m;    long long k, ans, l, r, sum, mid;    scanf("%d%d%I64d", &n, &m, &k);    l = 1, r = 1ll * n * m;//r = (long long)n * m;    while(l <= r)    {        mid = (l + r) >> 1;        sum = 0;        for(int i = 1; i <= n; i++)            sum += min((mid - 1) / i, m);        if(sum < k)            l = mid + 1, ans = mid;        else            r = mid - 1;    }    printf("%I64d\n", ans);    return 0;}