D. Dyson Box

题意简述

一个二维的格子框，有些格子里面放了正方形盒子，现在给它一个向下 / 向左的重力，求系统平衡后的盒子外框周长。

解题报告

首先向下向左是一样的，这里只考虑向下。

注意到其实每一竖列放哪是一样的，最终都会落到最底部。

将上下的贡献和左右的贡献分开算，上下的贡献就是：这一排有就 + 2

左右的贡献就是：相邻排的盒子数之差绝对值

这个式子是线性的，然而因为每次修改只会影响到两边（\(|h_i - h_{i - 1}| + |h_{i + 1} - h_i|\)），所以可以做到 \(O(1)\) 修改

代码实现

const int MAXN = 2e5 + 10;

int n;
int land[MAXN], port[MAXN];
int ansland, ansport;

int main() {
    n = read();
    for (int i = 1; i <= n; ++i) {
        int x = read(); int y = read();
        // portrait
        // maintain |h3 - h2| + |h4 - h3|
        ansport -= std::abs(port[x] - port[x - 1]);
        ansport -= std::abs(port[x + 1] - port[x]);
        ++port[x];
        if (port[x] == 1) ansport += 2; // 该列首次添加
        ansport += std::abs(port[x] - port[x - 1]);
        ansport += std::abs(port[x + 1] - port[x]);
        // landscape
        // same
        ansland -= std::abs(land[y] - land[y - 1]);
        ansland -= std::abs(land[y + 1] - land[y]);
        ++land[y];
        if (land[y] == 1) ansland += 2;
        ansland += std::abs(land[y] - land[y - 1]);
        ansland += std::abs(land[y + 1] - land[y]);
        printf("%d %d\n", ansport, ansland);
    } 
    return 0;
}

G. Grade Points Average

题意简述

实现下取整保留 \(k\) 位小数的除法。

解题报告

直接模拟竖式计算就可以了

代码实现

int n, k;

int main() {
    n = read(); k = read();
    int sum = 0;
    for (int i = 1; i <= n; ++i) sum += read();
    printf("%d.", sum / n); sum %= n;
    for (int i = 1; i <= k; ++i) {
        printf("%d", sum * 10 / n); (sum *= 10) %= n;
    } puts("");
    return 0;
}

H. Adventurer's Guild

题意简述

一个勇者在打怪，有红条和蓝条两个参数，红条归零就死，蓝条归负用红条补到零。
一个怪有三个参数，消耗的红条、蓝条和获得的金币。
现在勇者初始有一些红条蓝条，要在不死的情况打怪获得最多金币，求最多金币数。

解题报告

花费一些东西获得另外一些东西，这一看就背包

设 \(f[i][j][k]\) 表示前 \(i\) 个怪，红条剩 \(j\)，蓝条剩 \(k\) 能获得的最大金币数

转移很简单，求出打完怪的红条和蓝条，之后加上金币值转移

需要把第一维滚掉

代码实现

const int MAXN = 1000 + 10;
const int MAXH = 300 + 10;
const int MAXS = 300 + 10;

int n, h, s;
int dp[2][MAXH][MAXS];
int hs[MAXN], ss[MAXN], ws[MAXN];

int main() {
    n = read(); h = read(); s = read();
    for (int i = 1; i <= n; ++i) {
        hs[i] = read(); ss[i] = read(); ws[i] = read();
    }
    for (int i = 1; i <= n; ++i) {
        int ii = i & 1;
        for (int he = 1; he <= h; ++he) {
            for (int san = 0; san <= s; ++san) {
                dp[ii][he][san] = dp[ii ^ 1][he][san];
                int nh = he - hs[i];
                int nsan = san - ss[i];
                if (nsan < 0) nh += nsan, nsan = 0;
                if (nh <= 0) continue;
                dp[ii][nh][nsan] = std::max(dp[ii][nh][nsan], dp[ii ^ 1][he][san] + ws[i]);
                // DEBUG(i); DEBUG(nh); DEBUG(nsan);
                // DEBUG(dp[ii][nh][nsan]);
            }
        }
    }
    int ans = 0;
    for (int i = 0; i <= 1; ++i)
        for (int he = 1; he <= h; ++he) 
            for (int san = 0; san <= s; ++san)
                ans = std::max(ans, dp[i][he][san]);
    printf("%d\n", ans);
    return 0;
}