Severus. - 个人主页动态 - 牛客网

发布(63) 刷题

2022-01-11 22:18

C++

2021 ICPC NanJing D

2021 ICPC NanJing D 题目链接 题意 def Sort(A): n = len(A) for i in range(n): for j in range(n): if a[i] < a[j]: swap(a[i], a[j]) 给定长度为nnn的序列AAA，求序列AAA长度为kkk的前缀序列执行上述代码时进行交换操作的次数(1≤k≤n)(1\leq k\leq n)(1≤k≤n) 数据范围 1≤n≤1051 \leq n \leq 10^51≤n≤105 1≤ai≤n1 \leq a_i \leq n1≤ai≤n ...

0 点赞评论收藏

转发

2022-01-09 17:44

C++

Atcoder abc 234 G

Atcoder abc 234 G 题目链接 题意 对于长度为 n \ n\  n 的序列 ai \ a_i\  ai ，有 2n−1 \ 2^{n-1}\  2n−1 种方案将其划分为非空连续的子区间B1,B2,...,Bk B_1, B_2, ... ,B_k\ B1,B2,...,Bk ，对于所有划分方法，求出其关于以下式子对 998244353 \ 998244353\  998244353 取模后的...

0 点赞评论收藏

转发

2022-01-07 18:14

C++

字符串 & 计算几何优惠链接

计算几何： https://www.nowcoder.com/courses/cover/live/737?coupon=AJ47lQc 字符串： https://www.nowcoder.com/courses/cover/live/738?coupon=AeHSQE8 用链接后加我QQ：2241921218 每科返现再10元 120元拿下优质课程

0 点赞评论收藏

转发

2020-08-20 10:05

C++

矩阵消除游戏

题目描述 牛妹在玩一个名为矩阵消除的游戏，矩阵的大小是行列，第行第列的单元格的权值为，牛妹可以进行个回合的游戏，在每个回合，牛妹可以选择一行或者选择一列，然后将这一行或者这一列的所有单元格中的权值变为，同时牛妹的分数会加上这一行或者这一列中的所有单元格的权值的和。 牛妹想最大化她的得分，球球你帮帮她吧！ 输入描述: 第一行三个整数n,m,k接下来n行每h行m个整数表示矩阵中各个单元格的权值。 输出描述: 输出一个整数表示牛妹能获得的最大分数。 题解 为什么不能贪心的每次找行或列的最大值因为选列行或列之和，对列或行有影响，即选不同的行产生的最大不一样也就是不满足无后效性故贪心有问题 发现数据只有...

0 点赞评论收藏

转发

2020-08-20 08:51

C++

题目描述 上课的时候总有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的D对同学上课时会交头接耳。同学们在教室中坐成了M行N列，坐在第i行第j列的同学的位置是（i，j），为了方便同学们进出，在教室中设置了K条横向的通道，L条纵向的通道。于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳...

0 点赞评论收藏

转发

2020-08-08 20:52

C++

题目描述 “你，你认错人了。我真的，真的不是食人魔。”--蓝魔法师给出一棵树，求有多少种删边方案，使得删后的图每个连通块大小小于等于k，两种方案不同当且仅当存在一条边在一个方案中被删除，而在另一个方案中未被删除，答案对998244353取模 输入描述: 第一行两个整数n,k, 表示点数和限制2 <= n <= 2000, 1 <= k <= 2000接下来n-1行，每行包括两个整数u,v，表示u,v两点之间有一条无向边保证初始图联通且合法 输出描述: 共一行，一个整数表示方案数对998244353取模的结果 题解 为什么拖了好几天才写，dp杀我呜呜呜 ...

0 点赞评论收藏

转发

2020-08-06 23:02

C++

题目描述 小明现在要追讨一笔债务，已知有n座城市，每个城市都有编号，城市与城市之间存在道路相连（每条道路都是双向的），经过任意一条道路需要支付费用。小明一开始位于编号为1的城市，欠债人位于编号为n的城市。小明每次从一个城市到达另一个城市需要耗时1天，而欠债人每天都会挥霍一定的钱，等到第k天后（即第k+1天）他就会离开城n并再也找不到了。小明必须要在他离开前抓到他（最开始为第0天），同时希望自己的行程花费和欠债人挥霍的钱的总和最小，你能帮他计算一下最小总和吗？ 输入描述: 第1行输入三个整数n，m，k，代表城市数量，道路数量和指定天数第2-m+1行，每行输入三个整数u，v，w，代表起点城市...

0 点赞评论收藏

转发

2020-08-04 22:53

C++

题目描述 在遥远的东方，有一家糖果专卖店。这家糖果店将会在每天出售一些糖果，它每天都会生产出m个糖果，第i天的第j个糖果价格为C[i][j]元。现在的你想要在接下来的n天去糖果店进行选购，你每天可以买多个糖果，也可以选择不买糖果，但是最多买m个。（因为最多只生产m个）买来糖果以后，你可以选择吃掉糖果或者留着之后再吃。糖果不会过期，你需要保证这n天中每天你都能吃到至少一个糖果。这家店的老板看你经常去光顾这家店，感到非常生气。（因为他不能好好睡觉了）于是他会额外的要求你支付点钱。具体来说，你在某一天购买了 k 个糖果，那么你在这一天需要额外支付 k2 的费用。那么问题来了，你最少需要多少钱才能达...

