看见大佬们一个个都用map，身为蒟蒻的我瑟瑟发抖，只好手打离散化虽然时间有点慢只跑了6000ms 我这里采取的是用vector进行离散化： vector<int>v; v用来储存需要离散的数 read(a[i]),v.push_back(a[i]); stable_sort(v.begin(),v.end()); 读入并排序 很关键的一步操作↓↓↓ v.erase(unique(v.begin(),v.end()),v.end()); 这里我来解释一下 unique()是C++标准库函数里面的函数，其功能是去除相邻的重复元素（只保留一个），所以使用前需要对数组进行排序（升序降序...

简单版 #include<cstdio> #include<cstring> #include<queue> using namespace std; #define rg register int #define I inline int #define V inline void #define ll long long #define db double #define B inline bool #define F1(i,a,b) for(rg i=a;i<=b;++i) #define F2(i,a,b) for(rg i=a;i>=b...

题目 POJ3764 The xor-longest Path 原题传送门 主要思路： 求出每个点到根节点（这里是树，所以直接取0）路径上所有权值xor和为d[i],则任意两点间路径xor和则为 d[x]^d[y]（至于证明，作者太懒，不想写） 接着用trie树跑出 max(d[x]^d[y]) (0<=x<n && 0<=y<n) Code #include<cstdio> #include<cstring> //#include<windows.h> using namespace std;...

题目大意： 给定一个整数 和一个表示消息的字符串 ，找到至少出现 次的 的最长子字符串。 如果存在多个解决方案，则优选最右边出现的子串（即样例 ）。 由多组数据，当 时输入结束。其中 、 。 如果没有解决方案，则输出 ；否则，输出两个整数，用空格分隔，第一个整数表示出现至少 次的子串的最大长度; 第二个整数给出了这种子串最可能的起始位置（同时要注意**题目中字串从 开始**）。 ------------------------------------------------ 分析： 啊，本蒟蒻不会后缀数组咋办啊……可不要忘了我们还有 +二分这种好东西！！ ...

什么是DLX？ 让我们看看百度百科上的解释：在 计算机科学 中, Dancing Links ,舞蹈链, 也叫 DLX, 是由 Donald Knuth 提出的数据结构，目的是快速实现他的 X算法.X算法是一种递归算法，时间复杂度不确定, 深度优先, 通过回溯寻找精确覆盖问题所有可能的解。有一些著名的精确覆盖问题，包括铺砖块，八皇后问题，数独问题。 X算法 概念 X算法用由0和1组成的矩阵A来表示精确覆盖问题，目标是选出矩阵的若干行，使得其中的1在所有列中出现且仅出现一次。（出自度娘） 实现步骤 1.如果矩阵A为空（没有任何列），则当前局部解即为问题的一个解，返回成功；否则继续。2.根据一定方...

Day -inf~0 Day -12~-10 明明知道要考试了，一看日期：哈，还有接近两周时间复习，不慌。 Day -3~-1 嗯怎么不知不觉一周就过去了，我TM还什么都没怎么复习啊（看来这次药丸）；不行，不能颓了，我要复习！ 话音未落，“pzy,来狼人杀吗？” 。。。 “肯定要啦！”（真香） Day 0 虽然没怎么复习，但这次是区上出的卷子，应该比较简单吧！（ ） 话说这大大小小的考试怎么也考了 次，可我 语文从来没上过 、英语没上过 …… 这次一定要辉煌一把（ ） Day 1 ##语文莫名有点虚语文，感觉我的阅读又要被阅卷老师***得很惨。 好不容易连蒙带猜地做完了选择题（...

前言 与 虽然都是随机算法，不过用起来是真的爽。 算法是一种高效的质数判断方法。虽然是一种不确定的质数判断法，但是在选择多种底数的情况下，正确率是可以接受的。 是一个非常玄学的方式，用于在 的期望时间复杂度内计算合数的某个非平凡因子。 事实上算法导论给出的是 ， 是 的某个最小因子，满足 与 互质。 但是这些都是期望，未必符合实际。但事实上 算法在实际环境中运行的相当不错。 注：以上摘自洛谷。 前置芝士 费马小定理 内容：若 ，则 或 证明：戳这里 二次探测定理 内容：如果 ，且，那么 证明： 是大于的质数...

