题解

题解 ATabc334F Christmas Present 2

0 条评论 OI 题解 无标签 hycqwq
小蒟蒻想不出 $O(n)$ 的解法，来交一发二维 dp 加优化的题解。Problem圣诞老人要按顺序给 $n$ 个人送礼物，每个人（包括它自己）家都有一个坐标，而圣诞老人手上最多只能拿 $k$ 个礼物（这就意味着他可能要在送完某些人之后回家补充礼物），求他给所有人送完礼物再回到自己家所需要走的最短距离。Solution考虑 $dp_{i, j}$ 表示当前已经送完了前 $i$ 个人的礼物，（...

题解 CF1900D Small GCD

1 条评论 OI 题解 无标签 hycqwq
赛时没做出来。第二天把题告诉同机房大佬，想了一天说不会 /ch。后面看了官方题解，同时感谢这位佬 /bx。Solution与官方题解相似。定义：$m = \max\limits_{j = 1}^n a_j$。$cg_i$ 表示对于任意 $1 \le x < y < z \le n$，$f(a_x, a_y, a_z) = i$ 的 $(x, y, z)$ 个数；$cm_i$ 表示...

题解 CF1840D Wooden Toy Festival

0 条评论 OI 题解 无标签 hycqwq
Problem给定 $n$ 个数 $a_1, a_2, a_3, \cdots, a_n$，自选 $3$ 个数 $x, y, z$ 使$$\max\limits_{i = 1}^{n} \{\min\{|a_i - x|, |a_i - y|, |a_i - z|\}\}$$最小。求这个最小值。Solution考虑将 $a$ 分为 $3$ 个区间，使区间中最大数与最小数之差不超过 $m$，利...

题解 CF1840C Ski Resort

0 条评论 OI 题解 无标签 hycqwq
Problem给定一个序列 $a$，问在其中有多少个连续的长度不小于 $k$ 且所有数不大于 $q$ 的子序列。Solution读入时统计在 $a_i$ 和 $a_i$ 前面有多少个不大于 $q$ 的数，设其为 $d_i$，于是以 $a_i$ 结尾的复合条件的子序列个数为 $\max\{0, d_i - k + 1\}$。累加即可。Code#include <iostream> ...

题解 ATpast202004E 順列

0 条评论 OI 题解 无标签 hycqwq
Solution按题意模拟即可。但是一个坑点是，答案加 $1$。还有，计算过程中，$a_i$ 的值不会改变，要另开变量存值。Code#include <iostream> #include <algorithm> #include <cstdio> #include <cstdlib> #include <ctime> #inclu...

题解 UVA11661 Burger Time?

0 条评论 OI 题解 无标签 hycqwq
Problem在一条路上，有饭店也有药店，一个位置可以兼而有之也可以一个都没有。现在的问题是：距离最近的一个饭店和一个药店的距离是多少？Solution首先，如果有一个地方两种店都有，那么答案为 $0$。其次，每次输入时记录一下上一个饭店和药店的位置，每一次位置更新时算一下现在前面的饭店和药店之间的距离，然后取最小值即可。Code#include <iostream> #incl...

题解 UVA10013 Super long sums

0 条评论 OI 题解 无标签 hycqwq
Problem逐位同时输入两个 $M$ 位的数，算出它们的和。多组数据。什么是逐位同时输入呢？就是一起输入两个数的第 $i$ 位。要全部输入之后把两个数拼起来。Solution逐位读入到两个字符串中，然后加起来即可。数据范围大，需要高精度。Code#include <iostream> #include <algorithm> #include <cstdio&...

题解 LGP9390 金盏花

0 条评论 OI 题解 无标签 hycqwq
这是一道数学题。Solution设 $Z$ 去掉后六位之后为 $Z_1$，后六位为 $Z_2$。特别地，$100001 \le Z_1 \le 999998$，如果超出范围则取边界值。接下来分类讨论：当 $Z_2 < Y$ 时，最接近 $Z$ 的 $X$ 只可能为 $Z_1 \times 10^6 + Y$ 或 $(Z_1 - 1) \times 10^6 + Y$；当 $Z_2 &g...

题解 LGP9253 [PA 2022] Ornitolog 2

0 条评论 OI 题解 无标签 hycqwq
Problem给定一个序列，问最少要改几个数才能使该序列变为一大一小交错的"波浪形"。Conditions"波浪形"有两种可能：Condition 11 3 5 \ / \ / ... 2 4即：第一个数是大数。那么如果发现了一个不符合规律的数，如果应该是大数则设为 $+\infty$，否则（即应该是小数时）则设为 $-\infty$。Condition 2 2 4 ...

题解 LGP9254 [PA 2022] Liczenie punktów

0 条评论 OI 题解 无标签 hycqwq
Problem给出一个字符串，把它平均分成 $10$ 个部分，问有几个部分全部都是 T。Solution模拟有什么好说的。枚举每个部分，看看是否都是 T 即可。Code#include <iostream> #include <algorithm> #include <cstdio> #include <cstdlib> #include &l...