A. Bus to Pénjamo
题意：有n个家庭，每个家庭有\(a_i\)个人，现在有r排座位，每个座位可以坐两个人。如果一个人自己一个坐一个座位或者和自己家庭的人坐一个座位，他就会开心，问所有人都入座后最多有多少人开心。
我们肯定尽量让一个座位坐两个同一家庭的人，这样一个座位可以让两个人开心。考虑每个家庭落单人数和为cnt，并且还剩下m个座位，我们应该尽量让一个人坐一个位置，设有x个位置坐两个人，y个位置坐一个人，如果$m $$\geqslant$$ cnt $，则直接让所有人一个人坐一个座位，否则有 \(2x\) + \(y\) = cnt, \(x\) + \(y\) = m。解得\(x = cnt - m\)，\(y = cnt - 2 * (cnt - m)\)
点击查看代码
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
int cnt = 0, ans = 0;
for (int i = 0; i < n; ++ i) {
cnt += a[i] % 2;
ans += a[i] / 2;
}
m -= ans;
cnt -= std::max(0, 2 * (cnt - m));
std::cout << ans * 2 + cnt << "\n";
}
B. Kar Salesman
题意: 有n种类型的车, 每种类型的车有\(a_i\)辆, 一个顾客可以最多买\(x\)辆不同的车, 最少需要几个顾客才能买完所有车?
这x搞个小于等于10, 开始我还以为是什么模拟题.
顾客数至少为\(max(a)\), 不然有一种车不可能卖完.
顾客数至少为\(\lceil \frac{\sum_{i=1}^{n} a_i}{x} \rceil\), 因为假设每个顾客都能买\(x\)个,那么这是最少的购买次数.
那么答案就是上面两个的最大值, 因为最大值同时满足这两个的最少顾客数,并且已经是满足条件的顾客数里最小的了. 我们想象有一个有这个最大值行x列的矩阵,每个顾客一行一行的放车, 因为这个矩阵格子数一定大于等于总车辆数, 一定能放完, 并且恰好放到最后一行. 再少一行都不行.
点击查看代码
void solve() {
int n, x;
std::cin >> n >> x;
std::vector<i64> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
i64 sum = 0, max = 0;
for (int i = 0; i < n; ++ i) {
sum += a[i];
max = std::max(max, a[i]);
}
std::cout << std::max(max, (sum + x - 1) / x) << "\n";
}
C. Gerrymandering
题意: 有一个\(2\)行\(n\)列的矩阵, 每个格子上的人要么投票给a, 要么投票给b, 你要给他们分成\(\frac{2n}{3}\)个块内格子数为\(3\)的联通块, 每个联通块如果有两个以上人投票给a, 那么这个连通块就会投票给a, 你要让a获得最大票数.
考虑dp, \(f[i][j]\), \(j \in \{-1, 0, 1\}\)表示第一行填到第i个位置时, 第二行填到的位置j的 i - j, 那么我们就可以考虑每种情况可以转移. 我们如果给第一行三个一起填, 那么第二行也一定是三个一起跟着填, 其他情况画图就懂了.
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<std::string> s(2);
for (int i = 0; i < 2; ++ i) {
std::cin >> s[i];
}
auto get = [&](int a, int b, int c, int d, int e, int f) -> int {
return (s[a][b] == 'A') + (s[c][d] == 'A') + (s[e][f] == 'A') >= 2;
};
std::vector f(n + 1, std::vector<int>(3, -1e9));
const int D = 1;
f[0][0 + D] = 0;
for (int i = 0; i < n; ++ i) {
//f[i][-1]
//1 0
//0 0
if (i && i + 3 < n) {
f[i + 3][-1 + D] = std::max(f[i + 3][-1 + D], f[i][-1 + D] +
get(0, i, 0, i + 1, 0, i + 2)) + get(1, i - 1, 1, i, 1, i + 1);
}
if (i && i + 1 <= n) {
f[i + 1][0 + D] = std::max(f[i + 1][0 + D], f[i][-1 + D] + get(0, i, 1, i - 1, 1, i));
}
//f[i][0]
//1 0
//1 0
if (i + 3 <= n) {
f[i + 3][0 + D] = std::max(f[i + 3][0 + D], f[i][0 + D] +
get(0, i, 0, i + 1, 0, i + 2) + get(1, i, 1, i + 1, 1, i + 2));
}
if (i + 1 < n) {
f[i + 1][1 + D] = std::max(f[i + 1][1 + D], f[i][0 + D] + get(0, i, 1, i, 1, i + 1));
}
if (i + 2 < n) {
f[i + 2][-1 + D] = std::max(f[i + 2][-1 + D], f[i][0 + D] + get(0, i, 0, i + 1, 1, i));
}
//f[i][1]
//1 0
//1 1
if (i + 3 < n) {
f[i + 3][1 + D] = std::max(f[i + 3][1 + D], f[i][1 + D] +
get(0, i, 0, i + 1, 0, i + 2) + get(1, i + 1, 1, i + 2, 1, i + 3));
}
if (i + 2 <= n) {
f[i + 2][0 + D] = std::max(f[i + 2][0 + D], f[i][1 + D] + get(0, i, 0, i + 1, 1, i + 1));
}
}
std::cout << f[n][0 + D] << "\n";
}
D1. Asesino (Easy Version)
待补
标签：std,cnt,int,max,cin,978,VP,++,Div From： https://www.cnblogs.com/maburb/p/18673239