D. Dyson Box
题意简述
一个二维的格子框，有些格子里面放了正方形盒子，现在给它一个向下 / 向左的重力，求系统平衡后的盒子外框周长。
解题报告
首先向下向左是一样的，这里只考虑向下。
注意到其实每一竖列放哪是一样的，最终都会落到最底部。
将上下的贡献和左右的贡献分开算，上下的贡献就是：这一排有就 + 2
左右的贡献就是：相邻排的盒子数之差绝对值
[sum |h_i - h_{i - 1}|
]
这个式子是线性的，然而因为每次修改只会影响到两边（(|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
", 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
", ans);
return 0;
}
M. Matrix Problem
题意简述
有 A B C 三个 01 矩阵，满足 A and B = C，且 A B 的 1 都是四联通的。现在给定 C，构造出 A B 的一组可行解。
保证 C 的边框一圈都是 0。
解题报告
保证 C 边框一圈都是 0 这个条件很有意思，这意味着我们可以通过两边将矩阵联通
设 A 的左边都是 1，右边都是 0；B 的右边都是 1，左边都是 0。这样 and 起来也是 0，而且联通了每个矩阵的每一行。
接下来隔行填 1，比如 A 的奇数行是 1，B 的偶数行是 1。
这样就可以通过操纵 A 的偶数行元素、B 的奇数行元素来确定每个格子。
代码实现
const int MAXNM = 500 + 10;
int n, m;
bool A[MAXNM][MAXNM], B[MAXNM][MAXNM], C[MAXNM][MAXNM];
char ss[MAXNM];
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%s", ss + 1);
A[i][1] = B[i][m] = 1;
for (int j = 1; j <= m; ++j) {
C[i][j] = (ss[j] == '1');
if ((i & 1) && j != 1 && j != m) {
A[i][j] = 1;
B[i][j] = C[i][j];
} else if ((!(i & 1)) && j != 1 && j != m) {
B[i][j] = 1;
A[i][j] = C[i][j];
}
}
}
puts("");
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
printf("%d", (int) (A[i][j]));
} puts("");
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
printf("%d", (int) (B[i][j]));
} puts("");
}
return 0;
}