- 2024-07-18C. Jellyfish and Green Apple
原题链接题解1.由于是除二操作,所以最后的平均数一定能表示成\(k_1\cdot\frac{1}{2^{i_1}}+...+k_t\cdot\frac{1}{2^{i_t}}\)的形式2.最小的\(\frac{1}{2^i}\)由于没有往下再分,所以数量一定是偶数,把他们的数量除二加到\(\frac{1}{2^{i-1}}\)上,此时\(i-1\)就变最小的了
- 2024-07-03D. Jellyfish and Mex
题目:链接:https://codeforces.com/problemset/problem/1875/D思路:这题刚开始没啥想法,后面推演了一下发现是个动态规划:从左到右先找出首先为0的点,那么我要求的值就是这个区间内的值。然后假设先把ax清为0,那么所加的值就是ax*ptr,对比发现就是上一阶段的小规模。所以可以用递推
- 2024-05-15A. Jellyfish and Game
原题链接题解1.经过样例证明,双方的交换策略一定是自己最小值去换对面最大值2.双方交换的最大值一定局限在双方各自初始最大值之间,最小值也是code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;intmain(){llt;cin>>t;while(t--)
- 2024-03-29Jellyfish and EVA
这道题目实在没有什么好的办法去描述状态空间,只能感性理解一下,等对概率的理解更深了再来吧。。。发现这是一道概率DP,而且满足拓扑序,我们直接倒序转移就好了设\(f_i\)表示从第\(i\)个点到第\(n\)个点的概率,我们发现当只有一条出边是非常好转移的,但是其他就不太行了我们遇到这种
- 2024-01-1813 Jellyfish and Game
JellyfishandGame因为n,m很小,所有直接暴力就行#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;voidsolve(){ intn,m,k; cin>>n>>m>>k; vector<int>a(n+1); vector<int>b(m+1); for(inti=1;i<=n;i++)cin>
- 2024-01-1812 Jellyfish and Green Apple
JellyfishandGreenApple数论将苹果平均的分给人,可以将苹果一分为二,问你最少分多少次。首先把能分的都分掉就是n%=m,其次操作数是很好想的,就一直*2并且%m,直到n==0,关于这题有难度的就是n,m分不了的情况。设想一下,成功的情况,也就是这个n一直在乘2最后能==m。那么转换一下就是
- 2023-12-21Jellyfish and OEIS
JellyfishandOEIS题意题面传送门题解恭恭敬敬给致远磕大头。首先我们将原序列分割成很多块,使得每一块都是相对位置的排列。且这一块内不可分割出另外的块。例如:\([3,1,2][5,4]\),而\([1,2,3]\)是不合法的,因为他可以被分割为\([1][2][3]\)。在进行这一步操作之后,我们发
- 2023-11-161-1875D - Jellyfish and Mex
题意:有一个长度为\(n\)的数组,每次删除一个数直到删完,求每次删除后数组的mex的和的最小值。(\(\sumn\leq5000,a_i\leq10^9\))思路:排序后,只有从0开始连续的数在会有贡献,对于连续的数,如果要消去他的对答案的贡献,只有全部去掉才行,考虑n的范围小于5000,n^2做法被允许。//因为排
- 2023-10-08【题解】CodeForces-1874/1875
CodeForces-1875AJellyfishandUndertale一定是等待降到\(1\)或者能补满到\(a\)时才使用工具,依题意模拟即可。提交记录:Submission-CodeForcesCodeForces-1874AJellyfishandGame这种题目有点思路但是不是很会。赛时第一发写得根据奇偶性判断,\(k\)为偶数错了,然后感
- 2023-10-07Codeforces Round 901 (Div. 2) C. Jellyfish and Green Apple (位运算)
CodeforcesRound901(Div.2)C.JellyfishandGreenApple//思路:浮点数转二进制,a/b的结果为gcd(a,b)*最简分式(n/m)的结果//苹果能分的前提是人数得是一个2的次幂数,通过切割只能分为形同0.001的二进制小数//a/b的二进制如果在从左到右的sp位为1,则需要切割到这个情况//一个
- 2023-10-04[CF1874D] Jellyfish and Miku
JellyfishandMikuD<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}dp_{i+1}\]化简第三个式子可得\[a_{i+1}(dp_i-dp_{i+1})=a_i(dp_{i-1}-dp_i)+a_i+a_{i+1}\]设\(
- 2023-10-01CodeForces 1874B Jellyfish and Math
洛谷传送门CF传送门看到这种操作乱七八糟不能直接算的题,可以考虑最短路。对于\(a,b,c,d,m\)按位考虑,发现相同的\((a,b,m)\)无论如何操作必然还是相同的。于是考虑对于每个可能的\((0/1,0/1,0/1)\),所有终态有\((c=0/1,d=0/1)\)或者不确定。这样我们对于一
- 2023-10-01Jellyfish and Mex
2023-10-01题目JellyfishandMex难度&重要性(1~10):5题目来源luogu题目算法dp解题思路这道题一眼dp。我们需要考虑的是对于函数\(\operatorname{mex}\)的性质,假设当前\(a\)数组存在\(0\simx\),则\(\operatorname{mex}a=x+1\)。再记每一个数出现过\(s_0,s_1,\cd
- 2023-10-01CF1875B Jellyfish and Game
思路题意大概是两人都有一组数,奇数轮,第一个人可以选择和第二个人交换一个数字也可以不换,偶数轮,第二个人可以选择和第一个人交换一个数字也可以不换。首先可以猜测,我们每次都应该选择交换对方的最大值和自己的最小值,如果自己的最小值都比对方大的话就不交换。应该比较好想,这里感
- 2023-10-01CF1875D Jellyfish and Mex
思路看到\(n\)的范围只有\(5000\),并且\(\sumn\)的范围也是\(5000\),所以可以考虑\(n^2\)的做法。每次操作肯定都是一次性删完某个数字,如果删除某个数字删一半又去删别的数字,答案肯定会变大。所以我们可以考虑统计所有数字的数量,记为\(num_i\),来计算删完某个数字的最小
- 2023-10-01题解 CF1875D【Jellyfish and Mex】
显然,除非\(\operatorname{mex}a=0\),否则不会删除\(>\operatorname{mex}a\)的数。而\(\operatorname{mex}a=0\)时不对答案产生贡献,因此任意时刻我们都可以忽略\(a\)中\(>\operatorname{mex}a\)的数。又显然,一旦我们开始删一个数,就会先把所有与之相等的数删光。否则,设最先