[ICPC 2018 Shenyang R] The Kouga Ninja Scrolls
题目链接： [ICPC 2018 Shenyang R] The Kouga Ninja Scrolls 。
题目描述：
故事围绕着 nnn 个互为对手的忍者氏族展开，氏族编号从 111 到 nnn，同样也有 nnn 名忍者，编号从 111 到 nnn。对每一名忍者，其家族决定了他/她最初的信念与所属的氏族。但故事中会发生一些冲突，例如两个年轻的灵魂，面对各自家族的敌对却坠入爱河，可能会改变心意，一些忍者也可能叛逃至其他敌对的氏族。
这些忍者生活在一个相当宁静的小镇，镇上的小径简单明了，但他们却像一群野兽，时刻盯着其他氏族的忍者，不停逃亡并伺机杀戮。这片区域的领主知道，他们之间战争的终结取决于那些分属不同氏族且相距最远的忍者。
这正是作为领主忠实仆人的一只高贵秃鹫应当做的事情。现在你需要扮演这只秃鹫，实时向领主报告：在编号属于某个指定连续范围内的忍者中，分属不同氏族的两名忍者之间的最大距离是多少。具体而言，平面上两点之间的距离定义为曼哈顿距离，也就是它们笛卡尔坐标差的绝对值之和。
答案求 ...
[ICPC 2018 Shenyang R] Insertion Sort
题目链接： [ICPC 2018 Shenyang R] Insertion Sort 。
题目描述（简化版）：
经过原题面转化。
给定 n,k,Pn,k,Pn,k,P ，求所有长度 nnn 的排列中，将前 kkk 个排好序之后最长上升子序列至少为 n−1n-1n−1 的方案数。对 PPP 取模。
首先考虑前 kkk 个的分布。
Case #1
前 kkk 个数恰为 1∼k1\sim k1∼k 。
此时只需后面 k+1∼nk+1\sim nk+1∼n 的最长上升子序列至少 n−k−1n-k-1n−k−1 即可。
易知方案数为 k!×((n−k−1)2+1)k!\times ((n-k-1)^2+1)k!×((n−k−1)2+1) 。
Case #2
前 kkk 个数恰为 1∼k+11\sim k+11∼k+1 中 kkk 个（不包括 Case #1 ）。
此时只需后面 k+2∼nk+2\sim nk+2∼n 有序。
所以此时我们需要将前 kkk 个位置的数乱序，并枚举 1∼k1\sim k1∼ ...
[ICPC 2018 Nanjing R] Mediocre String Problem & [ICPC 2018 Nanjing R] Magic Potion
第一道简单字符串， manacher 和 exKMP 搞一搞就行。第二道随便建模都能过。
[ICPC 2018 Nanjing R] Kangaroo Puzzle
题目链接： [ICPC 2018 Nanjing R] Kangaroo Puzzle 。
题目描述：
你的朋友制作了一款名为“袋鼠谜题”的电脑视频游戏，想让你帮他试玩一下。正如游戏名称所示，谜题中困着若干只（至少 222 只）袋鼠，玩家的目标是控制它们聚集在一起。只要谜题中的所有袋鼠都聚到一起，它们就能借助袋鼠的神奇力量逃出谜题。
谜题是一个包含 n×mn \times mn×m 个格子的 nnn 行 mmm 列网格。某些格子是墙壁，袋鼠无法进入这些格子。其余格子为空地。袋鼠可以向上、下、左、右四个方向移动。保证一只袋鼠可以从任意一个空格子出发到达任意另一个空格子。同时保证谜题中不存在环——也就是说，袋鼠不可能从一个空格子出发，经过若干不同的空格子，再回到初始格子。
初始时，每个空格子上恰好有一只袋鼠。你可以通过按下键盘上的 U\texttt{U}U、D\texttt{D}D、L\texttt{L}L、R\texttt{R}R 键来控制袋鼠。所有袋鼠会根据你按下的键同时移动。例如，当你按下 U\textt ...
[APIO2020] 交换城市
题目链接： [APIO2020] 交换城市 。
题目描述（简化版）：
给一个 nnn 点 mmm 边的无向连通图，多次询问，每次给定 x,yx,yx,y ，找到 xxx 和 yyy 的两条不同路径的最大边权的最小值。若不存在两条路径则输出 −1-1−1 。
询问强制在线。
原题面要多一步转化，在此省略。
这是一个类似于最小瓶颈路的问题，于是建立 Kruskal 重构树之后我们可以在树上 lca(x,y)lca(x,y)lca(x,y) 为起点进行倍增，每次判断一个节点 ttt 是否存在链接 xxx 和 yyy 的 222 条路径。
考虑如何进行判断。容易发现只要不是链，则 xxx 和 yyy 一定存在这样的路径。于是问题变为了如何在并查集的过程中维护集合是否为链。
参考 [USACO17OPEN] Switch Grass P ，我们每次只需要维护当前并查集的两个端点。在每次合并边时更新端点即可。
PS: 当并查集过程中遇到 x==yx==yx==y 时的边时，由于这条边的存在，原先可能为链的子图现在一定不为链了，所以我们应该新建一个点，并将 x ...
[ICPC 2018 Nanjing R] Country Meow
题目链接： Country Meow 。
题目描述：
给 n≤100n\le 100n≤100 个三维点，求最小球覆盖的半径（精度 333 位即可）。
因为精度不高，于是三份套三分套三分。
代码：
12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include <bits/stdc++.h>using namespace std;const int N=110;const double eps=1e-8;int n;double x[N],y[N],z[N];double dis(double x,double y,double z,double X,double Y,double Z){ return sqrt((x-X)*(x-X)+(y-Y)*(y-Y)+(z-Z)*(z-Z));}double h(double X,double Y,double Z){ dou ...
[ICPC 2018 Xuzhou R] Rikka with Intersections of Paths
题目链接： [ICPC 2018 Xuzhou R] Rikka with Intersections of Paths 。
题目描述：
有 nnn 个点的树， mmm 条路径，求选出 kkk 个路径满足有至少一个公共点的方案数，对 109+710^9+7109+7 取模。
n,m,k≤3×105n,m,k\le 3\times 10^5n,m,k≤3×105 。
一眼树上差分统计每一个点被多少路径覆盖。记为 cnticnt_icnti 。
然而直接计算 ∑(cntik)\sum \binom{cnt_i}{k}∑(kcnti) 有问题，因为可能有些路径拥有超过 111 个公共点，这些路径就会在他们的所有公共点处被重复统计。
注意到以下性质：
一个路径 x,yx,yx,y 经过 iii 意味着 lca(x,y)lca(x,y)lca(x,y) 为 iii 的祖先或 iii 。
也就是说，所有经过 iii 的路径的 lcalcalca 必然为 iii 的祖先或 i ...
[ICPC 2018 Xuzhou R] Rikka with A Long Colour Palette
题目链接： [ICPC 2018 Xuzhou R] Rikka with A Long Colour Palette 。
题目描述：
有 nnn 个线段，第 iii 个线段覆盖 [li,ri)[l_i,r_i)[li,ri) 。共 kkk 种颜色。
你可以为每一个线段分配一个颜色 cic_ici ，之后对每一个 iii ，将区间 [li,ri)[l_i,r_i)[li,ri) 加入颜色 cic_ici 。
要求使被所有颜色覆盖的面积最大，并构造方案。
n,k≤2×105n,k \le 2\times 10^5n,k≤2×105 。
经典按照左端点排序。之后考虑贪心：
先将前 kkk 个线段加入，并赋予颜色 1∼k1\sim k1∼k 。
对于 i=k+1∼ni=k+1\sim ni=k+1∼n ，每次肯定要考虑目前右端点最靠前的那个线段并继承她的颜色。
正确性是因为她是右端点最靠前的。如果你不继承她的颜色，那么中间的一段必然不可能贡献。
这个贪心思路还是挺 ...
APIO 2026 YouJi
So tasty /cy
Day 0
LH said that he would give us a test. I thought that I could not meet with LH, so I decided to escape. /cy
I slept well at night.
Day 1
In the morning, I went to Beijing which have a senior school named 北京大学附属中学\text{北京大学附属中学}北京大学附属中学 . when I met with some people in hsy, we went to a nice restaurant looked very tasty to eat lunch. I ate an absolutely tasty 烧肉饭 , making me happy and have full of tastiness.
In the afternoon, we achieved our hotel – YouYi Hote ...
APIO 2026 游记
好吃 /cy
Day 0
LH 晚上说要考试，反正接下来一周都见不到，逃走了。 /cy
晚上睡的很好。
Day 1
上午坐火车，到达 北京大学附属中学\text{北京大学附属中学}北京大学附属中学 的所属地北京。跟 hsy 的人汇合后，去了一家很好吃的餐厅吃饭。我吃了一碗很好吃的烧肉饭，好吃好吃。 /cy
下午到达了酒店——友谊宾馆。
第一次住五星级酒店.png
一个房间两个人，我和 lpr 大神在一起。
下午好累，睡了一觉起来后发现有饭票，于是到北大附中的食堂吃饭。今天晚上吃了十分好吃的 番茄牛肉面\text{番茄牛肉面}番茄牛肉面 ，满满一大碗， 大约是 ??? 一碗饭的 18 倍吧。真好吃 /cy 。
吃完饭回宾馆后，我突然想到 xrxt 他们正在考试，内心狂喜十分悲痛，他们能开心的考试，而我只能伤心的玩耍。 /bx
晚上 lpr 大神找 W 去玩了，我在房间里随便玩了玩。 /cy
Day 2
一早上要求 7:20 起来吃早饭，不过奇怪的事情是我平常根本起不来，结果这几天每天 7:00 就醒了，真神奇。
也是终于体验了一回五星级酒店的早餐，还是 ...
