题号 NC14419名称 线路规划 来源 Wannafly挑战赛4 戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 首先，我们实际上是求一个最小生成树（原来树上的边是单向边，所以要实现两两双向通信，最后一个特别行动组内部成员新连的边还是得是一棵树）。因为是最小生成树，考虑kruskal算法，要对边从小到大排序然后合并，所以先排上序再说。然后来看这个给边的方法：X及X向上k个点和Y及Y向上k个点分别可以连一条长度为wi的边——直接暴力建边肯定会t，我们考虑将X向上长度为k的区间和Y向上长度为k的区间按2的次幂进行拆分（...

广搜，搜到4以后广搜的层数就是答案。 #include<iostream> #include<queue> using namespace std; const int MAXN = 50; int G[MAXN][MAXN]; bool visit[MAXN][MAXN]; struct node{ int x,y,cur; }; int main() { int M,N,M1,M2; cin >> M >> N >> M1 >> M2; int sx,sy,ex,ey; for(int i = 1 ;i <= M...

题号 NC23051名称 华华和月月种树 来源 牛客小白月赛12 戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 如果没有加点的操作，其实就是dfs序上的区间加和单点查询，用线段树或者树状数组维护即可。加点操作其实也不难，我们只需要最开始就把所以操作离线下来，先把最终形状的树建上，执行加点操作的时候这个点才开始有值即可。 欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！ 活动奖励：  在牛客博客中写出题解，并回复地址审核通过可获得（依据题目难度和题解的内容而定）  本道题目9月1日中午12：00之前写的题...

先把括号的内容搞掉。处理出一个字符串tempCorona(Trump)USA<<<Virus->temp = CoronaUSA<<<Virus然后再处理temp，遇到'<'就弹出末尾的字符。 #include<iostream> #include<vector> using namespace std; int main() { string s; cin>> s; int len = s.length(); string temp = ""; int k = 0; for(int i = 0 ; i &lt...

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。先考虑另一个问题，一个整型数组里除了一个数字之外，其他的数字都出现了两次，那把所有的数据异或起来，异或的结果就是那一个数字。（因为出现过两次的数字异或起来就抵消了） 对于这个题来说，如果把数字全异或起来，最后异或出来的结果是不同的那两个数的异或，然后随便从异或结果里面找一位1。我用的是lowbit方法，X&(-X)得到最低位的1，因为某一位上异或结果是1的话，说明要找两个数，这一位上一个是1，一个是0。那么就可以把原来数组中，这一位是1的分成一组，这一位是0的分成一组。这样就有了两组每一组中会包...

用 表示到达第 行 第 列的最小和。第一行和第一列单独考虑：  对于第一行的位置，肯定是从转移过来的。 对于第一列的位置，肯定是从转移过来的。 对于其他位置 来说，可能是从上边，左边，左上方过来的，所以有了状态转移方程  #include<iostream> #include<vector> using namespace std; class Solution { public: /* * * @param presentVolumn int整型vector<vector<>> N*M的矩阵，每个元素是这个地板砖上的礼物体积 * @return...

题号 NC200532名称 装货物 来源 牛客练习赛57 戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 可以暴搜，搜的时候维护当前每个箱子的剩余空间，如果当前这个物品能放进之前的某个已经放了物品的箱子里就放进去尝试一下，然后再在没用过的箱子里面开一个放进去（放进哪一个空箱子都是完全一样的所以只开一个空箱子就行）。可以把物品从大到小排序，即先塞大的物品这样箱子的可用空间会迅速减小然后搜索树就小了。再说一下dp的做法f[i] 表示拿的物品状态为i下最少箱子数。g[i] 下最少箱子数方案中一个箱子的最大剩余量。把一个不属...

