1. Meet in the Middle
给定一个 $n$ 个数的数组 $t$。问在这些数中选择若干数使得总和为 $x$ 的方案数。
限制:
- $1 \leqslant n \leqslant 40$
- $1 \leqslant x \leqslant 10^9$
- $1 \leqslant t_i \leqslant 10^9$
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n, T;
cin >> n >> T;
vector<int> a(n);
rep(i, n) cin >> a[i];
vector<ll> s(1), t(1);
rep(i, n) {
for (int j = s.size()-1; j >= 0; --j) {
ll now = s[j]+a[i];
if (now <= T) s.push_back(s[j] + a[i]);
}
swap(s, t);
}
unordered_map<ll, int> mp;
for (int x : s) mp[x]++;
ll ans = 0;
for (ll x : t) {
ans += mp[T-x];
}
cout << ans << '\n';
return 0;
}
2. ABC184F
给定 $N$ 个数,在数组中选任意个数,使得它们的总和不超过 $T$ 且最大。
限制:
- $1 \leqslant N \leqslant 40$
- $1 \leqslant T \leqslant 10^9$
- $1 \leqslant A_i \leqslant 10^9$
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n, T;
cin >> n >> T;
vector<int> a(n);
rep(i, n) cin >> a[i];
vector<ll> s(1), t(1);
rep(i, n) {
for (int j = s.size()-1; j >= 0; --j) {
ll now = s[j]+a[i];
if (now <= T) s.push_back(now);
}
swap(s, t);
}
sort(s.begin(), s.end());
ll ans = 0;
for (ll x : t) {
int si = upper_bound(s.begin(), s.end(), T - x) - s.begin();
ans = max(ans, x + s[si - 1]);
}
cout << ans << '\n';
return 0;
}
3. 最接近目标值的子序列和
代码实现
using ll = long long;
class Solution {
public:
int minAbsDifference(vector<int>& nums, int goal) {
vector<ll> s(1), t(1);
for (int x : nums) {
for (int j = s.size()-1; j >= 0; --j) {
s.push_back(s[j]+x);
}
swap(s, t);
}
sort(s.begin(), s.end());
ll res = 1001001001;
for (ll x : t) {
auto it = lower_bound(s.begin(), s.end(), goal-x);
if (it != s.end()) res = min(res, abs(x + *it-goal));
if (it != s.begin()) res = min(res, abs(x + *prev(it)-goal));
}
return res;
}
};
4. 最大的余数
给定 $n$ 个数字 $a_1,a_2,\dots,a_n$,在给定一个整数 $m$,请从给定的数字中挑选任意多个数字,使得它们的和模 $m$ 的余数尽量大,输出这个最大的余数。
限制:
- $1 \leqslant n \leqslant 40$
- $1 \leqslant a_i \leqslant 10^9$
- $1 \leqslant m \leqslant 10^9$
算法分析
折半搜索 $\to$ 二分
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n);
rep(i, n) cin >> a[i];
vector<int> s(1), t(1);
rep(i, n) {
for (int j = s.size()-1; j >= 0; --j) {
int x = s[j]+a[i];
x %= m;
s.push_back(x);
}
swap(s, t);
}
set<int> st(t.begin(), t.end());
int ans = 0;
for (int x : s) {
auto it = st.upper_bound(m-1-x);
--it;
int now = *it + x;
ans = max(ans, now);
}
cout << ans << '\n';
return 0;
}