GreenHatHGのBlog

一些STL知识填坑 参考：https://oi-wiki.org nth_element作用是找到选定区间内第 大的数，并将所有比它小的数与比它大的数分别置于两侧，返回它的地址。原理是未完成的快速排序，时间复杂度：期望 O(n) 123456789101112131415161718#include<iostream>#include<algorithm>using namespace std;int main(){ int a[]={3,1,5,4,2,6,8,7,9}; nth_element(a, a+5, a+9); for(int i=0;i<9;i++) cout << a[i] << " "; cout<<endl<<"输出第五大的数： "<<a[4]<<endl; //注意下标是从0开始计数的 return 0;}/*output:2 1 4 3 5 6 8 7 9输出第...

EXBSGS $a^{x} \equiv b(\bmod p)$ BSGS只能求解p为素数的情况，EXBSGS可以完美解决这个问题，其基本思路就是通过转换，然后可以运用BSGS算法来求解，最终还是基于BSGS基础 EXBSGS参考：https://www.cnblogs.com/TheRoadToTheGold/p/8478697.html https://blog.csdn.net/a_bright_ch/article/details/83513731 https://www.cnblogs.com/lajioj/p/9529255.html 求解$a^{x} \equiv b(\bmod p)$（P不一定是质数）的最小非负正整数解 先放三个同余定理 定理1： 定理2： 定理3： 求解 如果b==1，那么x=0，算法结束 若gcd(a, p) != 1，令d=gcd(a, p)，若d不能整除b，则无解，算法结束，否则继续 12例如当x=1，a=4，p=8，b=3时，代入公式有4 mod 8和3 mod 8，此时d = gcd(a, p) = 4，说明a...

BSGS BSGS(baby-step gaint-step)该算法是指类似于$a^{x} \equiv b(\bmod p$)的方程，已知a，b，p，求x的算法 原始的BSGS只能解决p为质数的情况 由费马小定理$a^{p-1} \equiv 1(\bmod p)$（a，p互质） 同时拆开上面两式得 $a^{p-1} (\bmod p)= 1(\bmod p)$ $a^{x} (\bmod p)= b(\bmod p)$ b最小取值1，而当$x=p-1$时正好为$b=1$，所以当b增大时，x须小于p-1，才能让b大于1，综合得 解x满足$0 \leq x<p$ 求解过程设$m=\lceil\sqrt{p}\rceil$（根号p向上取整），$x=Am-B(0 \leq A,B < m)$ 则由$a^{x} \equiv b(\bmod p)$有$a^{Am- B} \equiv b(\bmod p)$ 即$\frac{a^{Am}}{a^{B}}\equiv b(\bmod p)$ 即$a^{Am } \equiv b a^{B}(\bmod p)$ 我们已知的是...

学习自周志明老师的《深入理解Java虚拟机》第二版 同时参考：http://www.cnblogs.com/plxx/p/4528688.html 类的加载虚拟机把描述类的数据从Class文件加载到内存，并对数据进行校验,转换解析和初始化，最终形成可以被虚拟机直接使用的Java类型，这就是虚拟机的类加载机制 与那些在编译时需要进行连接工作的语言不同，在Java语言里面，类型的加载、连接和初始化过程都是在程序运行期间完成的，这种策略虽然会令类加载时稍微增加一些性能开销，但是会为Java应用程序提供高度的灵活性 Java里天生可以扩展的语言特性就是依赖运行期动态加载和动态连接这个特点实现的，比如 编写一个面向接口的应用程序，可以等到运行时再指定其实际的实现类 用户可以通过Java预定义的和自定义类加载器，让 一个本地的应用程序可以在运行时从网络或其他地方加载一个二进制流作为程序代码的一部 分，这种组装应用程序的方式目前已广泛应用于Java程序之中。从最基础的Applet、JSP到相 对复杂的OSGi技术 OSGi(Open Service Gateway Initiativ...

