codeforces Contest 466

题目链接在这里

A. Cheap Travel

题意： n站地铁，有两种买票的方式，a):一次一站a元，b):一次m站b元。问如何搭配可以最省钱。

分析：有三种坐车的方式, a, b, a&b，找个最小值即可。

int main()
{
    ios::sync_with_stdio(0);
    int n, m, a, b;
    cin >> n >> m >> a >> b;
    int ans1 = n * a;
    int c = n / m;
    int r = n - m * c;
    int ans2 = c * b + r * a;
    int ans3 = (n % m) ? (c + 1) * b : c * b;

    cout << min(ans1, min(ans2, ans3)) << endl;
    return 0;
}

B. Wonder Room

题意： axb的宿舍，n个人住进去需要6xn的面积，如果不够可以增加宽高，问如何增加使得能住进去同时面积最小。

分析：注意范围：1≥n, a, b≤10⁹，因此理论上讲a的范围是[a, 6xn/b]，b的范围是[b, 6n/a]，在这个范围里搜索会超时。可以发现其中会有一些重复对。如果目标是构造6xn的面积，可以想到是短边≤sqrt(6xn)，长边≥sqrt(6xn)，刚好≥6xn也可以类似的思路。即短边的范围≤sqrt(6xn)。这样就可以避免重复对了。

int main()
{
    ios::sync_with_stdio(0);
    LL n, a, b;
    cin >> n >> a >> b;
    LL square = 6 * n;
    LL s = 0, a1 = a, b1 = b;
    bool swaped = false;

    if (a > b) {
        swaped = true;
        swap(a, b);
    }

    for (LL i = a; i * i <= square; ++i) {
        LL t = square / i;
        if (square % i != 0)
            ++t;
        if (t <= b)
            break;

        LL new_s = t * i;
        if (s == 0 || new_s < s) {
            s = new_s;
            a1 = i;
            b1 = t;
        }
    }

    if (swaped) {
        swap(a1, b1);
    }

    if (s == 0) {
        s = a * b;
    }

    cout << s << endl;
    cout << a1 << " " << b1 << endl;
    return 0;
}

C. Number of Ways

题意： n长度的数组，要求分成三份，每份的元素和都是整个数组元素和的1/3，问所有可能的组合数目。

分析： O(n)可以求出整个数组的元素和sum，因此题目变成求分割的办法使得每份都是sum/3。只要满足下列条件就可以分成三份：
假设从左往右求和，加到某个数和为 sum / 3成为2分点，和为sum * 2 / 3称为2分点。

sum可以整除3.
2分点可以与前面任意一个1分点组合成一种办法。
1分点后面至少要有两个元素，2分点前面至少要有1个元素，后面至少要有一个元素。
否则就没法分成3份了。

int main()
{
    ios::sync_with_stdio(0);
    LL n, a[500005] = {0}, sum = 0, ans = 0;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sum += a[i];
    }

    LL k1 = 0;
    if (sum % 3 == 0) {
        LL s = 0, aver = sum / 3;
        for (int i = 0; i < n; ++i) {
            s += a[i];
            if (2 * aver == s && i > 0 && i < n - 1) {
                ans += k1;
            }
            if (aver == s && i < n - 2) {
                k1++;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

D. Increase Sequence

题意： n长度的数组，a₁， a₂， …， a_n初始高度为1目标需要每个元素增加到高度h，增加的方式是选择一个闭区间[l,r]，闭区间内所有元素高度+1，同时任意一个元素不能被选作左端点两次，也不能被选作右端点两次。

分析：非常奇妙的一个DP的题目。解法里有一维和二维，从二维的角度比较容易理解。

首先dp[i][j]表示第i个元素处理完成同时还有j个左端点没有闭合的情况数。处理完成是指i元素增加到了h高度。

对i元素要满足有j个左端点处理的方式有5种：

”]” 即添加一个右端点要满足有j个左端点，需要从[i-1][j+1]转化而来，j+1任意选择一个添加上右端点闭合即可。因此方法数j+1，处理后i元素增加的高度增加j+1。
”][” 即添加一个右端点，并且开启一个区间（添加一个左端点），由[i-1][j]转化而来，方法数j，处理后增加高度j+1。
”[” 即添加一个左端点，由[i-1][j-1]转化而来，方法数1，处理后高度增加j。
”[]” 即添加一个区间[i, i]，由[i-1][j]转化而来，方法数1，处理后高度增加j+1。
“N” 即什么都不做，由[i-1][j]转化而来，方法数1，处理后高度增加j。

同时需要满足的条件是增加的高度需要为h - a[i]，如果不满足则可以认为方法数为0.
即对于方法1,2,4，增加的高度是j+1，我们需要这个值等于h - a[i]，即j = h - a[i] - 1，因此关心的i-1的j^’也能推算出来。

因此虽然我们开辟了二维的数组dp，但是O(n)就可以完成了。
看到有开辟一维数组的办法，没看懂，有路过的高手欢迎讲解下。
初始条件dp[0][0] = 1;即0个元素0个左端点的方法数为1。
最后的结果数放在dp[n][0]，即所有元素迭代完，所有区间关闭。

总结一下的话就是下面几行
//操作 : 转化方法 : 转化后增加的高度
// ] : i,j = i-1,j+1 * j+1 : j+1
// ][ : i,j = i-1,j * j : j+1
// [ : i,j = i-1,j-1 : j
// [] : i,j = i-1,j : j+1
// N : i,j = i-1,j : j

int main()
{
    ios::sync_with_stdio(0);

    cin >> n >> h;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i] = h - a[i];
    }

    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        //a[i] height needed.
        if (a[i] != 0) {
            add_equal(dp[i][a[i] - 1], dp[i - 1][a[i]] * a[i]);
            add_equal(dp[i][a[i] - 1], dp[i - 1][a[i] - 1] * (a[i] - 1));
            add_equal(dp[i][a[i] - 1], dp[i - 1][a[i] - 1]);
            add_equal(dp[i][a[i]], dp[i - 1][a[i] - 1]);
        }
        add_equal(dp[i][a[i]], dp[i - 1][a[i]]);
    }

    cout << dp[n][0] << endl;
    return 0;
}

PREVIOUScodeforces Contest 465

NEXTcodeforces Contest 479