Solution 题面简洁明了，（就喜欢这种题面）。首先我们需要知道的前导知识，任何一个数，都可以分解为一些素数的幂之积，又叫唯一分解定理，那么对于阶乘这样一个乘积运算，自然也可以进行多次分解质因数。写成素数幂之积。这里给出阶乘求解质因数幂的算法 ll factory(ll n, ll s) { //n！对素数s的求解 ll sum = 0; while (n) { n /= s; sum += n; } return sum; //返回幂 } 那么知道了分解质因数之后，首先如果当前答案的阶乘是p的倍数，就说明每一个素数幂大于等...

Solution 根据题意已知有2种合成方法，假设A方法合成a件，B方法合成b件成品。那么可以得到对应式子约束条件为：a>=0；b>=0；2a+4a<=x；3a+b<=y **（注意a,b才是未知数x,y是已知的，并且 ）**求解: z = a + b的最大截距如果思路清晰就是一道高中的线性规划知识，不过因为斜率原因需要分几种情况取对应点而已。 这里借用一下这位大佬的图本菜鸡画图不行 （1）![图片说明](https://uploadfiles.nowcoder.com/images/20200428/919749006_15880879...

Solution 题面把意思说的比较清楚，其实可以比较明显的知道，这是一个从n件物品选一些出来，需要收益最大。挺明显的01背包，但是直接按照01背包来做确实错误的。想想为什么？没错，背包问题，是动态规划的过程，动态规划需要满足两个性质，最优子结构和无后效性。显然这个题目直接做不满足无后效性，改变做菜顺序，带来的收益明显不同，那我们就要想想办法去让这个收益最大化，才能保证无论如何更换顺序，保证当前求解的动态规划都是利润最大的。那么显然，我们选定2个菜品去做它。假设为A，B，那么向A后B得到的利润就是那么与之对应向B后A利润为 可以对比两个式子很明显发现，前面加法都是一样的，带来的差异只有后面乘积...

这次练习赛难度有点裂开。。 A、牛妹的游戏 解题思路：其实题意比较简单，我们假设给出的点，没有被蓝色方占领的边全部被绿色方战领。这样我们就可以得出一个结论，只有三条边成一个环，才可能被控制，否则四个条边的话，如果中间存在自己家的边，就会形成三边环，否则就不构成控制区域。现在题目就转变成求图或者补图中是否存在三边的环。 我们先得到一个结论，当整个地图上 的时候一定会形成控制区域。我通过题解给出简单的理由，假设 存在 六个点，那么对于每一个点，都一定至少存在三条边被蓝色方或者绿色方控制，蓝色方控制2条，剩余3条被绿色方控制，蓝色方控制3条，就显然存在三边给一方控制。我们假设为 给蓝色方控制，...

讲到子序列，而且有大小关系，应该可以第一时间想到和动态规划有关系，带着这个思路，我们再看下题目。对于每个位置（i，j），都要存在 两边同时取对数，再相除得到 题目就变成了求以 为判断条件的递增子序列问题，问题规模比较小，可以直接二重循环遍历，也可以发现只和单个变量有关系，可以通过离散+树状数组取优化到时间复杂度O(N * log(N)) PlanAPlanB // A #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); cout.tie...

解题思路 ，这道题目看题解才看出来的，先看边权 其实不好操作，那么我们可以调整一下，一条边连接2个点，把边权，改成它连接2点的异或值，一个环的异或值需要为0，对于环中的点，开头的点任意取1，或者0，对于整个环的异或值 =0恒成立。 所以对于连通块，首先对于给定0，1值的边，保存起来，通过我们转换点值的定义，去先把这些连通值处理，如果存在冲突，即无解，直接输出0，程序结束。否则只剩下边权为-1的边，值确定的边可以添加到连通块。情况1、这条边在一个连通块中充当环中最后一条边，那么这条边就可以通过前面的值以及边权异或值为0，唯一确定。情况2、这条边是连通另外一个连通块，可能只有一个元素或者一...

wnm喜欢的数学题 解题思路比较明确，也没啥难的，除了一个比较弱的考点，两数最小公倍数等于两数乘积除以最大公约数。一个数等于两个数乘积一定能被小于等于的数整除，比如9被1整除（1，9）9被3整除（3，3）平方根3只能算一个因子，所以因子个数就更少了，所以我们直接把全部的因子保存起来，再通过二重循环遍历每一对组合，判断是否满足题目条件。如果满足，答案数加1。可想而知当初我是多么的弱……这种题目都没时间看……很多时候题目不写一定不对，有了思路就是时间复杂度可能过大，也要去尝试，再去想想优化或者改进思路。 cpp代码搓我还用了GNU的内置函数__gcd以及STL容器vector以及auto关键字...

A、Jelly 给定三维地图，并且给出不能走的位置）星号，问从 到 的最短路径是多长。挺裸的 题目，这里提醒一下走图最好别用DFS会爆内存死的很惨。规定移动方向，判断是否越界，在判断这个点是否走过，在判断这个点是不是不能走的位置，如果都不是，就把这个点进队，位移长度是前一个走法加一，一直到 ，因为是 ，第一次到终点就是最短路了。直接 出循环。 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43532270 #include <bits/stdc++.h> using namespace st...

题目大意 从给定的A数组，选择全部的长度大于等于K连续子集，构成新的集合，并且从这个集合里面每个拿出第K大加入到B数组中，最后要求B数组中给定的第M大元素。 解题思路 其实这个题目看了挺久都没什么思路和想法，想过去模拟，或者全部保存。。不过空间复杂度和时间复杂度都是 ，有点难顶。走投无路的时候看了一眼题解。二分+尺取。讲道理有点秀到我。参考链接我们假设初始集合为 ,取K=3，集合为 得到B数组为 再根据题目给定的M输出就行了。二分：那么在这里，我们可以发现，每一个输出的元素，都是原先数组里面存在的一个值，那么对于一个在原先数组中的一个值，如果对这个值求第K大数大于等于这个数x的区间个数，...

题目大意 存在 个人，每个人分配在0，1两个阵营之中，还有对应自己的能力值存在 次操作，每次输入 把 能力值+1。 解决方法 如果从前往后统计，对于每个人，需要在 秒之后才可以被增幅，要考虑的因素比较多。换个思路，我们知道每 个人在他行动阶段只会对前 个人产生影响。后面的人是不存在影响的，所以如果后面存在能力值比第 个人能力值高的，第 个人就会牺牲。这样我们先考虑全部玩家先增幅完毕，计算到能力值的最大值。从后往前遍历，因为这样的话如果这个人小于另一队当前的最大值，并且这个是被增幅之后的，仍小于最大值，说明这个人就将被另一队最大值淘汰。 时间复杂度O(N) https://ac.nowcode...

A、组队比赛 最强和最弱一组，其余两个人一组，注意求绝对值，不要输出负数。。我就因为负数WA一发。 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43475100 #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) typedef long long ll; inline int read() { int s = 0, ...

F、斗兽棋 签到题，注意关系就行了，只有在牛妹赢了才输出 其余都输出 #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) bool check(string& a, string& b) { if (a == "elephant" && b == "tiger") return true; if (a == "tiger" && b == "ca...

华华给月月准备礼物 Solution 根据题目大意，很快可以发现，如果我们枚举一个 ，可以在这个 情况下求到 根木棍，我们就希望能不能再求更大的 ；否则，可行解一定比当前ans更小。符合单调特性，采取二分的思路。 再说说我对二分的心得二分大致可以分为两种思路，范围缩小让 逼近答案 while (l < r) { ll mid = r + l >> 1; if (a[mid]>=x) r = mid; else l = mid + 1; }范围缩小让 逼近答案 while (l < r) { ...

Oulipo Plan A:KMP 题意很简单，就是通过 算法求得 数组，这点能力相信大家还是要掌握的，还没搞得很明白的去百度或者看我下面代码，我写的是和书上一模一样的，百度里面的可能是0结尾。这些没什么大区别，思路懂了就行。还有就是 数组是可以求到最后一个的，这个老师上课没讲道过，因为我们上课讲的都是求第一次出现位置，所以匹配到指定长度就不需要再找了，直接 长度就行了。而这个地方，需要我们找到后再找下一个，所以我们要求到最后一个点的值。其实书上也求了，只是没有用而已。如果暴力匹配每一个点 朴素匹配时间复杂度 O( ),N,M都是1e6，TLE妥妥的 KMP时间复杂度 O( ),线性阶，AC妥...