A 重新排列 题目地址： https://ac.nowcoder.com/acm/contest/7509/A 基本思路： 尺取法,然后每次一下范围内的字母数量能否构成”puleyaknoi“就行了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define IO std::ios::sync_with_stdio(false); cin.tie(0) #define int long long #define u...

E 会当凌绝顶，一览众山小 题目地址： https://ac.nowcoder.com/acm/contest/7412/E 基本思路： 没有什么思维难度,但是代码难度比较高,做一个类似离散化的排序,然后就是建线段树,实现所有操作。因为线段树就是天然二分结构,所以实际上这里的所有操作都可以在线段树上实现,这里算是给自己存一个模板。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define IO std::ios::...

[SCOI2009]游戏 题目地址： https://ac.nowcoder.com/acm/problem/20271 基本思路： 根据题意，我们将每种置换方法转换成图论模型,例如题中的置换关系 1->2 2->3 3->1 4->5 5->4 6->6,就能转换为 1->2->3->1,4->5->4,6->6,这样三个长度分别为,,的环,那么我们就容易发现每次的循环节的长度就是所有环长度的,所以实际题意就转换成了,将分解成若干个数的和,求它们的可能方案数。我们怎样构造出多的不同方案数,首先我们根据唯一分解定理...

联合权值 题目地址： https://ac.nowcoder.com/acm/problem/16495 基本思路： 要找距离为的点对,我们考虑枚举中间点,那么每次能产生联合权值的点,必然在这个点的儿子和儿子或者儿子和父亲之间,所以每次我们用其中权值最大的两个点就能更新出最大值,然后权值之和实际上就是每次求一个序列中任意两点乘积之和的计算,这部分实际上每次乘一下前缀和就能搞定,注意,这样算两个,所以最后要乘个。 ps. 的过程好像直接用循环代替就行了XD 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include &...

D 能量水晶 题目地址： https://ac.nowcoder.com/acm/contest/7226/D 基本思路： 我们要让水晶不能再释放下一个法术,那么也就是说要让剩下的能量,不足以去施展剩下的消耗最小的那个法术,我们可以先将法术按消耗从大到小排序,那么如果一个法术它作为了剩下的消耗最小的法术,也就是说比它还小的那部分法术都使用了,这部分的法术消耗用一个后缀和就能求到;而比它大的那部分中我们可以来选择,所以我们用类似背包的过程,找到每种选择带来法术消耗,和这个消耗下的选择方案数,如果以上两部分选择带来的共同法术消耗要位于中,那么就是可行的方案,对于每种可行方案,我们去累加背包...

选择客栈 题目地址： https://ac.nowcoder.com/acm/problem/16594 基本思路： 我们考虑倒着枚举,对于每个客栈,我们只要考虑它后面第一个最低消费不超过元的咖啡店的位置,这个咖啡店之后的每个相同色调的客栈很明显都能和当前这个客栈被一起选择,所以我们求个后缀和,预处理一下每个位置之后每种颜色的客栈有几个,就能在限制时间范围内得到答案了。实际上正着枚举也是一样的,选择具有对称性。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> u...

B 牛牛的算术 题目地址： https://ac.nowcoder.com/acm/contest/7079/B 基本思路： 我们发现这个是连乘的形式,那么如果,那么必然会取模成0,所以我们考虑的部分怎么算,我们将式子拆分一下： ,最后一部分很明显是一个前缀和,然后第二个部分也是一个前缀和,所以我们预处理两个前缀和就能的预处理出所有小于的结果。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define IO std...

C 牛牛的无向图 题目地址： https://ac.nowcoder.com/acm/contest/7079/C 基本思路： 我们考虑离线每次查询的,在最小生成树的过程中,我们每次是从小往大加边的,同样将也按从小到大排序,每次加到一个比当前要大的边的时候,之前的那些已经连上的边一定是都比小的,所以在这些联通块中的点，两两之间的一定是比小的,也就是符合条件的,那么这时符合条件的点对的数量就是(为每个联通块的大小),每次并查集合并时维护这个结果就行了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include &lt...

Is It A Tree? 题目地址： https://ac.nowcoder.com/acm/problem/105905 基本思路： 并查集维护生成树的过程,每次加边时判断一下是不是会产生环,然后用存一下出现了的节点,最后判断一下这些出现了的节点是不是在一个联通块里面就行了。注意空树的情况这时它也是树。 参考代码： #include <iostream> #include <string> #include <list> #include <map> #include <set> using namespace std...

XOR-pyramid 题目地址： https://ac.nowcoder.com/acm/problem/112798 基本思路： 肯定不能暴力求所有,所以我们要找到它的递推关系,我们带入几个数字将化开： 也就是所以我们设，为这段区间的结果,我们能够得到,然后我们是每次是要找到里结果最大的一个子区间,所以我们再做一个递推,我们设为,这段区间里的最大子区间结果，那么有： 对于每次查询,我们输出结果就行了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> us...

Beautiful Numbers 题目地址： https://ac.nowcoder.com/acm/problem/17385 基本思路： 我们发现因为位数只有位,所以数位之和不会超过,因此我们考虑枚举数位之和,那么对于每个确定的我们把问题转化为了,数字能被整除,并且数位之和为的数的数量,那么这样我们就能每次取模,去进行一个比较简单的数位了,注意如果我们用记录,还有位没有确定,当前数取模结果为,剩下部分数位和为,总数位和为的数的数量,那么对于每次查询并不用去重新初始化,能大大降低复杂度。 参考代码： #pragma GCC optimize(2) #pragma GCC opt...

诡异数字 题目地址： https://ac.nowcoder.com/acm/problem/20669 基本思路： 考虑维护数位,每次我们维护表示填到位，前一个数位的数为,它连续出现了次的答案,对于每次我们只有两个转移方向,要么这一位和上一位相同,，要么不同变为。其余部分都套上数位的板子就可以了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define IO std::ios::sync_with_stdio(...

7的意志 题目地址： https://ac.nowcoder.com/acm/problem/20665 基本思路： 一道比较简单的数位,方便自己熟悉数位的基本思路,和解题模板。总结一下数位,分为几个步骤：首先将数字做拆位,进入记忆化搜索过程,和一般的搜索不同,数位,通常是从高位先开始尝试,而且是在高位尝试了并且未选择该位的极限数字时,该位之后的数位才没有限制了可以在之间任意设置,而也只有这一部分的结果,我们可以使用记忆化的方式进行优化。我们再来分析这道题,明显我们只要维护各个数位之和,和数字大小的和是不是都能被整除,所以我们在中使用两个维度维护这两个值模的结果,然后套用数位的基本模板...

华华和月月种树 题目地址： https://ac.nowcoder.com/acm/problem/23051 基本思路： 我们考虑先离线,将树建出来,然后在序上用差分树状数组维护,但是在这样做的过程中,对于每次的操作二,有些实际还没有被加入的点也被算了权值,所以我们在每次新加点的时候记录一下,这个点被加进来的时候已经有多少权值了,很明显这部分权值是无效的,我们在之后的查询里去除这部分就是了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using name...