#题解

分享算法思考、训练复盘与日常交流。

rail题解

temp 2026-10-2 21:58:49

#算法#题解

#include<bits/stdc++.h> #define int long long using namespace std; int n,L,s,S; char d; signed main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); freopen("rail.in","r",stdin); freopen("rail.out","w",stdout); cin>>n>>L>>s>>d; for(int i=1;i<=n;i++){ int x; cin>>x; S+=x; } if(s==0&&d=='L') d='R'; if(s==L&&d=='R') d='L'; int z; if(d=='R') z=s; else z=2*L-s; int ans=(z+S)/L-z/L; int t=(z+S)%(2*L); if(t<=L) s=t; else s=2*L-t; if(t<L) d='R'; else d='L'; cout<<ans<<" "<<s<<" "<<d; return 0; }

42 浏览0 点赞0 收藏0 评论

rankdiff题解

temp 2026-10-2 21:57:16

#算法#题解

水题不说废话了首先，这道题用到了排序但是需要用到多个参数如

id,rank

等这时可以用

sort

函数来解决sort(first,end,cmp);这么一个形式于是我想到了一个用STL的

pair

来解决这个问题pair<type1,type2> p;这里，我们可以用

.first

和

.second

来访问完整代码#include <bits/stdc++.h> using namespace std; const int N = 2e5+10; using LL = long long; const int inf = 1e9, N2 = 1e3, mod = 998244353; #define PII pair<int,int> int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0}; auto compare = [](int a, int b){ return a > b; }; PII a[N]; bool cmp(PII a,PII b){ if(a.first != b.first)return a.first > b.first; return a.second < b.second; } void solve(){ freopen("rankdiff.in","r",stdin); freopen("rankdiff.out","w",stdout); int n,p,q; cin>>n>>p>>q; for(int i = 0;i < n;i++){ cin>>a[i].first; a[i].second = i; } sort(a,a+n,cmp); cout<<abs(a[p-1].second-a[q-1].second); } int main(){ int _ = 1; while(_--){ solve(); } return 0; }

39 浏览0 点赞0 收藏0 评论

洛谷P13273 [NOI2025] 数字树题解

司马只因锥 2026-6-20 15:23:02

#题解

题目保证存在一种合法方案，我们可以考虑由一个合法方案怎么调整出不同的合法方案。为了方便理解，我们钦定优先向左遍历，把换向操作转换成翻转子树的操作。容易发现，翻转一棵子树时已经合法匹配的点不受影响，那么只有那些当前未配对的点需要考虑。跟虚树的角度差不多，我们把这些子树内已经匹配上的点踢掉分析。分析问题的重要方法：从小入手。两种颜色

X

和

Y

子树内都有一个

A

和一个

B

颜色节点没有参与匹配，翻转点

X

后应该翻转

Y

才能构成新的合法结构。

Y

子树内只有

A_1

没有匹配，可以随意翻转；而

X

翻转后无法通过翻转其他节点构成合法结构。可以发现，对于一个合法序列，翻转一部分，如果这个部分中至少有两个未匹配的点，那么必须将对应区间也翻转，或者在其他点把这个部分翻转回来。那假如我们已经翻转了一个部分，到底翻转哪些点才能转回合法？两个不够具有普适性，我们引入第三个节点。三种颜色

翻转

Y

后，

Z

和

W

都可以把

A_2,B_2

相对位置调整正确，然而这会使得

C_2

调到中间不再合法，因此只能翻转

W

。通过上述的分析，我们发现，翻转了一个点

u

，就必须翻转树上管辖着一模一样的

S

的

v

。至此我们可以得出结论：设

S_u

为

u

子树内未匹配节点集合。若

|S_u| \geq 2

，则当且仅当

S_u=S_v \ (u \neq v)

，可以通过同时翻转子树

u, v

得出新的合法方案。若

|S_u|=1

，那怎么样翻转都行。怎么计数？设等价类

A_k

包含了所有

S

相同，且

|S| \geq 2

的点，等价类共有

m

个。设

|S|=1

的点有

t

个。每个等价类我们都可以任选偶数个翻转，则：问题转化为计算等价类的个数。第

