侥幸全ac了，第二题多重背包的一种优化写法，前几天刚好复习过，运气好。
题目1:给定一个数x，数据对 (a, b)使得a ^ b ^ x能达到最大，求使|a - b|最小的方案总数有多少。
x,a,b的范围都是0 - （2^31 次方-1）
0 -> 2, 100 -> 16
题目2:包粽子, 四个数n, m, c0, d0, 一共n 克面粉， m种馅料
然后m行,每行四个数ai, bi, ci, di, ai 表示一共多少克该种馅料
每个粽子包法, bi克第i种馅料 + ci 克面粉, 收益di, 或者 c0 克面粉, 不包馅料, 收益d0
求最大收益
第一题，可知x^a^b=INT_MAX,就是除去符号位每一位都是1,遍历x的每个bit，如果是1，那么a,b在此位的bit必相等，因为1^1^1=1,1^0^0=1，而相等的话对它们的差就没有贡献了，所以0、1皆可，方案数*2。对于bit为0的情况，差值取最小的话是确定的。最后由于绝对值的对称性*2。特殊情况x=INTMAX，此时x的每一位已经全是1了，所以a-b取最小其实就是所有a=b，方案数INT-MAX + 1,用long存储输出。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
int n, x;
scanf("%d", &n);
while (n--) {
scanf("%d", &x);
LL res = 2;
for (int i = 0; i < 32; ++i) {
if ((x >> i) & 1)
res *= (LL)2;
}
if (x == INT_MAX) printf("%lld\n", res / 2);
else printf("%lld\n", res);
}
return 0;
} 第二题，对于c0,完全背包，对于有馅料的是多重背包
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, c0, d0;
int a, b, c, d;
struct Node {
int v, w;
};
int dp[N];
int main() {
fill(dp, dp + N, 0);
vector<Node> ns;
scanf("%d%d%d%d", &n, &m, &c0, &d0);
for (int i = 0; i < m; ++i) {
scanf("%d%d%d%d", &a, &b, &c, &d);
int cnt = a / b, k = 1;
while (cnt) {
if (cnt >= k) {
ns.push_back(Node{k * c, k * d});
cnt -= k;
k *= 2;
} else {
ns.push_back(Node{cnt * c, cnt * d});
cnt = 0;
}
}
}
for (int i = 0; i < ns.size() + 1; ++i) {
if (i == ns.size()) {
for (int j = c0; j <= n; ++j)
dp[j] = max(dp[j], dp[j - c0] + d0);
} else {
for (int j = n; j >= ns[i].v; --j)
dp[j] = max(dp[j], dp[j - ns[i].v] + ns[i].w);
}
}
printf("%d\n", dp[n]);
return 0;
} 
全部评论
(21) 回帖