当前位置: 首页 > news >正文

QBXT2025S刷题 Day6

T2

这道题是树形 \(\mathcal{DP}\),我们注意到如果一个点能和他的一个子树合并成为一个三叉,那么可以是以下四种情况。
image
然后我们的状态记录一下当前有 \(i\) 个链,\(j\) 个倒 "Y"。
这样,我们可以先让 \(i\) 个链三三匹配。
那么如果 \(j \geq i\%3\),那么这 \(i\) 个链就可以完全用掉。
我们看第一种情况,我们要留下一个链。
因此要满足 \(j\geq (i-1)\%3\)
其他的情况同理。
再就是我们要把状态压缩一下。
我们注意到 \(i = 3\)\(i = 0\) 是两种不同的状态,因为我们不能从 \(0\) 中取出两条链。
\(i = 4\) 同理。
因此我们状态要记录到 \(5\)
\(j\) 要记录到 \(3\),这个很好看出来。
代码:

// ☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭
// ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
// ░░░░░░░░░░░░░░░░░░░░░▄▄▄▄▄▄▄░░░░░░░░░░░░░░░░░░░░
// ░░░░░░░░░░░░░░░░░░░░░█▀▀▀▄░░▀▀▀▄▄░░░░░░░░░░░░░░░
// ░░░░░░░░░░░░░░░░░░░░░█▄▄▄░▀▀▄▄░░░▀▀▄░░░░░░░░░░░░
// ░░░░░░░░░░░░░░░░░░░░░░░░░▀▀▄▄░▀▄░░░░▀▄░░░░░░░░░░
// ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▄░▀▄░░░░▀▄░░░░░░░░
// ░░░░░░░░░░░░░░░░░▄▀▀▀▀▀▀▀▀▄░░░░▀▄░█░░░░▀▄░░░░░░░
// ░░░░░░░░░░░░░░░▄▀░░░░░░░░░░█░░░░░█░█░░░░▀▄░░░░░░
// ░░░░░░░░░░░░░▄▀░░░░░░░░░░░▄█░░░░░░█░█░░░░▀▄░░░░░
// ░░░░░░░░░░░▄▀░░░░░░░░░░░▄▀░█░░░░░░░█░█░░░░█░░░░░
// ░░░░░░░░░▄▀░░░░░░░░░░░░█░▄▀░░░░░░░░░█▀█░░░░█░░░░
// ░░░░░░░░█░░░░░░░░░░░░░░░▀▄░░░░░░░░░░▀▄█░░░░█░░░░
// ░░░░░░░░█▄░░░░░░░░▄▄░░░░░░▀▄░░░░░░░░░██░░░░█░░░░
// ░░░░░░░░█░▀▄░░░░▄▀░░▀▄░░░░░░▀▄░░░░░░░██░░░░█░░░░
// ░░░░░░░░░▀▄░▀▄▄▀░▄▀▀▄░▀▄░░░░░░▀▄░░░░░█░░░░░█░░░░
// ░░░░░░░░░░░▀▄█░▄▀░░░░▀▄░▀▄░░░░░░▀▄░░▄▀░░░░▄█░░░░
// ░░░░░░░░░░░░░▀▀░░░░░░░░▀▄░▀▄░░░░░░▀▄▀░░░░░██░░░░
// ░░░░░░░░░░▄▀▀▀▀▄░░░░░░░░░▀▄░▀▄░░░░░░░░░░░██░░░░░
// ░░░░░░▄▄▀▀░░░░░░█▄░░░░░░░░░▀▄░█░░░░░░░░░▄█▀░░░░░
// ░░░░▄▀░░░░░░░░░░░░▀▀▀▄▄▄▄▄▄▄▄▀░░░░░░░░░░▀█░░░░░░
// ░░░█░░░░░░░░░▄░░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▄░░░░
// ░░█░░░░░░░░▄▀░▀█░░░░░░░░░░░░░░░░░░█▀▀█░░░░░░▀▄░░
// ░░█░░░░░░░▄▀▄▀▄░▀▀▀▀▄▄▄▄▄▄▄▄▄▄▄▀▀▀░▄▄░▀█░░░░░█░░
// ░░█▀▄▄▄▄▀▀░▄▀░░▀▄▄▄▄░░░░░░░░░░░▄▄▄▀░░▀▄░▀▄▄▄▀█░░
// ░░▀▄░░░░▄▄▀░░░░░░░░░▀▀▀▀▀▀▀▀▀▀▀░░░░░░░░▀▄░░░▄▀░░
// ░░░░▀▀▀▀░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▀▀░░░░
// ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
// ☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭
#include <iostream>
#include <vector>
#define int long longusing std::cin;
using std::cout;
const int N = 1e5 + 10;
typedef long long ll;
struct Edge
{int to, w;
};int now[8][6];
int son[N][6];
int dp[N][8][6];
std::vector<Edge> e[N];void DP(int x, int father)
{dp[x][0][0] = 0;for (auto nxt : e[x]){int to = nxt.to;int val = nxt.w;if (to == father)continue;DP(to, x);for (int i = 0; i <= 5; ++i){for (int j = 0; j <= 3; ++j)now[i][j] = -1e18 - 7;}for (int i = 0; i <= 5; ++i){for (int j = 0; j <= 3; ++j){now[i][j] = std::max(now[i][j], dp[x][i][j] + son[to][0]);now[i][std::min(j + 1, 3ll)] = std::max(now[i][std::min(j + 1, 3ll)], dp[x][i][j] + val + std::max(son[to][2], son[to][3]));now[i == 5 ? 3 : i + 1][j] = std::max(now[i == 5 ? 3 : i + 1][j], dp[x][i][j] + val + std::max(son[to][0], son[to][1]));}}for (int i = 0; i <= 5; ++i){for (int j = 0; j <= 3; ++j)dp[x][i][j] = now[i][j];}}for (int i = 0; i <= 5; ++i){for (int j = i % 3; j <= 3; ++j)son[x][0] = std::max(son[x][0], dp[x][i][j]);}for (int i = 0; i <= 4; ++i){for (int j = i % 3; j <= 3; ++j)son[x][1] = std::max(son[x][1], dp[x][i + 1][j]);}for (int i = 0; i <= 3; ++i){for (int j = i % 3; j <= 3; ++j)son[x][2] = std::max(son[x][2], dp[x][i + 2][j]);}for (int i = 0; i <= 5; ++i){for (int j = i % 3; j <= 2; ++j)son[x][3] = std::max(son[x][3], dp[x][i][j + 1]);}
}signed main()
{int t;cin >> t;while (t--){int n;cin >> n;for (int i = 1; i <= n; ++i)e[i].clear();for (int i = 1; i < n; ++i){int u, v, w;cin >> u >> v >> w;e[u].push_back((Edge){v, w});e[v].push_back((Edge){u, w});}for (int i = 1; i <= n; ++i){for (int j = 0; j <= 5; ++j){for (int k = 0; k <= 3; ++k){dp[i][j][k] = -1e18 - 7;son[i][k] = -1e18 - 7;}}}DP(1, 0);cout << son[1][0] << '\n';}return 0;
}