i

次操作加入颜色

i

，下标不仅是元素编号，也表示了时间，务必记住这一点。用 01 序列表示集合

S_u

。若两 01 序列的 lcp 长度为

l

，则说明在前

l

次操作里它们都属于同一个等价类！使用树上差分标记修改，显然可以用线段树高效维护合并集合。至此我们得到了每个点子树内的未匹配点集，我们把这些字符串记为

a[i]

。已知所有集合，如何计数等价类？对所有字符串按字典序排序后（比较操作就是查询 lcp，这可以通过对比两棵线段树上区间哈希值来实现，单次对比复杂度是

O(\log n)

的），若

\text{lcp}(a[i-1], a[i])=L

，这意味着在

L+1

时新出现了一个等价类。由于更长的 lcp 覆盖了短的 lcp，如果字符串 $\text{lcp}(a[i], a[j]) \leq \text{lcp}(a[i], a[i-1])$，那么在

i-1

或更早，

a[i], a[j]

分歧产生的新等价类已经被计数过了。所以这就覆盖了所有的情况，避免了冗余的比较。Code有点难写啊，空间有点玄学，瞎开的。#include <bits/stdc++.h> #define int int64_t //#define int __int128 #define MOD (1000000007) //#define eps (1e-6) #define endl '\n' #define debug_endl cout<<endl; #define debug cout<<"debug"<<endl; using namespace std; const int MAXN = 2e6; const int MAXB = 24; int c, n; int lc[MAXN], rc[MAXN]; int fa[25][MAXN], depth[MAXN], pw131[MAXN], ans[MAXN]; vector<int> add[MAXN], del[MAXN]; struct Mergeable_Segment_Tree { struct Node { int h, pos1, pos2; int lc, rc; Node() { h = lc = rc = 0; pos1 = pos2 = 1e9; } }; Node tr[int(2e7)]; int root[MAXN], tot; void push_up(int p, int l, int r) { int mid = (l + r) >> 1; tr[p].h = (tr[tr[p].lc].h * pw131[r - mid] + tr[tr[p].rc].h) % MOD; if (tr[tr[p].lc].pos1 == 1e9) { tr[p].pos1 = tr[tr[p].rc].pos1; tr[p].pos2 = tr[tr[p].rc].pos2; } else { tr[p].pos1 = tr[tr[p].lc].pos1; if (tr[tr[p].lc].pos2 != 1e9) tr[p].pos2 = tr[tr[p].lc].pos2; else tr[p].pos2 = tr[tr[p].rc].pos1; } } int update(int p, int l, int r, int pos, int k) { int q = ++tot; tr[q] = tr[p]; if (l == r) { tr[q].h = k; tr[q].pos1 = (k ? l : 1e9); tr[q].pos2 = 1e9; return q; } int mid = (l + r) >> 1; if (pos <= mid) tr[q].lc = update(tr[p].lc, l, mid, pos, k); else tr[q].rc = update(tr[p].rc, mid + 1, r, pos, k); push_up(q, l, r); return q; } int merge(int p1, int p2, int l, int r) { if (!p1 || !p2) return p1 ? p1 : p2; int p = ++tot; if (l == r) { tr[p].h = (tr[p1].h + tr[p2].h) % MOD; tr[p].pos1 = min(tr[p1].pos1, tr[p2].pos1); tr[p].pos2 = 1e9; return p; } int mid = (l + r) >> 1; tr[p].lc = merge(tr[p1].lc, tr[p2].lc, l, mid); tr[p].rc = merge(tr[p1].rc, tr[p2].rc, mid + 1, r); push_up(p, l, r); return p; } pair<int, int> lcp(int p1, int p2, int l, int r) { if (tr[p1].h == tr[p2].h) return make_pair(n + 1, 1); if (!p1) return make_pair(tr[p2].pos1, 2); if (!p2) return make_pair(tr[p1].pos1, 1); if (l == r) return make_pair(l, !tr[p1].h ? 2 : 1); int mid = (l + r) >> 1; if (tr[tr[p1].lc].h != tr[tr[p2].lc].h) return lcp(tr[p1].lc, tr[p2].lc, l, mid); else return lcp(tr[p1].rc, tr[p2].rc, mid + 1, r); } }; Mergeable_Segment_Tree mst; void dfs(int x) { if (!x) return; for

