题意：有 $k$ 元钱，$n$ 样商品，不买低于 $l$ 元或者大于 $r$ 元的商品，最多能买几件
解法：贪心
#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
inline void solve() {
int n, l, r, k; cin >> n >> l >> r >> k;
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++ ) cin >> a[i];
sort(a.begin() + 1, a.end());
int cnt = 0;
for (int i = 1; i <= n; i ++ ) {
if (a[i] < l || a[i] > r) continue;
if (k >= a[i]) cnt ++, k -= a[i];
}
cout << cnt << endl;
}
int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(2);
int T; cin >> T;
while (T -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
题意：在一个带坐标的直线上造房子，要求从 0 号房子开始走，到 $i$ 号房子的代价是 $2 * times * |x_i - x_0|$，（$x_i$ 表示坐标，times表示访问次数)。问如何造让代价最小，输出最小代价。
解法：贪心，访问次数多的房子放在离起点近即可。
#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
inline void solve() {
int n; cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++ ) cin >> a[i];
vector<int> p(n + 1);
for (int i = 1; i <= n; i ++ ) p[i] = i;
sort(p.begin() + 1, p.end(), [&] (int x, int y) {
return a[x] > a[y];
});
vector<int> res(n + 1);
res[0] = 0;
for (int i = 1; i <= n; i += 2) res[p[i]] = (i + 1) / 2;
for (int i = 2; i <= n; i += 2) res[p[i]] = -(i + 1) / 2;
LL ans = 0;
for (int i = 1; i <= n; i ++ ) ans += 2ll * abs(res[i]) * a[i];
cout << ans << endl;
for (int i = 0; i <= n; i ++ ) cout << res[i] << ' ';
cout << endl;
}
int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(2);
int T; cin >> T;
while (T -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
C. Divan and bitwise operations
题意：一个序列的价值为所有非空子序列的异或值的和，现在不给出原序列，但是给出 $m$ 段连续序列的或值，问原序列的价值可能是多少，保证 $m$ 段连续序列覆盖所有的原序列。
解法：组合计数
由于位运算是按位贡献，所以我们算出每位的贡献即可。
假设对于第 $i$ 位来说，目前到 $l, r, x$ 这段信息了，当 $x$ 的第 $i$ 位为0，说明当前区间的所有数的该位都不可能为0，当 $x$ 的第 $i$ 位为1，不用理。这样扫下来，当确认该位为0的就是0，否则就是1。假设确认为0的数有 $cnt_x$ 个，那么该位对答案的贡献就是 $2^i * 2^{cnt_x} * \sum_{i\in odd}C_{n - cnt_x}^{i}$，化简后就是 $2^{n - 1 + i}$，注意到除非全部为0，否则就有贡献，可以简化写法。
#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
LL q_pow(LL a, LL b, LL p) {
LL res = 1;
for (; b; b >>= 1) {
if (b & 1) res = res * a % p;
a = a * a % p;
}
return res;
}
inline void solve() {
int n, m; cin >> n >> m;
int tmp = 0;
while (m -- ) {
int l, r, x; cin >> l >> r >> x;
tmp |= x;
}
cout << tmp * q_pow(2, n - 1, MOD) % MOD << endl;
}
int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(2);
int T; cin >> T;
while (T -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
D1. Divan and Kostomuksha (easy version)
D2. Divan and Kostomuksha (hard version)
题意：给定 $n$ 个数，让你给这 $n$ 个数重新排列，使得最大化 $$\sum_{i = 1}^{n}gcd(a_1, a_2, …, a_i)$$
解法：筛法+dp
首先容易看出，每组的gcd和第一个数字有密切关系。于是我们统计每个数字的倍数个数，然后利用dp转移来写。
这么说比较抽象，先看代码
#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 5e6 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
inline void solve() {
int n; cin >> n;
vector<int> a(N), cnt(N);//cnt[i]表示i的倍数个数
for (int i = 1; i <= n; i ++ ) {
int x; cin >> x;
a[x] ++;
}
int m = 5000000;
for (int i = 1; i <= m; i ++ ) {
for (int j = i; j <= m; j += i) cnt[i] += a[j];
}
vector<LL> dp(N);//dp[i]表示以i开头的时候的答案是多少
dp[1] = n;
LL res = n;
for (int i = 2; i <= m; i ++ ) {
if (!cnt[i]) continue;
for (int j = 1; 1ll * j * j <= i; j ++ ) {
if (i % j) continue;
dp[i] = max({dp[i], dp[j] + 1ll * cnt[i] * (i - j), dp[i / j] + 1ll * cnt[i] * (i - i / j)});
//答案的更新需要从i的因子来
}
res = max(res, dp[i]);
}
cout << res << endl;
}
int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(2);
// int T; cin >> T;
// while (T -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
但是刚刚的代码只能过 D1，因为其复杂度是O(n sqrtn) 的，想要过 D2，我们就得找一些地方做优化
首先容易看出可优化的地方就是两处转移，分别是cnt和dp的转移
#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 2e7 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
int pr[N], idx;
bool st[N];
void init() {
int n = 2e7;
for (int i = 2; i <= n; i ++ ) {
if (!st[i]) pr[++ idx] = i;
for (int j = 1; 1ll * pr[j] * i <= n; j ++ ) {
st[i * pr[j]] = true;
if (i % pr[j] == 0) break;
}
}
}
inline void solve() {
int n; cin >> n;
init();//加入一个线性筛筛质数
vector<int> cnt(N);
for (int i = 1; i <= n; i ++ ) {
int x; cin >> x;
cnt[x] ++;
}
int m = 2e7;
for (int i = 1; i <= idx; i ++ ) {
//注意这里需要反过来递推，因为这样可以把大的先计算，然后一起算到小的上面
for (int j = m / pr[i]; j; j -- ) cnt[j] += cnt[pr[i] * j];
}
//如果这里的转移没看懂的，建议设m为20然后手写模拟一遍过程，就会理解了。
vector<LL> dp(N);
LL res = 0;
for (int i = 1; i <= m; i ++ ) {
dp[i] = max(dp[i], 1ll * i * cnt[i]);
for (int j = 1; j <= idx; j ++ ) {
//这里的优化比较易懂，是直接拿质数倍优化，减少重复枚举因子
if (pr[j] * i > m) break;
dp[i * pr[j]] = max(dp[i * pr[j]], dp[i] + 1ll * cnt[i * pr[j]] * (i * pr[j] - i));
}
res = max(res, dp[i]);
}
cout << res << endl;
}
int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(2);
// int T; cin >> T;
// while (T -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
dp(i)的含义是什么
D2和D1的dp含义是一样的
如果不太理解的话建议了解下迪利克雷前缀和。
是个狠人！！