牛客算法竞赛入门课第四节习题 Part1（并查集基础） 加边的无向图 （思维+并查集） 题意：  给你一个 n 个点，m 条边的无向图，求至少要在这个的基础上加多少条无向边使得任意两个点可达  思路：  给定的m条边不一定能够联通所有点，只需要计算出联通块个数-1即可。因为3个区域只需要2条边就可以联通，所以答案是个数-1。求联通块的话，可以用并查集或dfs类似的题：传送门  代码： #include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; ///联通块个数-1 int root[maxn],n,m; in...

算法周周练9（ABDE） A.符合条件的整数 题意： 求[2^n,2^m)区间里有多少个整数x满足x%7==1 思路： 考虑周期性。可以求从1 ~ 2^n和1 ~ 2^m里符合条件的数，相减即是答案。 计算过程会爆int,应该用long long.(我以为也会爆ll，所以用的ull) 代码：  https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43894353  B. Relic Discovery 思路： 签到题，模拟。 代码：  https://ac.nowcoder.com/acm/contest/view-...

牛客—— [CQOI2010]扑克牌 （二分）原题链接：https://ac.nowcoder.com/acm/problem/19916##题意： 给n种牌，每种牌c[i]个，和m张万能牌，问最多能够组成多少套牌（包含所有的种类） 思路： 考虑二分答案，贪心进行检验。 如果最多能够构成x套牌，每种牌至少x张，如果c[i]<x的话就要用万能牌去补齐。 在check的时候，当c[i]<x时才使用万能牌，当万能牌不够时说明该答案偏大。 代码： #pragma GCC optimize(2) #include<bits/stdc++.h> using namespace st...

牛客—— 旅游 （树形DP求树的最大独立集） 原题链接  题意： 树的最大独立集定义： 对于一棵有N个结点的无根树，选出尽量多的结点，使得任何两个结点均不相邻（称为最大独立集） ； 对于任意一个点x，都有选和不选两种情况。 我们假设dp[x] [0]表示不选该点的最大值，dp[x] [1] 表示选择该点的最大值。 对于一个点来说，如果选了这个点，就不能选择他的子节点；如果不选这个点，他的子节点又有选和不选两种情况。 所以可以得出转移方程： dp[x][1]=1;///初始化 dp[x][1]+=dp[j][0]; dp[x][0]+=max(dp[j][0],dp[j][1]); ///j是x...

牛客——德玛西亚万岁（状压DP） 原题链接  题意： 已知一个n*m的01矩阵，0表示这个格子不可以站人，1表示这个格子可以站人。规定上下左右相邻的格子不能站人，问有多少种站人的方法。 思路： 因为n,m都很小，而且能够站人的人数也不是固定的。考虑状压枚举每一行的状态，进行转移。 在枚举状态的时候，有三种状态是不合法的。 1.当前的状态与地图的状态相矛盾； 2.当前状态本身不合法，即存在左右相邻的情况； 3.当前状态无法由上一个状态转移而来，即存在上下相邻的情况。 最后统计输出即可。 #pragma GCC optimize(2) #include<bits/stdc++.h> u...

2020年第十四届山东大学程序设计竞赛Part1（CDFL） C.分栏 题意： 转化一下就是先读偶数位，再读奇数位（假设下标从0开始的） 思路： 直接模拟，签到好评。 代码：  https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43855679  L. 开学？ 题意： 跟你说现在是周x，问n天后是周几。 思路： 签到题。注意取余后为0的情况，此时应当是7，特判一下就好了 代码：  https://ac.nowcoder.com/acm/contest/view-submission?submissionId=438...

“科林明伦杯”哈尔滨理工大学第十届程序设计竞赛Part2（A——重新定义的树的直径） A. 点对最大值 题意： 给定一棵既有点权又有边权的树，将两点之间的权值重新定义为路径上的边权和两点的点权之和。问两点之间的最大权值。 思路： 相当于是 重新定义了树的直径，让你求解。 对于无边权的树的直径的求解：（BFS或DFS） 1.任取一点作为起点，找到距离该点最远的一个点x 2.找到距离x最远的一个点y 3.x和y之间的路径就是一条直径 关于有边权的树的直径的求解：（树形DP） 我们可以根据每一条路径上的高度最高的点来把所有路径分类，在这类内部求max，再在每一类里取max. 现在的问题就转化成了如何...

