1235 lines
32 KiB
Markdown
1235 lines
32 KiB
Markdown
## 蓝桥基础
|
||
|
||
### 离散化
|
||
|
||
```
|
||
package LQ_10;
|
||
import java.util.*;
|
||
|
||
public class EXE {
|
||
public static void main(String[] args) {
|
||
Scanner scan=new Scanner (System.in);
|
||
int n=scan.nextInt();
|
||
int[] arr=new int[n];
|
||
int[] a=new int[n];
|
||
for(int i=0;i<n;i++) {
|
||
arr[i]=scan.nextInt();
|
||
a[i]=arr[i];
|
||
}
|
||
Set<Integer>set=new HashSet<>();
|
||
Arrays.sort(a);
|
||
Map<Integer,Integer>map=new HashMap<>();
|
||
for(int i=0;i<n;i++)
|
||
{
|
||
set.add(a[i]);
|
||
map.put(a[i],set.size());
|
||
}
|
||
for(int i=0;i<n;i++)
|
||
{
|
||
System.out.println(map.get(arr[i])+" ");
|
||
}
|
||
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
|
||
|
||
## 进制转化
|
||
|
||
### 奇怪的捐赠
|
||
|
||
地产大亨 Q 先生临终的遗愿是：拿出 100100 万元给 X 社区的居民抽奖，以稍慰藉心中愧疚。
|
||
|
||
麻烦的是，他有个很奇怪的要求：
|
||
|
||
1. 100 万元必须被正好分成若干份（不能剩余）。每份必须是 7 的若干次方元。比如：1 元, 7 元， 49 元，343 元，...
|
||
2. **相同金额的份数不能超过 5 份。**————》woc 这tm是迷惑你的
|
||
3. 在满足上述要求的情况下，分成的份数越多越好！
|
||
|
||
请你帮忙计算一下，最多可以分为多少份？
|
||
|
||
```java
|
||
思路就是：分成多少分，重点是7的平方
|
||
想一下一个数是又一个数的各种平方合成的————》进制***太深了
|
||
那么难点就是进制转换的问题了
|
||
```
|
||
|
||
```java
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
int n=1000000;
|
||
int cnt=0;
|
||
while(n>0){
|
||
cnt+=n%7;
|
||
n/=7;
|
||
}
|
||
System.out.println(cnt);
|
||
}
|
||
}
|
||
```
|
||
|
||
## 常识题
|
||
|
||
**本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。**
|
||
|
||
小蓝的IP地址为 `192.168.*.21`，其中 `*` 是一个数字，请问这个数字最大可能是多少？
|
||
|
||
|
||
|
||
## 高精度
|
||
|
||
### 题目描述
|
||
|
||
计算 A×B*A*×*B* 。
|
||
|
||
### 输入描述
|
||
|
||
每一行将包含两个整数 A*A* 和 B*B*。备注:每个整数的长度不能超过 1000010000。
|
||
|
||
### 输出描述
|
||
|
||
输出 A×B*A*×*B* 。
|
||
|
||
### 输入输出样例
|
||
|
||
#### 示例 1
|
||
|
||
### 题目描述
|
||
|
||
计算 A×B*A*×*B* 。
|
||
|
||
### 输入描述
|
||
|
||
每一行将包含两个整数 A*A* 和 B*B*。备注:每个整数的长度不能超过 1000010000。
|
||
|
||
### 输出描述
|
||
|
||
输出 A×B
|
||
|
||
|
||
|
||
```txt
|
||
1000
|
||
2
|
||
```
|
||
|
||
|
||
|
||
```txt
|
||
2000
|
||
```
|
||
|
||
|
||
|
||
```java
|
||
import java.util.Scanner;
|
||
// 1:无需package
|
||
// 2: 类名必须Main, 不可修改
|
||
import java.math.BigInteger;***注意导包
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner scan = new Scanner(System.in);
|
||
while(scan.hasNext()) {
|
||
BigInteger a=scan.nextBigInteger();
|
||
BigInteger b=scan.nextBigInteger();
|
||
System.out.println(a.multiply(b));
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
============================================================================================================================================================================================================================================================================================================================
|
||
|
||
## 双指针
|
||
|
||
|
||
|
||
1372
|
||
|
||
```java
|
||
package LQ_10;
|
||
import java.util.*;
|
||
|
||
public class LQ1372 {
|
||
public static void main(String [] args)
|
||
{
|
||
|
||
Scanner scan = new Scanner(System.in);
|
||
int n=scan.nextInt();//n个数
|
||
int s=scan.nextInt();//s 目标常数
|
||
int ans=Integer.MAX_VALUE;//表示长度
|
||
int sum=0;//表示和
|
||
int [] arr=new int[n];
|
||
for(int i=0;i<n;i++)
|
||
arr[i]=scan.nextInt();
|
||
for(int i=0,j=0;i<n;) {
|
||
if(sum<s) {
|
||
sum+=arr[i];
|
||
i++;
|
||
}else {
|
||
ans=Math.min(i-j,ans);
|
||
sum-=arr[j];
|
||
j++;
|
||
}
|
||
}
|
||
|
||
if(ans==Integer.MAX_VALUE)
|
||
System.out.println("0");
|
||
else
|
||
System.out.println(ans);
|
||
scan.close();
|
||
|
||
}
|
||
|
||
}
|
||
题目核心：
|
||
你什么时候达到S以及到达S的时候怎么能最小
|
||
刚开始 i=j=0
|
||
这个题用的是双指针 就是让sum=0 如果sum<=（都对）s那么就让sum+arr[i],i++ 这样就是扩大了i的长度
|
||
既然有扩大长度 那么就有缩短长度 那么如何缩短长度 就是需要j 如果sum>=s 那么就是sum=-arr[j] j++这样 i在前面扩大长度 j在后面缩小长度 当i<n的时候就是到头了 不能扩大了 就是程序结束的时候
|
||
Q：你怎么确定 排序是从小打大 （题目似乎没有给出） 是否需要用贪心算法 +动归
|
||
```
|
||
|
||
============================================================================================================================================================================================================================================================================================================================
|
||
|
||
## 常用函数
|
||
|
||
```java
|
||
public static int gcd (int m,int n) {
|
||
int r=n;
|
||
while(m%n!=0)
|
||
{
|
||
r=m%n;
|
||
m=n;
|
||
n=r;
|
||
}
|
||
return r;
|
||
}
|
||
R为最小公因数
|
||
m*n/r为最小公倍数s
|
||
|
||
判断是否是素数
|
||
public static boolean isPrime (int x) {
|
||
if(x==1)
|
||
return false;
|
||
for(int i=2;i<=Math.sqrt(x);i++)
|
||
{
|
||
if(x%i==0)
|
||
return false;
|
||
}
|
||
return true;
|
||
}
|
||
|
||
```
|
||
|
||
============================================================================================================================================================================================================================================================================================================================
|
||
|
||
## 字符串
|
||
|
||
```java
|
||
给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见实例 2）。
|
||
|
||
package LQ_10;
|
||
import java.util.*;
|
||
|
||
public class LQ396 {
|
||
public static void main(String args[]) {
|
||
Scanner scan=new Scanner(System.in);
|
||
int n=scan.nextInt();
|
||
int b=Math.abs(n);
|
||
StringBuilder str=new StringBuilder();
|
||
str.append(b);
|
||
StringBuilder str1=str.reverse();
|
||
String str2=str1.toString();
|
||
int a=Integer.valueOf(str2);
|
||
if(n>=0){
|
||
System.out.println(a);
|
||
}
|
||
else{
|
||
System.out.println(-a);
|
||
}
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
## 排序
|
||
|
||
### 冒泡
|
||
|
||
把最大的冒泡到前面去
|
||
|
||
```java
|
||
int []arr= {5,8,4,4,6,7,4,8};
|
||
for (int i = arr.length - 1; i > 0; i--) {
|
||
// 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
|
||
for (int j = 0; j < i; j++) {
|
||
if (arr[j] > arr[j + 1]) {
|
||
// 交换 arr[j] 与 arr[j + 1]
|
||
int tmp = arr[j];
|
||
arr[j] = arr[j + 1];
|
||
arr[j + 1] = tmp;
|
||
}
|
||
}
|
||
}
|
||
for(int i:arr) {
|
||
System.out.printf(i+" ");
|
||
}
|
||
时间复杂度O N^2
|
||
```
|
||
|
||
### 选择
|
||
|
||
选择最小的与前面的交换
|
||
|
||
```java
|
||
int []arr= {3,8,4,4,6,7,4,8,9,1,1,1,5,2,7,8,15};
|
||
for(int i=0;i<arr.length;i++) {
|
||
int k=i;
|
||
for(int j=i+1;j<arr.length;j++) {
|
||
if(arr[j]<arr[k])
|
||
k=j;
|
||
}
|
||
if(k!=i) {
|
||
int t=arr[i];
|
||
arr[i]=arr[k];
|
||
arr[k]=t;
|
||
}
|
||
}
|
||
```
|
||
|
||
### 插入排序
|
||
|
||
```java
|
||
package LQ_10;
|
||
|
||
public class EXE {
|
||
public static void main (String [] args) {
|
||
int []nums= {3,8,4,4,6,7,4,8,9,1,1,1,5,2,7,8,15};
|
||
|
||
for(int i=1;i<nums.length;i++){
|
||
int base=nums[i],j=i;
|
||
while(j>0&&nums[j]>base) {
|
||
nums[j+1]=nums[j];
|
||
j--;
|
||
}
|
||
nums[j+1]=base;
|
||
}
|
||
|
||
for(int i:nums) {
|
||
System.out.printf(i+" ");
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
### 快排
|
||
|
||
```java
|
||
package LQ_10;
|
||
|
||
public class EXE {
|
||
public static void main(String[] args) {
|
||
int[] nums = { 3, 8, 4, 4, 6, 7, 4, 8, 9, 1, 1, 1, 5, 2, 7, 8, 15 };
|
||
quickSort(nums,0,nums.length-1);
|
||
for (int i : nums) {
|
||
System.out.printf(i + " ");
|
||
}
|
||
}
|
||
|
||
public static void swap(int[] nums, int i, int j) {
|
||
int t = nums[i];
|
||
nums[i] = nums[j];
|
||
nums[j] = t;
|
||
}
|
||
public static void quickSort(int []nums,int left,int right) {
|
||
if(left>right)return;//左边的数等于右边的数 就是说只有一个数了 那还排什么
|
||
int pivot=partition(nums,left,right);//找中枢点
|
||
quickSort(nums,left,pivot-1);
|
||
quickSort(nums,pivot+1,right);
|
||
}
|
||
public static int partition(int []nums,int left,int right) {
|
||
int i=left,j=right;
|
||
while(i<j) {
|
||
while(i<j&&nums[j]>=nums[left])j--;
|
||
while(i<j&&nums[i]<=nums[left])i++;
|
||
swap(nums,i,j);
|
||
}
|
||
swap(nums,i,left);
|
||
return i;
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
### 归并排序
|
||
|
||
```java
|
||
package LQ_10;
|
||
|
||
public class EXE {
|
||
public static void main(String[] args) {
|
||
int[] nums = { 3, 8, 4, 4, 6, 7, 4, 8, 9, 1, 1, 1, 5, 2, 7, 8, 15 };
|
||
int[] arr=mergeSort(nums,0,nums.length-1);
|
||
for (int i : arr) {
|
||
System.out.printf(i + " ");
|
||
}
|
||
}
|
||
|
||
public static int[] mergeSort(int[] nums, int left, int right) {
|
||
if (left == right)
|
||
return new int[] {nums[left]};
|
||
int mid = (left + right) / 2;
|
||
int[] leftarr = mergeSort(nums, left, mid );
|
||
int[] rightarr = mergeSort(nums, mid+1, right);
|
||
int[] newarr = new int[leftarr.length + rightarr.length];
|
||
int m = 0, l = 0, r = 0;
|
||
while (l < leftarr.length && r < rightarr.length)
|
||
newarr[m++] = leftarr[l] <rightarr[r] ? leftarr[l++] : rightarr[r++];
|
||
while (l < leftarr.length)
|
||
newarr[m++] = leftarr[l++];
|
||
while (r < rightarr.length)
|
||
newarr[m++] = rightarr[r++];
|
||
return newarr;
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
## 进制转化
|
||
|
||
```java
|
||
public static String ts(int a,int x) {
|
||
StringBuilder str1=new StringBuilder();
|
||
while(a>0)
|
||
{
|
||
str1.append(a%x);
|
||
a/=x;
|
||
}
|
||
return str1.reverse().toString();
|
||
}
|
||
```
|
||
|
||
## 贪心
|
||
|
||
```java
|
||
package LQ_10;
|
||
|
||
import java.util.*;
|
||
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner scan = new Scanner(System.in);
|
||
int n=scan.nextInt();
|
||
List<Integer> lt=new ArrayList<Integer>();
|
||
for(int i=0;i<n;i++)
|
||
lt.add(scan.nextInt());
|
||
long sum=0;
|
||
Collections.sort(lt);
|
||
while(lt.size()>1) {
|
||
int a=lt.get(0);
|
||
int b=lt.get(1);
|
||
sum+=a+b;
|
||
lt.remove(0);
|
||
lt.remove(0);
|
||
lt.add(a+b);
|
||
Collections.sort(lt);
|
||
}
|
||
System.out.print(sum);
|
||
scan.close();
|
||
}
|
||
}
|
||
```
|
||
|
||
|
||
|
||
|
||
|
||
# 系统学习
|
||
|
||
## 循环
|
||
|
||
### 进制转换
|
||
|
||
```java
|
||
|
||
import java.util.Scanner;
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner scan = new Scanner(System.in);
|
||
int a=scan.nextInt();
|
||
int out=0;
|
||
int pow=1;
|
||
while(a>0){
|
||
int c=a%10;
|
||
a/=10;
|
||
out+=c*pow;
|
||
pow*=9;
|
||
}
|
||
System.out.println(out);
|
||
scan.close();
|
||
}
|
||
}
|
||
```
|
||
|
||
### 枚举法求最大公约数
|
||
|
||
```java
|
||
设a, b是两个整数，如果d能整除a且d能整除b，那么，d就称为是a和b的公约数。a和b的公约数中最大的整数称为a和b的最大公约数。
|
||
输入两个正整数a和b，求它们的最大公约数。
|
||
import java.util.Scanner;
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner scan = new Scanner(System.in);
|
||
int a = scan.nextInt(), b = scan.nextInt();
|
||
int min= Math.min(a, b);
|
||
for(int i=min;i>=1;i--){
|
||
if(a%i==0 && b%i==0){
|
||
System.out.println(i);
|
||
break;
|
||
}
|
||
}
|
||
scan.close();
|
||
}
|
||
}
|
||
|
||
递归大法
|
||
import java.util.Scanner;
|
||
// 1:无需package
|
||
// 2: 类名必须Main, 不可修改
|
||
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner sc = new Scanner(System.in);
|
||
int a = sc.nextInt();
|
||
int b = sc.nextInt();
|
||
sc.close();
|
||
System.out.println(gcd(a,b));
|
||
}
|
||
public static int gcd(int a,int b) {
|
||
return b == 0 ? a : gcd(b,a%b);
|
||
}
|
||
}
|
||
```
|
||
|
||
## 数组与字符串
|
||
|
||
### 冒泡排序
|
||
|
||
```java
|
||
|
||
import java.util.Scanner;
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner scan = new Scanner(System.in);
|
||
int n=scan.nextInt();
|
||
int arr[]=new int[n];
|
||
for(int i=0;i<n;i++){
|
||
arr[i]=scan.nextInt();
|
||
}
|
||
for(int i=0;i<n-1;i++){
|
||
for(int j=0;j<n-i-1;j++){//n-1-i n-1是因为有j+1的存在 i是因为每次冒出去一个就会占一个
|
||
if(arr[j]>arr[j+1]){
|
||
int temp=arr[j];
|
||
arr[j]=arr[j+1];
|
||
arr[j+1]=temp;
|
||
}
|
||
}
|
||
}
|
||
for(int i=0;i<n;i++){
|
||
if(i==0){
|
||
System.out.print(arr[i]);
|
||
}
|
||
else{
|
||
System.out.print(" "+arr[i]);
|
||
}
|
||
|
||
}
|
||
scan.close();
|
||
}
|
||
}
|
||
```
|
||
|
||
### 选择排序
|
||
|
||
```java
|
||
/* 选择排序 */
|
||
void selectionSort(int[] nums) {
|
||
int n = nums.length;
|
||
// 外循环：未排序区间为 [i, n-1]
|
||
for (int i = 0; i < n - 1; i++) {
|
||
// 内循环：找到未排序区间内的最小元素
|
||
int k = i;
|
||
for (int j = i + 1; j < n; j++) {//因为是找最小的 所以不用从自己开始
|
||
if (nums[j] < nums[k])
|
||
k = j; // 记录最小元素的索引
|
||
}
|
||
// 将该最小元素与未排序区间的首个元素交换
|
||
int temp = nums[i];
|
||
nums[i] = nums[k];
|
||
nums[k] = temp;
|
||
}
|
||
}
|
||
```
|
||
|
||
## JAVA基本API
|
||
|
||
```
|
||
Integer.parseInt(String s ,int radix) 将（radix表示的s是几进制的）转换为10进制
|
||
|
||
toString(String s ,int radix) 将s转换为radix进制的字符串
|
||
```
|
||
|
||
## JAVA快读
|
||
|
||
```java
|
||
static FastReader in = new FastReader(); // 创建一个静态的 FastReader 对象，用于处理输入
|
||
static PrintWriter out = new PrintWriter(System.out); // 创建一个静态的 PrintWriter 对象，用于输出数据
|
||
|
||
// FastReader 类，用于处理高效的输入
|
||
static class FastReader {
|
||
static BufferedReader br; // 静态的 BufferedReader，用于高效读取输入
|
||
static StringTokenizer st; // 静态的 StringTokenizer，用于将输入字符串分割为标记
|
||
|
||
// 构造函数，初始化 BufferedReader 以从标准输入读取数据
|
||
FastReader() {
|
||
br = new BufferedReader(new InputStreamReader(System.in)); // 使用 System.in 作为输入流初始化 BufferedReader
|
||
}
|
||
|
||
// next() 方法，返回下一个字符串标记
|
||
String next() {
|
||
String str = ""; // 定义一个空字符串，用于存储读取到的行
|
||
// 如果 StringTokenizer 为 null 或没有更多标记可读取，读取新行
|
||
while (st == null || !st.hasMoreElements()) {
|
||
try {
|
||
str = br.readLine(); // 使用 BufferedReader 读取一整行输入
|
||
} catch (IOException e) { // 捕获可能的 I/O 异常
|
||
throw new RuntimeException(e); // 如果发生异常，抛出运行时异常
|
||
}
|
||
st = new StringTokenizer(str); // 将读取到的行传递给 StringTokenizer 进行分割
|
||
}
|
||
return st.nextToken(); // 返回 StringTokenizer 的下一个标记
|
||
}
|
||
String nextLine(){
|
||
String str="";
|
||
try {
|
||
str = br.readLine(); // 使用 BufferedReader 读取一整行输入
|
||
} catch (IOException e) { // 捕获可能的 I/O 异常
|
||
throw new RuntimeException(e); // 如果发生异常，抛出运行时异常
|
||
}
|
||
return str;
|
||
}
|
||
// nextInt() 方法，返回下一个整数输入
|
||
int nextInt() {
|
||
return Integer.parseInt(next()); // 使用 next() 方法读取字符串并转换为整数
|
||
}
|
||
|
||
// nextDouble() 方法，返回下一个双精度浮点数输入
|
||
double nextDouble() {
|
||
return Double.parseDouble(next()); // 使用 next() 方法读取字符串并转换为双精度浮点数
|
||
}
|
||
|
||
// nextLong() 方法，返回下一个长整数输入
|
||
long nextLong() {
|
||
return Long.parseLong(next()); // 使用 next() 方法读取字符串并转换为长整数
|
||
}
|
||
}
|
||
```
|
||
|
||
还有一种
|
||
|
||
```java
|
||
|
||
class Read{
|
||
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
|
||
public int nextInt() throws Exception{
|
||
st.nextToken();
|
||
return (int)st.nval;
|
||
}
|
||
public String readLine() throws Exception{ // 不推荐使用
|
||
st.nextToken();
|
||
return st.sval;
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
## 一维前缀和
|
||
|
||
```
|
||
本题为一维前缀和模板。
|
||
给定一个长度为 n 的序列 a。
|
||
再给定 q组查询，对于每次查询:给定一对l r,你需要输出 的结果。
|
||
输入格式
|
||
第一行输入两个正整数 n, q。(1 ≤ n,q < 10°)
|
||
第二行输入 n 个正整数 αi。(1 ≤i≤ n,1 ≤ ai< 104)。
|
||
接下来 q 行，每行输入 2 个正整数 l,γ。(1 <l<r< n)。
|
||
输出格式
|
||
对于每次查询，输出一行一个整数，表示该次查询的结果。
|
||
|
||
样例输入
|
||
5 3
|
||
2 1 3 6 4
|
||
1 2
|
||
1 3
|
||
2 4
|
||
|
||
输出
|
||
3
|
||
6
|
||
10
|
||
|
||
|
||
自制小代码
|
||
import java.util.Scanner;
|
||
// 1:无需package
|
||
// 2: 类名必须Main, 不可修改
|
||
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner scan = new Scanner(System.in);
|
||
int n=scan.nextInt(),q=scan.nextInt();
|
||
int arr[]=new int[n];
|
||
for(int i=0;i<n;i++){
|
||
arr[i]=scan.nextInt();
|
||
}
|
||
for(int i=0;i<q;i++){
|
||
int l=scan.nextInt(),r=scan.nextInt();
|
||
int sum=0;
|
||
for(int j=l-1;j<r;j++){
|
||
sum+=arr[j];
|
||
}
|
||
System.out.println(sum);
|
||
}
|
||
scan.close();
|
||
}
|
||
} 简单易懂 但是时间很长
|
||
|
||
|
||
标准答案 利用了求和公式的变形
|
||
S[n]=s[n-1]+a;
|
||
|
||
然后要求l到r的和就是 S[r]-s[l-1] 因为是包括L的所以说是从L-1开始的
|
||
import java.util.Scanner;
|
||
// 1:无需package
|
||
// 2: 类名必须Main, 不可修改
|
||
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner scan = new Scanner(System.in);
|
||
int n=scan.nextInt(),q=scan.nextInt();
|
||
int arr[]=new int[n+2];
|
||
arr[0]=0;
|
||
for(int i=1;i<=n;i++){
|
||
arr[i]=scan.nextInt()+arr[i-1];
|
||
}
|
||
for(int i=0;i<q;i++){
|
||
int l=scan.nextInt(),r=scan.nextInt();
|
||
System.out.println(arr[r]-arr[l-1]);
|
||
}
|
||
scan.close();
|
||
}
|
||
}
|
||
```
|
||
|
||
## 差分
|
||
|
||
```java
|
||
问题描述
|
||
给定一个长度为 n 的序列 a。
|
||
再给定 m 组操作，每次操作给定3个正整数l,",d，表示对 ai~，中的所有数增加 d。
|
||
最终输出操作结束后的序列 a。
|
||
Update:由于评测机过快，n,m于2024-12-09 从 105加强至 2 x105杜绝暴力通过本题。
|
||
输入格式第一行输入两个正整数n,m。(1<n,m<2x105)第二行输入 n 个正整数 ai。(1 ≤i≤ n,1 ≤ ai < 104)。接下来 m 行，每行输入 3 个正整数 l,™,d。(1 ≤l≤r≤ n,-104 ≤d≤ 104)。
|
||
输出格式
|
||
输出 几 个整数，表示操作结束后的序列 a。
|
||
样例输入
|
||
6 3
|
||
2 2 12 1
|
||
3 1
|
||
5
|
||
6 1
|
||
样例输出
|
||
3 4 5 3 4 2
|
||
|
||
import java.util.Scanner;
|
||
// 1:无需package
|
||
// 2: 类名必须Main, 不可修改
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner scan = new Scanner(System.in);
|
||
int n= scan.nextInt(), m=scan.nextInt();
|
||
int arr[]=new int[n+5];
|
||
int brr[]=new int[n+5];
|
||
int crr[]=new int[n+5];
|
||
arr[0]=0;brr[0]=0;crr[0]=0;
|
||
for(int i=1;i<=n;i++) arr[i]=scan.nextInt();
|
||
for(int i=1;i<=n;i++) brr[i]=arr[i]-arr[i-1];
|
||
for(int i=1;i<=m;i++){
|
||
int l=scan.nextInt(),r=scan.nextInt(),d=scan.nextInt();
|
||
brr[l]+=d;
|
||
brr[r+1]-=d;
|
||
}
|
||
for(int i=1;i<=n;i++) crr[i]=crr[i-1]+brr[i];
|
||
|
||
for(int i=1;i<=n;i++){
|
||
System.out.print(crr[i]+" ");
|
||
}
|
||
scan.close();
|
||
}
|
||
}
|
||
差分数组求前缀和就是求原数组
|
||
```
|
||
|
||
### 小蓝的操作（2星）
|
||
|
||
|
||
|
||
```java
|
||
import java.util.Scanner;
|
||
// 1:无需package
|
||
// 2: 类名必须Main, 不可修改
|
||
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner in = new Scanner(System.in);
|
||
int n = in.nextInt();//n家店铺
|
||
int t = in.nextInt();//t行点赞情况
|
||
int q = in.nextInt();//q组查询
|
||
int x = in.nextInt();//信赖店铺的点赞数量
|
||
int arr[] = new int[n+20];//开辟一个n个空间的数组 表示店铺
|
||
for (int i = 0; i < t; i++) {
|
||
int l = in.nextInt();
|
||
int r = in.nextInt();
|
||
arr[l] += 1;//我在l的地方+1 在我后面代码arr[i]+=arr[i-1]中 所有的在l后面的代码都会加上1
|
||
arr[r+1] -= 1;//但是我又为了防止 r后面的不能加上因为我的加的范围是l-r 所以 r+1就需要减去1 与前面的l对冲
|
||
}
|
||
for (int i = 1; i <= n; i++) {
|
||
arr[i] = arr[i] + arr[i - 1]; //将差分数组 转化为原数组 bn=an+an-1
|
||
}
|
||
|
||
int brr[]=new int[n+10];
|
||
for (int i = 1; i <= n; i++) {
|
||
if (arr[i] >= x)//如果被定义为信赖的为1
|
||
arr[i]=1;
|
||
else
|
||
arr[i]=0;
|
||
brr[i]=brr[i-1]+arr[i];//前缀和
|
||
}
|
||
for(int i=1;i<=q;i++){
|
||
int l= in.nextInt(),r= in.nextInt();
|
||
System.out.println(brr[r]-brr[l-1]);
|
||
}
|
||
in.close();
|
||
}
|
||
|
||
}
|
||
```
|
||
|
||
### 二维差分数
|
||
|
||
给定一个 大小的矩阵 。
|
||
给定 组查询，每次查询为给定 4 个正整数 ，你需要输出 的值。
|
||
|
||
第一行输入 3 个正整数 。
|
||
接下来 行每行输入 个整数，表示 。
|
||
接下来 行，每行输入 4 个正整数
|
||
|
||
对于每次查询，输出一个整数，表示查询的子矩阵的和。
|
||
|
||
```plaintext
|
||
3 4 3
|
||
1 7 2 4
|
||
3 6 2 8
|
||
2 1 2 3
|
||
1 1 2 2
|
||
2 1 3 4
|
||
1 3 3 4
|
||
```
|
||
|
||
#### 样例输出
|
||
|
||
```plaintext
|
||
17
|
||
27
|
||
21
|
||
```
|
||
|
||
```java
|
||
import java.util.Scanner;
|
||
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner scan = new Scanner(System.in);
|
||
int n = scan.nextInt();
|
||
int m = scan.nextInt();
|
||
int q = scan.nextInt();
|
||
int[][] sum = new int[n + 1][m + 1];
|
||
for (int i = 1; i <= n; i++) {
|
||
for (int j = 1; j <= m; j++) {
|
||
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + scan.nextInt();
|
||
}
|
||
}
|
||
|
||
while (q-- > 0) {
|
||
int x1 = scan.nextInt();
|
||
int y1 = scan.nextInt();
|
||
int x2 = scan.nextInt();
|
||
int y2 = scan.nextInt();
|
||
int result = sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
|
||
System.out.println(result);
|
||
}
|
||
|
||
scan.close();
|
||
}
|
||
}
|
||
```
|
||
|
||
## 单调队列
|
||
|
||
### 滑动窗口问题
|
||
|
||
```java
|
||
import java.util.ArrayDeque;
|
||
import java.util.Deque;
|
||
import java.util.Scanner;
|
||
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner sc = new Scanner(System.in);
|
||
int[] num = new int[10];
|
||
int n, k;
|
||
n = sc.nextInt();
|
||
k = sc.nextInt();
|
||
int[] ans = new int[n - k + 1];
|
||
Deque<Integer> q = new ArrayDeque();
|
||
for (int i = 0; i < n; i++) {
|
||
while (!q.isEmpty() && num[i] > num[q.peekLast()]) {
|
||
q.pollLast();
|
||
}
|
||
q.addLast(i);
|
||
if (i - q.getFirst() >= k) {//如果队列头部的元素已经不在滑动窗口内，则将其移除
|
||
q.pollFirst();
|
||
}
|
||
if (i >= k - 1)
|
||
ans[i - k + 1] = num[q.getFirst()];//记录当前滑动窗口的最大值
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
|
||
|
||
## 位运算
|
||
|
||
### 相或为k（2星）
|
||
|
||
#### 问题描述
|
||
|
||
给定你n个非负整数a[i]，你是否可以从中选出一些数进行或运算使得值为k，若可以，则输出Yes，若不可以，则输出No。
|
||
|
||
或运算：二进制位1|1 = 1, 1|0 = 1, 0|0 = 0。
|
||
|
||
#### 输入格式
|
||
|
||
第一行一个t代表数据组数。
|
||
|
||
每组数组第一行二个整数n, k。
|
||
|
||
每组数据第二行n个数a[i]。
|
||
|
||
#### 输出格式
|
||
|
||
输出t行，为符合题目要求的Yes或No。
|
||
|
||
#### 样例输入
|
||
|
||
#### 1
|
||
4 6
|
||
1 2 3 4
|
||
|
||
#### 样例输出
|
||
|
||
Yes
|
||
|
||
```java
|
||
import java.util.Scanner;
|
||
// 1:无需package
|
||
// 2: 类名必须Main, 不可修改
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner sc = new Scanner(System.in);
|
||
int t = sc.nextInt();
|
||
while(t-->0) {
|
||
int n = sc.nextInt();
|
||
int k= sc.nextInt();
|
||
int ans=0;
|
||
for(int i=0;i<n;i++){
|
||
int r= sc.nextInt();
|
||
if((r&k)==r){
|
||
ans|=r;
|
||
}
|
||
}
|
||
/**
|
||
* 判断是否为k的子集
|
||
* 如果r&k==r，则说明r是k的子集
|
||
* 就让ans 加上r也就是ans|r
|
||
* 最后再看是否ans==k 也就是所有的k的子集是否都出现了
|
||
* 这个题 题目不好理解 但是 只要理解了 就很简单了
|
||
*/
|
||
if(ans==k){
|
||
System.out.println("Yes");
|
||
}
|
||
else{
|
||
System.out.println("No");
|
||
}
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
|
||
|
||
## 求阶乘（3星）
|
||
|
||
**问题描述**：满足 `N!` 的末尾恰好有 `K` 个 `0` 的最小的 `N` 是多少？如果这样的 `N` 不存在输出 `-1` 。 **输入格式**：一个整数 `K` 。 **输出格式**：一个整数代表答案。
|
||
|
||
**样例输入**： 2
|
||
|
||
**样例输出**： 10
|
||
|
||
```java
|
||
import java.util.Scanner;
|
||
// 1:无需package
|
||
// 2: 类名必须Main, 不可修改
|
||
|
||
public class Main {
|
||
|
||
static long cale(long x) {
|
||
long num = 0;
|
||
while (x > 0) {
|
||
//求出能有几个会被5整除的 因为在阶乘中5有1个5 25有2个5 所以说通过循环 来判断这个数究竟能被几个5整除
|
||
num += x / 5;
|
||
|
||
x /= 5;
|
||
}
|
||
return num;
|
||
}
|
||
|
||
public static void main(String[] args) {
|
||
Scanner scan = new Scanner(System.in);
|
||
long n = scan.nextLong();
|
||
long left = 0L;
|
||
long right = (long) 1e18 ;
|
||
|
||
while (left < right) {
|
||
long mid = (left + right) / 2;
|
||
|
||
if(n<=cale(mid)){
|
||
right = mid ;
|
||
}
|
||
else{
|
||
left = mid+1 ;
|
||
}
|
||
}
|
||
|
||
if(cale(right)!=n){
|
||
System.out.println(-1);
|
||
}
|
||
else{
|
||
System.out.println(right);
|
||
}
|
||
scan.close();
|
||
}
|
||
}
|
||
```
|
||
|
||
## 莫名其妙中间省略了好多
|
||
|
||
## 背包01dp
|
||
|
||
```java
|
||
n = in.nextInt();
|
||
m = in.nextInt();
|
||
int []v=new int[n+1];//价值
|
||
int []w=new int[n+1];//体积
|
||
for(int i=0;i<n;i++){
|
||
v[i]=in.nextInt();
|
||
w[i]=in.nextInt();
|
||
}
|
||
int [][]dp=new int[m+1][m+1];
|
||
for(int i=1;i<=n;i++){
|
||
for(int j=0;j<=m;j++){
|
||
dp[i][j]=dp[i-1][j];
|
||
if(j>=w[i]){
|
||
dp[i][j]=Math.max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
|
||
}
|
||
}
|
||
//////////////////////////////// ////////////////////////////////////////////////////////////////
|
||
一维优化
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner in = new Scanner(System.in);
|
||
int n, m;
|
||
n = in.nextInt();
|
||
m = in.nextInt();
|
||
int[] v = new int[n + 1];
|
||
int[] w = new int[n + 1];
|
||
for (int i = 0; i < n; i++) {
|
||
v[i] = in.nextInt();
|
||
w[i] = in.nextInt();
|
||
}
|
||
int[] dp = new int[m + 1];
|
||
for (int i = 0; i < n; i++) {
|
||
for (int j = m; j >= w[i]; j--) {//这是从后往前来的 只能这样 因为只有这样 不然从前往后的话就会多加
|
||
dp[j] = Math.max(dp[j], dp[ j - w[i] ] + v[i]);
|
||
/*
|
||
是这样的 因为啊 这个dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
|
||
需要等价于
|
||
dp[i][j]=dp[i-1][j];
|
||
if(j>=w[i]){
|
||
dp[i][j]=Math.max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
|
||
dp[j] = Math.max(dp[j] 是没有错的Math.max(dp[j] 是上一个的 其实就是等价于dp[i][j]=Math.max(dp[i][j]
|
||
可以这么认为 因为此时左边的dp[j]还没有被算出来 而右边的dp[j]是上一个dp[i-1][j]的 已经被算出来的
|
||
*/
|
||
|
||
}
|
||
}
|
||
in.close();
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
## 完全背包
|
||
|
||
```java
|
||
n = in.nextInt();
|
||
m = in.nextInt();
|
||
int []v=new int[n+1];//价值
|
||
int []w=new int[n+1];//体积
|
||
for(int i=0;i<n;i++){
|
||
v[i]=in.nextInt();
|
||
w[i]=in.nextInt();
|
||
}
|
||
int [][]dp=new int[m+1][m+1];
|
||
for(int i=1;i<=n;i++){
|
||
for(int j=0;j<=m;j++){
|
||
dp[i][j]=dp[i-1][j];
|
||
if(j>=w[i]){
|
||
dp[i][j]=Math.max(dp[i][j],dp[i][j-w[i]]+v[i]);
|
||
}
|
||
}
|
||
//注意这个 dp[i][j]=Math.max(dp[i][j],dp[i][j-w[i]]+v[i]);
|
||
|
||
其实完全背包和01背包差不多 都是依赖上一层的来推出下一层
|
||
只不过完全背包可以对同一个物品多次拿去 所以它的上一层就可能是自己发展过来的 所以就是dp[i][j-w[i]]+v[i]
|
||
|
||
////////////////////////////////////////////////////////////////////////////////////////////////
|
||
|
||
一维优化
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner in = new Scanner(System.in);
|
||
int n, m;
|
||
n = in.nextInt();
|
||
m = in.nextInt();
|
||
int[] v = new int[n + 1];
|
||
int[] w = new int[n + 1];
|
||
for (int i = 0; i < n; i++) {
|
||
v[i] = in.nextInt();
|
||
w[i] = in.nextInt();
|
||
}
|
||
int[] dp = new int[m + 1];
|
||
for (int i = 0; i < n; i++) {
|
||
for (int j =w[i]; j<=m; j++) {//这是从前往后来的 所以说就是可以直接从w[i]到m 跟上面的反着记就好了
|
||
dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
|
||
}
|
||
}
|
||
in.close();
|
||
}
|
||
}
|
||
```
|
||
|
||
## 多重背包
|
||
|
||
```java
|
||
import java.util.Scanner;
|
||
// 1:无需package
|
||
// 2: 类名必须Main, 不可修改
|
||
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner sc=new Scanner(System.in);
|
||
int n=sc.nextInt(),m=sc.nextInt();
|
||
int v[]=new int[n+1];
|
||
int w[]=new int[n+1];
|
||
int c[]=new int[n+1];
|
||
int dp[]=new int[m+1];
|
||
|
||
for (int i = 1; i <= n; i++) {
|
||
v[i]=sc.nextInt();
|
||
w[i]=sc.nextInt();
|
||
c[i]= sc.nextInt();
|
||
}
|
||
for (int i = 1; i <= n; i++) {
|
||
for (int j = m; j >=v[i]; j--) {
|
||
for (int k = 0; k*v[i]<=j&&k<=c[i] ; k++) {//不仅选的次数要关注容量 也要关注本身的限制
|
||
dp[j]=Math.max(dp[j],dp[j-k*v[i]]+k*w[i]);
|
||
}
|
||
}
|
||
}
|
||
System.out.println(dp[m]);
|
||
}
|
||
}
|
||
O(N*M*K)比较大 只能支持100的数值
|
||
|
||
```
|
||
|
||
## 区间DP
|
||
|
||
```JAVA
|
||
|
||
题目描述
|
||
在一条直线上有n堆石子，每堆有一定的数量，每次可以将两堆相邻的石子合并，合并后放在两堆的中间位置，合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。例如：输入{1，2，3，4，5}，输出33。【3+6+9+15=33】
|
||
输入
|
||
本题应该处理到文件尾，每组输入包括两行，第一行为石子堆的个数n，第二行则为每堆石子的个数。
|
||
输出
|
||
输出最小花费。
|
||
样例输入
|
||
5
|
||
1 2 3 4 5
|
||
样例输出
|
||
33
|
||
import java.util.Scanner;
|
||
|
||
// 1:无需package
|
||
// 2: 类名必须Main, 不可修改
|
||
public class Main {
|
||
static int N = 300;
|
||
static int[] s = new int[N];//前缀和
|
||
static int[][] dp = new int[N][N];//i j 这个数组的每一位ij 都代表的是i->j 的最少的花费
|
||
|
||
public static void main(String[] args) {
|
||
Scanner in = new Scanner(System.in);
|
||
int n=in.nextInt();
|
||
for(int i=1;i<=n;i++){
|
||
s[i]=in.nextInt()+s[i-1];
|
||
}
|
||
for(int len=2;len<=n;len++){
|
||
for(int l=1;len+l-1<=n;l++){
|
||
int r =len+l-1;
|
||
dp[l][r]=Integer.MAX_VALUE;
|
||
for(int k = l; k< r; k++){
|
||
dp[l][r]=Math.min(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);
|
||
}
|
||
}
|
||
}
|
||
System.out.println(dp[1][n]);
|
||
}
|
||
}
|
||
```
|
||
|