iOS

P8112 [Cnoi2021] 符文破译题解

题目传送门思路先看数据范围，我们发现两个字符串的长度最大会达到 (5 times 10^7)。这立刻打消了我用暴力的想法。于是，我选择了用 KMP 模式匹配，这一个能够在线性时间内判定字符串 (A) 是否是字符串 (B) 的字串，并求出字符串 (A) 在字符串 (B) 中各次出现的位置。如果不清楚 KMP 算法是如何实现的，可以看看这个或这个。我们知道一个字符串 (A) 每次往后成功匹

查看详情

UVA10539

根据题意，可以很容易地发现，题目所要求的数都可以用形如 $ p^x$ 的式子表示（其中 $ p $ 为质数， (x ge 2)），即分解成只含同一个质因子的式子。这提示我们使用构造的思想。因为 (n) 最大为 $ 10 ^ {12}$，所以最大的 (sqrt n) 也不会超过 (10^6)。考虑使用线性筛求出 (10^6) 以内的质数，再依次枚举每个质数 (p) 的幂：(p^2)，(p^3)

查看详情

AT_codefestival_2016_final_b

根据题意，很容易得知要使得它们的最大值最小，就要从最小的 (1) 开始用。转化一下题意，不难发现，我们只需求出最小的 (k)，使得 [ sum_{i=1}^k i ge n ]于是思路便产生了：对 (1)，(2)，(3)，⋯(k) 求和，直到上述式子成立。可以很容易地看出来一个规律： [( sum_{i=1}^k i ) - n<k+1 ]根据这个规律，我们知道多出来的那一部分就存在于 (

查看详情

比赛日程问题

问题描述： 1.设有n（n为任意值）个选手进行循环赛，手工设计一个满足以下要求的比赛日程表： (1) 每个选手必须与其他n-1个选手各赛一次； (2) 每个选手一天只能赛一次； (3) 循环赛一共进行n-1天。算法设计：假设有N名选手参赛，不妨构造一个N×N的矩阵。在矩阵第一行填充1，2,…,N，第一列填充1，2,…,N。矩阵定义：把矩阵的第一列作为参赛选手的编号，第2~N列作为某一参赛选手的

查看详情

UVA640

根据题意，首先可以一眼看出一个重要的规律：对于任意的正整数 (n)，都有 [d(n)>n ]根据这个规律，我们很容易得知一个性质，当枚举到一个数 (k) 时，如果已经枚举过的数 (i(i<k)) 没有一个能满足 (d(i)=k)，那么 (k) 是“Self-Number”。这与质数筛的条件十分相似，因此考虑使用类似欧拉筛的思路实现。实现过程比较简单，具体地，当枚举到一个正整数 (

查看详情

UVA10000

这道题的题意十分简单：求从 (k) 出发到每个点的最长路。看到最长路这个词，可能一时半会儿没有思路，因为我们平时学习的都是最短路算法。回忆小学学过的一句话“一个负数的绝对值越大，那么它本身的值就越小”，这提示我们将求最长路设法转化为求最短路。于是便很容易得出转化思路：先对每条边的长度取相反数，再对整个图求最短路，最后再将答案取相反数。可以证明，这样做能确保最长路的正确性。接下来看求最短路的算

查看详情

CF371B

这题十分简单，化简一下题意为：一次操作定义为对一个数乘 (frac{1}{2})，(frac{1}{3}) 或 (frac{1}{5})，求使用最少的操作次数，使得两个数 (a) 和 (b) 相等。不难发现，每一次都是倍数变换，所以最终的 (a) 和 (b) 是 (gcd(a,b))。当然，由于题目的限制（即指定的数），所以我们要分别对 (dfrac{a}{gcd(a,b)}) 和 (dfra

查看详情

LG8443

JROI 果然很良心，签到题终于可以用来签到了。这道题一看数据范围 $1 le l le r le 10^{18} $，就能知道肯定是数学题。遇到数学题不用急，我们一步步分析。回忆小学学习的关于互质的一条性质：相邻的两个正整数互质。形式化地说，若 (a) 和 (b) 为两个相邻的正整数，则 (gcd(a,b)=1)。然后，我们又不难想到，一段连续的正整数，设它们的长度为 (len)，若 (le

查看详情

LG8444

这道题的难度不错，出题人很良心。相信大家都能看出来是贪心。题意就不用说了。可能有人会认为是背包，但题目要的是物品越多越好，而不是价值越大越好，所以优先选择价格小的物品，这就是贪心思想了。这题的思路也十分简单。首先将所有的 (a_i) 从小到大排序，找出不超过 (w) 的最大的 (a_i)，因为它的价格越大，后面能换来的东西就越多。然后从 (a_1) 开始累加，直到总价钱超过刚刚所选的物品的价钱

查看详情

LG8459

这题一看到要判断 (a times b = c) 是否成立，立马想到了用 FFT/NTT。但看到数据范围 (a,b le 10^n)，(c le 10^{2n})，(n le 1 times 10^6 + 50)，再加上时限很紧（(1) 秒），因此 (O(Tn log n)) 的 FFT/NTT 会超时。既然暴力求解不行，我们不妨从数学的角度思考这个问题。还记得关于模运算的性质吗？这题用到了两

查看详情

LG8448

题目要求了 (z) 为奇素数，而为了进行更多次的有效操作，很容易想到直接让 (z=3)。这样做，对于原题中 (1 le n le 10^{18})，最大的 (sqrt[3]{n}) 不会超过 (10^6)，完全可以在 (O(n)) 的时间复杂度内解决。于是思路便产生了：(y) 从 (2) 开始枚举，判断此时的 (n) 是否为 (y^3) 的倍数，是则不断用 (y^3) 除 (n)，统计次数，直到

查看详情

LG8466

题意十分简单：找出你的手牌中是否有炸弹（有炸弹定义为有大小王各一张或有四张数码相同的牌）。这题因为手牌已经有序，且牌的种类很少，所以直接依次判断是否存在王炸或者四个连续的数码即可。代码见下：还是菜。

查看详情

SP28604

这题一看到 (1 le T le 10^5)，(1 le n le 10^{11})，就知道暴力是肯定不行的了。但是看到题目限制“因子个数为奇数”，发现是一个突破口。众所周知，一个正整数 (n) 的因子总是成对出现的。举个例子，若有正整数 (a) 和 (b) 满足 (a times b=n)，则 (a) 和 (b) 都是 (n) 的因数。大部分情况下，(a) 和 (b) 是不相等的。但有一种特

查看详情

CF489A

这题要求用不超过 (n) 次的交换将 (n) 个整数从小到大排序。很显然，在最坏的情况下，为了满足条件，我们需要使每个数一步到位，即只与要到达的那个位置上的的数交换一次。那么我们很容易想到用选择排序了。先回顾一下选择排序，核心代码如下：我们很容易发现：当到达第 (i) 个位置时，前面的 (i-1) 个数已经有序了，因此我们只需求出 $ min(a_{i+1},a_{i+2},cdots,a_

查看详情

CF1712B

题意构造一个 (n) 的排列 (p)，使得 $ sumlimits_{i=1}^n operatorname{lcm}(i,p_i)$ 最大。分析首先要知道，(operatorname{lcm}) 是求两数的最小公倍数。因此，我们把思考方向引向公约数与公倍数。先回顾一下这条等式，对于任意的正整数 (m) 和 (n) 都有 [gcd(m,n) times operatorname{lcm}(m

查看详情

CF1712A

看完题目，很容易得知要使 $ sumlimits_{i=1}^k p_i$ 最小，且 (p_i) 是 (n) 的一个排列，可以知道最终的答案为 (sumlimits_{i=1}^k i)。现在我们考虑如何将原序列转化成答案序列。得知答案后，我们要做的就是将所有的 (p_i le k) 移到序列的前 (k) 位中。暴力枚举序列的前 (k) 位，判断该位置上是否满足 (p_i le k)，是则说明满

查看详情

LG8480

这题各个神仙都用了 (O(n)) 的算法，只有我用了 (O(2^n)) 的暴搜。分析既然要使极差最大，很容易想到要使最大数尽可能大，最小数尽可能地小。那么每一次操作就有两种选择：处理最大数或最小数。在本题中操作次数 (m le 10)，因此可以每次分两种情况，并分别搜索下去。对于每次操作，判断哪种运算能使结果最小或最大，赋值即可。时间复杂度 (O(n+2^m))，代码如下：

查看详情

LG8481

题意这题花了我好长时间才看明白。一道二分查找题。每次查找一个数 (t)（保证一定能找到），每次 (operatorname{mid}) 可以取 (leftlfloordfrac{(l+r)}{2}rightrfloor) 或 (leftlfloordfrac{(l+r+1)}{2}rightrfloor)，求最少需要多少次可以定位到 (t) 的位置。分析看到查询次数 (q le 100)，

查看详情

LG8837

题目传送门分析既然要使得购买到商品的人最多，很容易想到要用贪心的策略。对于拥有的钱越少的人，就应当给 ta 匹配越便宜的商品。可以证明这种方案能使人数最大化。接下来看具体的方法。首先将 (w_i) 和 (c_i) 从小到大排序（(w_i) 和 (c_i) 的含义如题目中所述），接着，将 (w_1) 与 (c_1) 比较，看是否能买下，如果能买则买，不能买则将 (c_1) 推给下一个人。以此类

查看详情

CF1760A

题意 (T) 组数据，每组数据给 (3) 个数，要求选出既不是最大值也不是最小值的那个数。做法这题由于十分简单，因此各种做法均可通过。最朴素的做法为比较出最大值和最小值，然后对三个数依次判断，找出符合条件的那个数即可。 Code 还是菜。

查看详情

LG8563

题目传送门貌似各路神仙都用线段树、平衡树秒了这题，蒟蒻在此献上一篇暴力的题解。分析看到数据范围 $ 1 le n,q le 2 times 10^5$，而且还要求区间最大乘积 (M)，很容易想到用线段树。但当我们看完题目，看到当 (M) 大于 (2^{30}) 时直接输出一个字符串，便发现很多情况下是无解的。在本题中，由于保证了所有的 (a_i)（包括修改后）满足 $ leftvert a

查看详情

CF1760B

题意 (T) 组数据，每次给定一个只含小写字母的字符串，求要拼出这个句子至少需要长度为多少的字母表。定义长度为 (x) 的字母表含有 (26) 字母表上的前 (x) 个字母。做法转化一下题目，很容易发现题目本质上就是要求字符串中最大的字母在 (26) 字母表中的位置。其它不是最大的字母也能出现在上面。因此实现就十分简单了。 Code 还是菜。

查看详情

CF1760C

题意 (T) 组数据，每组数据给定一个长度为 (n) 的序列 (s)。求出每个数与最大值的差（最大值本身除外），以及最大值和次大值的差（最大值的位置），按照原来的顺序输出。做法模拟题，十分简单，只需对原序列求最大值和次大值即可，然后再按位置输出。 Code 具体实现细节见代码。还是菜。

查看详情

LG8891

题意给定一个长度为 (n) 的序列 (a)，下标从 (1) 开始，(m) 次操作，每次操作给定 (x) 和 (y)，将所有满足 (i oplus x = 0) 的 (a_i) 减 (y)，(m) 次操作后输出序列 (a)。思路要使得 (i oplus x = 0)，即要使这两个数的二进制位全部都一样（根据异或的规则），则这两个数相等。所以题意转化为每次给定 (x) 和 (y)，将 (a_x)

查看详情

LG8928

题意给定 (n,m,p)，求 [sum_{i=1}^n sum_{j=1}^m (i times j bmod p) ]分析看到 (1 le n,m le 10^{12})，知道 (O(nm)) 的暴力算法行不通。但 (1 le p le 10^3)，范围很小，是本题的突破口。那怎么利用这个特点呢？这里需要用到一条同余的性质，即 [(i times j) bmod p = (i bmod p

查看详情

LG9024

一道简单的签到题。每两个栅栏之间就相当于构成了一个梯形，两边的栅栏分别为上底和下底，木板的宽度为高，因此按照梯形的面积计算公式计算每块木板的面积，再计算总和即可。代码如下：还是菜。

查看详情

LG9022

一道简单的签到题。按照题意模拟即可。循环输入，对其进行分类讨论，最后输出即可。实现上有一些细节，具体见代码。还是菜。

查看详情

AT_abc188_d

看到这题，第一反应是用线段树。但本题数据 (1 le a_i le b_i le 10^9)，时间、空间复杂度均无法接受，于是改变思考方向。维护区间修改的另一种方法是差分。但是由于区间长度很长，就不能对整个差分数组进行计算。取而代之的有一种方法，即将所有的有差分值的点记录下来，按其时间先后顺序进行排序，最后再依次枚举每一个点，计算当前每天应交的钱，再计算当前区间的长度，即可求出每一个区间的应交的

查看详情

AT_abc179_d

题意给定 (n) 和 (k) 个区间，并且保证 $ k le 10$ 且互不相交。可以进行任意次操作，每次可以选择一个整数 (j)，(j) 要满足在其中一个给定的区间上，从当前位置向右移动 (j) 的距离。求 (1) 到 (n) 的方案数。思路提供一种数据结构的做法。依次枚举 (1) 到 (n) 的每个点，对于每个点，先查询其方案数（已知），然后枚举每个区间，确定从当前点出发能跳到的区间，

查看详情

AT_abc179_e

题意定义 (f(x,m)= x bmod m)。有一个序列 (a)，满足 (a_1=1)，(a_i=f(a_{i-1}^2,m))。求 [sum_{i=1}^na_i ]思路这道题 (n) 的数据范围很大，但 (m) 最多只有 (10^5)，因此考虑以此为突破口。需要用到如下的同余性质： [(a times b) bmod m = (a bmod m times b bmod m) bm

查看详情

iOS

热门话题