Jellyfish

题目链接 点击打开链接 题目解法 一个朴素的结论是：\(fun(p)\le \frac{n\times (n+1)}{2}\) 所以可以把 \(lim\) 的范围缩小到 \(\frac{n\times (n+1)}{2}\) 首先可以得到一个简单的 \(O(n^6)\) 做法： 令 \(f_{i,j ......

Jellyfish and OEIS 题意 题面传送门 题解 恭恭敬敬给致远磕大头。 首先我们将原序列分割成很多块，使得每一块都是相对位置的排列。且这一块内不可分割出另外的块。 例如：\([3,1,2][5,4]\)，而 \([1,2,3]\) 是不合法的，因为他可以被分割为 \([1][2][3] ......

题意： 有一个长度为\(n\)的数组，每次删除一个数直到删完，求每次删除后数组的mex的和的最小值。（\(\sum n \leq 5000 , a_i\leq 10^9\)） 思路： 排序后，只有从0开始连续的数在会有贡献，对于连续的数，如果要消去他的对答案的贡献，只有全部去掉才行，考虑n的范围小于 ......

C. Jellyfish and Green Apple 题目大意： 有\(n\)苹果，\(m\)个人，将苹果平分给每个人，每块苹果可以二分，问最少的分割次数 思路： 首先，当\(n\%m==0\)时,说明，苹果可以等分直接输出\(0\) 其次当\(n>m\)时，\(n\%=m\), 最终的苹果块数 ......

题意 给定一个序列 \(m\) ，你需要求出满足以下性质排列 \(p\) 的个数，对大质数取模： 对于任意 \(l,r\) ，\(p_{l...r}\) 为一个 \([l,r]\) 的排列与 \(r \le m_l\) 不同时成立。 Sol 考虑从题目的奇怪限制入手（也只能从这里入手），我们记一个区 ......

题目链接 不明白出题人的脑回路是不是被宇宙射线改变过 /jy。 题目给出了若干个区间，要我们计算满足每个区间都不是对应下标的排列的数量，正着计算不满足要求的数量是困难的，我们将其容斥，转化为钦定一些区间要求其必须满足它是对应下标的排列，在下文中，我们称这样的区间为一个约束。 我们设约束的集合为 \( ......

给定序列 \(m_i\)，求有多少排列 \(p\) 满足：对于满足 \(l \le r \le m_l\) 的所有 \((l,r)\)，\(p_{l \sim r}\) 都不是 \(l \sim r\) 的排列。答案对 \(10^9 + 7\) 取模。 \(n \le 200\)，时限 \(\tex ......

Codeforces Round 901 (Div. 2) D. Jellyfish and Mex //思路：对于大于mex的数不做处理，把0删完为结束 //dp[j]为mex更新到j所需要的最小花费 //用mex=i时更新到j，转移方程为 dp[j] = min(dp[j], dp[i] + i ......

Codeforces Round 901 (Div. 2) C. Jellyfish and Green Apple //思路：浮点数转二进制，a/b的结果为 gcd（a，b）*最简分式（n/m）的结果 //苹果能分的前提是人数得是一个2的次幂数，通过切割只能分为形同0.001的二进制小数 //a/ ......

Jellyfish and Miku D<C<B,哈哈。 设 \(dp_i\) 为起点为 i 时的期望步数,则 \[dp_0=1+dp_1\\ dp_n=0\\ dp_i=1+\frac{a_{i-1}}{a_{i-1}+a_i}dp_{i-1}+\frac{a_{i-1}}{a_{i-1}+a_i ......

考虑对 \(\sum m_i-i+1\) 个不可行的集合进行容斥，即钦定一些区间集，要求它们对应的 \(p_l,p_{l+1},\cdots,p_r\) 必须是 \([l,r]\) 的排列，计算方案数乘以容斥系数之和。 如果容斥的集合中存在相交的区间，那么这个方案数其实不太好计算。不过根据区间的性质 ......

题意 给定一个有向无环图，对于任意一条边 \((u_i, v_i)\)，有 \(u_i < v_i\)。 定义一次从节点 \(u\) 开始的移动为如下过程： \(\tt{Alice}\) 选择从 \(u\) 出发的且未被删除的一条边。 \(\tt{Bob}\) 在从 \(u\) 出发的且未被删除的边 ......

洛谷传送门 CF 传送门 看到这种操作乱七八糟不能直接算的题，可以考虑最短路。 对于 \(a, b, c, d, m\) 按位考虑，发现相同的 \((a, b, m)\) 无论如何操作必然还是相同的。 于是考虑对于每个可能的 \((0/1, 0/1, 0/1)\)，所有终态有 \((c = 0/1, ......

2023-10-01 题目 Jellyfish and Mex 难度&重要性(1~10):5 题目来源 luogu 题目算法 dp 解题思路 这道题一眼 dp。 我们需要考虑的是对于函数 \(\operatorname{mex}\) 的性质，假设当前 \(a\) 数组存在 \(0\sim x\)，则 ......

思路 题意大概是两人都有一组数，奇数轮，第一个人可以选择和第二个人交换一个数字也可以不换，偶数轮，第二个人可以选择和第一个人交换一个数字也可以不换。 首先可以猜测，我们每次都应该选择交换对方的最大值和自己的最小值，如果自己的最小值都比对方大的话就不交换。应该比较好想，这里感性证明一下。 如果用的不是 ......

思路 看到 \(n\) 的范围只有 \(5000\)，并且 \(\sum n\) 的范围也是 \(5000\)，所以可以考虑 \(n^2\) 的做法。 每次操作肯定都是一次性删完某个数字，如果删除某个数字删一半又去删别的数字，答案肯定会变大。 所以我们可以考虑统计所有数字的数量，记为 \(num_i ......

思路 首先我们可以考虑把能分的都先分了，再选择去切剩下的苹果。 那么我们只需要考虑苹果数量少于人数的情况，每个人能分的苹果都必然少于目前的单个苹果，所以每个苹果都必须切一刀，那么答案数就会增加当前的数量，再把能分的都分了，重复这一过程，直到分完为止。这样去切一定是最优的。 那么，什么时候无解呢？ 因 ......

显然，除非 \(\operatorname{mex}a=0\)，否则不会删除 \(>\operatorname{mex}a\) 的数。而 \(\operatorname{mex}a=0\) 时不对答案产生贡献，因此任意时刻我们都可以忽略 \(a\) 中 \(>\operatorname{mex}a\ ......

Jellyfish: 快速统计长序列中每个K-mers出现次数 一个老工具，2011 发表于Bioinformatics，目前引用1018次。因为需要用所以看了一下原文。 Jellyfish，是此研究开发的，可以快速统计长序列中每个K-mers出现次数的软件。 基于K-mers的应用很广，包括基因组 ......