Codeforces Round 816 (Div. 2)

A.Crossmarket

算法本质

思维

题目大意

有一个n*m的地图，小蓝在(1,1)目标(n,m)，小红在(n,1)目标(1,m)，每走一步花费一秒。

小红走过的路径会留下空间之力，小蓝在任意具备空间之力的格子，可以花费一秒的代价，去到任意具备空间之力的格子。

小红先走，到终点后小蓝再出发。输出最小化其所用时间。

思路推演

小红所用时间固定n+m-2，对于小蓝，有3种走法：

• 直接走，不使用空间之力
• 使用空间之力在y轴方向传送
• 使用空间之力在x轴方向传送

三种情况都计算，然后取小输出即可。

B.Beautiful Array

算法本质

思维

题目大意

对于长度为n的数组，定义魅力值为：

• 元素/k之和。（除法取下限）

现在需要你构造一个长度为n、魅力值为b、元素和为s的数组a[]。（若不可能输出-1）

思路推演

显然，若保证数组魅力值为b，其元素和范围：[bk, bk+n*(k-1)]

将bk随便放到某个下标去，然后将s-bk平均分配到n个元素内即可。

C.Monoblock

算法本质

思维

题目大意

给定长度n的数组a[]。

定义a[l, r]的魅力值：

• 可以拆分数组的连续相同数字的最小块数

不懂的看一下题目中的样例解释

定义a[]的帅气值：

• 所有区间魅力值之和

接下来有q次询问，每次询问会改变某元素的值（之后永久有效），需要输出当前a[]的帅气值。

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。