- 博客(120)
- 收藏
- 关注
RSS订阅原创 AcWing 795. 前缀和
输入一个长度为n的整数序列。接下来再输入m个询问，每个询问输入一对l, r。对于每个询问，输出原序列中从第l个数到第r个数的和。输入格式第一行包含两个整数n和m。第二行包含n个整数，表示整数数列。接下来m行，每行包含两个整数l和r，表示一个询问的区间范围。输出格式共m行，每行输出一个询问的结果。数据范围1≤l≤r≤n,1≤n,m≤100000,−1000≤数列中元素的值≤1...
2020-03-05 11:10:54
309
原创 AcWing 794. 高精度除法
给定两个正整数A，B，请你计算 A / B的商和余数。输入格式共两行，第一行包含整数A，第二行包含整数B。输出格式共两行，第一行输出所求的商，第二行输出所求余数。数据范围1≤A的长度≤100000,1≤B≤10000输入样例：72输出样例：31#include<iostream>#include<cstdio>#include<cstr...
2020-03-04 20:04:35
240
原创 AcWing 793. 高精度乘法
给定两个正整数A和B，请你计算A * B的值。输入格式共两行，第一行包含整数A，第二行包含整数B。输出格式共一行，包含A * B的值。数据范围1≤A的长度≤100000,1≤B≤10000输入样例：23输出样例：6#include <iostream>#include<cstdio>#include<cstring>#includ...
2020-03-04 17:07:07
293
原创 AcWing 792. 高精度减法
给定两个正整数，计算它们的差，计算结果可能为负数。输入格式共两行，每行包含一个整数。输出格式共一行，包含所求的差。数据范围1≤整数长度≤105输入样例：3211输出样例：21#include <iostream>#include<vector>using namespace std;bool cmp(vector<int> &...
2020-03-04 16:44:49
202
原创 AcWing 791. 高精度加法
给定两个正整数，计算它们的和。输入格式共两行，每行包含一个整数。输出格式共一行，包含所求的和。数据范围1≤整数长度≤100000输入样例：1223输出样例：35#include <iostream>#include<cstdio>#include<cstring>#include<algorithm>#include&...
2020-03-04 15:58:12
164
原创 AcWing 790. 数的三次方根
给定一个浮点数n，求它的三次方根。输入格式共一行，包含一个浮点数n。输出格式共一行，包含一个浮点数，表示问题的解。注意，结果保留6位小数。数据范围−10000≤n≤10000输入样例：1000.00输出样例：10.000000#include<iostream>#include<cstdio>#include<cstring>#in...
2020-03-04 11:17:01
180
原创 AcWing 789. 数的范围
给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。如果数组中不存在该元素，则返回“-1 -1”。输入格式第一行包含整数n和q，表示数组长度和询问个数。第二行包含n个整数（均在1~10000范围内），表示完整数组。接下来q行，每行包含一个整数k，表示一个询问元素。输出格式共q行，每行包含两个整数，表示所求...
2020-03-04 11:03:36
207
1
原创 AcWing 95. 费解的开关
你玩过“拉灯”游戏吗？25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态1011101101101111000011011在改变了最左上角的灯的状态后将变成：011...
2020-03-04 10:07:51
216
原创 AcWing 90. 64位整数乘法
求 a 乘 b 对 p 取模的值。输入格式第一行输入整数a，第二行输入整数b，第三行输入整数p。输出格式输出一个整数，表示a*b mod p的值。数据范围1≤a,b,p≤1018输入样例：345输出样例：2#include<cstdio>#include<cstring>using namespace std;typedef long lon...
2020-03-03 16:08:32
150
原创 AcWing 1273. 天才的记忆
从前有个人名叫 WNB，他有着天才般的记忆力，他珍藏了许多许多的宝藏。在他离世之后留给后人一个难题（专门考验记忆力的啊！），如果谁能轻松回答出这个问题，便可以继承他的宝藏。题目是这样的：给你一大串数字（编号为 1 到 N，大小可不一定哦！），在你看过一遍之后，它便消失在你面前，随后问题就出现了，给你 M 个询问，每次询问就给你两个数字 A,B，要求你瞬间就说出属于 A 到 B 这段区间内的最大...
2020-03-03 13:27:38
349
原创 AcWing 107. 超快速排序
在这个问题中，您必须分析特定的排序算法----超快速排序。该算法通过交换两个相邻的序列元素来处理n个不同整数的序列，直到序列按升序排序。对于输入序列9 1 0 5 4，超快速排序生成输出0 1 4 5 9。您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。输入格式输入包括一些测试用例。每个测试用例的第一行输入整数n，代表该用例中输入序列的长度。接下来n行每行输...
2020-03-03 12:51:32
218
原创 AcWing 106. 动态中位数
依次读入一个整数序列，每当已经读入的整数个数为奇数时，输出已读入的整数构成的序列的中位数。输入格式第一行输入一个整数P，代表后面数据集的个数，接下来若干行输入各个数据集。每个数据集的第一行首先输入一个代表数据集的编号的整数。然后输入一个整数M，代表数据集中包含数据的个数，M一定为奇数，数据之间用空格隔开。数据集的剩余行由数据集的数据构成，每行包含10个数据，最后一行数据量可能少于10个，...
2020-03-03 12:27:47
205
原创 AcWing 105. 七夕祭
七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。于是TYVJ今年举办了一次线下七夕祭。Vani同学今年成功邀请到了cl同学陪他来共度七夕，于是他们决定去TYVJ七夕祭游玩。TYVJ七夕祭和11区的夏祭的形式很像。矩形的祭典会场由N排M列共计N×M个摊点组成。虽然摊点种类繁多，不过cl只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。Vani预先联系了七夕祭的负...
2020-03-03 11:33:51
200
原创 AcWing 788. 逆序对的数量
给定一个长度为n的整数数列，请你计算数列中的逆序对的数量。逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。输入格式第一行包含整数n，表示数列的长度。第二行包含 n 个整数，表示整个数列。输出格式输出一个整数，表示逆序对的个数。数据范围1≤n≤100000输入样例：62 3 4 5...
2020-03-03 10:16:16
154
原创 AcWing 786. 第k个数
给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列的第k小的数是多少。输入格式第一行包含两个整数 n 和 k。第二行包含 n 个整数（所有整数均在1~109范围内），表示整数数列。输出格式输出一个整数，表示数列的第k小数。数据范围1≤n≤100000,1≤k≤n输入样例：5 32 4 1 5 3输出样例：3#include<algorithm&g...
2020-03-03 09:23:16
213
原创 AcWing 1058. 股票买卖 V
给定一个长度为 N 的数组，数组中的第 i 个数字表示一个给定股票在第 i 天的价格。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。输入格式第一行包含整数 N，表示数组长度。第二行包含 N 个不超过 10000 ...
2020-03-02 10:49:13
193
原创 AcWing 1057. 股票买卖 IV
给定一个长度为 N 的数组，数组中的第 i 个数字表示一个给定股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润，你最多可以完成 k 笔交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。一次买入卖出合为一笔交易。输入格式第一行包含整数 N 和 k，表示数组的长度以及你可以完成的最大交易数量。第二行包含 N 个不超过 10000 的正整数，表示完整的数组...
2020-03-02 10:22:02
250
原创 AcWing 1049. 大盗阿福
阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。这条街上一共有 N 家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？输入格式输入的第一行是一个整数 T，表示一共有...
2020-03-02 09:31:38
594
原创 AcWing 1016. 最大上升子序列和
一个数的序列 bi，当 b1<b2<…<bS 的时候，我们称这个序列是上升的。对于给定的一个序列(a1,a2,…,aN)，我们可以得到一些上升的子序列(ai1,ai2,…,aiK)，这里1≤i1<i2<…<iK≤N。比如，对于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。这些子序列中和最大为18，为子序列(1,...
2020-03-01 19:39:16
150
原创 AcWing 1012. 友好城市
Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。输入格式...
2020-03-01 19:30:36
176
原创 AcWing 482. 合唱队形
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<…Ti+1>…>TK(1≤i≤K)。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。输入格式输入的第一行...
2020-03-01 19:05:21
190
原创 AcWing 1014. 登山
五一到了，ACM队组织大家去登山观光，队员们发现山上一个有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？输入格式第一行包含整数N，表示景点数量。第二行包含...
2020-03-01 19:00:19
254
原创 AcWing 1017. 怪盗基德的滑翔翼
怪盗基德是一个充满传奇色彩的怪盗，专门以珠宝为目标的超级盗窃犯。而他最为突出的地方，就是他每次都能逃脱中村警部的重重围堵，而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。有一天，怪盗基德像往常一样偷走了一颗珍贵的钻石，不料却被柯南小朋友识破了伪装，而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。不得已，怪盗基德只能操作受损的滑翔翼逃脱。假设城市中一共有N幢建筑排成一条线，每幢建筑的高...
2020-03-01 18:33:38
392
原创 AcWing 896. 最长上升子序列 II
给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。输入格式第一行包含整数N。第二行包含N个整数，表示完整序列。输出格式输出一个整数，表示最大长度。数据范围1≤N≤100000，−109≤数列中的数≤109输入样例：73 1 2 1 8 5 6输出样例：4#include<iostream>#include<algorithm>...
2020-03-01 17:10:34
83
原创 AcWing 275. 传纸条
小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排坐成一个 m 行 n 列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给...
2020-03-01 16:24:01
199
原创 AcWing 1027. 方格取数
设有 N×N 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。如下图所示：某人从图中的左上角 A 出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。此人从 A 点到 B 点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。输入格式第一行为一个整数N，表示 N×N 的方格图。接...
2020-03-01 15:26:45
239
原创 AcWing 1018. 最低通行费
一个商人穿过一个N×N的正方形的网格，去参加一个非常重要的商务活动。他要从网格的左上角进，右下角出。每穿越中间1个小方格，都要花费1个单位时间。商人必须在(2N-1)个单位时间穿越出去。而在经过中间的每个小方格时，都需要缴纳一定的费用。这个商人期望在规定时间内用最少费用穿越出去。请问至少需要多少费用？注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。输入...
2020-03-01 14:42:02
195
原创 AcWing 1015. 摘花生
Hello Kitty想摘点花生送给她喜欢的米老鼠。她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。Hello Kitty只能向东或向南走，不能向西或向北走。问Hello Kitty最多能够摘到多少颗花生。1.gif输入格式第一行是一个整数T，代表一共有多少组...
2020-03-01 14:29:34
290
原创 AcWing 426. 开心的金明
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。...
2020-03-01 11:16:16
149
原创 AcWing 1013. 机器分配
总公司拥有M台 相同 的高效设备，准备分给下属的N个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。盈利与分配的设备数量有关。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M。输入格式第一行有两个数，第一个数是分公司数N，第二个数是设备台数M；接下来是一个N*M的矩阵，矩阵中的第 i 行第 j ...
2020-03-01 11:05:46
225
原创 AcWing 1020. 潜水员
潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸：一个为氧气，一个为氮气。让潜水员下潜的深度需要各种数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少？例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：3 36 12010 25 1295 50 25...
2020-03-01 10:30:42
293
原创 AcWing 6. 多重背包问题 III
有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。输入格式第一行两个整数，N，V (0<N≤1000, 0<V≤20000)，用空格隔开，分别表示物品种数和背包容积。接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示...
2020-03-01 09:58:08
168
原创 AcWing 8. 二维费用的背包问题
有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。输出最大价值。输入格式第一行两个整数，N，V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。接下来有 N 行，每行三个整数 vi,mi...
2020-02-29 22:54:41
69
原创 AcWing 7. 混合背包问题
有 N 种物品和一个容量是 V 的背包。物品一共有三类：第一类物品只能用1次（01背包）；第二类物品可以用无限次（完全背包）；第三类物品最多只能用 si 次（多重背包）；每种体积是 vi，价值是 wi。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。输入格式第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。接下来有 N 行，每...
2020-02-29 22:41:46
178
原创 AcWing 1019. 庆功会
为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。输入格式第一行二个数n，m，其中n代表希望购买的奖品的种数，m表示拨款金额。接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和能购买的最大数量（买0件到s件均可）。输出格式一行：一个数，表...
2020-02-29 22:21:00
160
原创 AcWing 532. 货币系统
在网友的国度中共有 n 种不同面额的货币，第 i 种货币的面额为 a[i]，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为 n、面额数组为 a[1…n] 的货币系统记作 (n,a)。在一个完善的货币系统中，每一个非负整数的金额 x 都应该可以被表示出，即对每一个非负整数 x，都存在 n 个非负整数 t[i] 满足 a[i]× t[i] 的和为 x。然而，在网友的国度中，货币系统...
2020-02-29 21:50:29
183
原创 AcWing 1021. 货币系统
给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。输入格式第一行，包含两个整数n和m。接下来n行，每行包含一个整数，表示一种货币的面值。输出格式共一行，包含一个整数，表示方案数。数据范围n≤15,m≤3000输入样例：3 10125输出样例：10#include<iostream>#include<cstring>#includ...
2020-02-29 18:57:43
200
原创 AcWing 1023. 买书
小明手里有n元钱全部用来买书，书的价格为10元，20元，50元，100元。问小明有多少种买书方案？（每种书可购买多本）输入格式一个整数 n，代表总共钱数。输出格式一个整数，代表选择方案种数。数据范围0≤n≤1000输入样例1：20输出样例1：2输入样例2：15输出样例2：0输入样例3：0输出样例3：1#include<iostream>#inc...
2020-02-29 18:43:56
129
原创 AcWing 278. 数字组合
给定N个正整数A1,A2,…,AN，从中选出若干个数，使它们的和为M，求有多少种选择方案。输入格式第一行包含两个整数N和M。第二行包含N个整数，表示A1,A2,…,AN。输出格式包含一个整数，表示可选方案数。数据范围1≤N≤100,1≤M≤10000,1≤Ai≤1000输入样例：4 41 1 2 2输出样例：3#include<iostream>#inc...
2020-02-29 18:32:06
295
原创 AcWing 1022. 宠物小精灵之收服
宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。小智也想收服其中的一些小精灵。然而，野生的小精灵并不那么容易被收服。对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。当皮卡丘的体力小于等于0时，小智就必须结束狩猎（因为...
2020-02-29 18:09:20
162
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人