于洛谷专栏获得更差的阅读体验。
于 CSDN 获得更一般的阅读体验。
赛时 AC ABCD，赛后补出了 E。
由于比赛在一个月前，本来已经忘记这场比赛了，直到我看到了：
（来自一位超厉害的小学同学神犇）
\(364\)？很近的比赛啊，我打过吗？似乎打过？
打开题目一看：这不就是斯坦纳树板题吗？但我为什么没印象？
打开 AT 一看，额，我还真打过：
菜爆了。。。也难怪对 G 没印象。
重新看一下题，发现还挺好玩，遂把 F、G 题干掉了。
作为第二场 AK 的比赛（第一场是 ABC126，但是太简单了），决定写篇总结。
以下 \(5\) 题是比赛当天做的。
[ABC364A] Glutton Takahashi
只要判断是否有 \(2\) 个连续的 sweet。
笑点解析：赛时吃了一发罚时，数组下标写错了。
过此题时比赛已经过去了 \(6\) 分钟。
[ABC364B] Grid Walk
按题意模拟。
过此题时比赛已经过去了 \(11\) 分钟。
[ABC364C] Minimum Glutton
贪心。
想要停止吃饭，甜度限制和咸度限制只需要超过一个就可以了。所以可以分别按甜度和咸度从大到小排序，看哪种策略先结束。
过此题时比赛已经过去了 \(16\) 分钟。
[ABC364D] K-th Nearest
二分套二分，需要思维转换。
与直接其求距离给定点第 \(k\) 近的点是哪个，不如直接求这个距离。设给定点坐标为 \(x\)，二分这个距离（记为 \(b\)），看在 \([x-b,x+b]\) 的范围内有几个点。区间查询使用线段树，由于值域范围过大，动态开点。
然而刚才看题解区发现全是二分套二分……二分距离后，二分距离 \(x-b,x+b\) 最近的点，判断中间的点的数量。
赛后为了涨咕值写了篇题解。
过此题时比赛已经过去了 \(57\) 分钟。
[ABC364E] Maximum Glutton
注意看这个 Maximum，和前文的 minimum 形成了鲜明的对比，设置悬念，吸引读者的阅读兴趣，引发读者的思考，前后呼应，提示我们二者有相同也有不同。
由于要吃尽量多的东西，就要求两个参数都不能超过限制，此时一道菜的两个参数都会对当前情况的优劣产生影响，所以贪心会比较难绷。
于是使用 DP。
然后一看数据范围：
空间去掉 \(n\) 那维还勉强是 \(x \times y=10^8\) 刚刚好，时间就这 \(O(nxy)=8 \times 10^9\)，根本不带超时的好吧！
赛时吃了 \(2\) 发罚时（未 AC），win！
赛后 \(20\) min 看题解。
Instead, noticing that the value of \(N\) is fairly smaller than those of \(X\) and \(Y\) in this problem, we take the following typical approach: swapping the key and value of DP. Specifically, bring the number of dishes to the key and total saltiness to the value to define:
- \(dp_{i,j,k}=\) (the minimum total saltiness when choosing exactly \(k\) dishes from dishes
\(1,2,\dots,i\) so that the total sweetness is exactly
\(j\)).This way, the DP table can be filled in a total of
\(O(N ^2X)\) time. All that left is to find the maximum
\(k\) such that there exists \(j\) with \(dp_{N,j,k}\le Y\).
沃德？？？那么妙又那么帅的吗？我居然没想到，是自己太菜了……还不是因为自己不够努力。。。
常用 DP trick \(+1\)。
于是开始补题。一开始填表法过不去，用了刷表法才过。
此时已经 \(22:18\) 了。
以下 \(2\) 题是 \(2024.8.27\) 才做的。
[ABC364F]Range Connect MST
好玩，kruskal 与并查集小技巧 \(+1\)。
按照 kruskal 的步骤去做，但是发现不能暴力判断一条边的两个点是否连通。但由于一个区间的所有点都连向一个点，所以 \([l_i,r_i]\) 有几个连通块就会连几条边。暴力处理每个连通块，把前面的合并到后面。
哦，想起来了，赛时看过几眼。
[ABC364G]Last Major City
一眼得斯坦纳树。
先考虑只有 \(k-1\) 个关键点，直接复制板题代码即可。对于每一个询问，输出 \(f_{i,S}\) 即可，因为当第 \(i\) 个点被连通时，可以把它当做又一个关键点。
总结
好比赛，好题。
希望可以多出点这样的比赛，不要像某些比赛只会出三维前缀和。于博客园获得更好的阅读体验。
赛时 AC ABCD，赛后补出了 E。
由于比赛在一个月前，本来已经忘记这场比赛了，直到我看到了：
（来自一位超厉害的小学同学神犇）
\(364\)？很近的比赛啊，我打过吗？似乎打过？
打开题目一看：这不就是斯坦纳树板题吗？但我为什么没印象？
打开 AT 一看，额，我还真打过：
菜爆了。。。也难怪对 G 没印象。
重新看一下题，发现还挺好玩，遂把 F、G 题干掉了。
作为第二场 AK 的比赛（第一场是 ABC126，但是太简单了），决定写篇总结。
以下 \(5\) 题是比赛当天做的。
[ABC364A] Glutton Takahashi
只要判断是否有 \(2\) 个连续的 sweet。
笑点解析：赛时吃了一发罚时，数组下标写错了。
过此题时比赛已经过去了 \(6\) 分钟。
[ABC364B] Grid Walk
按题意模拟。
过此题时比赛已经过去了 \(11\) 分钟。
[ABC364C] Minimum Glutton
贪心。
想要停止吃饭，甜度限制和咸度限制只需要超过一个就可以了。所以可以分别按甜度和咸度从大到小排序，看哪种策略先结束。
过此题时比赛已经过去了 \(16\) 分钟。
[ABC364D] K-th Nearest
二分套二分，需要思维转换。
与直接其求距离给定点第 \(k\) 近的点是哪个，不如直接求这个距离。设给定点坐标为 \(x\)，二分这个距离（记为 \(b\)），看在 \([x-b,x+b]\) 的范围内有几个点。区间查询使用线段树，由于值域范围过大，动态开点。
然而刚才看题解区发现全是二分套二分……二分距离后，二分距离 \(x-b,x+b\) 最近的点，判断中间的点的数量。
赛后为了涨咕值写了篇题解。
过此题时比赛已经过去了 \(57\) 分钟。
[ABC364E] Maximum Glutton
注意看这个 Maximum，和前文的 minimum 形成了鲜明的对比，设置悬念，吸引读者的阅读兴趣，引发读者的思考，前后呼应，提示我们二者有相同也有不同。
由于要吃尽量多的东西，就要求两个参数都不能超过限制，此时一道菜的两个参数都会对当前情况的优劣产生影响，所以贪心会比较难绷。
于是使用 DP。
然后一看数据范围：
空间去掉 \(n\) 那维还勉强是 \(x \times y=10^8\) 刚刚好，时间就这 \(O(nxy)=8 \times 10^9\)，根本不带超时的好吧！
赛时吃了 \(2\) 发罚时（未 AC），win！
赛后 \(20\) min 看题解。
Instead, noticing that the value of \(N\) is fairly smaller than those of \(X\) and \(Y\) in this problem, we take the following typical approach: swapping the key and value of DP. Specifically, bring the number of dishes to the key and total saltiness to the value to define:
- \(dp_{i,j,k}=\) (the minimum total saltiness when choosing exactly \(k\) dishes from dishes
\(1,2,\dots,i\) so that the total sweetness is exactly
\(j\)).This way, the DP table can be filled in a total of
\(O(N ^2X)\) time. All that left is to find the maximum
\(k\) such that there exists \(j\) with \(dp_{N,j,k}\le Y\).
沃德？？？那么妙又那么帅的吗？我居然没想到，是自己太菜了……还不是因为自己不够努力。。。
常用 DP trick \(+1\)。
于是开始补题。一开始填表法过不去，用了刷表法才过。
此时已经 \(22:18\) 了。
以下 \(2\) 题是 \(2024.8.27\) 才做的。
[ABC364F]Range Connect MST
好玩，kruskal 与并查集小技巧 \(+1\)。
按照 kruskal 的步骤去做，但是发现不能暴力判断一条边的两个点是否连通。但由于一个区间的所有点都连向一个点，所以 \([l_i,r_i]\) 有几个连通块就会连几条边。暴力处理每个连通块，把前面的合并到后面。
哦，想起来了，赛时看过几眼。
[ABC364G]Last Major City
一眼得斯坦纳树。
先考虑只有 \(k-1\) 个关键点，直接复制板题代码即可。对于每一个询问，输出 \(f_{i,S}\) 即可，因为当第 \(i\) 个点被连通时，可以把它当做又一个关键点。
总结
好比赛，好题。
希望可以多出点这样的比赛，不要像某些比赛只会出三维前缀和。