AcWing第153场周赛题解

type

status

date

slug

summary

📝 主旨内容

叠砖块

叠砖块，第一层放一块砖，第二层放两块砖，第三层放三块砖，以此类推。

请你计算，如果要叠 n 层，则一共需要用到多少块砖。

输入格式

一个整数 n。

输出格式

一个整数，表示需要用到的砖块总数量。

数据范围

前 3 个测试点满足 1≤n≤10。

所有测试点满足 1≤n≤100。

输入样例：

输出样例：

题解：

💡

1+2+3+……+n 等差数列求和公式秒了

区间分组

给定 n 个整数闭区间 [l1,r1],[l2,r2],…,[ln,rn]。

请你判断能否将这 n 个区间分成两组，并使得两个组都满足：组内区间两两不重叠。

注意：

可以存在空组。

[1,2] 和 [2,3] 虽然只有一个公共点，但也算作重叠。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含两个整数 li,ri。

输出格式

如果可以顺利分组，则输出 YES，否则输出 NO。

数据范围

前 6 个测试点满足 1≤n≤5。

所有测试点满足 1≤n≤2×10^5，0≤li<ri≤10^9。

题解：

💡

简单的贪心题，从模板题改来的。按照区间左端点排序，维护两个组的区间右端点，如果区间无法纳入两个组中的任何一个就是非法的

改变数值

给定一个整数 x，初始时 x 等于 0。

有 n 个改变数值的能力，其中第 i 个能力为：将当前的 x 值增大或减少 ai。

激活第 i 个能力所需要花费的代价为 bi。

每个能力激活后均可以无限次使用。

我们的目标是通过激活一些能力，令 x𝑥 有能力变为任意整数（变化过程中可能会涉及到一些中间数）。

请你判断，该目标是否有可能实现，如果能，请你计算激活能力所需花费的最小总代价。

注意：整数分为三个部分，即正整数、零与负整数。

输入格式

第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

第三行包含 n 个整数 b1,b2,…,bn。

输出格式

如果有可能实现目标，则输出激活能力所需花费的最小总代价。

否则，输出 -1。

数据范围

前 6 个测试点满足 1≤n≤10。

所有测试点满足 1≤n≤300，1≤ai≤10^9，1≤bi≤10^5。

输入样例1：

输出样例1：

输入样例2：

输出样例2：

题解：

💡

想到了需要让两个数或者n个数凑出1来，那么这样所有数都可以凑出来了，当然凑出来-1也行。就是不知道怎么凑了，背包模型也看出来了，每个数都是取和不取，求代价最小，但是背包的体积会特别大，没想到一个裴蜀定理就搞定了

💡

转移方程会有两个方向，从左到右和从右到左，即从什么状态能转移到当前状态，或者我能更新哪些状态，这道题是后者，否则就需要枚举当前数和哪些数的最大公约数能得到特定值，相反直接从特定值与当前数取最大公约数就可以得到能更新的状态

🤗 总结归纳

瞬秒两题然后坐牢

第二题看题解还以为数据有问题，就是在维护两个组的最右端点时，我是取max的，但是其他人都是直接赋值？？？

仔细一想，当前区间左端点都大于组的最右端点了，那么区间的右端点就一定会大于最右端点，取不取max都和直接赋值是一样的

📝 主旨内容

叠砖块

输入格式

输出格式

数据范围

输入样例：

输出样例：

题解：

区间分组

输入格式

输出格式

数据范围

题解：

改变数值

输入格式

输出格式

数据范围

输入样例1：

输出样例1：

输入样例2：

输出样例2：

题解：

🤗 总结归纳

📎 参考文章