离ACM还有一定距离

分类

学习笔记(7) 牛客多校2020(1) 题解(43)

/ 注册

全部文章（共51篇）

【题解】2020牛客暑期多校训练营（第二场）BCFJ

F Fake Maxpooling 题意规定矩阵对应的值为其下标的，求所有子矩阵最大值之和。 Solution 线性求 + 二维单调队列线性求： for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)...

2020-07-14

1 805

【每日一题】扑克牌

题意有n种扑克牌，每种有ci个。还有m张王牌。可以代替其中任一张。最多可以造出几个套牌（每副牌只能用一次）。 solution 典型的二分答案，每副牌只能使用一次，所以限制使用的王牌数为，每种牌不够张需要王牌补，计算使用的王牌数为判断是否满足条件即可。 Code #include <...

2020-06-06

0 723

【每日一题】旅游

题意：给定一棵树，从s点开始，每次选择一个没有染色过的点居住，居住后所有相邻的点都会被染色，问最多住几个点？ solution：树形dp，这题和“没有上司的舞会”几乎完全一样，表示i点住/不住的最大值，，只不过起点必选，所以答案只可能是， Code： #include <bits/stdc...

2020-06-05

0 695

【每日一题】contest

题意支队伍一共参加了三场比赛。一支队伍认为自己比另一支队伍强当且仅当在至少一场比赛中比的排名高。求有多少组，使得自己觉得比强，自己也觉得比强，, 算一组。 solution 若和都互相认为更强，那么必定存在两场，一场强于，一场强于，那么就是对...

2020-06-04

0 779

【每日一题】Protecting the Flower

题意一共有只牛在花坛旁边，第头牛每分钟破坏朵花，把第i头牛带回牛棚需要这么多时间，每次只能带回一头牛，请问怎样能使得被破坏的花最少。 solution 以小化大，先考虑两头牛，先领，损失为：，先领，损失为，故得到排序条件，最后模拟得出答案。 Code #include &...

2020-05-29

0 664

[每日一题] 货币系统

题意种面额货币，数量无限，问最多保留几种，使得原来可以组成的仍然可以组成。（） solution 由于大的只会被小的组成，所以先排序，对于存在性问题就显然是完全背包了，dp[i] 表示是否能表示出价值，得到状态转移方程：，对于已经可以表示出来对，已经可以由小的组成，因此不需要在枚举。 Co...

2020-05-29

0 773

【每日一题】建筑抢修

题意栋建筑，第栋建筑需要时间修，截止到时间，问最多可以修多少建筑。 solution 我们可以类比成写作业，先截止的我们会先做，这是大体的贪心策略。但他并不是最优的，因为可能那一科会花你非常多的时间，够你做更多的科目，得不偿失。因此我们用优先队列维护做过的作业中花费时间最大的那份，当...

2020-05-29

0 617

【每日一题】中位数图

题意给定一个排列，求长度为奇数子串以为中位数的子串个数。 solution 由于求的是中位数，所以我们只需要关心这个数和的大小关系就好了，大于看作 1，小于看作 -1，等于看作 0，问题转化为求包含 0 且和为 0 的子串有多少个。从的位置开始遍历，map 统计右边累...

2020-05-28

0 729

【每日一题】图的遍历

题意无向图个点，每次必须跳两个，至少需要加多少条边可以遍历所有点。 solution 首先，如果图不联通，那么需要加联通分量 - 1 条边使图联通，然后发现一点，只要这个图存在奇数环，就一定能全部走完，不存在的话，随便加一条边生成奇数环即可。 Code #include <bits/st...

2020-05-28

0 650

【每日一题】简单瞎搞题

title: 每日一题：简单瞎搞题（STL）copyright: truedate: 2020-05-26 17:44:37tags: STLcategory: 每日一题mathjax: true 题意一共有个数，第个数是可以取中任意的一个值。设，求种类数。（0 ~ n,...

2020-05-26

0 665