失败尽失常态！
目录
前缀和与差分
输入一个长度为 nn 的整数序列。
接下来再输入 mm 个询问，每个询问输入一对 l,rl,r。
对于每个询问，输出原序列中从第 ll 个数到第 rr 个数的和。
输入格式
第一行包含两个整数 nn 和 mm。
第二行包含 nn 个整数，表示整数数列。
接下来 mm 行，每行包含两个整数 ll 和 rr，表示一个询问的区间范围。
输出格式
共 mm 行，每行输出一个询问的结果。
数据范围
1≤l≤r≤n1≤l≤r≤n,
1≤n,m≤1000001≤n,m≤100000,
−1000≤数列中元素的值≤1000−1000≤数列中元素的值≤1000输入样例：
5 3 2 1 3 6 4 1 2 1 3 2 4输出样例：
3 6 10
import java.util.*;
public class Main {
private static int N = 100010; // 定义数组大小, 防止越界
public static void main(String[] args) {
// 初始化输入值
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[] arr = new int[N];
// 注意这里是从 1开始的
for (int i = 1; i <= n; i++)
arr[i] = in.nextInt();
// s[i]代表 arr的前 i项和
int s[] = new int[N];
s[0] = 0;
// 计算出 s[i]
for (int i = 1; i <= n; i++)
s[i] = s[i - 1] + arr[i]; // 注意运算方式
// 循环输出
while (m-- > 0) {
int l = in.nextInt();
int r = in.nextInt();
System.out.println(s[r] - s[l - 1]); // 关键
}
}
}
输入一个 nn 行 mm 列的整数矩阵，再输入 qq 个询问，每个询问包含四个整数 x1,y1,x2,y2x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 n，m，qn，m，q。
接下来 nn 行，每行包含 mm 个整数，表示整数矩阵。
接下来 qq 行，每行包含四个整数 x1,y1,x2,y2x1,y1,x2,y2，表示一组询问。
输出格式
共 qq 行，每行输出一个询问的结果。
数据范围
1≤n,m≤10001≤n,m≤1000,
1≤q≤2000001≤q≤200000,
1≤x1≤x2≤n1≤x1≤x2≤n,
1≤y1≤y2≤m1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000−1000≤矩阵内元素的值≤1000输入样例：
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输出样例：
17 27 21
难度：简单 时/空限制：2s / 64MB 总通过数：56389 总尝试数：79361 来源：模板题 算法标签
挑战模式
import java.util.*;
public class Main {
public static void main(String[] args) {
// 输入值进行初始化
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int q = in.nextInt();
// 初始化 arr
int[][] arr = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
arr[i][j] = in.nextInt();
// 输出查看 arr
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++)
// System.out.print(arr[i][j] + " ");
// }
// 求解 s[i][j]
int[][] s = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
// 计算, 结合图来理解
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + arr[i][j];
// 循环输出
while (q-- > 0) {
// 定位获取区间大小
int x1 = in.nextInt();
int y1 = in.nextInt();
int x2 = in.nextInt();
int y2 = in.nextInt();
// 计算, 结合图来理解
int res = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
System.out.println(res);
}
}
}
输入一个长度为 nn 的整数序列。
接下来输入 mm 个操作，每个操作包含三个整数 l,r,cl,r,c，表示将序列中 [l,r][l,r] 之间的每个数加上 cc。
请你输出进行完所有操作后的序列。
输入格式
第一行包含两个整数 nn 和 mm。
第二行包含 nn 个整数，表示整数序列。
接下来 mm 行，每行包含三个整数 l，r，cl，r，c，表示一个操作。
输出格式
共一行，包含 nn 个整数，表示最终序列。
数据范围
1≤n,m≤1000001≤n,m≤100000,
1≤l≤r≤n1≤l≤r≤n,
−1000≤c≤1000−1000≤c≤1000,
−1000≤整数序列中元素的值≤1000−1000≤整数序列中元素的值≤1000输入样例：
6 3 1 2 2 1 2 1 1 3 1 3 5 1 1 6 1输出样例：
3 4 5 3 4 2
难度：简单 时/空限制：1s / 64MB 总通过数：57990 总尝试数：77062 来源：模板题, Hulu面试题 算法标签
import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main {
static int N = 100010;
public static void main(String[] args) {
Scanner scanner = new Scanner(new BufferedInputStream(System.in));
int n = scanner.nextInt();
int m = scanner.nextInt();
//a为原数组，b为差分数组
int[] a = new int[N];
int[] b = new int[N];
for (int i = 1; i <= n; i++) {
a[i] = scanner.nextInt();
}
//进行n次插入，初始化差分数组
for(int i=1;i<=n;i++) {
insert(b, i, i, a[i]);
}
while(m-->0) {
int l,r,c;
l = scanner.nextInt();
r = scanner.nextInt();
c = scanner.nextInt();
insert(b, l, r, c);
}
//经过一系列插入操作后，现在答案数组应该是b数组的前缀和，让b数组变成b的前缀和。
//公式 b[i] = b[i-1] + b[i]
for(int i=1;i<=n;i++)b[i] +=b[i-1];
for(int i=1;i<=n;i++)System.out.print(b[i]+" ");
System.out.println();
scanner.close();
}
//插入操作函数
public static void insert(int[] a,int l,int r,int c) {
a[l]+=c;
a[r+1]-=c;
}
}
输入一个 nn 行 mm 列的整数矩阵，再输入 qq 个操作，每个操作包含五个整数 x1,y1,x2,y2,cx1,y1,x2,y2,c，其中 (x1,y1)(x1,y1) 和 (x2,y2)(x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上 cc。
请你将进行完所有操作后的矩阵输出。
输入格式
第一行包含整数 n,m,qn,m,q。
接下来 nn 行，每行包含 mm 个整数，表示整数矩阵。
接下来 qq 行，每行包含 55 个整数 x1,y1,x2,y2,cx1,y1,x2,y2,c，表示一个操作。
输出格式
共 nn 行，每行 mm 个整数，表示所有操作进行完毕后的最终矩阵。
数据范围
1≤n,m≤10001≤n,m≤1000,
1≤q≤1000001≤q≤100000,
1≤x1≤x2≤n1≤x1≤x2≤n,
1≤y1≤y2≤m1≤y1≤y2≤m,
−1000≤c≤1000−1000≤c≤1000,
−1000≤矩阵内元素的值≤1000−1000≤矩阵内元素的值≤1000输入样例：
3 4 3 1 2 2 1 3 2 2 1 1 1 1 1 1 1 2 2 1 1 3 2 3 2 3 1 3 4 1输出样例：
2 3 4 1 4 3 4 1 2 2 2 2
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
public static void main(String[] args) throws IOException {
//普遍Scanner会超时，所以使用BufferedReader
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
String[] str1 = reader.readLine().split(" ");
int n = Integer.parseInt(str1[0]);
int m = Integer.parseInt(str1[1]);
int q = Integer.parseInt(str1[2]);
int N = 1010;
int[][] a = new int[N][N];
int[][] b = new int[N][N];
// 读入原数组
for (int i = 1; i <= n; i++) {
String[] str2 = reader.readLine().split(" ");
for (int j = 1; j <= m; j++) {
a[i][j] = Integer.parseInt(str2[j-1]);
// 初始化差分数组
insert(b, i, j, i, j, a[i][j]);
}
}
while (q-- > 0) {
String[] str3 = reader.readLine().split(" ");
int x1 = Integer.parseInt(str3[0]);
int y1 = Integer.parseInt(str3[1]);
int x2 = Integer.parseInt(str3[2]);
int y2 = Integer.parseInt(str3[3]);
int k = Integer.parseInt(str3[4]);
insert(b, x1, y1, x2, y2, k);
}
// 求b数组的前缀和
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
b[i][j] += b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1];
//输出
writer.write(b[i][j] + " ");
}
writer.write("\n");
}
//所有write下的内容，会先存在writers中，当启用flush以后，会输出存在其中的内容。如果没有调用flush，则不会将writer中的内容进行输出。
writer.flush();
reader.close();
writer.close();
}
// 插入操作函数
private static void insert(int[][] b, int x1, int y1, int x2, int y2, int k) {
b[x1][y1] += k;
b[x2 + 1][y1] -= k;
b[x1][y2 + 1] -= k;
b[x2 + 1][y2 + 1] += k;
}
}
双指针算法
给定一个长度为 nn 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式
第一行包含整数 nn。
第二行包含 nn 个整数（均在 0∼1050∼105 范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤1051≤n≤105
输入样例：
5 1 2 2 3 5输出样例：
3
import java.util.Scanner;
public class Main{
static int n;
static int N = 100010;
static int[] a = new int[N], s = new int[N]; //这里的s针对的值只能是正整数，建议利用hashmap优化为O(1)
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for(int i = 0; i < n; i ++) a[i] = sc.nextInt();
int res = 0;
for(int i = 0, j = 0; i < n; i ++){
s[a[i]] ++;
while(j <= i && s[a[i]] > 1){
s[a[j]] --;
j ++;
}
res = Math.max(res, i - j + 1);
}
System.out.println(res);
}
}
给定两个升序排序的有序数组 AA 和 BB，以及一个目标值 xx。
数组下标从 00 开始。
请你求出满足 A[i]+B[j]=xA[i]+B[j]=x 的数对 (i,j)(i,j)。
数据保证有唯一解。
输入格式
第一行包含三个整数 n,m,xn,m,x，分别表示 AA 的长度，BB 的长度以及目标值 xx。
第二行包含 nn 个整数，表示数组 AA。
第三行包含 mm 个整数，表示数组 BB。
输出格式
共一行，包含两个整数 ii 和 jj。
数据范围
数组长度不超过 105105。
同一数组内元素各不相同。
1≤数组元素≤1091≤数组元素≤109输入样例：
4 5 6 1 2 4 7 3 4 6 8 9输出样例：
1 1
import java.util.Scanner;
public class Main{
static int n, m, x;
static int N = 100010;
static int[] a = new int[N], b = new int[N];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
x = sc.nextInt();
for(int i = 0; i < n; i ++){
a[i] = sc.nextInt();
}
for(int j = 0; j < m; j ++){
b[j] = sc.nextInt();
}
//O(n + m)
for(int i = 0, j = m - 1; i < n; i ++){
while(j > 0 && a[i] + b[j] > x) j --;
if(a[i] + b[j] == x) {
System.out.println(i + " " + j);
break;
}
}
}
}
给定一个长度为 nn 的整数序列 a1,a2,…,ana1,a2,…,an 以及一个长度为 mm 的整数序列 b1,b2,…,bmb1,b2,…,bm。
请你判断 aa 序列是否为 bb 序列的子序列。
子序列指序列的一部分项按原有次序排列而得的序列，例如序列 {a1,a3,a5}{a1,a3,a5} 是序列 {a1,a2,a3,a4,a5}{a1,a2,a3,a4,a5} 的一个子序列。
输入格式
第一行包含两个整数 n,mn,m。
第二行包含 nn 个整数，表示 a1,a2,…,ana1,a2,…,an。
第三行包含 mm 个整数，表示 b1,b2,…,bmb1,b2,…,bm。
输出格式
如果 aa 序列是 bb 序列的子序列，输出一行
Yes。否则，输出
No。数据范围
1≤n≤m≤1051≤n≤m≤105,
−109≤ai,bi≤109−109≤ai,bi≤109输入样例：
3 5 1 3 5 1 2 3 4 5输出样例：
Yes
import java.util.Scanner;
public class Main{
static int n, m;
static int N = 100010;
static int[] a = new int[N], b = new int[N];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for(int i = 0; i < n; i ++) a[i] = sc.nextInt();
for(int j = 0; j < m; j ++) b[j] = sc.nextInt();
int i = 0, j = 0;
while(i < n && j < m){
if(a[i] == b[j]) i ++;
j ++;
}
if(i == n) System.out.println("Yes");
else System.out.println("No");
}
}
位运算
给定一个长度为 nn 的数列，请你求出数列中每个数的二进制表示中 11 的个数。
输入格式
第一行包含整数 nn。
第二行包含 nn 个整数，表示整个数列。
输出格式
共一行，包含 nn 个整数，其中的第 ii 个数表示数列中的第 ii 个数的二进制表示中 11 的个数。
数据范围
1≤n≤1000001≤n≤100000,
0≤数列中元素的值≤1090≤数列中元素的值≤109输入样例：
5 1 2 3 4 5输出样例：
1 1 2 1 2
难度：简单 时/空限制：1s / 64MB 总通过数：45957 总尝试数：54407 来源：模板题 算法标签
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
while(n -- != 0){
int x = sc.nextInt();
int res = 0;
while(x != 0){
x -= lowbit(x);
res ++;
}
System.out.print(res + " ");
}
}
public static int lowbit(int x){
return x & -x;
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// 对输入数据进行初始化
Scanner in = new Scanner(System.in);
int n = in.nextInt();
// n次输出
while (n-- > 0) {
int target = in.nextInt();
int res = 0;
while (target != 0) {
target -= (target & -target); // 十进制进行计算
res++;
}
System.out.print(res + " ");
}
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// 对输入数据进行初始化
Scanner in = new Scanner(System.in);
int n = in.nextInt();
// n次输出
while (n-- > 0) {
int target = in.nextInt();
int res = 0;
while (target != 0) {
target -= (target & -target); // 十进制进行计算
res++;
}
System.out.print(res + " ");
}
}
}
离散化
假定有一个无限长的数轴，数轴上每个坐标上的数都是 00。
现在，我们首先进行 nn 次操作，每次操作将某一位置 xx 上的数加 cc。
接下来，进行 mm 次询问，每个询问包含两个整数 ll 和 rr，你需要求出在区间 [l,r][l,r] 之间的所有数的和。
输入格式
第一行包含两个整数 nn 和 mm。
接下来 nn 行，每行包含两个整数 xx 和 cc。
再接下来 mm 行，每行包含两个整数 ll 和 rr。
输出格式
共 mm 行，每行输出一个询问中所求的区间内数字和。
数据范围
−109≤x≤109−109≤x≤109,
1≤n,m≤1051≤n,m≤105,
−109≤l≤r≤109−109≤l≤r≤109,
−10000≤c≤10000−10000≤c≤10000输入样例：
3 3 1 2 3 6 7 5 1 3 4 6 7 8输出样例：
8 0 5
import java.util.*;
public class Main {
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); //n次操作
int m = sc.nextInt(); //m次询问
int N = 300010; //因为需要将所有x，l，r存在数组中，这样就是n + 2m <= 300000
int[] a = new int[N]; //从1开始，需要通过x找到离散量，然后+1，
int[] s = new int[N]; //前缀和来做，所以需要从1开始记录a
List<Integer> alls = new ArrayList<>(); //将所有的使用到的数存在alls中，比如x，l，r
//但其中会有先后顺序的差别，以及重复，所以需要排序和去重
List<Pairs> add = new ArrayList<>(); //用来存n次操作
List<Pairs> query = new ArrayList<>(); //用来存m次询问
for (int i = 0; i < n; i++) {
int x = sc.nextInt();
int c = sc.nextInt();
add.add(new Pairs(x, c));
alls.add(x); //存入alls中，为后续操作做准备
}
for (int i = 0; i < m; i++) {
int l = sc.nextInt();
int r = sc.nextInt();
query.add(new Pairs(l, r));
alls.add(l);
alls.add(r);
}
//到此为止，alls中存好了所有会被用到的数轴上的点，可以进行离散化操作
// 1. 排序 2. 去重
Collections.sort(alls);
int unique = unique(alls);
alls = alls.subList(0, unique); //将去重后的List保存下来，或者此处也可以将unique作为最后一个数，用r作为二分
for (Pairs item:add) {
int index = find(item.first, alls);
a[index] += item.second;
}
//求前缀和
for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];
for (Pairs item:query) {
int l = find(item.first, alls);
int r = find(item.second, alls);
System.out.println(s[r] - s[l - 1]);
}
}
//去重
static int unique(List<Integer> list) {
int j = 0;
for (int i = 0; i < list.size(); i++) {
if (i == 0 || list.get(i) != list.get(i - 1)) {
list.set(j, list.get(i));
j++;
}
}
return j;
}
static int find(int x, List<Integer> list) {
int l = 0;
int r = list.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (list.get(mid) >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l + 1; //因为要考虑到前缀和
}
}
class Pairs {
int first;
int second;
public Pairs(int first, int second) {
this.first = first;
this.second = second;
}
}
import java.util.Scanner;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), m = in.nextInt();
int[][] q = new int[m][2];
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int i = 0; i < n; i++) {
int add1 = in.nextInt();
int add2 = in.nextInt();
map.put(add1, map.getOrDefault(add1, 0) + add2);
}
for (int i = 0; i < m; i++) {
q[i][0] = in.nextInt();
map.put(q[i][0], map.getOrDefault(q[i][0], 0));
q[i][1] = in.nextInt();
map.put(q[i][1], map.getOrDefault(q[i][1], 0));
}
Object[] keys = map.keySet().toArray();
for (int i = 1; i < keys.length; i++) { // 前缀和
map.put((Integer) keys[i], map.get(keys[i-1]) + map.get(keys[i]));
}
for (int i = 0; i < m; i++) {
if(q[i][0] == (Integer)keys[0]){ // 避免空指针异常
System.out.println(map.ceilingEntry(q[i][1]).getValue());
}else{
System.out.println(map.ceilingEntry(q[i][1]).getValue() - map.lowerEntry(q[i][0]).getValue());
}
}
}
}
区间合并
给定 nn 个区间 [li,ri][li,ri]，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[1,3][1,3] 和 [2,6][2,6] 可以合并为一个区间 [1,6][1,6]。
输入格式
第一行包含整数 nn。
接下来 nn 行，每行包含两个整数 ll 和 rr。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。
数据范围
1≤n≤1000001≤n≤100000,
−109≤li≤ri≤109−109≤li≤ri≤109输入样例：
5 1 2 2 4 5 6 7 8 7 9输出样例：
3
import java.util.*;
public class Main{
private static int N = 100010;
private static int[] a;
private static ArrayList<int[]> list = new ArrayList();
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for(int i = 0;i < n;i++){
a = new int[2];
a[0] = scanner.nextInt();
a[1] = scanner.nextInt();
list.add(a);
}
//对列表中每个数组0位置元素升序排序
list.sort(new Comparator<int[]>(){
@Override
public int compare(int[] o1,int[] o2){
return o1[0] - o2[0];
}
});
int k = 0;
int r = Integer.MIN_VALUE;
for(int a[] : list){
//下一个区间左端点大于老区间右端点
if(a[0] > r){
k++;
}
//更新右端点
r = Math.max(r,a[1]);
}
System.out.println(k);
}
}
题目描述
有N个学生，每个学生的数据包括学号、姓名、3门课的成绩，从键盘输入N个学生的数据，要求打印出3门课的总平均成绩，以及最高分的学生的数据（包括学号、姓名、3门课成绩）
输入格式
学生数量N占一行每个学生的学号、姓名、三科成绩占一行，空格分开。
输出格式
各门课的平均成绩 最高分的学生的数据（包括学号、姓名、3门课成绩）
样例输入
2 1 blue 90 80 70 b clan 80 70 60样例输出
85 75 65 1 blue 90 80 70
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
class student{
//学号、姓名、三科
String id;
String name;
int a;
int b;
int c;
}
public class 结构体之成绩记录 {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
/*题目 1050: [编程入门]结构体之成绩记录
时间限制: 1Sec 内存限制: 128MB 提交: 9461 解决: 5387
题目描述
现有有N个学生的数据记录，每个记录包括学号、姓名、三科成绩。 编写一个函数input,用来输入一个学生的数据记录。
编写一个函数print,打印一个学生的数据记录。 在主函数调用这两个函数，读取N条记录输入，再按要求输出。 N<100*/
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
student [] stur=new student[n];
for (int i = 0; i < stur.length; i++) {
stur[i]=new student();
stur[i].id=scanner.next();
stur[i].name=scanner.next();
stur[i].a=scanner.nextInt();
stur[i].b=scanner.nextInt();
stur[i].c=scanner.nextInt();
}
//85 75 65
//1 blue 90 80 70
int a1=0,b2=0,c3=0;
for (student a : stur) {
a1+=a.a;
b2+=a.b;
c3+=a.c;
}
System.out.println(a1/n+" "+b2/n+" "+c3/n);
Arrays.sort(stur,new Comparator<student>() {
@Override
public int compare(student arg0, student arg1) {
// TODO Auto-generated method stub
return (arg0.a+arg0.b+arg0.c)/3>(arg1.a+arg1.b+arg1.c)/3?1:-1;
}
});
System.out.println(stur[n-1].id+" "+stur[n-1].name+" "+stur[n-1].a+" "+stur[n-1].b+" "+stur[n-1].c);
}
}