Link-Cut_Trees - 博客园

2026年6月1日

P3206 [HNOI2010] 城市建设

摘要：题意给一张 \(n\) 个点，\(m\) 条边的唔无向图，有边权，\(q\) 次修改，每次修改一条边的边权，查询最小生成树上的边权和。 \(n\le2\times 10^4\)，\(m,q\le5\times10^4\)。思路把修改边权看作删除原来的边，加入一条新的边。记录每条边出现的时间段，阅读全文

posted @ 2026-06-01 17:24 Link-Cut_Trees 阅读(6) 评论(0) 推荐(0)

P5229 [AHOI2013] 立方体

摘要：题意给出 \(n\) 个立方体，求由祂们组成的几何图形的表面积。 \(n,x,y,z\le200\)。思路直接跑扫描线是不行的，因为那样会把内表面也算进去，考虑用一些更暴力的方法。先用三维差分求出每个位置是否被立方体占据。然后从 \((0,0,0)\) 开始宽搜，不能穿过被占据的位置。如果遇阅读全文

posted @ 2026-06-01 17:14 Link-Cut_Trees 阅读(6) 评论(0) 推荐(0)

2026年5月27日

20260527紫题训练总结

摘要： A - 数字串拆分简单题。题解 B - 打扫房间简单题，但是没想到用网络流，认为可以直接插头 \(DP\)。题解 C - 苦无码量很大。没想到在同一条 \(45^{\circ}\) 倾斜的线上的点方向正确可以相遇。题解阅读全文

posted @ 2026-05-27 22:33 Link-Cut_Trees 阅读(6) 评论(0) 推荐(0)

P3635 [APIO2012] 苦无

摘要：题意一个 \(W\times H\) 的平面，有 \(n\) 个点，每个点有一个方向，每个时刻点会向祂的方向移动一个方向移动一个单位，两个点相遇时会消失。平面内被点经过的格子数量。 \(H,W\le10^9,n\le10^5\)。思路两个点如果能相遇，那么祂们一定在同一行或同一列或同一条 \( 阅读全文

posted @ 2026-05-27 22:28 Link-Cut_Trees 阅读(4) 评论(0) 推荐(0)

P3877 [TJOI2010] 打扫房间

摘要：题意给一个 \(n\times m\) 的房间，有些位置是障碍。问能否在空地上画出若干条回路，使得每个空地恰好被经过一次。 \(n,m\le30\)。思路直接插头 \(DP\)？不对，会 \(TLE\)。考虑用网络流。如果每个空地的度都是 \(2\)，并且两条边不是连向同一个点，那么就是合阅读全文

posted @ 2026-05-27 22:11 Link-Cut_Trees 阅读(7) 评论(0) 推荐(0)

P3176 [HAOI2015] 数字串拆分

摘要：题意给出一个数字串 \(s_0\) 和一个数 \(m\)。定义 \(f(n)\) 为把 \(n\) 拆分成若干个 \(1∼m\) 的数的和的方案数（有序）。定义 \(g(n)\) 为将数字串 \(n\) 分成若干个数字（可以有前导 \(0\)），设祂们和为 \(x\)，则 \(g(n)\) 为阅读全文

posted @ 2026-05-27 22:06 Link-Cut_Trees 阅读(7) 评论(0) 推荐(0)

2026年5月26日

20260526紫题训练总结

摘要： A - 按位或 \(min-max\) 反演题，但是我不会。题解 B - 数字序列 \(2-sat\) 题，一些小细节没考虑清楚。题解 C - 最小生成树简单题题解阅读全文

posted @ 2026-05-26 22:15 Link-Cut_Trees 阅读(8) 评论(0) 推荐(0)

P5039 [SHOI2010] 最小生成树

摘要：题意给一个 \(n\) 个点 \(m\) 条边的无向图，边有边权，每次操作可以给出了某一条指定边外的所有边权值减一。要求用最小的操作次数，使得一条给定的边一定在原图的最小生成树中。 \(n\le500,m\le800\)。思路每次操作相当于给一条边权值加一。设题目要求边 \((x,y,z)\) 阅读全文

posted @ 2026-05-26 22:12 Link-Cut_Trees 阅读(5) 评论(0) 推荐(0)

P3876 [TJOI2010] 数字序列

摘要：题意要求构造一个序列，包含 \(0,1,2,3\)，相邻的两个数不能是 00,11,22,33,02,20,23,32,13,31，并且有 \(m\) 个限制，每个限制给出一些位置，要求这些位置上的数两两不同，问有没有解。 \(n\le10^5,m\le5000\)。思路显然，当一个约束集合的阅读全文

posted @ 2026-05-26 22:06 Link-Cut_Trees 阅读(4) 评论(0) 推荐(0)

P3175 [HAOI2015] 按位或

摘要：题意你有一个数 \(x\)，初始时 \(x=0\)，每次按照给定的概率选择一个 \(y\in[0,s^n-1]\)，把你 \(x\) 变成 \(x|y\)。问期望几次，能让 \(x\) 变成 \(2^n-1\)。 \(n\le20\)。思路设 \(\max(S)\) 表示 \(S\) 中最晚的阅读全文

posted @ 2026-05-26 21:24 Link-Cut_Trees 阅读(5) 评论(0) 推荐(0)

Link-Cut-Trees

公告