|
由于今年线上比，所以都是用自己熟悉的环境，只要记住最后提交试卷就好。那么下面开始今年模板：
日期类：
Calendar calendar=Calendar.getInstance();
calendar.set(Calendar.YEAR,2022);
calendar.set(Calendar.MONTH,5);//注意月份是从0开始算的
calendar.set(Calendar.DATE,17);
int d = calendar.get(Calendar.DATE);
calendar.set(Calendar.DATE,d+1);
全排(老样子):
方法一：
package Permutations;
/*
* 全排列1：
* 利用swap进行交互的全排
*/
public class Main {
static int nums[]= {1,2,3,4,5};
public static void main(String[] args) {
dfs(0);
}
static void dfs(int step) {
if (step==nums.length) {
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i]+" ");
}
System.out.println();
return;
}
for (int i = step; i < nums.length; i++) {
swap(i,step);
dfs(step+1);
swap(i, step);
}
}
static void swap(int a,int b) {
int mid=nums[a];
nums[a]=nums[b];
nums[b]=mid;
}
}
/*
* 部分示例：
* 1 2 3 4 5
* 1 2 3 5 4
* 1 2 4 3 5
* 1 2 4 5 3
* 1 2 5 4 3
* 1 2 5 3 4
* 1 3 2 4 5
* 1 3 2 5 4
*/
方法二：
package Permutations;
/*
* 全排列2：
* 利用targetnums数组进行记录是否标记过
* 优点：可以解决大部分重复无重复问题
* 缺点：没有全排1那么简洁，效率应该低一点,包含0的需要计算好边界。
*/
public class Main2 {
static int n=5;
static int nums[]= new int[n];
static int targetnums[]=new int[n];
public static void main(String[] args) {
dfs(0);//要排列不包含0的需要自己为1
}
static void dfs(int step) {
if (step==n) {
for (int i = 0; i < nums.length; i++) {//要排列不包含0的需要自己为1
System.out.print(nums[i]+" ");
}
System.out.println();
return;
}
for (int i = 0; i < nums.length; i++) {//要排列不包含0的需要自己为1
if (targetnums[i]==0) {
targetnums[i]=1;
nums[step]=i;
dfs(step+1);
targetnums[i]=0;
}
}
}
}
/*
* 部分示例：
* 0 1 2 3 4
* 0 1 2 4 3
* 0 1 3 2 4
* 0 1 3 4 2
* 0 1 4 2 3
*/
并查集连通:
package Union_Find;
/*
* 并查集
*/
public class Main {
static int n=5;
static int nums[]=new int[n];
public static void main(String[] args) {
init();
merge(1, 2); //连通1-2
merge(3, 4); //连通3-4;
System.out.println(connect(1,3));//false
System.out.println(connect(1,2));//true
System.out.println(connect(3,4));//true
}
static void init() { //初始化
for (int i = 0; i < nums.length; i++) {
nums[i]=i;
}
}
static int far(int num) { //寻找根节点
if (nums[num]!=num) {
return far(nums[num]);
}
return num;
}
static void merge(int a,int b) { //合并
int fara=far(a);
int farb=far(b);
if (fara!=farb) {
nums[b]=fara;
}
}
static boolean connect(int a,int b) { //是否连通
int fara=far(a);
int farb=far(b);
if (fara==farb) {
return true;
}
return false;
}
}
数论(最烦数论，只能死记硬背+理解了)：
最大公约数，最小公倍数：
package Number_Theory;
public class Main {
public static void main(String[] args) {
System.out.println(gcd(20, 8)); //4
System.out.println(lcm(20, 8)); //40
}
static int gcd(int a,int b) { //最大公约数
return a%b==0?b:gcd(b,a%b);
}
static int lcm(int a,int b) { //最小公倍数
return a*b/gcd(a, b);
}
}
素数筛（好用）：
package Number_Theory;
/*
* 素数筛(质数)也叫打表法
* 快一点的思想 ：从2开始，每个质数的倍数标记成合数。
* 原理：埃氏筛法
*/
public class Main2 {
static int n=10000;
static int nums[]=new int[n];
public static void main(String[] args) {
prime();
for (int i = 2; i < nums.length; i++) {
if (nums[i]==1) {
System.out.println(i+" ");
}
}
}
static void prime() {
for (int i = 2; i < nums.length; i++) {
if (nums[i]==0) {
nums[i]=1; //标记为素数（1）
for (int j = i+i; j < nums.length; j+=i) {
nums[j]=-1;//标记为合数(-1)
}
}
}
}
}
/*
* 部分示例:
* 2
* 3
* 5
* 7
* 11
* 13
* 17
* 19
* 23
*/
唯一分解定理（记住公式留个印象，代码自己考场写也可以，万一考到就赚到）：
package Number_Theory;
/*
* 唯一分解定理
* 原理:对任何一个整数n都可以将其拆分有n = P1^a1 * P2^a2 * …………* (P1 < P2 < ……Pn);Pi是素数
* 那么n的因子个数为=(a1+1)(a2+1)(a3+1)......
* n的所有因子之和为（q1^ 0+q1^ 1+q1^ 2…q1^ a1）（q2^ 0+q2^ 1+q2^ 2…q2^ a2）…*（qn^ 0+qn^ n+qn^ 2 …qn^ an）;
*/
public class Main3 {
static int n=10000;
static int primenums[]=new int[n+1];
static int nums[]=new int[n+1];
static int index=0;
public static void main(String[] args) {
prime();//打表素数
split(20);
System.out.println(number(20));
System.out.println(numberSum(20));
}
static void prime(){
int prime[]=new int[n+1];
for (int i = 2; i <=n; i++) {
if (prime[i]==0){
prime[i]=1;
primenums[index++]=i;//存入另一个数组方便到时候拆分
for (int j = i+i; j <=n; j+=i) {
prime[j]=-1;
}
}
}
}
static void split(int num){ //求num=P1^a1 * P2^a2 * …………* (P1 < P2 < ……Pn);//Pi是素数，保存到nums中
for (int i = 0; i <index; i++) {
while(num%primenums[i]==0){
nums[primenums[i]]++;//拆分出来的素数数量+1
num/=primenums[i];
}
if (num==0)break;
}
}
static int number(int num) { //求因子num个数
int sum=1;
for (int i = 2; i <=num; i++) {
if (nums[i]>0){
sum*=(nums[i]+1);
}
}
return sum;
}
static int numberSum(int num){
int sum=1;
for (int i = 2; i <=num; i++) { //求num因子之和
int mid=0;
if (nums[i]>0){
for (int j = 0; j <=nums[i]; j++) {
mid+=Math.pow(i,j);
}
sum*=mid;
}
}
return sum;
}
}
康托展开公式（复习一边留个印象吧）：
package Number_Theory;
/*
* 康托展开公式
*X = A[0] * (n-1)! + A[1] * (n-2)! + … + A[n-1] * 0!
* A[n] 指的是位于位置n后面的数小于A[n]值的个数,后面乘的就是后面还有多少个数的阶乘
* 例如：1，2，3，4，5排列组合，求34152的排名第几位， 其中A[1]是2，要乘的阶乘则为3！.因为从1这个位置（值为4）
* 开始往后比4小的只有2个数（1和2），所以A[1]为2，后面还有3个位置（1，5，2）按顺序来，则就是2*3！。
* 这只是A[1] * (n-2)!的一个例子，每个位置都要算
*/
public class Main4 {
static int nums[]= {3,4,1,5,2}; //1，2，3，4，5排列组合，求34152的排名第几位
public static void main(String[] args) {
System.out.println(cantor()); //输出61则，34152，在12345排列组合中排61位.
}
static int cantor() {
int sum=0;
for (int i = 0; i < nums.length; i++) {
int Anum=0,n=1,m=1; //Anum记录A[],n记录(n-1)!
for (int j = i+1; j < nums.length; j++) {
if (nums[i]>nums[j]) {
Anum++;
}
n*=m;
m++;
}
sum+=Anum*n;
}
return sum;
}
}
海伦公式(看一边公式):
package Number_Theory;
/*
* 海论公式
* 给出三角形三边可以求三角形面积
* 首先p为三角形的半周长 则 p=（a+b+c）/2
* 面积为S=sqrt(p(p-a)(p-b)(p-c))
* 用法:在三角形不是直角三角形，也求不到高的情况下
*/
/*
* 给一道例题
*
*
* 已知三角形三个顶点在直角坐标系下的坐标分别为：
(2.3, 2.5)
(6.4, 3.1)
(5.1, 7.2)
求该三角形的面积。
注意，要提交的是一个小数形式表示的浮点数。
要求精确到小数后3位，如不足3位，需要补零。
*/
public class Main5 {
public static void main(String[] args) {
double a=Math.sqrt(Math.pow((3.1-2.5),2)+Math.pow((6.4-2.3),2));
double b=Math.sqrt(Math.pow((5.1-2.3),2)+Math.pow((7.2-2.5),2));
double c=Math.sqrt(Math.pow((6.4-5.1),2)+Math.pow((7.2-3.1),2));
System.out.println(a);
System.out.println(b);
System.out.println(c);
double p=(a+b+c)/2;
System.out.println(Math.sqrt(p*(p-a)*(p-b)*(p-c)));//答案 8.795
}
}
这段刷题总结的小技巧（也有模板）
int数据范围：
取值范围为 -2^31——2^31-1,即-2147483648——2147483647。
大概约为10的9次方，所以一般数据范围10的8次方左右可以用int.
long数据范围：
long 占8个字节,也就是2^64,大约是10的18次方，long。
二分法出现的征兆:
1.具有单调性,若问题答案具有单调性，可能使用二分法
2.数据范围大，若给出的数据范围太大，可能是使用二分法.
3.求最大最小值
二分技巧:
(1)确定答案区间和mid的选定;
(2)在保证答案在区间内的前提下,逐步缩小区间;
(3)当区间缩小到仅包含一个可能解时，该可能解即为答案。
二分模板:
int left=0;
int right=l+1; //注意处理最大值
while (left+1<right){
int mid=(left+right)/2;
if (!check(mid)){ //处理判断
right=mid;
}else {
left=mid;
}
}
System.out.println(left);
搜索对角线的技巧(例如八皇后问题)：
右下:
如图
第1行的1和第2行的1可以：|1-2|=|2-3|
第1行的1和第3行的1可以：|1-2|=|3-4|
第1行的1和第4行的1可以：|1-2|=|4-5|
第1行的1和第5行的1可以：|1-2|=|5-6|
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
0 0 0 0 0 0
左下:
如图
第1行的1和第2行的1可以：|1+6|=|2+5|
第1行的1和第3行的1可以：|1+6|=|3+4|
第1行的1和第4行的1可以：|1+6|=|4+3|
第1行的1和第5行的1可以：|1+6|=|5+2|
第1行的1和第6行的1可以：|1+6|=|6+1|
0 0 0 0 0 1
0 0 0 0 1 0
0 0 0 1 0 0
0 0 1 0 0 0
0 1 0 0 0 0
1 0 0 0 0 0
例如：
if (col[i]==0&&left[step+i]==0&&right[step-i+n]==0){ //主要看这里left是左下，right是右上，+n是防止数组越界。
col[i]=1;
row[step]=i;
left[step+i]=1;
right[step-i+n]=1;
loop(step+1);
left[step+i]=0;
right[step-i+n]=0;
row[step]=0;
col[i]=0;
}
输出格式
左对齐：下面表示每个数字占7位，从最左边输出，后面依次补齐空格
System.out.printf("%-7d %-7d",3,3);
右对齐，同理从最右边 输出，在前面补空格。
System.out.printf("%7d %7d",3,3);
%f默认保留6位，.后面的表示的是小数保留的位数
System.out.printf("%.2f",3.1415926);
差分，有些情况需要对二维对行对列差分减少操作次数：
假设我们现在要给[2,5]这个区间加一。原来的序列是：
0 1 1 1 1 1 0 0
这时候我们在2上面打 +1 标记， 6 上面打 -1 标记。那么现在的序列是：
0 +1 0 0 0 -1 0
有什么用呢？从左往右扫描这个数组，记录当前经过的标签之和。这个和就是对应那个数的答案。
这样，对于每个区间加操作，只需要O(1) 的时间打上标记。
最后扫描输出即可。
现在把问题拓展到二维。假设我们要覆盖[(2,2),(5,5)] ，那么标记便可以这样打：
0 0 0 0 0 0
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 0 0 0 0 0
然而很明显这还可以再差分一次，对列差分，然后就成了这样：
0 0 0 0 0 0
0 +1 0 0 0 -1
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 -1 0 0 0 +1
这样就可以O(1)修改啦
最后先对每列求前缀和，得到第一个图，再对每行求前缀和，就是答案啦
输出或计算的时候复原：
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
map[i][j]=map[i][j]+map[i-1][j];//复原列
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
map[i][j]=map[i][j]+map[i][j-1];//复原行
}
}
一直接受输入直到换行结束（应该考试的时候不会有这种情况吧，但是说不准）：
Scanner s= new Scanner(System.in);
String str=s.nextLine();
Scanner scanner=new Scanner(str);
while (scanner.hasNextInt()){
dp[index++]=scanner.nextInt();
}
下面是Dp的一些推到代码，主要看思路:
01背包:
for (int i = 1; i <=m; i++) {
for (int j = 0; j <=t; j++) {
if (j<use[i]){
dp[i][j]=dp[i-1][j];
}else{
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-use[i]]+v[i]);
}
}
}
完全背包:
for (int i = 1; i <=m; i++) {
for (int j = 0; j <=t; j++) {
if (j<use[i]){
dp[i][j]=dp[i-1][j];
}else{
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-use[i]]+v[i]);//注意这行代码和01背包有不同
}
}
}
最长公共子序列
for (int i = 1; i <=n; i++) {
for (int j = 1; j <=m; j++) {
if (p[i]==q[j]){
dp[i][j]=dp[i-1][j-1]+1;
}else{
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
最长上升子序列:
for (int i = 0; i <index; i++) {
dp[i]=1;
for (int j = 0; j <i; j++) {
if (v[i]<=v[j])
dp[i]=Math.max(dp[i],dp[j]+1);
}
}
区间DP：
将整个区间不断的拆分一下，将一个区间[l,r]分成[l,k] [k+1,r]，然后再对[l,k]和[k+1,r]进行类似的拆分，直到拆分成最小的区间
for(int i=1;i<=n;i++)
{
for(int l=1;l+i<=2*n;l++)
{
int r=l+i-1;
for(int mid=l;mid<r;mid++)
{
Max[l][r]=max(Max[l][mid]+Max[mid+1][r]+w[r]-w[l-1],Max[l][r]);
}
}
}
|