4月1日¶
2025-04-01 最近准备多做点DP。。。
总结¶
今日效率较低，白天看了笛卡尔树，洛谷模板题，顺便把杭州M补了，不咋难。
晚上只写了一道绿题。。然后现在是1点53，也是把那个P2679的补了。。
P5658这个，题单里说是树形DP，好好好，还是有一些需要理解的东西。明天接着做DP题单。。
洛谷P1095 普及/提高-¶
2025-04-01 tag: DP
黄题，但是还是做了四五十分钟。。。没啥好说的。
void ChatGptDeepSeek()
{
int m, s, t;
cin >> m >> s >> t;
// 水题 枚举用了多少次魔法就行
vector<int> d(t + 1), T(t + 1), r(t + 1), ned(t + 1);
r[0] = m; // 用 i 次魔法后 剩余的魔法
T[0] = 0; // 用 i 次魔法 恢复需要的时间
ned[0] = (s + 16) / 17; // 用 i 次魔法 走到终点需要的时间
d[0] = (t + 16) / 17 * 17; // 用 i 次魔法 t时间走的距离
for (int i = 1; i <= t; i++)
{
T[i] = T[i - 1];
r[i] = r[i - 1];
if (r[i - 1] < 10)
{
T[i] += (10 - r[i - 1] + 3) / 4;
r[i] = r[i] + (T[i] - T[i - 1]) * 4 - 10;
}
else
r[i] -= 10;
// 剩下 t-T[i]的时间 看能走多少
ned[i] = T[i] + i;
if (ned[i] > t)
break;
d[i] = i * 60 + (t - ned[i]) * 17;
if (s >= i * 60)
{
ned[i] += (s - i * 60 + 16) / 17;
}
// cerr << i << " " << r[i] << " " << T[i] << " " << ned[i] << " \n";
}
int time = t + 1;
for (int i = 0; i <= t; i++)
{
if (d[i] >= s && ned[i] <= t)
{
// cerr << i << " " << ned[i] << " \n";
time = min(time, ned[i]);
}
}
if (time != t + 1)
cout << "Yes\n"
<< time << '\n';
else
cout << "No\n"
<< *max_element(d.begin(), d.end()) << '\n';
}
洛谷P2679 普及+/提高¶
2025-04-01 tag: DP
虽然想了一会，写了一个多小时。但这个就是很正常的DP题，挺好的。
学到一个小技巧，就是很多时候我们开多维的 DP 只会用到 \(i\) 和 \(i-1\) 的，可以滚动数组，我一般喜欢每次循环新开一个。但是其实可以用 \(i\& 1\) 和 \((i\&1) \oplus 1\) 这种表示，比较好写。
constexpr int mod = 1000000007;
int dp[2][202][202];
void ChatGptDeepSeek()
{
int n, m, k;
cin >> n >> m >> k;
// 匹配了i长度，用了 j 段
vector<char> A(n + 1), B(m + 1);
for (int i = 1; i <= n; i++)
cin >> A[i];
for (int i = 1; i <= m; i++)
cin >> B[i];
vector<vector<int>> DP(m + 1, vector<int>(k + 1));
dp[0][0][0] = DP[0][0] = 1;
for (int i = 1; i <= n; i++)
{
vector nDP = DP;
for (int j = 1; j <= min(i, m); j++)
{
if (A[i] == B[j])
{
for (int l = 1; l <= min(k, j); l++)
{
dp[i & 1][j][l] = (dp[i & 1][j][l] + DP[j - 1][l - 1]) % mod;
nDP[j][l] = (nDP[j][l] + DP[j - 1][l - 1]) % mod;
dp[i & 1][j][l] = (dp[i & 1][j][l] + dp[(i ^ 1) & 1][j - 1][l]) % mod;
nDP[j][l] = (nDP[j][l] + dp[(i ^ 1) & 1][j - 1][l]) % mod;
}
}
}
for (int j = 0; j <= min(i, m); j++)
for (int l = 1; l <= min(k, j); l++)
dp[(i ^ 1) & 1][j][l] = 0;
DP = nDP;
}
cout << DP[m][k] << '\n';
}
洛谷P5658 普及+/提高¶
2025-04-01 tag: DFS
我服了，本来是在写 DP题单的，WA了一晚上，不是哥们这跟DP有关系吗？虽然应该可以，但是会很不好做。
学习了题解的方法。。。
void ChatGptDeepSeek()
{
int n;
cin >> n;
string s;
cin >> s;
vector<vector<ll>> adj(n + 1, vector<ll>());
vector<int> fa(n + 1);
for (int i = 2; i <= n; i++)
{
int x;
cin >> x;
fa[i] = x;
adj[x].push_back(i);
}
s = " " + s;
vector<int> stk, lst(n + 1);
vector<long long> sum(n + 1);
auto dfs = [&](auto &&self, int u, int pre) -> void
{
int tmp = 0;
if (s[u] == ')')
{
if (!stk.empty())
{
tmp = stk.back();
stk.pop_back();
lst[u] = lst[fa[tmp]] + 1;
}
}
else
stk.push_back(u);
sum[u] = sum[pre] + lst[u];
for (auto v : adj[u])
{
if (v == pre)
continue;
self(self, v, u);
}
if (tmp)
stk.push_back(tmp);
else if (!stk.empty())
stk.pop_back();
};
dfs(dfs, 1, 0);
long long ans = 0;
for (int i = 1; i <= n; i++)
{
ans ^= (1LL * i * sum[i]);
}
cout << ans << '\n';
}