传送门

勇者比太郎

看懂题后可以发现，我们要求每个 J 右边的 O 的数量乘下面的 I 的数量之和。

预处理前缀和后枚举每个 J 计算即可。

代码

画展

先以 $V_i$ 为第一关键字、$S_i$ 为第二关键字对所有画排个序，以 $C_i$ 为关键字对所有画框排序。

然后从后往前扫，如果当前的画能装进没有装画的 $C$ 最大的画框里，就把它装进去。

正确性比较显然？反正我不会证

代码

有趣的家庭菜园 3

设 $dp_{i,j,k,0/1/2}$ 表示前 $i$ 位，有 $j$ 个 G、$k$ 个 Y，第 $i$ 位的颜色是 R/G/Y 的最小代价。

转移很显然枚举新加的一位的颜色，那么我们只需要求出一个 $cost(x,y,z,0/1/2)$ 表示前 $x+y+z$ 位有 $x$ 个 R、$y$ 个G、$k$ 个 Y ，第 $x+y+z+1$ 位的颜色是 R/G/Y 的最小代价。

这个东西比较好求：首先我们补一个 $x+y+z+1$ 位的颜色，然后其它两种颜色如果有不够的也要补。代码大概长这样：

// pos[i][j] 表示第 j 个颜色 i 的下标
// sum[i][j] 表示前 j 位有多少个颜色 i
inline int cost(int x,int y,int z,int k) {
    int p=x+y+z+1;
    if (x>cnt[0]||y>cnt[1]||z>cnt[2]) return inf;
    if (k==0) {
        if (x+1>cnt[0]) return inf;
        int q=pos[0][x+1];
        return q-p+max(0,y-sum[1][q])+max(0,z-sum[2][q]);
    }
    if (k==1) {
        if (y+1>cnt[1]) return inf;
        int q=pos[1][y+1];
        return q-p+max(0,x-sum[0][q])+max(0,z-sum[2][q]);
    }
    if (k==2) {
        if (z+1>cnt[2]) return inf;
        int q=pos[2][z+1];
        return q-p+max(0,x-sum[0][q])+max(0,y-sum[1][q]);
    }
}

然后就可以 $O(1)$ 转移了，时间复杂度 $O(n^3)$。

代码

硬币收藏

我们先把所有硬币移到范围内离它最近的格子处。这时可能有一些格子里没有硬币，有一些格子里有很多硬币。

我们从左往右扫描每一列，如果当前列有位置空着就可以移过来一个，否则就把当前列多的硬币移出去。

这个看着代码模拟一下差不多就懂了...不知道为啥讲不清楚 QAQ

代码

独特的城市

广告

首先有一个显然的结论：一个点的独特的城市一定在最长链上。

那么我们先把直径找出来，以两个端点为根各 DFS 一次，那么每个点的独特的城市都会在某一次 DFS 中在它到根的路径上。

因此在 DFS 时，我们用一个栈维护根到当前节点的独特的城市，再开一个桶记一下每种特产的出现次数，这样子就可以在修改栈内元素时维护出答案了。

考虑怎么维护这个栈。在当前节点到根的路径上会有一些分叉，这些分叉会让一段点不是独特的城市，因此我们要在 DFS 时利用这些分叉来删掉不是独特的城市的点。

具体的，在 DFS 时做如下过程：

1. 将父节点入栈。
2. 将栈中到当前节点距离 $\leq$ 子树内次长链长度的点删掉。这里的次长链长度可以预处理出来。
3. 递归处理最长链所在的子树（即长链剖分后的重儿子）。
4. 将栈中到当前节点距离 $\leq$ 子树内最长链长度的点删掉。这里的最长链长度可以预处理出来。
5. 用此时维护的答案更新当前节点的答案。
6. 递归处理最长链不在的子树（即长链剖分后的轻儿子）。

然后每个点的实际答案是两个端点算出来的答案的 $\max$。

代码