kittens专题

G - Pictures with Kittens (easy version) dp

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

Codeforces Round #541 (Div. 2) F、Asya And Kittens||并查集

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

dp 优化 F2. Pictures with Kittens (hard version)

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;

Codeforces 541 F. Asya And Kittens(并查集+DFS)

题目大意是说,输入 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所在的集合必须相邻(数组的第一个和最后一个不算相邻)。求这组序列最开始的排列情况,答案不唯一,输出一组答案即可 做

F. Asya And Kittens(思维+树形构造+启发式合并)

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

F. Asya And Kittens(List+并查集)

有 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

codeforces 构造 Asya And Kittens

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

CF1077F2 Pictures with Kittens (hard version)(单调队列+dp优化)

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

Codeforces 1077F1 Pictures with Kittens (easy version)(DP)

题目链接: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个位置中的其中