NC19427 换个角度思考 题目地址： https://ac.nowcoder.com/acm/problem/19427 基本思路： 离线+树状数组，将查询离线，把待查询数组按照值从小到大排序，将查询按照x的大小从小到大排序，那么我们每次查询时先在树状数组插入比当前查询的x小的所有下标位置(因为数组是有序的所以直接接着上次的位置往后不会重复操作)，然后查询[L,R]范围内里有多少个数就是了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using nam...

NC14704 美味菜肴 题目地址： https://ac.nowcoder.com/acm/problem/14704 基本思路： 这题我们考虑01背包,但是由于选择的时间先后会影响结果,所以我们要根据谁先选择更优做一个贪心,我们先考虑两个菜肴i和j,如果先选择i再选择j那么结果为 如果先选择j再选择i那么为 我们联立不等式设第一种情况更优就能解出 所以我们将菜肴根据 和 的大小做一个排序再01背包就行了。 同时注意题目最后备注了：最大总美味值可能为负。也就是所我们不能一个菜肴都不做,这点感觉题目没有说清楚,所以注意负数情况和不要统计一个菜都不做的情况。 参考代码： #...

NC17137 Removal 原题地址： https://ac.nowcoder.com/acm/problem/17137 数据没锅,是我的锅orz,谢谢邓老师帮我找bug 基本思路： 这题的本质是一个挺简单的计数dp，和这道题其实比较像https://ac.nowcoder.com/acm/contest/4853/C 我们看m比较小所以只要将前i个里取j个变换成前i个里j个不取就行了。我们设dp[i][j]表示前i个数中j个不取,那么不考虑重复的情况我们可以考虑这样的转移方程： 即在第i个位置取或不取的情况。那么考虑去重，去重的方法其实和上面那题思路完全一样，对于每个位...

NC17065 子序列 题目地址： https://ac.nowcoder.com/acm/problem/17065 基本思路： 很明显这个题目是一个计数dp但是 这个式子值很大不好用来比较，但是我们化简一下两边取log就能得到这个式子，然后就是一个很朴素的计数dp了。设dp[i]表示以第i个元素结尾的所有子序列那么我们能得到转移方程 那么最后的答案就是 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define ...

E Sunscreen 题目地址： https://ac.nowcoder.com/acm/contest/5338/E 基本思路： 这题我们贪心就好了，我们将奶牛的最小SPFi按照从小到大排序，同时将防晒乳液的SPFi从小到大排序；那么我们遍历防晒乳液，对于每种防晒乳液，我们将之前的最小SPFi值比这种防晒乳液SPFi值小的牛加进来，然后每次我们优先让最大SPFi小的奶牛使用当前这种防晒乳液(这里我们可以使用优先队列实现)也就是将最大SPFi大的留给之后SPFi更高的防晒乳液，这样贪心一遍就能得到答案了，具体实现可以参考代码。 参考代码： #pragma GCC optimiz...

D 表达式求值 题目地址： https://ac.nowcoder.com/acm/contest/5338/D 基本思路： 这题难点没有什么，就是模拟比较麻烦，注意到我们取后四位也就是说在计算过程中对10000取模就行了，然后处理我这里是先把数字和字符全部独立出来放在两个数组里，然后再开一个数组，对于直接+的我们放在数组中，对于有*(注意会有连乘，因为这个WA了一次)的我们先连续乘出答案再放在数组中，那么最终这个数组里的加起来就是答案了，具体细节可以看代码。ps.听说这题Python一行就能写QAQ，不会Python的自闭了。 参考代码： #pragma GCC optimize...

C 小雨坐地铁 题目地址: https://ac.nowcoder.com/acm/contest/5338/C 基本思路： 这题我们分层建图再跑最短路，对于每条地铁线我们建一层图，依次的两个站之间连双向的权值为b的边，然后对于换乘，我们多建一层的虚点，每条线的每个站到虚点的边设为0，从虚点出去到每条线的每个站的边权值设为a，这样我们就建图完成了，然后再跑一边dijkstra计算答案就好了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using names...