121 浏览1 点赞1 收藏0 评论

精华

洛谷P14637 [NOIP2025] 树的价值题解与碎碎念

司马只因锥 2026-6-10 15:51:52

#题解

前言本文去掉代码全文共 4800 字。这篇博客并非完全意义上的题解，主要是对我学习这道题的思路回顾与总结，基于以下两篇题解融合和补充（所以记号不是我原创的，我觉得尤其是第二篇题解定义的名词非常形象易懂直接抄了），以及一些碎碎念。写了很多细节问题，都是我在学习这个题时思考过的，所以这篇文章非常长。两篇神犇的题解：

20_200（下文称作“第一篇题解”）

tiger2005（下文称作“第二篇题解”）

因为我是蒟蒻，我已经尽量在让这篇题解启发式了qwq，所以对于“显而易见的结论”讲述的废话可能很多，请巨佬们多多批评指教。由于文章太长，写作周期也长，精修困难。如有不解请敲在讨论区，我若看到一定会尽力修正表述。部分记号表

记号

含义

son_u

u

节点的子节点集

subt_u

X

节点的子树点集

fa(u)

u

节点的父节点

\vert subt_u\vert

u

节点的子树点集大小

暴力这部分会有两个复杂度的做法，但均为暴力及其优化，与正解关联不大。但能从中初步理解某些性质，个人感觉还是比较重要的。由于本人是蒟蒻，这个暴力对我来说也是个难点之一，本着彻底学透的想法，这部分也会很长，可选择跳过。考虑一个非常劣的贪心：从下到上对每一层点按层分配数值，叶子结点是

0

，其父节点是

1

……不用我说也知道这东西没有分。那么为什么是极劣的呢？我们发现在这个策略里每个点都对自身

\text{mex}

有贡献，这使得大量节点没有对祖先进行贡献而被浪费，因此一个特殊点便十分显然：有一些点不对自己的

\text{mex}

做贡献，而是留给祖先，这部分点我们称之为“垫脚石”。垫脚石的严格定义：自身权值

a_u

严格大于自身

\text{mex}

的点。因此根据这些特殊点设计状态，设

dp[u][i][j]

为

u

子树根节点

\text{mex}

为

i

，子树内有

j

个垫脚石，即有

j

个点满足

a_v>a_u

。两位神犇对于这一暴力是完全口胡的，然而蒟蒻如我连这个暴力都无法写好，因此也将讲解一下。暴力树上背包

O(n^4)

根节点需要决策自身，所以先不着急考虑根节点以及使用垫脚石。设临时数组

dp\_v[i][j]

表示当前合并的所有子树的

\text{mex}

为

i

，有

j

个垫脚石。初始状态为空，

dp\_v[0][0]=0

，其余状态全部设置为极小值表示不可能。合并的过程中，总

\text{mex}

为各子树最大的

\text{mex}

，总垫脚石数为各子树垫脚石数之和。本质上这是一个二维树形背包，容易写出合并转移方程。注意用临时数组进行背包以隔离新旧状态，具体转移不再赘述，如有需要详见代码。考虑根节点的转移。如果

u

不是垫脚石，显然应该枚举使用的垫脚石数量更新状态。你可能会发现一个问题。如果

u

自己是垫脚石，那么它到底能不能使用垫脚石呢？仔细回想垫脚石的定义，它是子树内权值严格大于子树

\text{mex}

的点。如果

u

自己是垫脚石，在使用垫脚石之前它的

\text{mex}

必然与各个子树最大的

\text{mex}

相等。那根据垫脚石的定义，这部分垫脚石数不能使用的，否则将会违反定义！难道先合并的做法是错的吗？实则不然，不妨考虑违反定义意味着什么。违反定义则意味着在最优解中这个垫脚石实际上在更早之前就应该被使用，这样权值才不会大于此时的

\text{mex}

。那这种情况实际上已经在

u

不是垫脚石的情况里转移过了，因此这种可能是多余的，我们不需要写。时间复杂度