T3

这道题我们可以对 \(e_i \geq \dfrac{E}{2}\)\(e_i < \dfrac{E}{2}\) 进行两两分组。
如果都第一组里,就可以任意交换。
我们记录每一个第一组最左,最右可以走到哪。
我们发现这些形成的区间要么是完全包含,要么是不交。
因此这些形成了一个树形的结构。
我们直接使用类似树形 \(\mathcal{DP}\) 的方法做就行。
代码:

#include <iostream>
#include <vector>
#include <algorithm>
#define int long longusing std::cin;
using std::cout;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
struct Node
{int min;Node(){min = 2e9 + 7;}void init(int v){min = v;}friend Node operator+(const Node &l, const Node &r){Node ret;ret.min = std::min(l.min, r.min);return ret;}
} z[N << 2];int ans = 1;
int n, E;
int po;
int ee[N];
int l[N];
int r[N];
int e[N];
int sum[N];
std::vector<std::pair<int, int>> p;#define root 1, n, 1
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1void build(int l, int r, int rt)
{if (l == r){z[rt].init(ee[l]);return;}int mid = (l + r) >> 1;build(lson);build(rson);z[rt] = z[rt << 1] + z[rt << 1 | 1];
}
int query1(int l, int r, int rt, int nowl, int nowr, int k)
{if (z[rt].min > k || nowr < nowl)return 0;if (l == r)return l;int mid = (l + r) >> 1;int now = 0;if (nowr > mid)now = query1(rson, nowl, nowr, k);if (nowl <= mid && now == 0)now = query1(lson, nowl, nowr, k);return now;
}
int query2(int l, int r, int rt, int nowl, int nowr, int k)
{if (z[rt].min > k || nowr < nowl)return n + 1;if (l == r)return l;int mid = (l + r) >> 1;int now = n + 1;if (nowl <= mid)now = query2(lson, nowl, nowr, k);if (nowr > mid && now == n + 1)now = query2(rson, nowl, nowr, k);return now;
}
int dfs()
{int x = po++;int nowsize = 1;while (po < p.size() && p[po].second <= p[x].second)nowsize += dfs();ans = 1ll * ans * (nowsize + sum[p[x].second - 1] - sum[p[x].first]) % mod;return nowsize;
}signed main()
{freopen("str.in", "r", stdin);freopen("str.out", "w", stdout);cin >> n >> E;for (int i = 1; i <= n; ++i){cin >> e[i];ee[i] = (e[i] <= (E >> 1) ? e[i] : 2e9 + 7);}build(root);for (int i = 1; i <= n; ++i){if (e[i] > (E >> 1)){l[i] = query1(root, 1, i - 1, E - e[i]);r[i] = query2(root, i + 1, n, E - e[i]);sum[i] = sum[i - 1];}elsesum[i] = sum[i - 1] + 1;}for (int i = 1; i <= n; ++i){if (e[i] > (E >> 1))p.push_back({l[i], r[i]});}std::sort(p.begin(), p.end(), [&](const std::pair<int, int> &a, const std::pair<int, int> &b){ return (a.first != b.first ? a.first < b.first : a.second > b.second); });sum[n + 1] = sum[n];po = 0;while (po < p.size())dfs();cout << ans << '\n';return 0;
}
http://www.hskmm.com/?act=detail&tid=26388

