[SCOI2008]着色方案 题目地址： https://ac.nowcoder.com/acm/problem/20265 基本思路： 必须吐槽一下，怎么题目又没有写数据范围QAQ，这题没数据范围写不了啊。 考虑，但是如果我们用每种颜色的油漆作为维度显然不太行，因此我们关注,考虑到每一种油漆，如果能涂的木块的数量相同的话，其实是等效的，所以我们用分别表示还剩下次使用次数的油漆的数量为，上一次我们涂的是使用次数剩余为的油漆，然后注意我们每次转移时因为不能连续两块相同颜色，所以如果上一次用的还能涂次的油漆，那么当前就有一种还能够涂次的油漆无用。由于并没有明显的顺序递推关系，所以我们考虑...

2020牛客暑期多校训练营（第一场） 比赛地址： https://ac.nowcoder.com/acm/contest/5666 补题开始了，一题题慢慢补吧，顺序由简到难，尽量将能补的题都补了，这篇长久更新。 F Infinite String Comparision 题目地址： https://ac.nowcoder.com/acm/contest/5666/F 基本思路： 这题很明显不会比较很多次，所以我们我们可以猜一下结论，我们直接尝试将字符串循环比较 次就行了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimi...

点权和 题目地址： https://ac.nowcoder.com/acm/problem/14393 基本思路: 这题的题意好像说的不是很明白，其实意思应该是第次操作先将与x树上距离<=1的点点权加一后，再将这些与x树上距离<=1的点的点权之和作为这次操作的结果乘以记录进最终结果。 所以根据题意，我们设三个数组变量,,分别表示，当前点被操作次数,当前点孩子节点被操作次数,当前点孙子节点被操作次数。对于每次的操作,我们先更新这三个数组变量的值然后再利用这三个变量计算这次操作的结果,每次操作后的结果应当是自己，父亲，和所有孩子的点权之和，那么我们分别计算贡献：此时父亲节点的点...

D 树上求和 题目地址： https://ac.nowcoder.com/acm/contest/6290/D 基本思路： 比较裸的一道题，没有什么思维量，首先要维护子树状态，很明显我们可以求个序，然后用数据结构去维护，观察一下题意，要维护区间平方和，进行区间查询和区间修改，所以考虑线段树。那么维护区间平方和的线段树怎么写函数,其实也比较简单,假设这段区间内的平方和开始为,那么我们将整个区间加,就变为化简一下提出来其实就是所以我们在维护区间平方和的同时在维护一下那部分普通的区间和，然后就很容易进行了。 参考代码： #pragma GCC optimize(2) #pragma GC...

B 可持久化动态图上树状数组维护01背包 题目地址： https://ac.nowcoder.com/acm/contest/6290/B 基本思路： 名字非常的唬人，然而是一个***题，我们先将负数从后往前删，就能保证它们在自己所在的位置被删掉，获得最小的负值,然后再让正数都在第一个位置删掉，获得最小正值就可以了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define IO std::ios::sync_wi...

A 数列下标 题目地址： https://ac.nowcoder.com/acm/contest/6290/A 基本思路： 找离一个位置最近的比他大的数的位置，比较明显的一个单调栈，不懂单调栈的同学可以去学习一下，就是在入栈之前保证栈的单调性就可以了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define IO std::ios::sync_with_stdio(false) #define int long ...

[SCOI2009]生日快乐 题目地址： https://ac.nowcoder.com/acm/problem/20272 基本思路： 由于，所以我们考虑直接暴力;我们用double dfs(double x,double y,int k)表示将长为,宽为的矩阵切成块的最小长宽比;对于每次切，这时的每块蛋糕的面积一定是确定的，而我们一定是平行切，也就是说我们切长的时候切出来的一定要是的倍数，切宽的时候一定要是的倍数，所以我们枚举每种切法，然后将切出来的两个剩余部分继续就可以了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize...

[SCOI2007]压缩 题目地址： https://ac.nowcoder.com/acm/problem/20252 基本思路： 题目没有给数据范围QAQ，去查了一下原题，所以考虑区间;我们如果朴素的去区间，设表示范围能被压缩的最小长度，那么我们容易得到如下的转移方程: 不压缩，正常的长度转移：, , 如果区间能被压缩: 压缩后要填加一个; 但是在这题中我们并不能这样朴素的去转移，因为假设区间中已经有了，由于是和最近的匹配的，所以我们并不可能压缩掉这整块区间，因此我们考虑多加一维,设,表示这段区间有，表示没有; 那么在没有的情况里前两个转移方程不变为: 不压缩，正常的长度转移： ...

NC19810 kingdom 题目地址： https://ac.nowcoder.com/acm/problem/19810 基本思路： 题意是让我们构造一棵树，父亲的重儿子的权值等于父亲，否则权值等于父亲节点加一，我们要让整棵树权值最大。我们设表示个节点能构造出来的权值最大的树，那么这棵树应当是多个子树和一个根节点连接起来的;连接以后这些子树里肯定存在一个重儿子，假设这个重儿子的节点数为，那么除了这个节点和根节点外，其余节点都要贡献一次加一，那么那么我们如何最优的构造这棵树的子树，我们可以猜个结论，首先对于节点数，我们枚举它可能的重儿子的大小，然后对于这个节点，我们尽量多的构造大小...

NC16645 矩阵取数游戏 题目地址: https://ac.nowcoder.com/acm/problem/16645 基本思路： 首先根据题意我们易发现矩阵的每一行是独立的，因此我们计算出每一行答案再相加就行了。 要计算每一行的答案，我们可以使用区间,设表示这一行范围内的最大取数方案，我们将原题的取数转换成向区间两边加数，每次能向两边扩展就有两种状态转移途径，因此设表示当前所在行易得如下的状态转移方程： 区间长度为时： 否则: 根据以上，我们就能求得每一行的最佳取数结果，相加就是答案了。 数据范围比较大，会爆 所以我们要开 。 参考代码： #pragma GCC opt...

E「水」悠悠碧波 题目地址： https://ac.nowcoder.com/acm/contest/6226/E 基本思路： 看到前缀后缀就应该能想到算法，我们先求一次的数组，然后直接从最后位置类似匹配失败过程往前找每次匹配的前缀作为模式串，然后每次再跑一遍看整段串中是否出现过三次以上的模式串就是了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define IO std::ios::sync_with_stdi...

D 绝地求生(pubg) 题目地址： https://ac.nowcoder.com/acm/contest/6226/D 基本思路： 就是一个裸的，数据比较大用或者开都行 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define IO std::ios::sync_with_stdio(false) #define int128 __int128 #define rep(i, l, r) for (int i =...

C Tree 题目地址： https://ac.nowcoder.com/acm/contest/6226/C 基本思路： 类似换根的思路，我们先只向下考虑，也就是先只考虑子树的情况。 这样我们设表示以为根的子树中联通点集的数量，那么易得如下转移方程： 然后我们要计算每个点里向上那部分点集的贡献设为，考虑换根，以表示当前节点的最终答案，那么易得如下转移方程： ；。 看上去问题已经解决了，可是题目有一个坑，因为答案是要取模的，所以在 时我们不能直接求逆元计算，所以这时候类似于将子树反向一下，再通过之前算子树的方法暴力计算当前节点的就行了。 参考代码： #pragma GCC opt...

B Circle 题目地址： https://ac.nowcoder.com/acm/contest/6226/B 基本思路： 相邻的两数一定互质，任何数和也一定互质，所以只要这样排就一定都满足相邻互质，最大对数是n。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define IO std::ios::sync_with_stdio(false) #define int long long #define rep...