TheOnlyMan

分类

题解(10)

/ 注册

全部文章（共10篇）

题解 | #小AA的数列#

链接：小AA的数列题意：求长度在区间内的偶数长度区间异或和之和。题解：显然区间异或和的和可以按为拆开分开计算，最后在累加上去（因为每一位异或时互不干扰）。现在考虑怎么把范围限制在中。可以发现，我们容易求出大于某个数的长度的答案，所以答案就是 (数位计算区间答案的思想)。递推时注意 ...

C++ 动态规划位运算

2021-09-15

2 553

题解 | #弩蚊怒夏#

假如个蚊子的位置都不一样的话，维护区间最大值。因为每个位置只会被访问一遍，所以复杂度还是。当遇到这个区间的最大值小于要拍死的体型最小值时，就退出，不然递归到叶子节点。现在因为个蚊子的位置可能重叠，那么其实我们可以排个序拍扁序列，重新排列一下位置，记录下来即可。 #include<io...

线段树

2021-09-07

6 563

题解 | #团结就是力量#

楼上已经提到了字符串同构，我这里也有个好玩的解法。就是对原始串求哈希值，然后对这串字符串直接滚动，可以知道求解所有字符串的同构字符串的哈希值的复杂度为。为字符串长度。其中因为存在对大数进行存储的map,总的求所有字符串归属集合的复杂度为。当然你也可以弄个小点的模数，然后限定在数组可达的范围内就...

哈希 tarjan

2021-09-01

0 681

题解 | #树的距离#

可在线版题解既然有离线的树状数组版本（时间空间非常优秀）题解，那怎么少的了可在线的主席树版本呢（时间空间不是很优秀）。前置芝士序，离散化，主席树思路 1.像这种对某个子树进行查询的操作，并且多组查询，很明显需要将整棵树拍扁（就是求序），这样我们就可以将子树化为一个连续的区间进行维护。2....

主席树 dfs序离散化

2021-08-29

1 801

题解 | #牛牛的计算机内存#

题意可以对条字符串进行任意排序，排好序后的代价为从前往后每次加入新串后多出位置数的平方的累加。解法由于数据量非常小（ ,很明显再告诉你用状压来做），可以采用状态压缩来解。用状压维护集合，同时提前预处理出每个集合对应的所有串或操作之后的串。预处理之后开始枚举子集，将...

状压 dp 进制

2021-08-25

2 713

题解 | #路径数量#

学过离散数学的都应该知道这题怎么做，然后我用的是矩阵快速幂，复杂度，就算是遇到值很大的情况下也可以解。 #include<iostream> #include<algorithm> #include<cstring> using namespace std...

最短路

2021-08-06

1 632

题解 | #Sum#

思路题目要求区间的的所有子集的与的和。让我们来想想与有什么特殊的性质。数据给出不超过，同时作为位运算的与，我们可以看看每个数的二进制的每一位有什么用。我们知道，不同数互与操作时，二进制下每一位是互不干扰的，这就给我们一个思路了。我们可以把所有区间拆成个区间，分别代表二进制下不同位的...

2021-08-05

2 554

水题加一

如果题目不取模的话，就是一道裸的线段树区间求积。但现在加了取模的话，其实就是第2种操作的时候乘上的逆元即可。逆元费马小定理就可以。 #include<iostream> #include<algorithm> #include<cstring> using ...

2021-07-23

2 644

A题

一个数的最小约数肯定是1，最大约数就是它自己。那么要求最小约数的和加最大约数的和，可以发现最小约数和为n(是n1)。最大约数和便是1+...+n(从1加到n),采用等差公式直接求得n(n+1)/2,两者相加便可以了。记得开long long,不然数据会溢出。 #include<iostrea...

2021-02-26

2 573

单源最短路

很明显，n最大100，floyd算法可以胜任o(Cn^3)复杂度,c是高精度的系数。当然用堆优化的迪克特斯拉或者spfa都可以秒了此题。显然我懒（不是）。具体用到有高精+高精，高精*单精，高精比较高精； #include<iostream> #include<cstdio>...

最短路 floyd 高精度

2021-02-24

1 795