题目地址：大家好，我是"题目地址"
想比较不容易偏，但写着细节贼多的题。
首先考虑最优策略，注意到题目给出强化牌的wi>1" role="presentation" style="position: relative;">wi>1wi>1wi>1的条件。
因此，优先打出最大的强化牌一定是最优的，考虑选择了两张最大的攻击牌，仍然与选择最小的强化牌等价。
接下来我们考虑选牌的情况：
设拿到了强化牌c" role="presentation" style="position: relative;">ccc张，攻击牌m−c
题目链接：https://loj.ac/problem/2537 考虑到题目是一颗二叉树，有一个简单的O(N^2)的DP做法。f(i,j)表示i号点取值为数集中第j大数的概率，每一次我们从子树合并上来。j被取到有两种情况：j更大并且当前选择的是最大值 j更小并且当前选择的是最小值分情况讨论，发现要转移需要一个选到比j小的值的概率和(比j大的可以直接用1减比j小的)。那么我们维护两个前缀和(对两边的元素分别计算)，即可完成一次合并。 如何优化这个算法呢？假设两边子树可以产生的j值集合分别为A，B。考虑A值域上这样连续的一段数：满足不存在B[i]使得A[l]<=B[i]<=A
地址：https://loj.ac/problem/2567
看来在组合计数的路上，还有很长一段路要走啊……
首先ai,bi≤109" role="presentation" style="position: relative;">ai,bi≤109ai,bi≤109a_i,b_i\leq 10^9，显然dp" role="presentation" style="position: relative;">dpdpdp不能和值域有关。
考虑最终的答案，发现答案统计的时候每一个学校只是在分界点之间做前缀和。
考虑O(n)" role="presen
地址：https://loj.ac/problem/2587 先来说说我和这道题的故事吧。作为APIO2018最良心得分题，放在T3的位置是真的阴……当打完了T1,T2的暴力后，才发现T3貌似很好拿分，想的是把T1，T2的二档暴力打完后来慢慢拿T3的分。于是就被坑进T1了。T3最后只打了有环和链的、n<=10的。树的档都没看到，血亏。知道了点双树(圆方树)后，这道题就很送分了。对于圆点统计从不同子树中选出两个点的方案，对于方点统计从不同子树选出三个点的方案，加起来就行了。细节比较多，详见注释#include<cstdio>
#include<cstring>
#i
地址：https://loj.ac/problem/2586 说一说我和这道题的故事吧。打完T1的5分后我又来看到了T2。一看完了又不会，赶快打了个7分暴力。再想想，我貌似可以拿Subtask2的12分，准备打完T1来码。然后T1的400个set死活打不出来……于是乎这道题是彻底凉了。一下来就听见很多人码了个KD-tree爆艹T2，什么鬼？？？？不过正解貌似是个线段树维护扫描线，没人写…… 然后为了练习KDtree，今天又搬出这道题来。思路大概是一个节点维护能框住下面所有圆的最小矩形。嗯……就是把圆并近似成矩形判相交剪枝然后骗分。这个做法在考场上就能得到87分，都怪当年
地址：https://loj.ac/problem/2585 说一说我和这道题的故事吧。APIO2018现场：和moonzero在一个考室，前一天才好不容易会使用linux系统后一天就要上考场了，非常的方。打开problems，首先映入眼帘的便是 A.新家。毫不犹豫先打了5分暴力，然后去打了T3，T2的暴力。回头来准备肝T1，发现自己会Subtask2的7分暴力。然后死也没调出来，400个set把自己送胸牌了。下来moonzero告诉我他更窒息，写了400个splay………………嗯，叙旧就叙到这里了，前几天又想起这道题，发现有了思路。接下来我们来看看APIO这道亲民的码农题的做法吧。首先我们容
题目描述曾经有一款流行的游戏，叫做 Infinity Loop，先来简单的介绍一下这个游戏: 游戏在一个 n×m 的网格状棋盘上进行，其中有些小方格中会有水管，水管可能在方格某些方向的边界的中点有接口，所有水管的粗细都相同，所以如果两个相邻方格的公共边界的中点都有接头，那么可以看作这两个接头互相连接。水管有以下 15 种形状： 游戏开始时，棋盘中水管可能存在漏水的地方。 形式化地:如果存在某个接头，没有和其它接头相连接，那么它就是一个漏水的地方。 玩家可以进行一种操作：选定一个含有非直线型水管的方格，将其中的水管绕方格中心顺时针或
Rockdu's Blog