“科林明伦杯”哈尔滨理工大学第十届程序设计竞赛Part2（D——数学公式+分数取模） D.扔硬币（数学公式+分数取模） 题意： 有n枚硬币，已知至少有m枚硬币是反面，求恰好有k枚硬币是正面的概率。 对于结果是p/q，输出分数取模1e9+7后的结果。 思路： 首先很容易可以知道，当m+k>n时，题目中描述的情况是不存在的，直接输出0即可。 接下来考虑其他合法的情况：问题是在至少m枚硬币是反面的前提下，恰好有k枚硬币是正面的概率。 假设事件A是至少m枚硬币是反面，事件B是恰好有k枚硬币是正面，所以答案就是$$ 因为P（AB）和P(A)的分母都是总事件，所以就可以约掉，问题就可以转化为方案数了...

牛客算法竞赛入门课第一节习题Part5（糖糖~数学考试） 糖糖别胡说，我真的不是签到题目 思路： 每只糖糖存活的条件是后面没有另外一组的比他大的糖糖，所以我们可以从后向前维护每一组糖糖的最大值就好了。 加上发功的话就先把最后的能力值算出来，再倒着维护一个最大值就好。 代码：  https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43887577&returnHomeType=1&uid=115850812  奇♂妙拆分 题意： 问n最多可以被拆分成多少个不同的自然数，使得该自然数的乘积等于n 思路： ...

牛客算法竞赛入门课第一节习题Part4（铺地毯~明明的随机数） 铺地毯 （思维+枚举） 题意： 找一个点被地毯覆盖的最上面的地毯编号，没有输出-1； 思路： UPC做过加强版233 可以倒着枚举每个地毯，看是否覆盖该点，如果覆盖则输出，因为是后面的覆盖前面的而且是倒着枚举，这时候这张地毯一定是覆盖该点的最上面的地毯。-1的情况特判一下就好了。 要注意给出的是左上角的端点和边长！！ 代码：  https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43887238&returnHomeType=1&uid=...

牛客算法竞赛入门课第一节习题Part3（拼数~Selfish Grazing） 拼数 题意： 给定n个整数，拼出最大的数。 思路： 我们只考虑两个字符串的拼接的话，肯定是选择拼接后字典序大的拼接，拓展到n个也是一样的。 所以排序的时候就是按照拼接后的字典序从大到小排序。 代码：  https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43886767&returnHomeType=1&uid=115850812  [HNOI2003]激光炸弹 题意： 二维矩阵的每个格子都有权值，问炸掉r*r的正方形可以...

“科林明伦杯”哈尔滨理工大学第十届程序设计竞赛Part1（BCEFHJ） 太菜了先写写签到题，按做题顺序的 C.面积（签到题） 题意： 求正方形周围接四个半圆的图形的面积。 思路： 推一下公式就可以了。假设正方形边长是x，π为PI。则 化简就是 注意PI=3.14。 代码：  https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43862364  H.直线(公式+大数) 题意：  n条直线在平面上最多存在多少交点 。 思路： 公式是 其实也很好理解，两条非平行直线有且只有一个交点，其中一条直线与其他直线都有n-1个交...

牛客算法竞赛入门课第一节习题Part2（ Flip Game ~ Subsequence） Flip Game 题意： 有一个4*4的棋盘，每个格子上都有一个黑白两面的棋子。每次任意选择一个棋子，把这颗棋子和他周围的棋子都反过来。当所有的棋子是同一个颜色时，游戏结束。 问给定的初始状态能否完成游戏，若能，输出最小的反转次数。 思路： 因为是最小的翻转次数，而且我们无法确定如果翻转才是最优解，所以我们只能对每一种状态都枚举他的所有可能状态，BFS求解。 但同时难点在于如何储存当前的状态，如果用数组的话，结合队列不是很好操作。我们可以用二进制表示每个棋子的黑白状态，这样就可以用一个数tmp来表示每...

牛客算法竞赛入门课第一节习题Part1（切长条~「土」巨石滚滚） 切长条（贪心） 题意： 给若干条线段，可以在任意一行做一条竖线，问至少做几条竖线才能把每一条线段都切开。 思路： 显而易见的贪心思路。 按照关键字为每条线段的左端点进行从小到大的排序，对于一个新的线段，如果他的左端点的值大于等于在前几条线段的右端点的最小值，那么就不能跟前面的重合，需要多做一条竖线，否则就更新右端点的最小值。 代码：  https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43860866&returnHomeType=1&amp...