-
Vim2
22222 my vim config git repositoryhttps://github.com/Janglejay/vim-confighttps://gitee.com/janglejay/vim-config…
-
状态压缩
AcWing 1064. 小国王 原题链接在 n×nn×n 的棋盘上放 kk 个国王，国王可攻击相邻的 88 个格子，求使它们无法互相攻击的方案总数。输入格式共一行，包含两个整数 nn 和 kk。输出格式共一行，表示方案总数，若不能够放置则输出00。数据范围1≤n≤101≤n≤10,0≤k≤n20≤k≤n2输入样例：3 2输出样例：16题目思路 private static int n; private static int m; private static int...…
-
状态机模型
AcWing 1049. 大盗阿福 原题链接阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。这条街上一共有 NN 家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？输入格式输入的第一行是一个整数 TT，表示一共有 TT 组数据。接下来的每组数据，第一行是一个整数 N...…
-
背包模型4
AcWing 1021. 货币系统 原题链接给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。输入格式第一行，包含两个整数n和m。接下来n行，每行包含一个整数，表示一种货币的面值。输出格式共一行，包含一个整数，表示方案数。数据范围n≤15,m≤3000n≤15,m≤3000输入样例：3 10125输出样例：10题目思路 public static void main(String[] args) { int n = in.nextInt(); ...…
-
背包模型3
AcWing 12. 背包问题求具体方案 原题链接有 NN 件物品和一个容量是 VV 的背包。每件物品只能使用一次。第 ii 件物品的体积是 vivi，价值是 wiwi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N1…N。输入格式第一行两个整数，N，VN，V，用空格隔开，分别表示物品数量和背包容积。接下来有 NN 行，每行两个整数 vi,wivi,wi，用空格隔开...…
-
背包模型2
AcWing 8. 二维费用的背包问题 原题链接有 NN 件物品和一个容量是 VV 的背包，背包能承受的最大重量是 MM。每件物品只能用一次。体积是 vivi，重量是 mimi，价值是 wiwi。求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。输出最大价值。输入格式第一行两个整数，N，V,MN，V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。接下来有 NN 行，每行三个整数 vi,mi,wivi,mi,wi，...…
-
背包模型1
多重背包-单调队列优化按照自己的理解说了一遍，心中还是有存疑，等之后看看会不会理解透再更新AcWing 6. 多重背包问题 III 原题链接有 NN 种物品和一个容量是 VV 的背包。第 ii 种物品最多有 sisi 件，每件体积是 vivi，价值是 wiwi。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。输入格式第一行两个整数，N，VN，V (0<N≤1000(0<N≤1000, 0<V≤20000)0<V≤20000)...…
-
最长上升子序列模型2
AcWing 1010. 拦截导弹 原题链接某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。...…
-
最长上升子序列模型1
AcWing 1017. 怪盗基德的滑翔翼 原题链接怪盗基德是一个充满传奇色彩的怪盗，专门以珠宝为目标的超级盗窃犯。而他最为突出的地方，就是他每次都能逃脱中村警部的重重围堵，而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。有一天，怪盗基德像往常一样偷走了一颗珍贵的钻石，不料却被柯南小朋友识破了伪装，而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。不得已，怪盗基德只能操作受损的滑翔翼逃脱。假设城市中一共有N幢建筑排成一条线，每幢建筑的高度各不相同。初始时，怪盗基德可以在任何一幢建筑...…
-
递推与递归
AcWing 95. 费解的开关 原题链接你玩过“拉灯”游戏吗？25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态1011101101101111000011011在改变了最左上角的灯的状态后将变成：0111111101101111000011011再改变它正中间的灯后...…
-
排序
AcWing 105. 七夕祭 原题链接七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。于是TYVJ今年举办了一次线下七夕祭。Vani同学今年成功邀请到了cl同学陪他来共度七夕，于是他们决定去TYVJ七夕祭游玩。TYVJ七夕祭和11区的夏祭的形式很像。矩形的祭典会场由N排M列共计N×M个摊点组成。虽然摊点种类繁多，不过cl只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。Vani预先联系了七夕祭的负责人zhq，希望能够通过恰当地布置会场，使得各行中cl感兴趣的...…
-
前缀和与差分
AcWing 99. 激光炸弹 原题链接地图上有 NN 个目标，用整数Xi,YiXi,Yi表示目标在地图上的位置，每个目标都有一个价值WiWi。注意：不同目标可能在同一位置。现在有一种新型的激光炸弹，可以摧毁一个包含 R×RR×R 个位置的正方形内的所有目标。激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和x，yx，y轴平行。求一颗炸弹最多能炸掉地图上总价值为多少的目标。输入格式第一行输入正整数 NN 和 RR ,分别代表地图上的目标数目和正方形的...…
-
位运算
龟速乘AcWing 90. 64位整数乘法 原题链接求 aa 乘 bb 对 pp 取模的值。输入格式第一行输入整数aa，第二行输入整数bb，第三行输入整数pp。输出格式输出一个整数，表示a*b mod p的值。数据范围1≤a,b,p≤10181≤a,b,p≤1018输入样例：345输出样例：2 private static long quickAdd(long a, long b, long p) { long res = 0L; while (b &...…
-
二分算法
AcWing 102. 最佳牛围栏 原题链接农夫约翰的农场由 NN 块田地组成，每块地里都有一定数量的牛,其数量不会少于1头，也不会超过2000头。约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。围起区域内至少需要包含 FF 块地，其中 FF 会在输入中给出。在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。输入格式第一行输入整数 NN 和 FF ，数据间用空格隔开。接下来 NN 行，每行输入一个整数，第i+1...…
-
RMQ
RMQRMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题。AcWing 1273. 天才的记忆 原题链接从前有个人名叫 WNB，他有着天才般的记忆力，他珍藏了许多许多的宝藏。在他离世之后留给后人一个难题（专门考验记忆力的啊！），如果谁能轻松回答出这个问题，便可以继承他的宝藏。题目是这样的：给你一大串数字...…
-
数字三角形模型
数字三角形模型AcWing 1015. 摘花生 原题链接Hello Kitty想摘点花生送给她喜欢的米老鼠。她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。Hello Kitty只能向东或向南走，不能向西或向北走。问Hello Kitty最多能够摘到多少颗花生。输入格式第一行是一个整数T，代表一共有多少组数据。接下来是T组数据。每组数据的第一行是两个整数，分别代...…
-
记忆化搜索
AcWing 901. 滑雪 原题链接给定一个R行C列的矩阵，表示一个矩形网格滑雪场。矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。下面给出一个矩阵作为例子： 1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9在给定矩阵中...…
-
树形DP
AcWing 285. 没有上司的舞会 原题链接Ural大学有N名职员，编号为1~N。他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。每个职员有一个快乐指数，用整数 HiHi 给出，其中 1≤i≤N1≤i≤N。现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。输入格式第一行一个整数N。接下来N行，第 i 行表示 i 号职员的快乐指数HiHi。接下来N-1行...…
-
计数类DP
整数划分AcWing 900. 整数划分 原题链接一个正整数nn可以表示成若干个正整数之和，形如：n=n1+n2+…+nkn=n1+n2+…+nk，其中n1≥n2≥…≥nk,k≥1n1≥n2≥…≥nk,k≥1。我们将这样的一种表示称为正整数n的一种划分。现在给定一个正整数n，请你求出n共有多少种不同的划分方法。输入格式共一行，包含一个整数n。输出格式共一行，包含一个整数，表示总划分数量。由于答案可能很大，输出结果请对109+7109+7取模。数据范围1≤n≤10001≤n≤1000输入...…
-
状态压缩DP
AcWing 291. 蒙德里安的梦想 原题链接求把NM的棋盘分割成若干个12的的长方形，有多少种方案。例如当N=2，M=4时，共有5种方案。当N=2，M=3时，共有3种方案。如下图所示：输入格式输入包含多组测试用例。每组测试用例占一行，包含两个整数N和M。当输入用例N=0，M=0时，表示输入终止，且该用例无需处理。输出格式每个测试用例输出一个结果，每个结果占一行。数据范围1≤N,M≤111≤N,M≤11输入样例：1 21 31 42 22 32 42 114 110 0输出样例：10...…
