211210400509

牛客刷题总结

c++(1) c语言(1) STL(8) 天梯赛(4) 字符串函数汇总(1) 蓝桥杯(2)

/ 注册

全部文章 / 牛客刷题总结（共14篇）

蓝桥杯2022年C/C++B组4406积木画

链接题意：有一个2 * N大小的画布，以及两种积木（i形和L形）,求出将画布排满共有多少种方式，积木可以旋转。题解：用f[i][j]表示第i+1列为j的积木排序的最大次数。 f[1][0] = 1; //第1列满了第i+1列为空的情况 f[1][1] = 1; //第1列满了第i+1列上层...

动态规划

2023-04-05

0 684

蓝桥杯2022年B组C/C++李白打酒加强版

链接题意：在一条路上，分别有N个店，M个花。初始有2两酒，每遇到店酒翻一倍，每遇到花喝一两酒。题解：记忆化搜索剪枝。一共有N+M个点，分别讨论该点是店和是花的情况。遇到不符合题意的递归回去，剪枝是为了减少时间复杂度。下面是记忆化搜索的步骤记忆化剪枝就是记录已经计算过的状态，不需要重新计算，...

记忆化搜索剪枝

2023-04-05

0 661

蓝桥杯2022年C/C++B组统计子矩阵

链接题意：给一个N * M的矩阵，求出有多少个子矩阵小于k。题解：一维前缀和+双指针算法。s[i][j]表示第j列前i个元素的和。这种类型的题确定一条边界，然后再对另外一条边界伸缩进行求解。本题先确定上下边界，然后让右边界右移，如果范围内的总和大于k，左边界右移。代码 #include <...

一维前缀和双指针

2023-03-30

0 507

蓝桥杯2022年C/C++B组X进制减法

链接题意：整数每位上的进制并不固定，例如321个位为2进制，十位为十进制，百位为八进制。换算为十进制数为((3 * 10) + 2) * 2 + 1 = 65。给定整数A和B，在同一进制规则下，A-B的最大值。题解：本题重点就是怎么理解X进制和大数组整数的存储。最小位在数组的第一位，最高位在最后...

大数组类型存储

2023-03-30

0 846

2023牛客寒假算法基础集训营M题

链接题意：有m个仙贝分给n个人，每个人的好感度为（分出的）/（当前剩余的）。求所有人好感度之和最大为多少。题解：动态规划，dp[i][j]表示前i个人有m个仙贝的情况下最大好感度。一个简单的动态规划问题，再用一个k表示分给当前人的仙贝。代码 #include <iostream> ...

动态规划

2023-03-29

0 366

小白牛客月赛69C题开题顺序

[链接]https://ac.nowcoder.com/acm/contest/52441/C 题意：在一场比赛中，有n道题，总时长为t，错误罚分为p。每道题满分为a，时间系数为b，保底分为c，花费的时间x，错误提交次数y。如果总消耗的时间小于t，这道题的得分为max(c,a-x * b-y * p...

dfs

2023-03-28

0 418

小白牛客月赛69D题旅游

[链接]https://ac.nowcoder.com/acm/contest/52441/D 题意：有n个城市，m条边（无向图），每条边有一个边权a。第k次操作时消耗为k * a。要求总消耗不能超过c，而且边权小于p的无消耗。求出最小的p使得满足条件。题解：先运用最小生成树算法Kruskal，将...

并查集最小生成树 kruskal

2023-03-28

0 423

牛客小白月赛66E题生成树与路径

链接题意：给定一个无向连通图的点个数n和边条数m。为使最小生成树的大小等于从顶点1到顶点n的最短路长度，输出m条边。题解：首先要搞懂最小生成树，把边数从小到大排序，每次选最小的边，直到所有顶点都在最小生成树中。所以1-n的边权一定是最小的并且不能相等。多余的边随便添加，前提是不能比前n个添加的小...

最小生成树

2023-03-26

0 433

牛客小白月赛66D题障碍

链接题意: 在一条数轴上有m个障碍，将数轴分成若干份，障碍可能位于端点。记x为移除的障碍，L为该区间内最长的线段。怎么使L - x * x最大。题解：枚举移除一个障碍到移除m个障碍的情况。因为 L - x * x 要最大。而L < x * x 时为负数，故x的范围为sqrt(L)，由题...

数据范围收缩

2023-03-25

0 379

牛客小白月赛67C题一刀二分三角

链接题意：给定三角形的三个顶点A(0,0) ,B(Xb,0),C(Xc,Yc);在底边AB能否找到一个整数点x0使得三角形能被x=x0分为部分相等的两部分。题解：本题主要考察了数学知识和二分。当Xc大于Xb/2时，x0一定在0到Xc之间，在此区间进行二分查找，最后判断一下是否满足条件。注意不能用...

二分数学知识

2023-03-24

0 346