0 点赞评论收藏

转发

2020-07-31 18:36

C++

小A的最短路

题目描述 小A这次来到一个景区去旅游，景区里面有N个景点，景点之间有N-1条路径。小A从当前的一个景点移动到下一个景点需要消耗一点的体力值。但是景区里面有两个景点比较特殊，它们之间是可以直接坐观光缆车通过，不需要消耗体力值。而小A不想走太多的路，所以他希望你能够告诉它，从当前的位置出发到他想要去的那个地方，他最少要消耗的体力值是多少。 输入描述: 第一行一个整数N代表景区的个数。接下来N-1行每行两个整数u,v代表从位置u到v之间有一条路径可以互相到达。接下来的一行两个整数U,V表示这两个城市之间可以直接坐缆车到达。接下来一行一个整数Q，表示有Q次询问。接下来的Q行每行两个整数x,y,代...

0 点赞评论收藏

转发

2020-07-30 23:15

C++

兔子的区间密码

题目描述 》有一只可爱的兔子被困在了密室了，密室里有两个数字，还有一行字：只有解开密码，才能够出去。可爱的兔子摸索了好久，发现密室里的两个数字是表示的是一个区间[L,R]而密码是这个区间中任意选择两个(可以相同的)整数后异或的最大值。比如给了区间[2,5] 那么就有2 3 4 5这些数，其中 2 xor 5=7最大 所以密码就是7。兔子立马解开了密室的门，发现门外还是一个门，而且数字越来越大，兔子没有办法了，所以来求助你。提示：异或指在二进制下一位位比较，相同则 0 不同则 1例如，。所以 输入描述: 第一行一个数 T，表示数据组数。接下来 T 行，每行两个数 L，R, 表示区间[L,R]。...

0 点赞评论收藏

转发

2020-07-29 23:57

C++

题目描述 给定一棵n个点的树，每个点有权值。定义表示 到 的最短路径上，所有点的点权异或和。对于，求所有的异或和。 输入描述: 第一行一个整数n。接下来n-1行，每行2个整数u,v，表示u,v之间有一条边。第n+1行有n个整数，表示每个点的权值。 输出描述: 输出一个整数，表示所有的异或和，其中。 题解 直接求复杂度肯定接受不了，我们考虑计算对答案的贡献 由于一个数异或它本身为0，所以偶数次异或本身为0，奇数次异或本身等于数字本身。 对于一棵树，两个节点间的最短路唯一，对于任意，我们设为根节点到x节点的路径权值异或和，那么。 之后，从根节点到到两节点的的路径被计算了两次，异或之...

0 点赞评论收藏

转发

2020-07-29 21:26

C++

题目描述 小卤蛋刚把dnf的技能点重新洗了一遍,现在他要重新加点,假设他的技能树一共有n层，第i层有n-i+1个技能，每个技能只能够学习一次。除了第1层的技能可以直接学习外，其他技能学习都要学习前置技能，即你要学习第i(i>=2)层第j列的技能，那么你要先学习第i-1层的第j列和第j+1列的技能。每个技能学习后都会获得一定的战力加成。现在小卤蛋有m个技能点，一个技能点可以学习一个技能，他想知道加完点后他可以获得的最大战力加成为多少。 输入描述: 有多组样例输入，输入到文件结束.每组样例第一行输入2个整数n(1<=n<=50)和m(1<=m<=1300)，对...

0 点赞评论收藏

转发

2020-07-27 23:39

C++

[CQOI2007]涂色PAINT

题目描述 假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。 每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。 用尽量少的涂色次数达到目标。 输入描述: 输入仅一行，包含一个长度为n的字符串，即涂色目标。字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。 输出描述: 仅一行，包含一个数，即最少的涂色次数。 题解 区间dp 显然对于一个区间...

0 点赞评论收藏

转发

2020-07-27 23:15

C++

题目描述 小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。乌龟棋的棋盘是一行N 个格子，每个格子上一个分数（非负整数）。棋盘第1 格是唯一的起点，第N 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。乌龟棋中M 张爬行卡片，分成4 种不同的类型（M 张卡片中不一定包含所有4 种类型的卡片见样例），每种类型的卡片上分别标有1、2、3、4 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每...

0 点赞评论收藏

转发

2020-07-24 22:18

C++

小A的柱状图

题目描述 柱状图是有一些宽度相等的矩形下端对齐以后横向排列的图形，但是小A的柱状图却不是一个规范的柱状图，它的每个矩形下端的宽度可以是不相同的一些整数，分别为a[i]a[i],每个矩形的高度是h[i]h[i],现在小A只想知道，在这个图形里面包含的最大矩形面积是多少。 输入描述: 一行一个整数N，表示长方形的个数接下来一行N个整数表示每个长方形的宽度接下来一行N个整数表示每个长方形的高度 输出描述: 一行一个整数，表示最大的矩形面积 题解 面积最大的矩形肯定是以x坐标轴为一条边的矩形 那么对于每个点，我们求出其向左最多可以扩展到哪个点以及向右最多可以扩展到哪个点，对于每个点所形成的...

0 点赞评论收藏

转发

工具箱

TA的圈子

TA的笔记

牛客网
牛客企业服务