题号 NC14250名称 MMSet2 来源 Wannafly挑战赛1 戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 首先我们要知道题目要求的究竟是什么:f[u]是每个点到集合中的点的最大距离，min(f[u])即找到一个点到点集S的最大距离最小——这个点应该出现在点集S中离得最远的两个点xy连线的中点上。所以问题就转化成了，求点集S里离得最远的两个点的距离。求一棵树上任意两个点的最长距离（也就是求树的直径）我们一般跑两趟dfs——第一遍以任意一个点为起点，找到离他最远的点，这个点就是直径的一个端点，然后以这个点为...

课程链接：https://ac.nowcoder.com/discuss/4622718月15日-9月15日，写以下题目中的题解，即可获得牛币~题单链接：https://ac.nowcoder.com/acm/problem/collection/843  在牛客博客中写题解，并回复地址在本贴下审核过后我们将为每篇题解发放5-50牛币   刷野 [HAOI2011]PROBLEM A  Min酱要旅行管道取珠 灯谜 打砖块(brike) [HAOI2010]最长公共子序列 [AHOI2009]CHESS 中国象棋 [SCOI 2009] 粉刷匠  区间价值 排列游戏 [HAOI2008]木棍分...

题号 NC20565名称 [SCOI2009]生日礼物 来源 [SCOI2009]戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 典型的双指针：对于每次r右移的时候，cnt[color[r]]++，然后判断cnt[color[l]]是不是大于1，如果是l就可以右移，直到l移到一个该颜色只出现过一次的位置，然后判断是不是颜色齐了（用一个计数变量在右指针右移的时候看看是不是增加了新颜色然后维护就可以了，左指针的移动并不会导致颜色数量发生变化），齐了就可以维护一下最短区间长度。本题需要注意的是：数轴长，需要离散化。 欢迎各...

比赛名称：牛客练习赛67官方题解：https://ac.nowcoder.com/discuss/477699有问题可以回帖询问出题人~ 活动具体内容  8月14日22:00-9月7日12:00，写牛客练习赛67题目的题解，即可获得牛币~  发放牛币的数量取决于题目难度，题目数量，题解质量  比赛结束之后点击每题后的进入题解->写题解，博客会被收录在每道题目之下 活动奖励：  在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~我们将在8月28日下午审核，并给每篇题解发放5-60牛币  PS:  如果题解写的非常好，会增加其获得的牛币 如果题解写的非常水，会减少获得其获得的...

题号 NC20566名称 [SCOI2010]游戏 来源 [SCOI2010]戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 （大家的题解都使用二分图匹配，其实这个题还有很多别的解法）先说二分图匹配：因为每个物品只能用一次，每个属性也只需要一个——每个物品和它对应的属性值连边，做二分图最大匹配。但是如果盲目做二分图的话有个问题：我们要求是从1开始的最多的能满足的连续属性，而二分图匹配不考虑连续不连续的问题——其实很简单，二分图匹配本来就是一个点一个点的去找匹配，所以我们只要对属性的点按从小到大排序跑增广，当这个点匹配...

题号 NC19833名称 地斗主 来源 牛客OI周赛3-提高组 戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 先考虑直接递推能不能推：如果前n-1行填满，第n行：两个1*2的竖着放，1种方法；如果前n-2行填满（但是前n-1行没满）：横着两个，竖着两个有3种方法，横着四个有1种方法，一共4种；如果n-3行填满（前n-1，n-2行没满），有2种情况；如果n-4行填满的话，有3种情况；n-大于等于3的奇数行填满——2种；n-大于等于4的偶数行填满——3种； ;省略号里面的东西在f[n-2]中也有所以我们把f[n-2]写...

题号 NC110793名称 Mr. Kitayuta, the Treasure Hunter 来源 CF505C戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 设f[i][j]表示到达第i个岛屿，跳的距离为j 得到的最大宝藏数，那么转移方程为：f[i+j][j] = max(f[i+j][j], f[i][j] + c[i+j])f[i+j+1][j+1] = max(f[i+j+1][j+1], f[i][j] + c[i+j+1])f[i+j-1][j-1] = max(f[i+j-1][j-1], f[i][...