GreenHatHGのBlog

单调队列及其优化dp 单调队列poj2823—Sliding Window 大意：给你一个长度为N的数组，一个长为K的滑动的窗体从最左移至最右端，你只能见到窗口的K个数，每次窗体向右移动一位，你的任务是找出窗体每个时刻中的最大值与最小值 优先队列优先队列能够进行排序，窗口往右一位，就把一个元素放到队列里面，然后每次取队首元素，如果队首元素的id在这个框的范围内的话，那么就取队首，如果不是的话那么就出队，找下一个队首元素，时间复杂度为O(nlogn) 对优先队列改良—单调队列O(n)基本思想：同样维护队首元素作为答案，去掉多余的元素（维护单调性） 因为是求最大值，所以维护一个单调递减队列，其队首就是最大值，就是我们想要的答案 L L+1 …… R-1 R 编号 A[L] A[L+1] …… A[R-1] A[R] 值 B[L] B[L+1] …… B[R-1] B[R+1] 上面单调递减队列满足： A[i+1]>A[i]>A[i-1] && B[i-1]>B[i]>B[i+1]（R>i>L） 单调...

接口初始化规则 接口初始化规则当java虚拟机初始化一个类时，要求它的所有父类都已经初始化，但是这条规则不适用于接口 在初始化一个类时，并不会先初始化它所实现的接口 在初始化一个接口时，并不会先初始化它的父接口 因此，一个父接口并不会因为它的子接口或者实现类的初始化而初始化，只有当程序首次使用特定接口的静态变量时，才会导致该接口的初始化 样例1123456789101112131415161718192021public class Main{ public static void main(String[] args) { new C(); new C(); }}class C{ { System.out.println("CC"); //每次创建对象时都会输出 } public C(){ System.out.println("c()"); }...

区间最值查询 参考：https://blog.csdn.net/qq_41311604/article/details/79900893 RMQRMQ（Range Minimum/Maximum Query），即区间最值查询，这是一种在线算法，所谓在线算法，是指用户每次输入一个查询，便马上处理一个查询。RMQ算法一般用较长时间做预处理，时间复杂度为O(nlogn)，然后可以在O(1)的时间内处理每次查询。 求dp现假设有一数组arr={1,3,6,7,4,2,5}； 设dp[i][j]表示从第i位开始连续2^j个数中的最小值。 例如dp[2][1]表示从第二位开始连续两个数的最小值（也就是从第二位数到第三位数的最小值），即3，6中的最小值，所以dp[2][1] = 3; 那么怎么求dp[2][1]呢？ 当i=2，j=3时，求dp[2][3] 因为2^3=8，代表从2开始有8个数，所以范围为[2,9]然后我们可以将其按照类似二分的思想将其拆分为两部分所以中间mid=(2+9)/2=5 左区间[2,5]：有4个数，其对应dp[2][2] 右区间[6,9]：有4个数，其对应...

编译期常量与运行期常量的区别及数组创建本质分析 样例11234567891011121314151617181920import java.util.UUID;public class Main{ public static void main(String[] args){ System.out.println(MyParent3.str); }}class MyParent3{ public static final String str = UUID.randomUUID().toString(); static{ System.out.println("MyParent3 code block"); }}/*output:MyParent3 code block0e7ed916-96de-4805-865d-1b2e703482ec*/ 当一个常量的值并非编译期间可以确定的，那么其值就不会被...

线段树入门 数据结构—线段树（segment tree）引入给定一个数组，数组长度可能非常大。现在我们需要对数组里面的数据反反复复进行两个操作 求出某一个区间里面所有元素之和，(query操作) 修改某个元素的值，(update操作) 暴力解决和前缀和对区间[L,R]（长度为n）取和，并且更新一个元素i的值，采用暴力解决方法 可得 query(L,R)时间复杂度为O(n) update(i)时间复杂度为O(1) 如果区间范围很大，再加上多次操作，暴力取和明显会超时，可以采用前缀和方式优化查询sum_arr[0]=arr[0]sum_arr[1]=arr[0]+arr[1]sum_arr[2]=arr[0]+arr[1]+arr[2]这样，假如我们想得到区间[2,4]的和，我们可以用sum_arr[4]-sum_arr[1]计算到 query(L,R)时间复杂度减小为O(1) 因为改变一个值后，要同时更新后面的sum_arr数组，所以update(i)时间复杂度增大为O(n) 如果用线段树的话，我们可以将查询和更新的的时间复杂度都变为O(logn) 方法 qu...

常量的本质含义以及反编译出现的部分助记符 样例112345678910111213141516171819public class Main{ public static void main(String[] args){ System.out.println(Mychild1.str); }}class MyParent1{ public static String str = "hello world"; static{ out.println("Myparent1 static block"); }}class Mychild1 extends MyParent1{ public static String str2 = "welcome"; static{ System.out.println("Mychild1 sta...

HDU6512 —Triangle && HDU6518—Clumsy Keke HDU6518—Clumsy Keke 解析题目大意： 给出一个三维图形的x，y，z轴的长度，然后分别给出正视图，侧视图，俯视图，视图的表示方法是在一个大方格里面，用0代表空白，用1代表阴影，这样就可以表示一个图形了，然后求出这个三维图形是由多少小正方体组成的。 我们可以运用逆向思维，首先构建一个完整的图形，然后减去没有出现的，最终剩下来的就是拥有的，然后再统计下有几个就是我们要求的答案了。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162/*2019-04-20 00:21:25 46MS 2184K*/#include <cstdio>#include <cstring>using namespace std;const int MAXN = 1e2;bool Map[MA...

一些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)$ 我们已知的是...