A,B都写了，但是拿出来讲的意义不打就不太讨论，D题目感觉过于麻烦，我讲讲C,D,F三个题目吧,
C - Robot Factory
题目面板如图所示:
问题陈述
高桥可以将头部部件和身体部件组合成一个机器人。如果头部部件的重量大于身体部件的重量，机器人就会摔倒。
目前，他有 $N$ 个头部部件和 $M$ 个身体部件。头部 $i$ - $(1\le i\le N)$ 的重量为 $H _ i$ 克，身体 $i$ - $(1\le i\le M)$ 的重量为 $B _ i$ 克。
他希望通过适当组合他所拥有的部件，制造出总共 $K$ 个不会倒下的机器人。请判断他能否通过合理组合零件来实现目标。
在这里，一个零件不能用来制造多个机器人，两个或多个头部零件（或两个或多个身体零件）不能用来制造一个机器人。
# #约束
—— $1\le N\le2\times10 ^ 5$
—— $1\le M\le2\times10 ^ 5$
—— $1\le K\le\min\lbrace N,M\rbrace$
—— $1\le H _ i\le10 ^ 9\ (1\le i\le N)$
—— $1\le B _ i\le10 ^ 9\ (1\le i\le M)$
—所有输入值均为整数。
# #输入
输入来自标准输入，格式如下：
$N$ $M$ $K$
$H _ 1$ $H _ 2$ $\ldots$ $H _ N$
$B _ 1$ $B _ 2$ $\ldots$ $B _ M$
`
# #输出
如果Takahashi能够很好地将零件组合在一起，制造出不摔倒的机器人，则打印“Yes”；否则，打印‘ No ’。
思考：如何判断能不能组成K个符合题目要求的机器人呢，我们可以贪心的想，我们拿前K个最轻的头部零讲和最重的K个身体部分一一配对，如果最后这K个能够合法，那么就能能够合成K个，否则不行。显然这个贪心是正确的。
AC代码：
#include <bits/stdc++.h>
using namespace std;
// CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p << 1
#define rc p << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps = 1e-5;
const int N = 1e5 + 10, M = 2 * N, K = 26;
const ll MOD = 1e9 + 7, Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template <typename T>
bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template <typename T>
void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
struct Random
{
mt19937_64 rng;
Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); }
ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); }
bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); }
template <typename T>
void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); }
};
ll qmi(ll a, ll b, ll p)
{
ll res = 1 % p;
a %= p;
while (b)
{
if (b & 1)
res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
/*
*/
void solve()
{
ll n, m, k;
cin >> n >> m >> k;
vll h(n + 1, 0), b(m + 1, 0);
rep(i, 1, n) cin >> h[i];
rep(i, 1, m) cin >> b[i];
ll ans = 0;
sort_range(h, 1, n);
sort_range(b, 1, m);
rep(i, 1, k)
{
if (h[i] > b[m - k + i])
{
cout << "No" << endl;
return;
}
}
cout << "Yes" << endl;
}
int main()
{
IOS;
int _ = 1;
// cin>>_;//如果是多组数据
while (_--)
{
solve();
}
return 0;
}D - Robot Customize
题目面板:
问题陈述
有一个由头部和身体组成的机器人。该机器人具有可同时连接的 $N$ 类零件： $1,$ 类零件 $2,\ldots,$ 类零件 $N$ 类零件。 $i\ (1\le i\le N)$ 型零件的重量为 $W _ i$ 。每个部分连接到头部和连接到身体时都有不同的“快乐”。类型 $i\ (1\le i\le N)$ 部件附在头部时的幸福值为 $H _ i$ ，附在身体时的幸福值为 $B _ i$ 。
如果头部的重量大于身体的重量，机器人就会摔倒。在这里，头部的重量和身体的重量是分别附着在头部或身体上的部分的重量之和。
Takahashi想把所有类型的零件都装到机器人上，每种都装一个。在不导致机器人摔倒的情况下，找到所有部件的最大可能幸福总和。
# #约束
—— $1\le N\le500$
—— $1\le W _ i\le500\ (1\le i\le N)$
—— $1\le H _ i\le10 ^ 9\ (1\le i\le N)$
—— $1\le B _ i\le10 ^ 9\ (1\le i\le N)$
—所有输入值均为整数。
Input
The input is given from Standard Input in the following format:
$N$
$W _ 1$ $H _ 1$ $B _ 1$
$W _ 2$ $H _ 2$ $B _ 2$
$\vdots$
$W _ N$ $H _ N$ $B _ N$
# #输出
打印出所有部件的最大可能幸福总和，当这些部件连接在一起时，不会导致机器人摔倒。
分析:我们有N个零件，装在头部和装到身体部分都有各自的对应的幸福值，我们在求最后答案的时候要满足所选择的头部分的重量要低于身体部分的重力，才能算可能合法的答案。
思考：
拿到题目，我们首先会想什么？
对于每个零件，我们都有两个选择：放头上，或者放身上。N个零件，就是N次“二选一”。这听起来是不是有股熟悉的味道？但那个“头部重量 ≤ 身体重量”的约束条件像一团迷雾，笼罩着我们。头部的重量和身体的重量是相互关联的。我们给头部增加一个零件，身体那边就少了一个，此消彼长，这个不等式该如何处理呢？
直接暴力搜索？2^N种组合，在N=500的规模下，超级计算机也得算到天荒地老。我们必须找到更聪明的办法！
想象一下，我们面前有一个巨大的工作台，所有N个零件都堆在上面。现在，我们做一个大胆的决定：默认先把所有零件都安装到“身体”上.此时，机器人稳如泰山，绝对不会摔倒。我们获得了一个基础的幸福值总和，就是所有零件B_i的总和。
现在，我们的任务变了！我们不再是“二选一”，而是变成了：对于每个零件，我们是否要将它从“身体”移动到“头部”？
*不移动：没变化。
*移动：如果我们把第i个零件从身体挪到头上：
1.重量变化：头部的重量增加了 W_i。
2.幸福值变化：我们失去了 B_i 的幸福值，但得到了 H_i 的幸福值。总幸福值的变化量是 H_i - B_i。
现在，我们的目标是：挑选一部分零件，将它们从身体移动到头部，使得我们获得的“幸福值增量”（H_i - B_i）之和最大。
但是，这个移动过程不能随心所欲，它必须遵守那个“不摔倒”的铁律：头部总重量 ≤ 身体总重量
那么我们背包的容量上限就是Total_W / 2（就是我们的机器人头部）。
于是我们的问题变成了：
1.我们有一个容量上限为 Total_W / 2 的背包（就是我们的机器人头部）。
2.我们有N个物品（就是N个零件）。
3.每个物品i的重量是 W_i。
4.把物品i放入背包能获得的价值是 H_i - B_i。（注意，这个价值可能是负数哦！）
我们的目标，不就是在不超过背包总容量的前提下，挑选物品放入，使得总价值最大吗？
这不就是经典的“0/1背包问题”吗？！ 想到这里一切都拨云见日了。
AC代码:
using namespace std;
// CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p << 1
#define rc p << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps = 1e-5;
const int N = 5e2 + 10, M = 2 * N, K = 26;
const ll MOD = 1e9 + 7, Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template <typename T>
bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template <typename T>
void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
struct Random
{
mt19937_64 rng;
Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); }
ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); }
bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); }
template <typename T>
void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); }
};
ll qmi(ll a, ll b, ll p)
{
ll res = 1 % p;
a %= p;
while (b)
{
if (b & 1)
res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
/*
*/
void solve()
{
ll n;
cin >> n;
vll w(n + 1, 0), a(n + 1, 0), b(n + 1, 0);
ll tot = 0;
rep(i, 1, n) cin >> w[i] >> a[i] >> b[i], tot += w[i];
vll f(tot + 1, -INF);
f[0] = 0;
rep(i, 1, n)
{
dep(j, tot, 0)
{
f[j] += b[i];
if (j >= w[i])
cmax(f[j], f[j - w[i]] + a[i]);
}
}
ll ans = 0;
rep(i, 0, tot / 2)
{
cmax(ans, f[i]);
}
cout << ans << endl;
}
int main()
{
IOS;
int _ = 1;
// cin>>_;//如果是多组数据
while (_--)
{
solve();
}
return 0;
}
思考:
为什么代码里面我要把f数组全部赋值为-INF（一个根本取不到的非法值）呢？
解答：f[j] 的含义：在使用过我们考虑的所有零件后，头部重量恰好为 j 时，能获得的最大总幸福度状态转移方程如下：
*f_新[j] = max( f_旧[j] + b[1], f_旧[j - w[1]] + a[1] )
*1.对于一个不可能的终点 j (比如 j 不等于0也不等于 w[1]):
*f_旧[j] 是 -INF (不可能)。
*f_旧[j - w[1]] 也是 -INF (不可能)。
*那么 f_新[j] = max(-INF + b[1], -INF + a[1])，结果仍然是 -INF。
*效果：一个“不可能”的状态，无论怎么转移，得到的都还是“不可能”。这个幻觉被成功地隔离了，无法影响到真实存在的情况。
一些参考背包问题的链接:
01背包概念
01背包、完全背包、多重背包、分组背包问题讲解
看完这些想必你一定明白了背包为什么有些循环是正序 有些又是倒叙更新的，有些背包问题初始化赋值是0就可以有些却要赋值一些不合法的值等，而且你一定明白了空间优化是如何来的，为什么可以这样优化。
F - Almost Sorted 2
题面：
问题陈述
给定一个长度为 $N$ 的整数序列 $A=(A _ 1,A _ 2,\ldots,A _ N)$ 和一个正整数 $D$ 。
求将 $A$ 重新排列得到的整数序列 $B=(B _ 1, B _ 2, \ldots, B _ N)$ 的模 $998244353$ ，并满足以下条件：
- $B _ {i+1}\geq B _ i-D$ 适用于所有 $i\ (1\leq i\leq N-1)$ 。
# #约束
—— $2\leq N\leq 2\times 10^5$
—— $1\leq D\leq 10^6$
—— $1\leq A _ i\leq 10^6$
—所有输入值均为整数。
# #输入
输入来自标准输入，格式如下：
$N$ $D$
$A_1$ $A_2$ $\ldots$ $A_N$
# #输出
打印答案。
思路：
核心规则 B[i+1] >= B[i] - D:后一个数可以比前一个数小，但最多不能小超过 D
直接去枚举所有 N! 种排列，然后逐一检查，对于 N=200000 来说是天文数字，肯定不行。我们需要更聪明的办法。
这种计数问题，通常可以尝试动态规划（DP）或者构造法。我们不一次性考虑所有 N 个数，而是从小到大，一个一个地把数字加入到我们的排列中。
1.排序:为了方便我们按从小到大的顺序处理，第一步自然是把原始数组 A 进行排序。我们叫排序后的数组为 a。例如，A = (5, 2, 1, 2) 排序后得到 a = (1, 2, 2, 5)。
2.构造过程：我们来模拟这个构造过程。
*第1步：我们只有最小的数 a[1]。构造一个只包含它的序列 (a[1])。方法只有 1 种。
*第2步：现在我们手里有一个新数字 a[2]，需要把它插入到已经排好的序列 (a[1]) 中去。
*可以插在 a[1] 后面，形成 (a[1], a[2])
*可以插在 a[1] 前面，形成 (a[2], a[1])
*3.我们又拿到了一个新数字 a[3]，需要把它插入到上一步形成的某个长度为2的合法序列中。比如我们上一步形成了 (a[1], a[2])，现在要把 a[3] 插进去。
*可以插在最前面 (a[3], a[1], a[2])。
*可以插在中间 (a[1], a[3], a[2])。
*可以插在最后面 (a[1], a[2], a[3])。
......
*第 i 步：我们手里有一个新数字 a[i]，需要把它插入到一个已经由 {a[1], ..., a[i-1]} 构成的合法序列中。
通过观察和推理后我们发现:a[i] 能插入的位置数量，与 {a[1], ..., a[i-1]} 的具体排列方式无关！我们得出了一个结论：a[i] 可以被插入到某个元素 x 的前面，当且仅当 x >= a[i] - D。
DP状态转移这下思路就清晰了。设 dp[i] 是用 {a[1], ..., a[i]} 这 i 个数能组成的合法序列的数量。
dp[i] = dp[i-1] * (在第i步时，a[i]的合法插入位置数量)
dp[i] = dp[i-1] * (1 + |{ j < i | a[j] >= a[i] - D }|)
*dp[1] = 1。
*总答案就是 dp[N]。
这个过程等价于一个累乘：
ans = 1 * (a[2]的插入位置数) * (a[3]的插入位置数) * ... * (a[N]的插入位置数)
AC代码附带注释：
#include <bits/stdc++.h>
using namespace std;
// CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define debug(...) cout << "[debug] " #__VA_ARGS__ " = " << (__VA_ARGS__) << endl;
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p << 1
#define rc p << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps = 1e-5;
const int N = 1e5 + 10, M = 2 * N, K = 26;
const ll MOD = 1e9 + 7, Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template <typename T>
bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template <typename T>
void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
struct Random
{
mt19937_64 rng;
Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); }
ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); }
bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); }
template <typename T>
void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); }
};
ll qmi(ll a, ll b, ll p)
{
ll res = 1 % p;
a %= p;
while (b)
{
if (b & 1)
res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
/*
*/
void solve()
{
ll n, d;
cin >> n >> d;
vll a(n + 1, 0), cnt(1e6 + 10, 0);
rep(i, 1, n) cin >> a[i];
sort_range(a, 1, n);
ll p = 1, ans = 1;// 这是一个双指针技巧里的慢指针
rep(i, 1, n)
{
while (a[p] < a[i] - d)// 找到第一个满足 a[p] >= a[i] - D 的位置 p
p++;
// 计算插入位置数并累乘
// |{j < i | a[j] >= a[i] - D}| = (i-1) - p + 1
// 总插入位置数 = 1 + ((i-1) - p + 1) = i - p + 1
ans = (ans * (i - p + 1)) % Md3;
}
ll down = 1;
rep(i, 1, n)
{
cnt[a[i]]++;
down = (down * cnt[a[i]]) % Md3;
}
ans = ans * qmi(down, Md3 - 2, Md3) % Md3;
cout << ans << endl;//最终答案 = (第一步算出的答案) / (所有数字的重复次数的阶乘的乘积)
}
int main()
{
IOS;
int _ = 1;
// cin>>_;//如果是多组数据
while (_--)
{
solve();
}
return 0;
}