如何快速且高效学习算法/刷题

不刷过难的题

见到新知识点—>学习(学思路，不是学代码)—>做模板题—>做带该知识点tag的简单题

力求精通，不要“差不多先生”

感觉自己可能没懂，一定要问，直到自己精通该知识点为止。
感觉可能懂了，也一定要自己去做一些题目验证一下是不是真懂了。
精通的判别标准：对于一个知识点，立刻能在脑海里形成代码，并迅速码出来。

练好debug的能力

首先一定要自己尝试debug，哪怕实在调不出来了，问老师了，也一定要总结。

一是总结错误原因，争取下次不犯同样错误。
二是总结debug的方式，下次哪怕遇到类似的问题也能自己解决。千万不要“这道题错了，找老师答疑，调过了就ok”
最佳状态是：遇到一个题，就算第一次提交没过，经过自己的debug找到错误的根源，然后调过了。这样的收益是远远大于通过答疑知道自己bug的收益。

笔试小技巧

根据数据范围猜知识点

一般1s时间限制的题目，时间复杂度能跑到1e8左右（python和java会少一些，所以建议大家使用c/c++做笔试题）。

n范围20以内：O(n*2^n) 状压搜索/dfs暴搜
n范围200以内：O(n^3) 三维dp
范围3000以内：O(n^2) 二维dp 背包枚举二维前缀和等
范围1e5以内：O(n√n) 暴力求因子等
范围1e6以内：O(nlogn) 二分答案使用各种stl 并查集欧拉筛等
范围1e7以内：O(n) 双指针线性dp 差分/前缀和
范围1e14以内：O(√n) 求约数和约数个数

遇到不会的，善于写暴力

举例：
1e6范围 O(n)或O(nlogn)没思路，但有一个O(n^2)的枚举的思路，实在想不出正解就写个暴力拿部分分。

编程题

点击消除

题目

牛牛拿到了一个字符串。他每次“点击”，可以把字符串中相邻两个相同字母消除，例如，字符串”abbc”点击后可以生成”ac”。但相同而不相邻、不相同的相邻字母都是不可以被消除的。牛牛想把字符串变得尽可能短。他想知道，当他点击了足够多次之后，字符串的最终形态是什么？

输入描述

输出描述

示例1

示例2

示例3

代码

import java.util.Scanner;

/**
 * @author liuwq
 * @create 2023-03-27 16:43
 */
public class 点击消除 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        StringBuilder sb = new StringBuilder(s.length());
        int j = -1;
        for (int i = 0; i < s.length(); i++){
            if (j == -1 || sb.charAt(j) != s.charAt(i)){
                sb.append(s.charAt(i));
                j++;
            }else {
                sb.deleteCharAt(j--);
            }
        }
        System.out.println(sb.length() != 0 ? sb.toString():0);
    }
}

计划清单

题目

小明设计了某个CPU，可是这个CPU有个缺点，习惯先做简单的任务，再做难的任务。
小明有一个做任务的计划清单，当CPU拿到这些任务时，CPU会依次检查当前任务的难度，按照以下规则加入清单：

如果清单为空，CPU会直接把当前任务加入清单。
如果当前的任务比清单中最简单的任务难度还要低，那么CPU会把当前任务插入清单的第一位的前面（马上即将做的任务）。
如果当前的任务比清单中最难的任务难度还要高，那么CPU会把当前任务插入清单的最后一位的后面（最后做的任务）。
如果不是以上三种情况，CPU将放弃该任务。

现在小明拿到了一系列任务，知道了每个任务对应的难度，请按顺序输出CPU最终计划清单的任务列表。

输入描述

输出描述

示例

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * @author liuwq
 * @create 2023-03-28 10:24
 */
public class 计划清单 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int max = 0, min = 0;
        Deque<String> deque = new ArrayDeque<>();
        for (int i = 0; i < n; i++){
            String[] s = br.readLine().split(" ");
            String name = s[0];
            int diff = Integer.parseInt(s[1]);
            if (deque.isEmpty()){
                deque.add(name);
                max = diff;
                min = diff;
            }else if (diff < min){
                deque.addFirst(name);
                min = diff;
            }else if (diff > max){
                deque.addLast(name);
                max = diff;
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append(deque.size() + "\n");
        while (!deque.isEmpty()){
            sb.append(deque.removeFirst() + "\n");
        }
        System.out.println(sb);
    }
}

算术教室

题目

琪露诺的算术教室又双叒开课啦！
这一次，琪露诺要问你这样一个问题：
已知A数组有 n 个数： $a_1,a_2...a_n\$

B数组有 m 个数： $b_1,b_2...b_m\$
琪露诺给你一个数 x ，问你是否可以做到在A和B中各取一个数（记为 ai 和 bj），满足 $a_i b_j=x\$

输入描述

输出描述

示例

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

/**
 * @author liuwq
 * @create 2023-04-01 11:00
 */
public class 算术教室 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        int x = Integer.parseInt(s[2]);
        String[] s1 = br.readLine().split(" ");
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++){
            set.add(x - Integer.parseInt(s1[i]));
        }
        String[] s2 = br.readLine().split(" ");
        for (int i = 0; i < m; i++){
            if (set.contains(Integer.parseInt(s2[i]))){
                System.out.println("YES");
                return;
            }
        }
        System.out.println("NO");
    }
}

kotori和n皇后

题目

kotori最近在研究n皇后的问题。

所谓n皇后问题是这样的：一个n*n的地图，上面一共放n个皇后，保证任意两个皇后都不能互相攻击（每个皇后可以攻击同一行、同一列以及同一45度角斜线和135度角斜线上的所有其他皇后）。

kotori思考了很久都无法得出答案，整个人都变成琴梨了。她于是拿了一堆皇后在一个无穷大的棋盘上模拟，按照次序一共放了k个皇后。但是，皇后的站位太复杂了，kotori甚至不知道是否存在两个皇后会互相攻击。于是她想问问聪明的你，在第i个皇后放置在棋盘上之后，是否存在两个皇后可以互相攻击？

输入描述

输出描述

示例

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

/**
 * @author liuwq
 * @create 2023-04-02 14:30
 */
public class kotori和n皇后 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine());
        Set<Integer> setX = new HashSet<>();
        Set<Integer> setY = new HashSet<>();
        Set<Integer> setA = new HashSet<>();
        Set<Integer> setS = new HashSet<>();
        int flag = 0;
        for (int i = 1; i <= k; i++){
            String[] s = br.readLine().split(" ");
            int x = Integer.parseInt(s[0]);
            int y = Integer.parseInt(s[1]);
            if (flag != 0) continue;
            if (!setX.add(x) || !setY.add(y) || !setA.add(x+y) || !setS.add(x-y)){
                flag = i; //找到第几个皇后是最小不重复的
            }
        }
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < t; i++){
            int index = Integer.parseInt(br.readLine());
            String a = (index < flag || flag == 0) ? "No":"Yes";
            sb.append(a);
            sb.append("\n");
        }
        System.out.println(sb);
    }
}