相关文章:

  • CF2145 Educational Codeforces Round 183 (Rated for Div. 2) 游记
  • 52个AI工具
  • 可观测专题【左扬精讲】——《Go 语言实现企业级 APM 监控系统实战:从 0 到 1 搭建高性能监控平台》
  • 多区域多 VLAN 网络搭建与访问控制及服务器部署实验
  • Tina_Linux_系统软件 开发指南
  • 2025方钢、扁钢、圆钢、光轴、六角钢、异型钢、冷拉/冷拔方钢、冷拉/冷拔扁钢、冷拉/冷拔圆钢、冷拉/冷拔六角钢、冷拉/冷拔异型钢、热轧方钢/扁钢厂家权威推荐榜:坚固耐用与精准定制口碑之选
  • GO_基础2
  • LDO(一)FVF型LDO
  • 详细介绍:进阶智能体实战九、图文需求分析助手(ChatGpt多模态版)(帮你生成 模块划分+页面+表设计、状态机、工作流、ER模型)
  • 09. 常用控件
  • 201007
  • 苍穹外卖第一天(Maven、Git、Nginx反向代理)
  • Python中的数据结构
  • 2025家纺摄影公司/南通摄影公司权威推荐榜:创意拍摄与专业服务的口碑之选
  • 合成数据生成技术研讨会深度解析
  • 纯 C++ 开发的 Telegram Bot 框架
  • 六级自测
  • Python 中的链式操作——重点讲解链式调用
  • io设备概述
  • 多元线性回归-梯度下降法-吴恩达机器学习
  • 概率论小测试
  • AI 产品研发的一些思考
  • 3.模块化与MVVM设计模式
  • 2025舒适轮胎厂家、静音轮胎厂家企业品牌权威推荐榜:静音技术与驾乘体验口碑之选
  • 幻想是最廉价的止疼药
  • 20251005 耳朵龙字符串
  • 玩转树莓派屏幕之五:自定义LCD屏幕显示
  • AtCoder ARC207 总结
  • 2025.10.7模拟赛
  • 详细介绍:ZLG ZCANPro,ECU刷新,bug分享