本题的题意非常简单。 安妮有一个技能是熔岩护盾，开启来之后持续5秒，并且冷却时间为10秒。这个护盾有一个效果就是能反伤敌军的基础攻击。反伤值如下公式： \(60 + (0.2 \times sp)\) 其中sp为安妮的法术强度。 我们假设安妮从一开始就开护盾，并且每次冷却结束就立马再开。 题目给出敌军每次攻击安妮的时刻，求最后安妮的熔岩护盾输出的总反伤伤害。 做法就是给每个时刻强制取整之后对10取模，如果是5以内的就是反伤，如果是5以外的则无反伤，但是如果是5的话，再判断这个时刻有没有小数部分。如果有小数部分也是无反伤。
伊丽丝有很多小蜘蛛，它们都有着各自的兴趣。一群蜘蛛里面，若任意两只蜘蛛之间没有直接或者间接的相同爱好就会吵架（间接相同爱好就是比如 蜘蛛A 喜欢唱歌， 蜘蛛B 喜欢唱歌和跳舞， 蜘蛛C 喜欢跳舞，那么我们就说 蜘蛛A 与 蜘蛛C 有着间接的相同爱好）。 为了让所有蜘蛛都不吵架，我们必须给其中一些蜘蛛培养一些新的兴趣使其与其它蜘蛛合群。 问让任意两只蜘蛛都不吵架，最少要给这些蜘蛛培养多少新的兴趣。 从题意上看这题是一道并查集的题目—— 对于每只蜘蛛来说，我们读取其所有的兴趣，然后这只蜘蛛的所有兴趣都并在一个集合中。 最后我们判断一共有多少个集合，那么就需要培养\(集合数 - 1\)个兴趣。 但值得注意的是，如果每只蜘蛛都没有兴趣的话，那我们就得给每一只蜘蛛都培养一个兴趣——即需要培养n个兴趣。
题目就是给你一坨点，然后你找出这些点构成的矩形中最大的那个矩形的面积。注意这个矩形是可以斜着的。 方法很多，这边标程的做法就是三重循环，枚举三个点，看这三个点是否能构成直角三角形（勾股定理）。若是直角三角形则再补上第四个顶点的坐标形成一个矩形，然后判断这个坐标存不存在给出的坐标中。若存在则这是一个矩形。 最后把所有矩形的面积比较一下拿出最大那个矩形即可。
奥利安娜的球有五档攻击。每一档在每一次攻击的时候造成的伤害都不一样。有一个条件，就是如果奥利安娜这次的攻击档数比上一次低，那么下一次攻击就要比这次高，相反如果奥利安娜这次的档数比上一次高，那么下一次攻击就要比这次低。 给出每个档在每次攻击所能造成的伤害，问最大能造成多少伤害。 这题的DP感觉还算明显的，我们设有如下的状态： dp[i][j][k] 设上式的意思为第i次攻击的时候选j档，然后最后的k只有0和1，代表这次攻击比上次攻击的档数是高还是低。 那么就有如下的转移方程： for(int i = 2; i < n; i++) { for(int j = 0; j < 5; j++) { for(int k = 0; k < 5; k++) { if(j == k) continue; if(j < k) dp[i][j][0] = max(dp[i][j][0], dp[i - 1][k][1] + M[j][i]); else if(j > k) dp[i][j][1] = max(dp[i][j][1], dp[i - 1][k][0] + M[j][i]); } } } 最后我们只需要选择最后一次攻击的时候的几个答案中最大的那个即可。
有一个数列，长度最大为 \(10^5\) ，每个数字的范围为 \(10^9\) 。现在有 Q 个询问（ \(1 \leqslant Q \leqslant 10^5\) ），每个询问是一个区间，你需要输出这个区间内每个数字出现的次数的立方和。 比如说下面的这个数列： 1 1 3 1 3 1 3 3 其中 1 出现了 4 次， 3 也出现了 4 次，那么立方和就是： \(4^3+4^3=128\)。 这题主要是用分段的思想来做的。 首先我们先考虑一种暴力的离线做法： 求出第一个询问的立方和，存起来。 然后一一去不断移动询问的左端点和右端点来做每一个询问。 比如上面的数列，我们设第一次询问为 1~4 ，第二次询问为 2~5 。那么我们先暴力做出 1~4 的结果为 28 ，并记录每个数字出现的次数（离散化）。然后做 3~5 ，在这里我们左端点移动两格；在第一格移动的时候，去掉一个 1 ，那么 1 的数量从 3 变为 2 ，即 \(28-3^3+2^3=9\) ；然后移动第二格的时候，又去掉一个 1 ，那么 1 的数量从 2 变为 1 ，即 \(9-2^3+1^3=2\) ；最后右端点往右移动一格，即多了一个 3 ，那么就是 \(2-1^3+2^3=9\) ，这就是 3~5 的答案了。 我们来算下时间复杂度吧，一共有 Q 个询问，每个询问我们左右端点最多移动 N 次左右，所以时间复杂度差不多就是 \(O(NQ)\) ，其中 N 和 Q 都为 \(10^5\) 。 这肯定要超时的。但为什么我还要介绍这个暴力的做法呢？ 因为下面的正解就是建立在这样的暴力的基础上的。 我们将这个数列分段——每段长度为 \(\sqrt{N}\) （当然最后一段长度可能比这个小），一共 \(\sqrt{N}\) 段。 然后我们所有询问分组——所有左端点在同一段的询问分为一组。 接下去我们对每一组的询问进行排序——按右端点正序排序。 我们现在就可以用之间讲的暴力的做法来做这个题目了。 也许有些人会感到奇怪，为什么这么一弄之后就可以了呢？好，让我们再分析一下分段之后的暴力时间复杂度： 首先对于每一组询问来说，左端点都在同一段内，而一段的长度不超过 \(\sqrt{N}\) ，所以对于左端点的询问时间复杂度为 \(O(Q\sqrt{N})\) 。 其次对于每一组询问来说，右端点是递增的，所以不管有多少询问，右端点的总步数肯定是在 N 以内，然后最多有 \(\sqrt{N}\) 组，那么右端点的询问时间复杂度为 \(O(N\sqrt{N})\) 。 两者一结合，时间复杂度就是 \(O((N + Q)\sqrt{N})\) 。非常巧妙有木有？这样一分段就将一个 \(O(NQ)\) 的时间复杂度简化到了 \(O((N + Q)\sqrt{N})\) 了。
Problems
[A] Annie View the problem View the source
Tags: Water
本题的题意非常简单。
题目给出敌军每次攻击安妮的时刻，求最后安妮的熔岩护盾输出的总反伤伤害。
做法就是给每个时刻强制取整之后对
10取模，如果是5以内的就是反伤，如果是5以外的则无反伤，但是如果是5的话，再判断这个时刻有没有小数部分。如果有小数部分也是无反伤。Standard Code
C++
[C] Elise View the problem View the source
Tags: Union-find Sets
伊丽丝有很多小蜘蛛，它们都有着各自的兴趣。一群蜘蛛里面，若任意两只蜘蛛之间没有直接或者间接的相同爱好就会吵架（间接相同爱好就是比如 蜘蛛A 喜欢唱歌， 蜘蛛B 喜欢唱歌和跳舞， 蜘蛛C 喜欢跳舞，那么我们就说 蜘蛛A 与 蜘蛛C 有着间接的相同爱好）。
为了让所有蜘蛛都不吵架，我们必须给其中一些蜘蛛培养一些新的兴趣使其与其它蜘蛛合群。
问让任意两只蜘蛛都不吵架，最少要给这些蜘蛛培养多少新的兴趣。
从题意上看这题是一道并查集的题目——
对于每只蜘蛛来说，我们读取其所有的兴趣，然后这只蜘蛛的所有兴趣都并在一个集合中。
最后我们判断一共有多少个集合，那么就需要培养\(集合数 - 1\)个兴趣。
但值得注意的是，如果每只蜘蛛都没有兴趣的话，那我们就得给每一只蜘蛛都培养一个兴趣——即需要培养
n个兴趣。Standard Code
C++
[E] LeBlanc View the problem View the source
Tags: Geometry
题目就是给你一坨点，然后你找出这些点构成的矩形中最大的那个矩形的面积。注意这个矩形是可以斜着的。
方法很多，这边标程的做法就是三重循环，枚举三个点，看这三个点是否能构成直角三角形（勾股定理）。若是直角三角形则再补上第四个顶点的坐标形成一个矩形，然后判断这个坐标存不存在给出的坐标中。若存在则这是一个矩形。
最后把所有矩形的面积比较一下拿出最大那个矩形即可。
Standard Code
C++
[H] Orianna View the problem View the source
Tags: DP
奥利安娜的球有五档攻击。每一档在每一次攻击的时候造成的伤害都不一样。有一个条件，就是如果奥利安娜这次的攻击档数比上一次低，那么下一次攻击就要比这次高，相反如果奥利安娜这次的档数比上一次高，那么下一次攻击就要比这次低。
给出每个档在每次攻击所能造成的伤害，问最大能造成多少伤害。
这题的
DP感觉还算明显的，我们设有如下的状态：设上式的意思为第
i次攻击的时候选j档，然后最后的k只有0和1，代表这次攻击比上次攻击的档数是高还是低。那么就有如下的转移方程：
最后我们只需要选择最后一次攻击的时候的几个答案中最大的那个即可。
Standard Code
C++
[I] Sona View the problem View the source
Tags: Segmentation
有一个数列，长度最大为 \(10^5\) ，每个数字的范围为 \(10^9\) 。现在有
Q个询问（ \(1 \leqslant Q \leqslant 10^5\) ），每个询问是一个区间，你需要输出这个区间内每个数字出现的次数的立方和。比如说下面的这个数列：
其中
1出现了 4 次，3也出现了 4 次，那么立方和就是：这题主要是用分段的思想来做的。
首先我们先考虑一种暴力的离线做法：
比如上面的数列，我们设第一次询问为
1~4，第二次询问为2~5。那么我们先暴力做出1~4的结果为28，并记录每个数字出现的次数（离散化）。然后做3~5，在这里我们左端点移动两格；在第一格移动的时候，去掉一个1，那么1的数量从3变为2，即 \(28-3^3+2^3=9\) ；然后移动第二格的时候，又去掉一个1，那么1的数量从2变为1，即 \(9-2^3+1^3=2\) ；最后右端点往右移动一格，即多了一个3，那么就是 \(2-1^3+2^3=9\) ，这就是3~5的答案了。我们来算下时间复杂度吧，一共有
Q个询问，每个询问我们左右端点最多移动N次左右，所以时间复杂度差不多就是 \(O(NQ)\) ，其中N和Q都为 \(10^5\) 。这肯定要超时的。但为什么我还要介绍这个暴力的做法呢？
因为下面的正解就是建立在这样的暴力的基础上的。
我们将这个数列分段——每段长度为 \(\sqrt{N}\) （当然最后一段长度可能比这个小），一共 \(\sqrt{N}\) 段。
然后我们所有询问分组——所有左端点在同一段的询问分为一组。
接下去我们对每一组的询问进行排序——按右端点正序排序。
我们现在就可以用之间讲的暴力的做法来做这个题目了。
也许有些人会感到奇怪，为什么这么一弄之后就可以了呢？好，让我们再分析一下分段之后的暴力时间复杂度：
首先对于每一组询问来说，左端点都在同一段内，而一段的长度不超过 \(\sqrt{N}\) ，所以对于左端点的询问时间复杂度为 \(O(Q\sqrt{N})\) 。
其次对于每一组询问来说，右端点是递增的，所以不管有多少询问，右端点的总步数肯定是在
N以内，然后最多有 \(\sqrt{N}\) 组，那么右端点的询问时间复杂度为 \(O(N\sqrt{N})\) 。两者一结合，时间复杂度就是 \(O((N + Q)\sqrt{N})\) 。非常巧妙有木有？这样一分段就将一个 \(O(NQ)\) 的时间复杂度简化到了 \(O((N + Q)\sqrt{N})\) 了。
Standard Code
C++