D. Timetable
转化成背包问题
dp预处理
很容易看出来是背包，但是怎么把区段内的时间转化成物品很吃力。
首先物品的体积肯定不能直接用题目给的时间点，而是用逃课的数量。
然后对物品的价值进行预处理
- 预处理出每天的日期
- 每次处理一天留下 \(k\) 个 \(1\) 的物品之前就先跑一遍找出贡献最小的方案
- 然后用这个方案来跑背包就行。
数据很小，不会超时
constexpr int N(500 + 10);
std::vector<int> sched[N];
int dp[N][N];
void solve() {
int n, m, k;
std::cin >> n >> m >> k;
std::string s;
for (int i = 1; i <= n; i++) {
std::cin >> s;
for (int j = 0; j < m; j++) {
if (s[j] == '1') {
sched[i].push_back(j);//预处理出每一天的1的日期
}
}
}
memset(dp, 0x3f, sizeof dp);
dp[0][0] = 0;
for (int i = 1; i <= n; ++i) {
int siz(sz(sched[i]));
for (int cnt = 0; cnt <= siz; ++cnt) {
int res = m;//先求出当前选择cnt个1的能得到的最小贡献
if (cnt) {
for (int l = 0, r = cnt - 1; r < siz; ++l, ++r) {//暴力枚举一边所有区间
res = std::min(res, sched[i][r] - sched[i][l] + 1);
}
}
else {//如果是选择0个，那显然贡献就是0
res = 0;
}
int cntSkip(siz - cnt);
for (int l = 0; l + cntSkip <= k; ++l) {//已经转化成了背包问题
dp[i][l + siz - cnt] = std::min(dp[i][l + cntSkip], dp[i - 1][l] + res);
}
}
}
std::cout << *std::min_element(dp[n], dp[n] + k + 1) << '\n';
}
E. Largest Beautiful Number
贪心构造和bitmask的妙用
void solve()
{
#define tests
std::string s;
std::cin >> s;
int n(sz(s));
std::string res;
for (int i = 0; i < n - 2; i++) {
res += '9';
}
for (int lcp = n - 1; lcp >= 0; lcp--) {//从右到左检查，一旦遇到合适的位就输出
if (s[lcp] != '0') {
for (char c = s[lcp] - 1; c >= (lcp == 0 ? '1' : '0'); c--) {//枚举该位的所有可能数码
std::string cur = s.substr(0, lcp) + c;
int mask = 0;//用位来当数码，标记这一位对应的数码是否出现偶数次
for (int i = 0; i < sz(cur); i++) {
mask ^= (1 << (cur[i] - '0'));
}
std::string me;
for (int i = 9; i >= 0; i--) {
if ((mask >> i) & 1) {
me += (i + '0');//为落单的凑，从大到小凑，尽量接近给的数
}
}
while (sz(cur) + sz(me) < sz(s)) {//剩下的全部凑9
cur += '9';
}
cur += me;
if (sz(cur) == sz(s)) {
res = cur;
break;
}
}
if (sz(res) == sz(s)) {
break;
}
}
}
std::cout << res << '\n';
}
F. Fibonacci String Subsequences
矩阵
考虑每个 \(F(x)\) 中与 \(s\) 相同的子序列的贡献。设这个子序列为 \(F(x)_{p_1}, F(x)_{p_2}, F(x)_{p_3}, \ldots, F(x)_{p_n}\)。
我们想要它成为一个子序列的子串，那么 \(F(x)_{[p_1, p_n]}\) 中除了 \(p_1 \sim p_n\) 就不能有别的字符被选。而 \([1, p_1 - 1] \cup [p_n + 1, |F(x)|]\) 中的每个字符都可以选或不选，相当于每个字符产生 \(2\) 的贡献。
如果我们设 \(f_{i, j}\) 为 kmp 过程中考虑到 \(F(x)\) 的第 \(i\) 位，匹配到 \(s\) 的第 \(j\) 位的答案，那么相当于
\(f_{i + 1, 0} \gets 2 f_{i, 0}, f_{i + 1, n} \gets 2 f_{i, n}, \forall j \in [1, n - 1], f_{i + 1, j} \gets f_{i, j}, \forall j \in [1, n] \land F(x)_i = s_j, f_{i + 1, j} \gets f_{i, j - 1}\)。
答案即为 \(f_{|F(x)|, n}\)。
可以用矩阵刻画这个转移过程。设 \(F_i\) 为 \(F(i)\) 的转移矩阵，那么 \(F_i = F_{i - 1} F_{i - 2}\)。
时间复杂度 \(O(n^3x)\)。
struct mat {
Z a[N][N];
mat() {
memset(a, 0, sizeof a);
}
}dp[N];
mat operator * (const mat &a, const mat &b) {
mat res;
for (int k = 0; k <= n; ++k) {
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= n; ++j) {
res.a[i][j] += a.a[i][k] * b.a[k][j];
}
}
}
return res;
}
void solve() {
std::cin >> n >> m >> s;
dp[0].a[0][0] = dp[0].a[n][n] = dp[1].a[0][0] = dp[1].a[n][n] = 2;
for (int i = 1; i < n; i++) {
dp[0].a[i][i] = dp[1].a[i][i] = 1;
}
for (int i = 1; i <= n; i++) {
if (s[i - 1] == '0') {
dp[0].a[i - 1][i] = 1;
}
else {
dp[1].a[i - 1][i] = 1;
}
}
for (int i = 2; i <= m; i++) {
dp[i] = dp[i - 1] * dp[i - 2];
}
mat ans;
ans.a[0][0] = 1;
ans = ans * dp[m];
std::cout << ans.a[0][n] << '\n';
}
G. Almost Increasing Array
CF946G - Almost Increasing Array - 洛谷专栏 (luogu.com.cn)
过于困难，先放着
标签：std,sz,cur,lcp,int,Edu39,dp From： https://www.cnblogs.com/kdlyh/p/18088228