Codeforec Contest 466

#codeforce

题目链接在这里

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≤109,因此理论上讲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分点。

  1. sum可以整除3.
  2. 2分点可以与前面任意一个1分点组合成一种办法。
  3. 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长度的数组,a1, a2, …, an初始高度为1目标需要每个元素增加到高度h,增加的方式是选择一个闭区间[l,r],闭区间内所有元素高度+1,同时任意一个元素不能被选作左端点两次,也不能被选作右端点两次。

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

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

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

  1. ”]” 即添加一个右端点 要满足有j个左端点,需要从[i-1][j+1]转化而来,j+1任意选择一个添加上右端点闭合即可。因此方法数j+1,处理后i元素增加的高度增加j+1。
  2. ”][” 即添加一个右端点,并且开启一个区间(添加一个左端点),由[i-1][j]转化而来,方法数j,处理后增加高度j+1。
  3. ”[” 即添加一个左端点,由[i-1][j-1]转化而来,方法数1,处理后高度增加j。
  4. ”[]” 即添加一个区间[i, i],由[i-1][j]转化而来,方法数1,处理后高度增加j+1。
  5. “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;
}