O(n^4)

，期望得分

32\text{pts}

，实际得分

48\text{pts}

，和

O(n^3)

一个分，常数小快到飞起。#include <bits/stdc++.h> //#define int int64_t //#define int __int128 //#define MOD (1000000007) //#define eps (1e-6) #define endl '\n' #define debug_endl cout<<endl; #define debug cout<<"debug"<<endl; using namespace std; const int MAXN=370; const int MAXM=MAXN; int T,n,m; vector<int> a[MAXN]; int dp[MAXN][MAXN][MAXN],siz[MAXN],ans; int tmp[MAXN][MAXN],dp_v[MAXN][MAXN]; inline void init(){ ans=0; for(int i=1;i<=n;++i){ a[i].clear(); } } void dfs(int u){ for(int v:a[u]){//先递归以防全局数组数据污染 dfs(v); } siz[u]=0;//为了服务背包，siz在dfs内表示当前合并了多少个点，根节点的转移特殊所以放最后，siz自然初始为0 for(int i=0;i<=n;++i){//mex最大值是子树大小 for(int j=0;j<=n;++j){ dp_v[i][j]=dp[u][i][j]=INT32_MIN; } } dp_v[0][0]=0;//空状态，无意义，转移用 for(int v:a[u]){//合并子树 for(int i=0;i<=siz[u]+siz[v];++i){ for(int j=0;j<=siz[u]+siz[v];++j){ tmp[i][j]=INT32_MIN; } } for(int i0=0;i0<=siz[u];++i0){ for(int j0=0;j0<=siz[u];++j0){ if(dp_v[i0][j0]==INT32_MIN) continue;//初始状态不合法 for(int i1=0;i1<=siz[v];++i1){ for(int j1=0;j1<=siz[v];++j1){ if(dp[v][i1][j1]==INT32_MIN) continue; int i2=max(i0,i1),j2=j0+j1; tmp[i2][j2]=max(tmp[i2][j2],dp_v[i0][j0]+dp[v][i1][j1]); } } } } siz[u]+=siz[v]; for(int i=0;i<=siz[u];++i){ for(int j=0;j<=siz[u];++j){ dp_v[i][j]=tmp[i][j]; } } } for(int i=0;i<=siz[u];++i){//考虑根节点u for(int j=0;j<=siz[u];++j){ if(dp_v[i][j]==INT32_MIN) continue; dp[u][i][j+1]=max(dp[u][i][j+1],dp_v[i][j]+i);//选择u作为垫脚石 for(int dj=0;dj<=j;++dj){//消耗dj个垫脚石给自己抬升 int i1=i+dj+1,j1=j-dj; if(i1<=siz[u]+2){ dp[u][i1][j1]=max(dp[u][i1][j1],dp_v[i][j]+i1); } } } } ++siz[u];//加入根节点 } signed main(){ //freopen(".in","r",stdin); //freopen(".out","w",stdout); ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>T; while(T--){ cin>>n>>m; init(); for(int i=2;i<=n;++i){ int p; cin>>p; a[p].emplace_back(i); } dfs(1); for(int i=0;i<=n;++i){ for(int j=0;j<=n;++j){ ans=max(ans,d

记号	含义
$son_u$	$u$ 节点的子节点集
$subt_u$	$u$ 节点的子树点集
$fa(u)$	$u$ 节点的父节点
$\vert subt_u\vert$	$u$ 节点的子树点集大小

166 浏览3 点赞1 收藏0 评论

【贪心】P4447 [AHOI2018初中组] 分组

YIZHIYANG初来乍到 2026-5-18 22:14:41

#题解

【贪心】P4447 [AHOI2018初中组] 分组题意概括给定

n

个队员的实力值，需要将他们分成若干个小组。要求每个小组内的实力值必须是连续的整数，且同一个组内不能出现相同的实力值。每个队员都必须恰好分入一个小组。求在所有合法的分组方案中，人数最少的小组人数的最大值。输入第一行是一个正整数

n

；第二行包含

n

个整数，代表队员的实力值。数据范围：

son_u

，实力值的绝对值不超过

10^9