B「木」迷雾森林 题目地址： https://ac.nowcoder.com/acm/contest/5338/B 基本思路： 比较经典的的简单dp思路，从最下往右上递推就是了具体递推式如下：当这个位置不是树时 ，是树的话跳过，注意取模。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define IO std::ios::sync_with_stdio(false) #define ll long long #de...

A Jelly 题目地址： https://ac.nowcoder.com/acm/contest/5338/A 基本思路： 这题本质上就是一个最基础的BFS找迷宫最短路，只是扩展到了三维的情况，所以相对而言麻烦一点点，要在空间里把每个位置想清楚。注意这种找最短路的最好用BFS写，开的一个dp数组在BFS过程中更新dp数组里每个位置的最小值。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define IO std:...

NC14301 K-th Number 原题地址： https://ac.nowcoder.com/acm/problem/14301 基本思路： 这题做法感觉还是蛮难想的，我也是参考大家的题解才想通，是一个二分+尺取。我们先看题意，基本意思就是找数组A中每个长度大于K的区间里的第K大形成数组B，然后再在B中找第M大，看上去比较复杂。我们看答案只是一个数，所以考虑二分答案，我们每次二分出这个第M大的值为X，那么我们在原数组中尺取左右端点L，R，如果在[L,R]范围内大于这个X的数出现大于等于K个那么就意味着这右端点之后的每个区间它的第K大一定也会是大于X的(这里是重点)，知道了这一点左...

NC14583 糖糖别胡说，我真的不是签到题目 原题地址： https://ac.nowcoder.com/acm/problem/14583 基本思路： 我觉得这题的主要难点还是在搞懂这个题意吧,这个题意还是比较绕的而且还有一些细节要注意,两个关键点：从第i秒的时候，第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖，然后是这句 第i次发功的时间为ci，则在第ci秒结束后，b1,b2,.....,bci都会增加1.我们从这两个关键点可以发现,这个发功实际上对于第i个糖糖能否消灭之前的糖糖本身是没有影响的，只是对之后的糖糖能否消灭之前存活的糖糖有关系，所以之后要...

牛客小白月赛24 I 求和 题目地址： https://ac.nowcoder.com/acm/contest/5158/I 基本思路： 来晚了,随便挑了一题I写,由于自己过于***树状数组写错了,所以没在比赛结束前交上去。这题总体来说还是比较裸的,我们求一下dfs序,然后用树状数组维护子树的和就是了。关于dfs序的具体内容的大家可以百度学习，这里简单介绍一下就是记录每个节点在dfs过程中进出栈的位置,两者中间的范围就是这个节点的子树即一个线性区间,我们知道了这一点就能将树形结构转化为线性结构,然后用数据结构类似树状数组去维护它就是了。dfs序的一般求法： int tot = 0,l...

NC23049 华华给月月准备礼物 题目地址： https://ac.nowcoder.com/acm/problem/23049 基本思路： 非常明显的二分答案,我们二分每根木棍的最大长度,然后每次check一下是否能切出大于等于K根的木棍就是了,然后就是大家二分的时候注意一下取答案的位置就好了,其他的没啥。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define IO std::ios::sync_with_...

NC14248 Treepath 题目地址： https://ac.nowcoder.com/acm/problem/14248 基本思路： 很简单的一个树染色,感觉非常像上场div2 D的一部分,昨天刚补了那题,所以一下就想到了;我们直接将图黑白染色,我们可以知道黑白染色之后,同种颜色之间的路径一定就是偶数的,所以我们把每种颜色的数量统计一下,假如黑色颜色节点有n个那么算下两两组合,就能组合出(n-1)!种路径,白色颜色节点同理,两者相加就是答案。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include &lt...