-
数位DP
计数问题AcWing 338. 计数问题 原题链接给定两个整数 a 和 b，求 a 和 b 之间的所有数字中0~9的出现次数。例如，a=1024，b=1032，则 a 和 b 之间共有9个数如下：1024 1025 1026 1027 1028 1029 1030 1031 1032其中‘0’出现10次，‘1’出现10次，‘2’出现7次，‘3’出现3次等等…输入格式输入包含多组测试数据。每组测试数据占一行，包含两个整数 a 和 b。当读入一行为0 0时，表示输入终止，且该行不作处理。输...…
-
线性DP
数字三角形最长上升子序列最长公共子序列最短编辑距离AcWing 898. 数字三角形 原题链接给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。 7 3 8 8 1 0 2 7 4 44 5 2 6 5输入格式第一行包含整数n，表示数字三角形的层数。接下来n行，每行包含若干整数，其中第 i 行表示数字三角...…
-
区间DP
石子合并AcWing 282. 石子合并 原题链接设有N堆石子排成一排，其编号为1，2，3，…，N。每堆石子有一定的质量，可以用一个整数来描述，现在要将这N堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。例如有4堆石子分别为 1 3 5 2， 我们可以先合并1、2堆，代价为4，得到4 5 2， 又合并 1，2堆，代价为9，得到9 2 ，再合并得到11，总代价为4+9+...…
-
进制转换
10进制转b进制b进制转10进制 private static int uget(char c) { if (c <= '9') return c - '0'; return c - 'A' + 10; } private static int base10(String num, int b) { int res = 0; for (char c : num.toCharArray()) { ...…
-
桶排序
桶排序基数排序public class RadixSort { private static int[] sort(int[] arr) { int[] temp = new int[arr.length]; int[] count = new int[10]; int mul = 1; for (int i = 0; i < 3; i++) { mul *= 10; for (...…
-
动态规划统一解题思路
动态规划统一解题思路 状态表示f(i,j....) 集合：每一个状态表示一类集合 集合代表的意义 集合要满足的条件 属性：max,min,count等 状态计算 集合划分：将集合划分成若干个子集使得，整个集合可以由子集表示出来 集合划分的原则：不重不漏 每一个元素会且仅会存在于某一个集合 ...…
-
背包问题
01背包问题完全背包问题多重背包问题分组背包问题AcWing 2. 01背包问题 原题链接有 NN 件物品和一个容量是 VV 的背包。每件物品只能使用一次。第 ii 件物品的体积是 vivi，价值是 wiwi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。输入格式第一行两个整数，N，VN，V，用空格隔开，分别表示物品数量和背包容积。接下来有 NN 行，每行两个整数 vi,wivi,wi，用空格隔开，分别表示第 ii 件物品的体积和价值。输出格式...…
-
高斯消元
高斯消元算法步骤 枚举每一列c 找到当前这一列中绝对值最大的一行 将这行换到最上面行（i）的位置，（第一次最上面行就是第一行） 将该行第一个数变成1，即所在行的数除以同一个数 将下面所有行的第c列消成0，即列元素所在行同时加减某个数 此时第c列以及最上面的行已固定，继续枚举后面的列，最上面的行更新成（i+1） AcWing 883. 高斯消元解线性方程组 原题链接输入一个包含n个方程n个未知数的线性方程组。方程组中的...…
-
绝对值不等式
绝对值不等式AcWing 104. 货仓选址 原题链接在一条数轴上有 NN 家商店，它们的坐标分别为 A1A1~ANAN。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。输入格式第一行输入整数N。第二行N个整数A1A1~ANAN。输出格式输出一个整数，表示距离之和的最小值。数据范围1≤N≤1000001≤N≤100000,0≤Ai≤400000≤Ai≤40000输入样例：46 2 9 1输出...…
-
简单博弈论
公平组合游戏ICG若一个游戏满足 由两名玩家交替行动 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关(游戏的局势不能区分玩家的身份，例如黑白棋就是不行的) 不能行动的玩家判负两种状态先手必败状态:不管怎么操作，剩下的状态都是先手必胜状态先手必胜状态 :存在一种操作可以将状态转成先手必败状态Nim游戏结论SG函数AcWing 891. Nim游戏 原题链接给定nn堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进...…
-
推公式
AcWing 125. 耍杂技的牛 原题链接农民约翰的N头奶牛（编号为1..N）计划逃跑并加入马戏团，为此它们决定练习表演杂技。奶牛们不是非常有创意，只提出了一个杂技表演：叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。这N头奶牛中的每一头都有着自己的重量WiWi以及自己的强壮程度SiSi。一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛...…
-
排序不等式
排序不等式AcWing 913. 排队打水 原题链接有 nn 个人排队到 1 个水龙头处打水，第 ii 个人装满水桶所需的时间是 titi，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？输入格式第一行包含整数 nn。第二行包含 nn 个整数，其中第 ii 个整数表示第 ii 个人装满水桶所花费的时间 titi。输出格式输出一个整数，表示最小的等待时间之和。数据范围1≤n≤1051≤n≤105,1≤ti≤1041≤ti≤104输入样例：73 6 1 4 2 5 7输出样例：5...…
-
容斥原理
容斥原理AcWing 890. 能被整除的数 原题链接给定一个整数nn和mm个不同的质数p1,p2,…,pmp1,p2,…,pm。请你求出11~nn中能被p1,p2,…,pmp1,p2,…,pm中的至少一个数整除的整数有多少个。输入格式第一行包含整数nn和mm。第二行包含mm个质数。输出格式输出一个整数，表示满足条件的整数的个数。数据范围1≤m≤161≤m≤16,1≤n,pi≤1091≤n,pi≤109输入样例：10 22 3输出样例：7题目思路 public static vo...…
-
区间问题
区间问题AcWing 905. 区间选点 原题链接给定N个闭区间[ai,biai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。输出选择的点的最小数量。位于区间端点上的点也算作区间内。输入格式第一行包含整数N，表示区间数。接下来N行，每行包含两个整数ai,biai,bi，表示一个区间的两个端点。输出格式输出一个整数，表示所需的点的最小数量。数据范围1≤N≤1051≤N≤105,−109≤ai≤bi≤109−109≤ai≤bi≤109输入样例：3-1 12 43...…
-
Huffman树
Huffman树是完全二叉树Huffman树构造方法假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为： 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和 从森林中删除选取的两棵树，并将新树加入森林 重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树AcWing 1...…
-
组合数
组合数根据数据量选择合适的方式卡特兰数组合恒等式AcWing 885. 求组合数 I 原题链接给定nn组询问，每组询问给定两个整数a，ba，b，请你输出Cba mod (109+7)Cab mod (109+7)的值。输入格式第一行包含整数nn。接下来nn行，每行包含一组aa和bb。输出格式共nn行，每行输出一个询问的解。数据范围1≤n≤100001≤n≤10000,1≤b≤a≤20001≤b≤a≤2000输入样例：33 15 32 2输出样例：3101 private stat...…
-
欧拉函数
欧拉函数筛法求欧拉函数欧拉定理AcWing 873. 欧拉函数 原题链接给定n个正整数aiai，请你求出每个数的欧拉函数。欧拉函数的定义 1 ~ N 中与 N 互质的数的个数被称为欧拉函数，记为ϕ(N)ϕ(N)。若在算数基本定理中，N=pa11pa22…pammN=p1a1p2a2…pmam，则：ϕ(N)ϕ(N) = N∗p1−1p1∗p2−1p2∗…∗pm−1pmN∗p1−1p1∗p2−1p2∗…∗pm−1pm输入格式第一行包含整数n。接下来n行，每行包含一个正整数aiai。输出格...…
-
扩展欧几里得算法
裴蜀定理扩展欧几里得算法线性同余方程AcWing 877. 扩展欧几里得算法 原题链接给定nn对正整数ai,biai,bi，对于每对数，求出一组xi,yixi,yi，使其满足ai∗xi+bi∗yi=gcd(ai,bi)ai∗xi+bi∗yi=gcd(ai,bi)。输入格式第一行包含整数n。接下来n行，每行包含两个整数ai,biai,bi。输出格式输出共n行，对于每组ai,biai,bi，求出一组满足条件的xi,yixi,yi，每组结果占一行。本题答案不唯一，输出任意满足条件的xi,yi...…
-
中国剩余定理
中国剩余定理AcWing 204. 表达整数的奇怪方式 原题链接输入格式第11 行包含整数 nn。第 22..n+1n+1行：每 i+1i+1 行包含两个整数aiai和mimi,数之间用空格隔开。输出格式输出最小非负整数 xx，如果 xx 不存在，则输出 −1−1。如果存在 xx，则数据保证 xx 一定在64位整数范围内。数据范围1≤ai≤231−11≤ai≤231−1,0≤mi<ai0≤mi<ai1≤n≤251≤n≤25输入样例：28 711 9输出样例：31 st...…
-
质数
质数质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。定义质数又称素数。试除法判定质数分解质因数质数筛埃氏筛法线性筛法AcWing 866. 试除法判定质数 原题链接给定n个正整数aiai，判定每个数是否是质数。输入格式第一行包含整数n。接下来n行，每行包含一个正整数aiai。输出格式共n行，其中第 i 行输出第 i 个正整数aiai是否为质数，是则输出“Yes”，否则输出“No”。数据范围1≤n≤1001≤n≤100,1≤ai≤231−11≤ai≤231−1输入样...…
