3月12日-3月31日¶
这里将记录每天写的一些不属于最新的比赛里的题目，并且是对当前的我稍微有点难度的题目。
CF2063D *2000¶
2025-03-12
这题并不难的，没看题解45分钟写出来的，WA了一发数组没开 ll ，耽误了三四分钟。
首先我们先考虑 \(x\) 取 \(1\) 的答案，必然是从上面或者下面选两个距离最远的点，再从另一边随便选一个点。
考虑 \(x\) 取 \(2\) 的情况呢，会不会把 \(x=1\) 的三个点给还原回来呢? 什么时候会还原回来？
如果你能直接再选 \(3\) 个合法的点出来，那么就不需要再去改之前的方案了。
因为你选另一边的点当底边显然不会影响这一边的底边的面积。至于说把这两个点重新分配到这边组两个底边，就更不可能了。
所以只有当前的点不够再开一个新的三角形了，才有可能拆一个已经拼好的三角形。并且拆了之后得能拼出两个三角形才行。
考虑一下，拆一个三角形会使一边增加2个点，另一边加1个点。新拼成的两个三角形的顶点是一定在同一条边上的。。。我上午写的时候都没考虑这个来着，就只想着是会在同一边，虽然这确实挺直觉的，也很好推的。可能是因为样例的提示吧。
然后就是直接模拟就好了。 拆一个三角形的话，肯定得删边最短的那个。
void ChatGptDeepSeek()
{
// 主要是看上面取多少个 下面取多少个
int n, m;
cin >> n >> m;
vector<int> a(n + 1), b(m + 1);
set<int> u, d;
priority_queue<int, vector<int>, greater<>> uq, dq;
for (int i = 1; i <= n; i++)
cin >> a[i], u.insert(a[i]);
for (int i = 1; i <= m; i++)
cin >> b[i], d.insert(b[i]);
int U = 0, D = 0;
ll ans = 0;
vector<ll> res;
for (int i = 1;; i++)
{
int uu = 0, dd = 0;
if (u.size() >= U + 2 && d.size() >= D + 1)
{
uu = *u.rbegin() - *u.begin();
}
if (d.size() >= D + 2 && u.size() >= U + 1)
{
dd = *d.rbegin() - *d.begin();
}
// cerr<<dd<<" "<<uu<<'\n';
if (dd + uu == 0)
{
// cerr<<u.size()<<" "<<U<<" "<<d.size()<<" "<<D<<'\n';
// cerr<<"empty: "<<uq.size()<<'\n';
// 上面的减去两个，或者是下面的减去两个
if (u.size() >= U + 3 && !dq.empty())
{
ans += *u.rbegin() - *u.begin();
// uq.push(*u.rbegin() - *u.begin());
u.erase(u.begin()), u.erase(prev(u.end()));
ans += *u.rbegin() - *u.begin();
// uq.push(*u.rbegin() - *u.begin());
u.erase(u.begin()), u.erase(prev(u.end()));
ans -= dq.top();
dq.pop();
U--;
}
else if (d.size() >= D + 3 && !uq.empty())
{
// cerr<<"here\n";
ans += *d.rbegin() - *d.begin();
// dq.push(*d.rbegin() - *d.begin());
d.erase(d.begin()), d.erase(prev(d.end()));
ans += *d.rbegin() - *d.begin();
// dq.push(*d.rbegin() - *d.begin());
d.erase(d.begin()), d.erase(prev(d.end()));
ans -= uq.top();
uq.pop();
D--;
}
else
break;
}
else if (dd >= uu)
{
d.erase(d.begin());
d.erase(prev(d.end()));
U++;
ans += dd;
dq.push(dd);
}
else
{
u.erase(u.begin());
u.erase(prev(u.end()));
D++;
ans += uu;
uq.push(uu);
}
// cout<<ans<<" ";
res.push_back(ans);
}
cout << res.size() << '\n';
for (auto x : res)
cout << x << " ";
cout << '\n';
}
CF2069E *2300¶
2025-03-14
由于是没有 AA 和 BB 这种的，所以连着的 A B ， 我们只能花单个的 A 和 B 。所以我们可以把序列拆成若干个首尾不同的序列。
例如 ABABA ABABAB BABAB BABA 这种。看起来会不太好处理。。但是当你看了题解之后就很简单了。。观察一下，对于奇数长度的，我们使用 AB 和 BA ， 额外的单个的花费是相同的。但是偶数长度的 ABABAB 如果要用 BA 的话会比使用 AB 多一个额外的花费。BABABA 同理。
所以我们优先把偶数长度的处理完，然后剩下的多的数量就去处理其他的。并且我们每用对应的 AB 或 BA 处理完一个偶数长度的序列都可以省一些花费，所以我们先处理长度较短的字符串。
然后就好好分类讨论就好了。（其实都没必要存字符串
void ChatGptDeepSeek()
{
string s;
cin >> s;
int a, b, ab, ba;
cin >> a >> b >> ab >> ba;
vector<string> v;
for (int i = 0; i < s.size(); i++) {
int j = i + 1;
string t(1, s[i]);
while (j < s.size() && s[j] != s[j - 1]) {
t += s[j];
j++;
}
i = j - 1;
if (t.size() > 1)
v.push_back(t);
}
sort(v.begin(), v.end(), [](string x, string y) {
if ((x.size() ^ y.size() ^ 1) & 1)
return x.size() < y.size();
// if(x.size()==y.size())
// return x<y;
return x.size() % 2 < y.size() % 2;
});
int A = count(s.begin(), s.end(), 'A'), B = s.size() - A;
for (auto x : v) {
// cerr<<x<<" \n";
int len = x.size();
if (x.size() & 1) {
// 奇数用谁都一样的
while (ab && len > 1) {
A--, B--;
ab--;
len -= 2;
}
while (ba && len > 1) {
A--, B--;
ba--;
len -= 2;
}
} else {
if (x.front() == 'A') {
if (ab >= len / 2) {
ab -= len / 2;
A -= len / 2, B -= len / 2;
len = 0;
// cerr<<ab<<'\n';
} else {
len -= 2 * ab;
A -= ab, B -= ab;
ab = 0;
}
if (len) {
if (ba >= (len - 2) / 2) {
ba -= (len - 2) / 2;
A -= (len - 2) / 2, B -= (len - 2) / 2;
} else {
A -= ba, B -= ba, ba = 0;
}
}
} else {
if (ba >= len / 2) {
ba -= len / 2;
A -= len / 2, B -= len / 2;
len = 0;
} else {
len -= 2 * ba;
A -= ba, B -= ba;
ba = 0;
}
if (len) {
if (ab >= (len - 2) / 2) {
ab -= (len - 2) / 2;
A -= (len - 2) / 2, B -= (len - 2) / 2;
} else {
A -= ab, B -= ab, ab = 0;
}
}
}
}
}
// cerr<<ab<<" "<<ba<<'\n';
assert(A >= 0 && B >= 0);
if (A <= a && B <= b)
cout << "YES\n";
else
cout << "NO\n";
}
CF1981C *1800¶
2025-03-14
好题。。
可以看成一颗满二叉树， \(x\) 可以走到 \(2x\) 和 \(2x+1\) ，这正好对应的是二叉树上的两个子节点。但是知道了这个也确实没办法做吧。
于是题解告诉我们这题与 LCA 有关。然后我去看了下 LCA ，回来发现，这这不对啊 \(10^8\) 这让我怎么 LCA 啊。。。
这题可以转换成给两个二叉树的点，我们要使它们相遇。那么最短的距离就是在它们两到LCA的路径上 ，然后如果有多的步数，就每次走到相邻的再走回来就行。当然剩余的步数必须是偶数才行。
考虑一下 再它们走到 相遇 之前，路径已经是最短的了，所以只能额外消耗步数。这一个过程是没有办法消耗奇数步的。因为比如一个节点后退了一步，那么这一步后面也是会补回来的 或者说是消耗了你的一个前进的步数，所以总体一直是奇偶保持不变的。
而它们相遇之后，同样不可能去消耗奇数步，要么一个节点出去再回来，这样是 2 倍的路程，消耗必然是偶数，如果它们一起走，那消耗的步数也必然是偶数。
所以现在问题转换成了如何让它们走到 LCA 上，看了哥哥的代码，太牛了。。。就是左右端点，哪个大就把哪个除以二。。这就是相当于把一个点往上移了一层，我们最终是要把两个点都移动到 LCA 那一层。而由于是一颗满二叉树，所以最多只会有二三十层的。如果一个节点数值更大，那么它的层数一定是大于等于另一个点的。
void ChatGptDeepSeek()
{
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
a[0] = 1;
int l = -1, r = 0;
for (int i = 1; i <= n; i++) {
if (a[i] != -1) {
r = i;
if (l == -1) {
for (int j = i - 1; j >= 1; j--)
a[j] = a[j + 1] == 1 ? 2 : a[j + 1] / 2;
} else {
int L = l, R = r;
while (L < R - 1) {
if (a[L] >= a[R]) {
a[L + 1] = a[L] == 1 ? 2 : a[L] / 2;
L++;
} else {
a[R - 1] = a[R - 1] == 1 ? 2 : a[R] / 2;
R--;
}
}
if (a[L] != a[R] / 2 && a[L] / 2 != a[R]) {
cout << "-1\n";
return;
}
}
l=i;
}
}
for (int i = r + 1; i <= n; i++)
a[i] = a[i - 1] == 1 ? 2 : a[i - 1] / 2;
for (int i = 1; i <= n; i++)
cout << a[i] << " \n"[i == n];
}
就像这题以及很多的 CF 题，你要问用了什么算法，好像真没什么算法。但你要说难不难。。。我感觉还是挺难的。
多做点好题吧，积攒一下（）。
CF1975D *1700¶
2025-03-17
很好的题目，即使是我也能感到心潮澎湃。
我们希望蓝色的点早点走到被染成红色的点上。
因为从一个点遍历树，最少的情况每个边都会被走 \(2\) 遍，但是这个情况下我们最后一次是不用回去的。
所以贡献会减去最后去的一个点到根节点的距离，所以我们希望最后一个点距离根节点尽量的远。并且蓝色的点肯定一走到红色的区域就该开始了，因为红色可以自动去把蓝色该走的地方给走了。而且即使这时调整位置，距离根节点最大的距离也最多只会减一，并不会使得答案更小。
// 感觉只能一个子树一个子树的走。。。
// 如果蓝色的不在根节点或与根相连
// 那么我们肯定让红色的先走它在的子树
// 然后它自己走到深度为1的点就好了 否则它需要走到根节点去
// 如果在根节点 那么需要额外花费两个费用
// 遍历一个子树必然会把这个子树的每条边都走两次 除了最后去的一些边。。
// 。。。。好像很不好讨论的。。。。
// 好像还真是什么很神奇的结论。。。
// 太牛，也是直接看了题解。。
// 遍历一颗树 如果最后要回到根节点 那么最小的走的路程就是每条边都走两次
// 但是如果最后不回来呢？实际上就是减少了最后一个点到根节点的距离
// 所以如果最后不回来，那我们希望它最后一个去的点距离根节点最远
// 所以我们希望a b 尽可能快的相遇。。
// 无法相遇也没关系。因为那就相当于红色比蓝色多一步了，那它显然可以去提前把蓝色要走的路给染色好
// 如果可以相遇 那就正好一起走就直接染成蓝色
// 所以其实就是希望蓝色的点尽可能快地走到被染成红色的点
// 所以最后的答案就是，2(n-1)-d
// d 为 a b 相遇的点到最远的点的距离
// 有没有可能移动初始的点使得d 更大呢？没有
// 因为你一次移动最多就使得d+1 这跟不移动 没啥区别
// Date: 2025-03-17
// Time: 16:25:11
#include <bits/stdc++.h>
using namespace std;
void ChatGptDeepSeek()
{
int n;
cin >> n;
int a, b;
cin >> a >> b;
vector<vector<int>> adj(n + 1, vector<int>());
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> dep(n + 1), f(n + 1);
auto dfs = [&](auto&& self, int u, int pre) -> void {
for (auto v : adj[u]) {
if (v == pre)
continue;
f[v] = u;
dep[v] = dep[u] + 1;
self(self, v, u);
}
};
dfs(dfs, a, 0);
int st = b, ans = 2 * (n - 1);
for (int i = 1; i <= dep[b] / 2; i++, ans++)
st = f[st];
if(dep[b]&1) st=f[st],ans++;
dep[st] = 0;
dfs(dfs, st, 0);
cout << ans - *max_element(dep.begin() + 1, dep.end()) << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T = 1;
cin >> T;
while (T--)
ChatGptDeepSeek();
return 0;
}
CF1974E *1800¶
2025-03-17
其实就是一个非常基础的dp啊。。。
但是我 WA + TLE 好多发。
vector ndp = dp;
for (int j = 0; j + h[i] < dp.size(); j++) {
if (have >= dp[j] + c[i]) {
ndp[j + h[i]] = min(ndp[j + h[i]], dp[j] + c[i]);
assert(j + h[i] <= m * 1000);
}
}
dp = ndp;
have += x;
刚开始是这样写的，之前一般都这样写的。。。但是我发现这其实没必要多开一个数组。。。因为只会影响后面的，所以直接倒着遍历就可以。。
for (int j = n; j - h[i] >= 0; j--) {
if (dp[j - h[i]] + c[i] <= have)
dp[j] = min(dp[j], dp[j - h[i]] + c[i]);
}
have += x;
但是 \(2202ms\) ， 原因是我开的 vector 以及每次都开的最大的，虽然过了啊，但是其实题目限制了 \(\sum h_i\) ，我理解有问题啊，那其实就该直接每次开 \(\sum h\) 的空间就行了。
using ll = long long;
constexpr ll inf = 1e18;
ll dp[1000 * 100 + 1];
void ChatGptDeepSeek()
{
int m, x;
cin >> m >> x;
vector<int> c(m + 1), h(m + 1);
int n = 0;
for (int i = 1; i <= m; i++) {
cin >> c[i] >> h[i];
for (int j = 1; j <= h[i]; j++)
dp[n + j] = inf;
n += h[i];
}
// vector<ll> dp(1000 * m + 1, inf);
dp[0] = 0;
ll have = 0;
for (int i = 1; i <= m; i++) {
// vector ndp = dp;
for (int j = n; j - h[i] >= 0; j--) {
if (dp[j - h[i]] + c[i] <= have)
dp[j] = min(dp[j], dp[j - h[i]] + c[i]);
}
have += x;
}
for (int i = n; i >= 0; i--) {
if (dp[i] != inf) {
cout << i << "\n";
return;
}
}
}
洛谷P10865 普及+/提高¶
2025-03-18
去年比赛没时间看，虽然看了也肯定不会写。偶然翻题单在状压DP里翻到，，但是我连啥叫状压DP都不太记得了，之前只看过几题。
其实是昨天先看了下题解，大概知道要用状压 DP ，然后每两位表示一个有鱼的单元格的状态。
因为每个池塘的鱼的数量最多只有3，所以我们用2位二进制位就可以表示出来。总共需要 \(2k\) 位。由于 \(k\) 很小，所以就可以这样。
并且还有一个很关键的信息就是，每个炸弹最多只能炸五个单元格，并且形状是固定的。所以每个池塘最多只会被5个单元格给炸到。
所以总共最多只有 \(5k\) 个池塘有可能被放置炸弹。我们枚举每一个状态，看使用每一个炸弹会转移到什么状态。
最后我们需要输出鱼全都被炸似的最小的答案，也就是 \(dp_0\) 。
int mp[1001][1001];
void ChatGptDeepSeek()
{
memset(mp, -1, sizeof mp);
// cerr<<mp[0][0]<<'\n';
int n, m, k;
cin >> n >> m >> k;
vector<int> x(k), y(k), a(k);
int now = 0;
// map<pair<int, int>, int> mp;
for (int i = 0; i < k; i++) {
cin >> x[i] >> y[i] >> a[i];
mp[x[i]][y[i]] = i;
// mp[{ x[i], y[i] }] = i;
now |= (a[i] << (2 * i));
}
// 10 01 10
// cerr << now << '\n';
vector<int> dp(now + 1, 666);
dp[now] = 0;
vector<pair<int, int>> dir { { 0, 0 }, { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
auto calc = [&](int now_val, int i, int j) {
for (auto it : dir) {
int nx = i + it.first, ny = j + it.second;
if (nx > n || nx < 1 || ny > m || ny < 1)
continue;
if (mp[nx][ny] != -1) {
int xx = (now_val >> (2 * mp[nx][ny])) & 3;
assert(xx <= 3 && xx >= 0);
now_val ^= (xx << (2 * mp[nx][ny]));
xx = max(0, xx - 1);
now_val |= (xx << (2 * mp[nx][ny]));
}
}
return now_val;
};
//k * 2**20
//k*1e6*5
for (int i = 0; i < k; i++) {
for (auto it : dir) {
int nx = x[i] + it.first, ny = y[i] + it.second;
if (nx > n || nx < 1 || ny > m || ny < 1)
continue;
// for (int _ = 1; _ <= 3; _++)
for (int j = now; j >= 0; j--) {
int nxt = calc(j, nx, ny);
assert(nxt <= j);
dp[nxt] = min(dp[nxt], dp[j] + 1);
}
}
}
cout << dp[0] << '\n';
}
然后其实就是一些简单的操作了。。但是我把 map 改成数组就不超时了。。
但是时间最多 500ms 了，算比较慢的了。看了别人的更快代码发现，有的是 DFS ，有的是把状态放外层，如果不是合法状态就跳过，可以减少很多的时间。
改了之后变成 240ms。。虽然写了十分钟多，且写错了看了一会才看出来。。我把 ny>m || ny<1 写成了 ny>m || ny>m 。
for (int i = now; i >= 0; i--) {
{
int tmp = i;
bool skip = false;
for (int j = 0; j < k; j++) {
if ((tmp & 3) > a[j]) {
skip = true;
break;
}
tmp >>= 2;
}
if (skip)
continue;
}
// cerr<<i<<" "<<dp[i]<<" \n";
for (int j = 0; j < k; j++) {
for (auto it : dir) {
int nx = x[j] + it.first, ny = y[j] + it.second;
if (nx > n || nx < 1 || ny > m || ny < 1)
continue;
int nxt = calc(i, nx, ny);
// cerr<<nxt<<'\n';
dp[nxt] = min(dp[nxt], dp[i] + 1);
}
}
}
洛谷P10864 普及+/提高¶
2025-03-18
乐，写了三个小时。。。虽然前面一直在写错误的做法。。
最后精力不太行了，实在看不出来。。问了下deepseek，帮我找到了一些问题。因为写错了重新写一下，然后忘记初始化并查集了。。
然后占了新格子的话，周围所有的点的气都不能有这个格子。这一点我也知道啊，但是脑子非常混乱了。。然后瞎改了下过了。
还是很麻烦的一个题的，然后我是没有想到每个连通块的气都放集合里不会TLE MLE。。。但是每个连通块每次 DFS BFS算气也是没问题。。
确实就是模拟。不然我也写不了这么久，可能就一点东西都敲不了。
感觉 BFS DFS 同样不好写。真要哈气了。
虽然效率很低，但也是多写一题吧。也该休息一下了。
int board[20][20];
int p[20][20];
constexpr int N = 5e5;
int cnt[N + 1], f[N + 1];
// bool vis[N + 1];
// vector<int> f(9);
int find(int x)
{
return f[x] == x ? x : f[x] = find(f[x]);
}
void ChatGptDeepSeek()
{
// 看自己上下左右的同色的
// 如果有 那么加入它们所在的联通块
// 用并查集维护联通的信息
//
// 看它周围的颜色不同的 若气为0了 则该全部移除了
// 怎么用并查集呢？好像还行 试试 ，其实没用过几次并查集（
for (int i = 0; i <= 19; i++)
for (int j = 0; j <= 19; j++)
board[i][j] = -1;
int m;
cin >> m;
vector<pair<int, int>> dir { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
vector<set<pair<int, int>>> Qi(m + 1, set<pair<int, int>>());
int res = 0;
auto Eat = [&](auto&& self, int x, int y, int v) -> void {
// cerr << x << " " << y << '\n';
res++;
assert(x <= 19 && x >= 1 && y <= 19 && y >= 1);
board[x][y] = -1;
for (auto it : dir) {
int nx = x + it.first, ny = y + it.second;
if (nx > 19 || nx < 1 || ny > 19 || ny < 1 || board[nx][ny] == -1)
continue;
if (board[nx][ny] != v) {
int idx = find(p[nx][ny]);
assert(idx <= m && idx > 0);
Qi[idx].insert({ x, y });
} else
self(self, nx, ny, v);
}
};
for (int i = 1; i <= m; i++) {
res = 0;
int x, y;
cin >> x >> y;
board[x][y] = (i % 2);
p[x][y] = i;
f[i] = i;
// 先算周围的反色的气
for (auto it : dir) {
int nx = x + it.first, ny = y + it.second;
if (nx > 19 || nx < 1 || ny > 19 || ny < 1 || board[nx][ny] == -1)
continue;
int idx = find(p[nx][ny]);
// if(!idx) continue;
assert(idx <= m && idx > 0);
if (!Qi[idx].empty())
Qi[idx].erase({ x, y });
if (p[nx][ny] % 2 != i % 2) {
// dbg(i, nx, ny);
if (Qi[idx].empty()) {
// dbg(nx, ny, idx);
Eat(Eat, nx, ny, p[nx][ny] % 2);
// f[idx] = 0;
}
}
}
for (auto it : dir) {
int nx = x + it.first, ny = y + it.second;
if (nx > 19 || nx < 1 || ny > 19 || ny < 1)
continue;
if (board[nx][ny] == -1)
Qi[i].insert({ nx, ny });
}
for (auto it : dir) {
int nx = x + it.first, ny = y + it.second;
if (nx > 19 || nx < 1 || ny > 19 || ny < 1 || (board[nx][ny] != i % 2))
continue;
int idx = find(p[nx][ny]);
if (idx == i)
continue;
assert(idx <= m && idx > 0 && board[nx][ny] == board[x][y]);
for (auto it : Qi[idx]) {
// if (board[it.first][it.second] == -1)
Qi[i].insert(it);
}
f[idx] = i;
}
// dbg(Qi[i]);
// cerr << Qi[i].size() << '\n';
int val = res;
res = 0;
if (Qi[i].empty())
Eat(Eat, x, y, i & 1);
if (i & 1) {
cout << res << " " << val << '\n';
} else {
cout << val << " " << res << '\n';
}
// dbg(Qi[find(1)]);
// dbg(Qi[2]);
}
// 我要哈气了
}
洛谷P4170 提高+/省选-¶
2025-03-25
tag: 区间DP
\(n\le 50\) ，但确实不太好写。
我们需要先去处理长度短的区间。
\(dp_{i,j}\) 为将 \([i,j]\) 区间涂成对应颜色所需的操作次数，当 \(i=j\) 时，\(dp_{i,j}=1\) 。
那么当 \(s_l=s_r\) 时，\(dp_{l,r}=dp_{l,r-1}\) ，否则一定至少需要两次操作，枚举间断点 \(m\) ， \(dp_{l,r}=min(dp_{l,m},dp_{m+1,r})\) 。
// 确实，我刚刚的思路完全是错的😅
void ChatGptDeepSeek()
{
string s;
cin >> s;
int n = s.size();
s = " " + s;
vector<vector<int>> dp(n + 1, vector<int>(n + 1, n));
for (int i = 1; i <= n; i++)
dp[i][i] = 1;
for (int len = 2; len <= n; len++)
{
for (int l = 1; l + len - 1 <= n; l++)
{
int r = l + len - 1;
if (s[r] == s[l])
dp[l][r] = min(dp[l][r], dp[l][r - 1]);
for (int m = l; m + 1 <= r; m++)
{
dp[l][r] = min(dp[l][r], dp[l][m] + dp[m + 1][r]);
}
}
}
cout << dp[1][n] << '\n';
}
CF1970E1 *1800¶
2025-03-25
不是哥们，这能给1800。其实很简单吧。
我们其实只需要知道有多少条长路多少条短路可能走回来，就能知道在第 \(i\) 有多少种方式可以到达每一个房子。
void ChatGptDeepSeek()
{
constexpr int mod = 1e9 + 7;
int m, n;
cin >> m >> n;
/*
1 0 1
0 1 1
第一天 1->1 1->2 1->3 (S,L)
第二天
d[1]=1 d[2]=1 d[3]=2
S=3 L=3
*/
vector<int> s(m + 1), l(m + 1);
for (int i = 1; i <= m; i++)
cin >> s[i];
for (int i = 1; i <= m; i++)
cin >> l[i];
ll S = s[1], L = l[1];
vector<ll> ways(m + 1);
for (int i = 1; i <= n; i++)
{
ll nS = 0, nL = 0;
for (int j = 1; j <= m; j++)
{
ways[j] = (1LL * s[j] * (S + L) % mod + 1LL * l[j] * S % mod) % mod;
nS = (nS + 1LL * ways[j] * s[j] % mod) % mod;
nL = (nL + 1LL * ways[j] * l[j] % mod) % mod;
// cerr << ways[j] << " \n"[j == m];
}
S = nS, L = nL;
// cerr << S << " " << L << '\n';
}
ll ans = 0;
for (int i = 1; i <= m; i++)
{
ans = (ans + ways[i]) % mod;
}
cout << ans << '\n';
}
洛谷P1013 普及+/提高¶
2025-03-28
很水的一个题目了，直接全排列枚举即可，二十分钟写完了。感觉难度评高了点，但是之前看过一眼题目，感觉不太想写。但是这次看了一会怀疑是水题，结果确实差不多。
但是还是也得有点耐心写和思考吧。
由于每个数字都不同，而且所有数字都会两两加一起，所以如果是合法方案，一定是表示的 \(n-1\) 进制的加法。直接枚举每个符号是哪个值即可。
void ChatGptDeepSeek()
{
int n;
cin >> n;
vector<vector<string>> s(n, vector<string>(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> s[i][j];
vector<int> p(n - 1);
iota(p.begin(), p.end(), 0);
auto check = [&]()
{
vector<int> q(129);
for (int i = 0; i < n - 1; i++)
q[s[0][i + 1][0]] = p[i];
vector<vector<int>> a(n, vector<int>(n));
for (int i = 1; i < n; i++)
a[0][i] = p[i - 1];
for (int i = 1; i < n; i++)
a[i][0] = p[i - 1];
auto get = [&](string x)
{
int res = 0;
for (auto y : x)
res = res * (n - 1) + q[y];
return res;
};
for (int i = 1; i < n; i++)
for (int j = 1; j < n; j++)
{
// if (i == j && i == 1)
// {
// cerr << p[i - 1] << " " << p[j - 1] << " " << get(s[i][j]) << '\n';
// }
if (p[i - 1] + p[j - 1] != get(s[i][j]))
return false;
}
return true;
};
do
{
if (check())
{
for (int i = 1; i < n; i++)
cout << s[0][i] << "=" << p[i - 1] << " \n"[i + 1 == n];
cout << n - 1 << '\n';
return;
}
} while (next_permutation(p.begin(), p.end()));
cout << "ERROR!\n";
}
洛谷P10915 普及+/提高¶
2025-03-28
蓝桥杯24 B组国赛题目？但是我感觉没见过，可能是 Java 或者 Python 组的吧，也可能是 C++ 的（）。
我们可以删除一个子串，假设我们的答案的前缀的长度是 len ，我们切割子串之后，必然前缀和后缀至少有一个的长度是大于等于 len 。所以我们的答案的前半部分或者后半部分，必然是 \(s\) 的一个前缀或者一个后缀。
若 len 是以得到的前缀长度，那么 [1, len-1] 必然也是可以得到的长度，只需要多删一部分就行。
所以我们可以用二分来求最长的长度，那么由于切割后至少有一边的长度是大于等于 len ，所以要么前面是 s[1, len] ，要么后面是 s[n-len+1, n] 。
我们可以只用考虑答案的前缀完全为 \(s\) 的前缀的情况，另一种情况可以通过翻转 \(s\) 来求解答案。
假设 t = s[1, len] ，\(t'=reverse(t)\) 那么我们实际上就是要在 s[len+1, n] 之中找到一个字符串 \(t'\) ，但是 \(t'\) 可能是在 \(s[len+1, n]\)被分成两段的。由于答案的后缀必须是切割后的字符串的后缀。有可能是把末尾一部分切了，有可能把中间的某一部分切了。
我们可以从末尾看 \(t\) 和 \(s\) 的这一位是否相等，若相等则把 \(t\) 的末尾删除。然后最后我们只需要在 \(s[len+1,n]\) 中查找新的 \(t\) 。
可以用 KMP 算法求，单次 check 时间复杂度为 \(O(n)\) 。
int solve(string s)
{
int n = s.size();
auto check = [&](int len)
{
string t = s.substr(0, len);
reverse(t.begin(), t.end());
for (int i = n - 1; i >= n - len; i--)
{
if (t.back() == s[i])
t.pop_back();
else
break;
}
if (t.empty())
return true;
int i = len, m = t.size();
vector<int> p(m);
for (int i = 1; i < m; i++)
{
int j = i - 1;
while (j > 0 && t[i] != t[j])
j = p[j - 1];
p[i] = j;
if (t[i] == t[j])
p[i]++;
}
int j = 0;
while (i < n)
{
while (j > 0 && s[i] != t[j])
j = p[j - 1];
if (s[i] == t[j])
i++, j++;
else
i++; // 如果不相等 那么j 必然等于0 所以直接看下一个1
if (j == t.size())
return true;
}
return false;
};
int lo = 0, hi = n / 2 + 1;
while (lo < hi - 1)
{
int mid = (lo + hi) >> 1;
if (check(mid))
lo = mid;
else
hi = mid;
}
return lo;
}
void ChatGptDeepSeek()
{
string s;
cin >> s;
int ans = solve(s);
reverse(s.begin(), s.end());
ans = max(ans, solve(s));
cout << ans << '\n';
}
洛谷P8812 普及+/提高¶
2025-03-31
同学问的题，于是顺便看一下，是某年某组的蓝桥杯的题。感觉水题。
但是还是发现一点问题，st.erase(st.lower_bound(val)) T了，st.erase(st.find(val)) AC了，大概差了150ms左右，总共是1000ms。感觉优先队列少放点东西，开个数组存信息应该快很多。
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
cin >> n >> m;
priority_queue<array<int, 5>, vector<array<int, 5>>, greater<>> pq;
priority_queue<array<int, 4>, vector<array<int, 4>>, greater<>> pq1;
vector<multiset<int>> price(n, multiset<int>());
vector<int> days;
for (int i = 1; i <= m; i++)
{
int s, t, p, c;
cin >> s >> t >> p >> c;
days.push_back(s);
days.push_back(t + 1);
for (int j = 1; j <= c; j++)
{
int a, b;
cin >> a >> b;
a--;
pq.push({s, t, a, b, p});
price[a].insert(b);
}
}
long long cost = 0;
for (int i = 0; i < n; i++)
cost += *price[i].begin();
long long ans = cost;
sort(days.begin(), days.end());
days.erase(unique(days.begin(), days.end()), days.end());
for (auto now : days)
{
while (!pq.empty() && pq.top()[0] == now)
{
auto [s, t, a, b, p] = pq.top();
pq.pop();
int val = 1LL * b * p / 100;
cost -= *price[a].begin();
price[a].insert(val);
cost += *price[a].begin();
pq1.push({t + 1, a, b, p});
}
while (!pq1.empty() && pq1.top()[0] == now)
{
auto [t, a, b, p] = pq1.top();
pq1.pop();
int val = 1LL * b * p / 100;
cost -= *price[a].begin();
price[a].erase(price[a].find(val));
cost += *price[a].begin();
}
ans = min(cost, ans);
}
cout << ans << '\n';
return 0;
}