HDU1024-Max Sum Plus Plus HDU1024 解析题意在n个数中选出m组数, 每组数连续且不能相交,使得这m组的和是所有m组数中最大的。 每组数也可以叫做每一段 例如: 122 6 -1 4 -2 3 -2 3选两组数,当我们选{4,-2,3},{3}这两组数时可得到最大的和8 DP参考： https://blog.csdn.net/zuzhiang/article/details/78450380 定义二维数组dp，dp[i][j]，表示前 j 项所构成 i 子段的最大和，且必须包含着第j项，即以第j项结尾 求dp[i][j]，有两种情况: dp[i][j] = dp[i][j-1]+a[j]，把第j项融合到第 j-1 项的子段中，子段数没变 dp[i][j] = dp[i-1][t]+a[j]（i-1<= t<j）,把第 j 项作为单独的一个子段，然后找一下i-1个子段时，最大的和，然后加上a[ j ] ，字段数由i-1变成i 然后比较上面两种情况，取最大的。即 dp[i][j] = max(dp...

HDU1231最大连续子序列 HDU1231 解析（转移方程好求，但是栽在了求位置上面，后来才想起是后往前推。） 转移方程 dp[i]表示以i结尾的最大连续子序列的和 1状态转移方程：dp[i] = max(dp[i - 1] + num[i],num[i]) 记录位置 根据转移方程求最大值，这样就能找到最大连续子序列的最后一个元素，然后根据这个位置再向前找起始位置即可 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556/*2019-04-14 11:46:05124MS 1628K*/#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int MAXN = 1e5+10;const int INF = 0x3f3f3f3f;int arr[MAXN];int dp[MAXN];...

HDU1217-Arbitrage HDU12171Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Problem Description Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 British pound, 1 British pound buys 10.0 French francs, and 1 French franc buys 0.21 US dollar. Then, by converting currencies, a clever trader can start with 1 US dollar a...

HDU1518—-Square 题目链接：HDU1518 分析参考：https://blog.csdn.net/guodongxiaren/article/details/23126997 题意就是好多棍子，看能不能拼成正方形。主要注意的有几点： 所有棍子都要用到，不能剩余 输入已经保证大于4根棍子了。所以无需判断可能小于3根棍子的情况 棍长的总数首先要是4的倍数，才能进行。否则直接输出 “no” 当前面前提满足以后，再满足3 根棍子拼好，就完工了。最后一根一定能拼好。 解法就是运用dfs方法不断尝试，当一个结果不符合题意时，就回溯到上一个结果。 此外，我们还可以提前对数据进行排序，将数据从大到小排序，以提高查找速率。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475/*421MS 1320K2019-04-12 22:40:37*/#inc...

Dijkstra—链式向前星—快速幂 题目链接：牛客283H-图论一顿套模版 解析题目求的是乘积，但是又因为W一定是2的整数次幂。所以我们可以将乘法换为加法，2^x * 2^y = 2^(x+y) 只要我们求出x+y的最小值，那么对应其答案也是最小值。算2^x可以运用快速幂解决 所以总体上我们可以用dij+优先队列优化+链式向前星+快速幂解决 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107/*运行时间(ms) 使用内存(KB) 代码长度 使用语言 提交时间62 4188 1543 C++ 2019-03-28 10:53:59*/#include <cs...

邻接矩阵，邻接表，链式向前星 参考： ACM图论之存图方式 邻接矩阵邻接矩阵是三种存图方式中最简单也最为暴力的一种存图方式了。 存图思想使用一个矩阵来描述一个图，对于矩阵的第i行第j列的值，表示编号为i的顶点到编号为j的顶点的权值 代码实现对于邻接矩阵来说，它的代码实现都十分简单，二维数组就可以了。 1234567891011121314151617181920#include <cstring>//最大顶点数const int MAXV = 1e3;//邻接矩阵,Map[i][j]:顶点i到顶点j的权值int Map[MAXV][MAXV];memset(Map, 0, sizeof(Map));// 增加边// 新增顶点`i`到顶点`j`的边，权值为`w`Map[i][j] = w;// 删除边// 删除顶点`i`到顶点`j`的边Map[i][j] = 0;// 查询边// 查询顶点`i`到顶点`j`的边权Map[i][j]; 优点使用邻接矩阵来进行建图存图有以下优点 简单易学 这个肯定不用多说，哪怕是没学过线性代数的童鞋也很容易理解这样的存图方式。 代码...