。保留样例输入：7 4 5 2 3 -4 -3 -5输出：3解释：可以将这 7 个数字分成两组：[-5, -4, -3] 和 [2, 3, 4, 5]。两组内部都是连续且不重复的整数。两组的人数分别为 3 和 4，其中人数较少的是 3。没有更优的分法能让最少人数大于 3。样例分析拿到样例中的 7 个数字：4 5 2 3 -4 -3 -5。如果把它们从小到大排个序，序列就变成了：-5, -4, -3, 2, 3, 4, 5。顺着这个顺序看：前面的 -5, -4, -3 是连在一起的，它们可以刚好组成一组，长度是 3。接下来的 2 和前面断开了，它只能自己新开一组。后面的 3, 4, 5 可以顺次接在 2 后面，组成 [2, 3, 4, 5] 这一组，长度是 4。此时所有的数字都分配完毕，一共分成了两组，人数较少的那一组人数就是 3。题目分析要让每个分组的实力值连续且不重复，处理这种具有连续性要求的问题时，将数据从小到大排序是一个自然的切入点。排序后，相近的、连续的数字就会排在一起。排好序后可以按顺序处理每一个数字。对于当前的数字

x

，有两种选择：把它接到某一个现有的、以

u

结尾的小组后面；或者让它作为开头，自己新成立一个小组。为了让最终“人数最少的小组人数最大”，在有多个现有小组都以

x-1

结尾时，应该优先把

x

接到当前人数最少的那一组后面。这是因为短板决定了最终的答案，把新数字分配给当前最短的小组，能最有效地拉长这个短板。如果没有以

x-1

结尾的小组，说明现有的组都无法容纳

x

，此时

x

只能自己新开一组，初始人数为 1。为了高效地实现这个挑选过程，需要记录每一个小组的结尾数值以及该小组的当前人数。可以使用一个映射，它的键是小组的结尾数值，对应的值是一个最小堆（优先队列）。最小堆里存放所有以该数值结尾的小组的人数。这样每次处理数字

x

时，只需看

x-1

对应的最小堆是否为空：

如果不为空，取出堆顶（也就是最短的小组人数），将其加 1 后放入

x

对应的最小堆中。

如果为空，说明无法拼接，直接在

x

对应的最小堆中插入 1。

把所有数字处理完后，遍历整个结构，找出所有现存小组人数的最小值即可。参考实现#include<bits/stdc++.h> using namespace std; using ll = long long; int a[100005]; map<int, priority_queue<int, vector<int>, greater<int>>> mp; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } sort(a, a + n); for (int i = 0; i < n; i++) { int x = a[i]; if (mp[x - 1].empty()) { mp[x].push(1); } else { int len = mp[x - 1].top(); mp[x - 1].pop(); mp[x].push(len + 1); } } int ans = 2e9; for (auto &p : mp) { if (!p.second.empty()) { ans = min(ans, p.second.top()); } } cout << ans << "\n"; return 0; }复杂度分析

时间复杂度：排序需要

|S_u| \geq 2

的时间。随后的遍历中，对每个元素进行 Map 查找以及优先队列的插入与删除操作，单次操作时间复杂度为

O(\log n)

。因此总时间复杂度为

O(n \log n)

，可以稳定通过所有测试点。

空间复杂度：主要消耗在存储原始实力的数组以及 Map 和优先队列上，它们总共存储的元素数量不会超过

a_v>a_u

，空间复杂度为

O(n)

。

https://www.luogu.com.cn/problem/P4447

128 浏览1 点赞0 收藏1 评论

#题解

rail题解

rankdiff题解

洛谷P13273 [NOI2025] 数字树 题解

两种颜色

三种颜色

已知所有集合，如何计数等价类？

Code

洛谷P14637 [NOIP2025] 树的价值题解与碎碎念

前言

部分记号表

暴力

暴力树上背包 O(n4)O(n^4)O(n4)

【贪心】P4447 [AHOI2018初中组] 分组

【贪心】P4447 [AHOI2018初中组] 分组

题意概括

保留样例

样例分析

题目分析

参考实现

复杂度分析

登录

洛谷P13273 [NOI2025] 数字树题解

暴力树上背包 $O(n^4)$