https://codeforces.com/problemset/problem/1077/F1   这个其实是一个比较简单的dp了 题目大意： 给你n个数，让你从n个数里选出x个数，并且每隔k个至少选一个数。 开始不知道怎么去写，也不知道怎么去定义dp 这个应该是对于dp不是特别的熟练，实际上dp用途很广，而且可以用到的地方很多，效果也很好。 这种时候就应该大胆一点，你需要什么，想达成什么效

Codeforces Round #541 (Div. 2) F、Asya And Kittens||并查集 F、Asya And Kittens 当时在比赛的时候没注意到这题，其实还是很好做的； 思维： 每次需要将一起玩的猫放在一个集合中就可以很简单的模拟过程； 懂并查集的同学也可以很轻松的实现集合的查找和合并； 不懂的同学向大家推荐一个大佬的博客； 那么接下的问题就是如何将集合中的

dp的优化可能是自己的弱项吧 F1中n*n*n的复杂度强行过去了　 F2就无能为力了； 状态转移 dp[ i ] [ j ] 第一个i存的是位置　　1-n;    j是放入数字的个数 　　然后F1就暴力过去了 #include<bits/stdc++.h>#define int long longusing namespace std;const int maxn=5000+10;

题目大意是说，输入 n n n，表示有 n n n个数 1 1 1~ n n n，接下来有 n − 1 n-1 n−1对关系，每行输入两个数 a a a和 b b b，表示将 a a a所在的集合与 b b b所在的集合合并，但是合并有前提条件， a a a所在的集合与 b b b所在的集合必须相邻（数组的第一个和最后一个不算相邻）。求这组序列最开始的排列情况，答案不唯一，输出一组答案即可 做

https://codeforces.com/problemset/problem/1131/F 思路: 对于每一个编号，我们将其连边都看作他的儿子，然后将儿子的状态最后都更新到他本身。 看成他的儿子就变成了树形结构。这里借用大佬的图 对于 1 3 1 2 4 5 4 6 1 4 G[1] = {3,2,4}，每个子树都保证顺序可行，那么合并起来的顺序也是可行的。   可以看到

有 n 只猫，原来分别在一个笼子里，但是相邻的猫想一起玩就将它们放在一个笼子里，但是现在它们凑成了一堆，问他们原来在几号笼子里  const int N=15*1e4+5;int n,m,t;int i,j,k;int fa[N];list<int> l[N];int Find(int x){return fa[x]==x? x: fa[x]=Find(fa[x]);}int ma

题目描述：   算法：并查集         使用两个并查集vl, vr分别记录当前集合的最左元素和最右元素，在合并时将记录最左元素的根节点接在左侧集合的根节点下，记录右侧的接在右侧根节点下即vr[ar] = br, vl[bl] = al，ar, br为两个集合的根节点。         在拼接过程中再记录拼接点的左右元素分别是谁，即r[ar] = bl, l[bl] = ar。

题目传送门 唉，曾经觉得单调队列学的没啥用。。。 题目大意 这个题目的意思就是说： 给你一个数列a，你需要选择s个元素，使得连续的k个元素都至少有一个被选中。 需要你最大化选出来的所有数的和。 也就是滑动窗口问题：一个k单位大小的窗口，每一个窗口必须有数字选中，求最大和。 思路 这道题我也没有思路。。还看题解聚聚们的做法： 这就是用单调队列，先模拟一下滑动窗口. 这里参考一下大佬的博

题目链接：Pictures with Kittens (easy version) 题意：给定n长度的数字序列ai，求从中选出x个满足任意k长度区间都至少有一个被选到的最大和。 题解：$dp[i][j]$：以i为结尾选择j个数字的最大和。 $dp[i][j]=max(dp[i][j],dp[s][j-1]+a[i])$，$s为区间[i-k,i)$。 以i为结尾的最大和可以由i之前k个位置中的其中