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

假如 个蚊子的位置都不一样的话，维护区间最大值。因为每个位置只会被访问一遍，所以复杂度还是 。当遇到这个区间的最大值小于要拍死的体型最小值时，就退出，不然递归到叶子节点。现在因为 个蚊子的位置可能重叠，那么其实我们可以排个序拍扁序列，重新排列一下位置，记录下来即可。 #include<iostream> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; const int maxn=1e5+5; int ml[maxn],mr[maxn],...

楼上已经提到了字符串同构，我这里也有个好玩的解法。就是对原始串求哈希值，然后对这串字符串直接滚动，可以知道求解所有字符串的同构字符串的哈希值的复杂度为 。 为字符串长度。其中因为存在对大数进行存储的map,总的求所有字符串归属集合的复杂度为 。当然你也可以弄个小点的模数，然后限定在数组可达的范围内就可以不需要带 了。具体做法先预处理出 的模数的累乘，然后在求滚动哈希值时，考虑去掉当前所在字符的影响，然后整体乘模数，再在后面加上当前字符即可。具体可以自己理解下求哈希的原理。至于后面的复杂度就是 的了。记得多组数据得初始化彻底，不然泪两行。 #include<iostream> ...

可在线版题解 既然有离线的树状数组版本（时间空间非常优秀）题解，那怎么少的了可在线的主席树版本呢（时间空间不是很优秀）。 前置芝士 序，离散化，主席树 思路 1.像这种对某个子树进行查询的操作，并且多组查询，很明显需要将整棵树拍扁（就是求 序），这样我们就可以将子树化为一个连续的区间进行维护。2.题目要求子树内距离该子树的根 的距离大于 的距离和，我们可以先求出所有点到根 的距离，这样一棵子树内某个点 距离该子树根 的距离就一目了然了，就是。然后我们求出子树内满足 即可。但是这每次询问枚举一整棵子树复杂度高达 ,非常不合理，我们需要维护子树。3.其实也很明显，维护一个子树内的每个...

题意 可以对 条 字符串进行任意排序，排好序后的代价为从前往后每次加入新 串后多出 位置数的平方的累加。 解法 由于数据量非常小（ ,很明显再告诉你用状压来做），可以采用状态压缩 来解。用状压维护集合，同时提前预处理出每个集合对应的所有 串或操作之后的 串。预处理之后开始枚举子集，将子集（以下称为原子集）从另一个子集（以下称为旧子集）的答案继承过来（旧子集集合内与原子集的区别为后者比前者多且仅多一个元素），继承过来的答案需要加上原子集比旧子集 串多出个数的平方，取全部继承过来答案的最小值即可，最后输出全集答案。复杂度 。 为 串的长度。 #include<iostre...

学过离散数学的都应该知道这题怎么做，然后我用的是矩阵快速幂，复杂度 ，就算是遇到 值很大的情况下也可以解。 #include<iostream> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; const int maxn=40; int n,k; struct node{ ll f[maxn][maxn]; inline node operator*(const node&x)const{ node...

思路 题目要求区间 的的所有子集的与的和。让我们来想想与有什么特殊的性质。数据给出 不超过 ，同时作为位运算的与，我们可以看看每个数的二进制的每一位有什么用。我们知道，不同数互与操作时，二进制下每一位是互不干扰的，这就给我们一个思路了。我们可以把所有区间拆成 个区间，分别代表二进制下不同位的区间。那这和问题要问的有什么关系呢？其实很容易发现，拆开区间后，我们一个区间子集的所有与操作和加起来其实就是这32个区间的与的和加起来。现在这 个区间分别代表的就是每一位的区间，这样计算大大简化。那么题目要求的就是 。解释一下这式子什么意思，首先累加 个位的区间的答案（刚才说过的），接着考虑对于...

如果题目不取模的话，就是一道裸的线段树区间求积。但现在加了取模的话，其实就是第2种操作的时候乘上 的逆元即可。逆元费马小定理就可以。 #include<iostream> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; const int maxn=1e6+5; const int mod=1e9+7; int n,m; ll a[maxn]; struct node{ int l,r; ll w; }t[maxn<&...

一个数的最小约数肯定是1，最大约数就是它自己。 那么要求最小约数的和加最大约数的和，可以发现最小约数和为n(是n1)。最大约数和便是1+...+n(从1加到n),采用等差公式直接求得n(n+1)/2,两者相加便可以了。记得开long long,不然数据会溢出。 #include<iostream> #define ll long long using namespace std; int main() { ll n; cin>>n; cout<<(ll)(n+n*(n+1)/2)<<endl; }

很明显，n最大100，floyd算法可以胜任o(Cn^3)复杂度,c是高精度的系数。当然用堆优化的迪克特斯拉或者spfa都可以秒了此题。显然我懒（不是）。​具体用到有高精+高精，高精*单精，高精比较高精； ​#include<iostream> #include<cstdio> #define rep(i,a,b) for(int i=a;i<=b;i++) #define rap(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int maxn=105,mod=1e5; int pow2[50...

请问测试点二为什么这么诡异，老是过不了😭😭😭😭下面是我的代码。 简单来说就是先把上升的子序列存起来，看能不能两个子序列连接。 或者直接判定可否加一。😭😭 #include<cstdio> #include<iostream> #include<algorithm> #define ll long long #define db puts("here!") #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=1e5+5; ...