位运算 1.知识 bit 是度量信息的单位，包含0和1两种状态。计算机的各种运算最后无不归结为一个个bit的变化。 符号 含义 & 与 | 或 ~ 按位取反 ^ 异或 >> 右移（算术右移，高位补符号） <&l...

Day -inf~0 Day -12~-10 明明知道要考试了，一看日期：哈，还有接近两周时间复习，不慌。 Day -3~-1 嗯怎么不知不觉一周就过去了，我TM还什么都没怎么复习啊（看来这次药丸）；不行，不能颓了，我要复习！ 话音未落，“pzy,来狼人杀吗？” 。。。 “肯定要啦！”（真香） Day 0 虽然没怎么复习，但这次是区上出的卷子，应该比较简单吧！（ \(flag\) $ \times 1 $） 话说这大大小小的考试怎么也考了 \(7\) 次，可我 \(TM\) 语文从来没上过 \(110\) 、英语没上过 \(140\) …… 这次一定要辉煌一把（ \(fl...

题目 BZOJ1053 反素数 原题传送门 题目分析 那么关于这道题，首先来了解一下这 \(4\) 个引理（大家可以自己推一推这些引理）： 引理\(1\)：\(\left[1,N\right]\) 中最大的反素数，就是 \(\left[1,N\right]\) 中约数个数最多的数中最小的一个。 引理\(2\)：\(\left[1,N\right]\) 中任何数的不同质因子不会超过 \(10\) 个，且所有质因子的指数和不超过 \(30\) 。 引理\(3\)：\(x\) 的质因子是连续的若干个最小的素数，并且指数单调递减。即： $ x = 2^{c_1} \...

积性函数 定义 积性函数是指一个定义域为正整数 $N$ 的算术函数 $f(n)$ ， 有如下性质：$f(1) = 1$ ，且 $\forall a,b \in \mathbb{N}^{+} \quad $ 且 $\quad \gcd(a,b) = 1$ ，有 $f(ab) = f(a) f(b)$。 若对于任意的 $a,b$ ， $f$ 均满足上述性质，则称此函数为完全积性函数。 积性函数举例： \(\varphi (n)\)－欧拉\(\varphi\)函数，计算与\(n\) 互质的正整数之数目 \(\mu (n)\)－默比乌斯函数，关于非平方数的质因子数目 \(\gc...

题目 Contest Hunter 3101 阶乘分解 原题传送门 题目分析 这里介绍一个本蒟蒻自己\(yy\)出来的方法。 我们发现，对于某一个单个的整数\(n\)，若\(n\)能被某一个数\(x\)整除，那么我们可以看作\(++count[x]\)、且将\(n\)变为\(n/x\)。 这时就相当有了两个\(n/x\)继续分解，就相当于缩小了问题规模！！！ Code： #include<cstdio> #include<bitset> //#include<bits/stdc++.h> using namespace std; ...

题目 POJ2689 Prime Distance 原题传送门 主要思路 刚看到这题，心想：不就筛个 \(\left[2,U\right]\) 的质数表出来就可以了吗？一看数据范围： \(1<=L< U<=2147483647\) \(\cdots\) \(Woc\)，这 \(TM\) 可以做吗？看来必须另辟蹊径了。于是就有了下面这个做法。 显而易见，一个数 \(x\) 如果不是 \(prime\) ，则在 \(\left[2,\sqrt{x}\right]\) 中必有 \(x\) 的一个质因子。 因为 \(U-L<=1000000\) ，我们可以筛...

前言 $Miller-Robbin$ 与 $Pollard Rho$ 虽然都是随机算法，不过用起来是真的爽。 $Miller Rabin$ 算法是一种高效的质数判断方法。虽然是一种不确定的质数判断法，但是在选择多种底数的情况下，正确率是可以接受的。 $Pollard Rho$ 是一个非常玄学的方式，用于在 $O(n^{1/4})$ 的期望时间复杂度内计算合数$n$的某个非平凡因子。 事实上算法导论给出的是 $O(\sqrt p)$ ， $p$ 是 $n$ 的某个最小因子，满足 $p$ 与 $\frac{n}{p}$ 互质。 但是这些都是期望，未必符合实际。但事实上 $Pollar...