zqy1018_

题解

/ 注册

全部文章 / 题解（共31篇）

2021 联想杯 E

E 题意略。本题先枚举是先去第一条线还是第二条线，再三分套三分也能过。但究竟为啥能呢？我并没有太看出来这个问题具有什么凸性质 ... #include <bits/stdc++.h> #define INF 2000000000 #define MOD 1000000007 #def...

2021-06-13

3 547

2020 ICPC 济南 F

F Gcd Product 题意很短。主要介绍一种和 std 不同、比 std 思维量更低一些的做法。定义，即是三元组的集合。定义，即两个三元组集合的积为另一个三元组的集合。那么：通过打表可以发现，具有积性。即对于互质的有。且当为质数的幂次时，容易直接求出。于是只需要按...

2021-05-22

0 602

CF803F Coprime Subsequences

题意给定一正整数序列，问有多少个非空子序列使得其中所有数的为 1。题解容斥，设为为的倍数，的非空子序列个数。那么如果中有个数是的倍数那么。设为恰为的非空子序列个数。那么。时间复杂度，其中。 #include <bits/stdc++....

2021-02-25

0 787

偶数

D 偶数手算几下会发现：实际上不用处理整个串，只需要关注一半的串即可。并且串的构成遵循一定规律。我们先用 KMP 算出一半的串（记为）的 border，记其长度为。记的长度为。如果这是个周期串就很好办，下面考虑非周期串的情况。考虑把扩展到足够长的串切分成若干段，如下所示。即：...

2020-10-24

7 640

牛牛的凑数游戏

给一个 T3 的不用主席树的简易做法。建线段树，对每个点维护一个值和一个有序 pair 列表，表示这个点对应的区间做完合并后，可以覆盖的区间为，且剩余的待合并的数为。这个列表的意义是：如果增大到某个不小于的，那么新的可覆盖区间会变成，但这时仍然有。对于的定义类似：如果...

2020-10-21

0 901

牛客挑战赛44 F

F 题意第一部分：给定，其中，求。第二部分：多组询问，求，其中是斐波那契数列。题解第一部分：矩阵快速幂，记录这七个值的转移即可。转移矩阵可以通过简单计算得出。第二部分：利用即可。 #include <bits/stdc++.h> #define MOD 9...

2020-10-16

6 611

牛客练习赛 68 C

C 牛牛的无向图题意：给定一个无向图，定义表示在无向图中点能到达点的所有路径中权值最小的路径的权值。多次询问，每次给出，问有多少无序点对的不超过。由定义，等于最小瓶颈生成树上，到路径上权值最大的边。而最小生成树是最小瓶颈生成树。所以问题就转化为：对于某个，有多少最小...

2020-08-28

0 674

牛客练习赛 68 A

A 牛牛的mex 题意：给一个到的长为的排列，多次询问，每次给出，问。做一个前缀最小值和后缀最小值，每次询问比一下即可。 #include <bits/stdc++.h> using namespace std; int read(){ int f =...

2020-08-28

3 638

牛客编程巅峰赛S1第12场 - 王者简要题解

A 认为树以为根。显然，牛牛和路由器均以最优策略移动时，两者会在某个叶子处相遇，且牛牛会从一直往下，追到这个叶子。那么我们就要求所有可能到达的叶子中最深的那个。我们写下从到，一路向上经过的节点序列。设其长度为。那么路由器在不会被抓住的情况下，向上走最高能到达的点就是这个序列的第 ...

2020-08-15

3 640

牛客练习赛67 E

E 题目大意给定个点，第个点有权值。如果对于有不为，那么间有无向边，边权为。问从到的最短路。题解想了一个很憨的做法：依次考虑每一个位，对当前位建立一个新点，设为。遍历所有点，如果点满足这一位上为，那么连一条从到的边，边权为这一位对应的二进制数；...

2020-08-14

2 775