nagisa_菜鸡 level
获赞
54
粉丝
18
关注
31
看过 TA
31
女
华南师范大学
2024
C++
IP属地：广东
暂未填写个人简介
私信
关注
发布(38) 刷题
头像
nagisa_菜鸡
2021-08-17 17:01
已编辑
华南师范大学 计算机类
2021牛客暑期多校训练营10 Game of Death（子集反演（容斥原理）+多项式优化）
链接：https://ac.nowcoder.com/acm/contest/11261/G 确实想不到这个状态设计（），估计是对于子集容斥（反演）这个概念接触不多。。 我们设的状态是表示被杀的人刚好是集合S，根据各种反演的惯例我们设表示被杀的人是S的子集，这里，我们子集反演因为根据子集反演(其实就是容斥)：（可能不是那么显然，但想想：g(S)的符号一定是+，那么就需要-g(比S少1人的集合)……这样的容斥形式，也不是不能接受）。 现在目标变成求：显然有式子：令q=1-p，也就是没有命中的概率。 G(x)为固定某x人被射死的概率。 （其实意义就是：对于S内的人，要么没打中，要么打中了集合内的其...
0 点赞 评论 收藏
转发
头像
nagisa_菜鸡
2021-08-01 02:22
华南师范大学 计算机类
2021牛客暑期多校训练营5（B.期望 G.暴力）
这场感觉需要记录的东西貌似不是很多，所以写个总的。 B.Boxes 根据贪心原则，其实我们可以注意到两点：1、是否要提示是开始前决定的。要么，你一开始不要提示，全部盒子都开一次。要么，先要提示，根据提示的数量开盒子。因为假若你中途再要提示，可能要到后发现盒子开多了，还不如一开始就要，花费只多不少。2、要了提示后，你一定是按照盒子价值从小到大开的。因为你开一个盒子都是的概率白或黑，因此从总体来说，从小往大开的话，期望的花费会比较少（可以往下看看期望的计算自己思考下）。显然，如果不要提示，则期望为。若要提示，则就要分情况了。因为有了提示，你就知道有几个白几个黑，这时候，你会在中途因为开够数量而停下...
0 点赞 评论 收藏
转发
头像
nagisa_菜鸡
2021-07-29 22:28
华南师范大学 计算机类
2021牛客暑期多校训练营1 I-Increasing Subsequence（期望dp）
原来上一题是多校第二道期望题啊，我怎么没印象 题目链接：https://ac.nowcoder.com/acm/contest/11166/I 这题转移就比上题容易了些，但这题的状态比较难找到。提取题目中的关键点：p是一个排列，每次选择的数需要大于所有已选的数。因为是一个排列，所以我们可以把当前选的数的大小作为状态。因此，我们可以尝试状态dp[i][j]：上一轮选择了i，前一轮选择了j时的期望轮数。之后，据次得出状态转移式： ps.这里式根据 （可能变成的状态的dp值和+单步贡献）*变成该状态的概率 值得到的。具体看代码吧（） #include <bits/stdc++.h> #d...
0 点赞 评论 收藏
转发
头像
nagisa_菜鸡
2021-07-31 11:44
已编辑
华南师范大学 计算机类
2021牛客暑期多校训练营4 B-Sample Game（概率生成函数、数学推导/期望dp）
链接：https://ac.nowcoder.com/acm/contest/11255/B 这篇题解可能会有些许错误，欢迎大佬们指正Orz 概率生成函数 首先，我们定义概率生成函数(为啥这么定义？菜了，不大清楚，当一个做题方向吧)我们现在需要的出这个函数。 由题意可知：我们抽到的数字的序列，除去最后一个数之外，它肯定是一个不下降的序列，像是1，1，2，3，3，7这样的。这时，我们可以枚举每个数的出现次数，来得到（指的是数字i被抽到的概率）具体的，假如1，1，2，3，3，7这样的序列，对应的就是。我们某个数出现的次数的生成函数，则我们可以知道。根据等比数列求和，因此，记住这个函数，我们后面会用...
0 点赞 评论 收藏
转发
头像
nagisa_菜鸡
2021-07-25 04:31
华南师范大学 计算机类
2021牛客暑期多校训练营3 E.Math 解题报告（结论、打表）
所以为什么会在这里出现imo题https://ac.nowcoder.com/acm/contest/11254/E 通过率非常高的一题，然而因为我太菜了，并没有过 这题我认为算是一个套路，实在无法理解可以暂时就留个印象，以后还遇到类似的可以对比着看。这道题一拿到手应该大部分人和我一样想到打表。打出一部分表后，我们发现，任意数都符合条件。 接下来，我们设，则我们固定x，方程可整理为，我们固定x（也就是说我们等会选择枚举x），则，由韦达定理：那么，接下来，我们固定k，我们要计算的是系数为k的(x,y)对数由上面的韦达定理可知：若一对值满足条件，则，另一对符合条件的，系数为k的数对为我们现在知道符...
0 点赞 评论 收藏
转发
头像
nagisa_菜鸡
2021-07-20 14:09
已编辑
华南师范大学 计算机类
2021牛客暑期多校训练营2-J.Product of GCDs（扩展欧拉定理+pr分解质因数+容斥原理）
题目：https://ac.nowcoder.com/acm/contest/11253/J大意为给一个数组a，求数组a中所有大小为k的子集的gcd的乘积。 根据惯例，估计是转化为枚举gcd后统计贡献。对于每个i，我们需要求有几个子集的gcd为i，考虑组合数为，num为数组中i的倍数的个数，但这样统计会包含gcd为i的倍数的集合，因此，考虑从大到小枚举，枚举一个i后，减去gcd为i的倍数的集合的个数，即可得到gcd为i的集合的个数。综上所述，假设gcd为i的集合的个数为，则答案为。但是，还没完，因为数字有这么大，可想而知的值一定不小，因此，考虑欧拉降幂。我们可以先通过扩展欧拉定理求出（或者是）...
0 点赞 评论 收藏
转发
头像
nagisa_菜鸡
2021-07-20 11:53
已编辑
华南师范大学 计算机类
2021牛客暑期多校训练营1-G.Game of Swapping Numbers（思维）
题目链接：https://ac.nowcoder.com/acm/contest/11166/G题目大意：给两个数组a,b，现在可以交换a中的数k次，求的最大值。 看了题解。可以这样想：把要求的值看作对每个和前面放符号，满足总的+的数目=总的-的数目。那么，最后的结果就是a、b所有数*符号后的和。统计没有交换前的答案。根据贪心原则，最大的结果应该就是。这样就相当于对每个赋为+，赋为-。考虑交换。显然，我们要交换的目标是两个符号不同的数，然后交换他们的符号，者才能使得答案变化。在考虑贪心，想要最后答案最大，肯定是要使得+的和最大，-的和最小，因此，考虑将上面+的数降序排列为数组add，-的数升序...
0 点赞 评论 收藏
转发
头像
nagisa_菜鸡
2021-07-20 01:51
华南师范大学 计算机类
2021牛客暑期多校训练营1-H.Hash Function (同余性质、多项式加速)
题目链接：https://ac.nowcoder.com/acm/contest/11166/H 涉及到的东西其实不是很难，但是多项式加速还是比较难想到的。 题目可以转化为：找到最小的mod，使得$a_i$处于mod的不同同余系中。扫一眼同余的性质，有一条： 若，则。并且，若，则对于p的某一因数，。根据上面两条，我们要求的就是：最小的、且不为所给的数中任意两个数的差的因数的数。但是这个多项式加速就比较难想。我们可以这样总结：若需要对于两个数组中的元素、两两之间进行操作，朴素算法需要，可以考虑多项式优化为。我们可以构造两个多项式：一个多项式系数为表示数i是否出现在数组中。另一个多项式系数表示数...
0 点赞 评论 收藏
转发
头像
nagisa_菜鸡
2021-03-01 18:24
华南师范大学 计算机类
CF696C PLEASE 解题报告（推式子+欧拉降幂+细节）
首先，根据题目要求，因为每一轮都需要把中间给替换掉可知，要想最终钥匙在中间，那么在最后一轮之前钥匙一定不能在中间。又因为一轮可以把中间替换成任意一个非中间元素，再加上经过n轮每轮一共有2种决策，所以共有种局面。所以，得到递推式：。之后，考虑我们要求的答案ans，则有：,要求,考虑求其通项公式，则,代替带入上式： ，这个高中做过不少了吧？得到。这里若不考虑符号，则上下可能都为负数，此时再去+mod之后的结果是上下分别mod之后的结果，不符合题意，因此，我们需要讨论下符号。当n为奇数： n为偶数： 考虑细节：(n为偶数)和(n为奇数)mod 3都为0（打表试试？），所以，3应该放在分子处*3的逆元...
0 点赞 评论 收藏
转发
头像
nagisa_菜鸡
2021-02-27 13:28
已编辑
华南师范大学 计算机类
2021牛客寒假算法基础集训营5 C.比武招亲（下）(拉格朗日插值法+欧拉降幂)
集训营第二次考欧拉降幂了Orz首先不管n，我们就算能选[1,m]的取值的时候的答案。和B题差不多的idea，我们能想到答案其实是,这是一个n+1次的多项式，如果说m很大的话，我们当然不能直接算，但是，我们可以利用拉格朗日插值法求出这个式的值。建议先学习下拉格朗日插值法。之后，考虑的情况，我们当然不能直接算这个m，那么，题目给了模数，我们考虑只求m mod p的值，那么，考虑如何利用f(m mod p)求f(m).因为为n+1次多项式，那么，我们设，则，，二项式定理展开后，发现，因此，我们只需要求。对于,我们考虑欧拉降幂求即可。这道题需要学的主要是欧拉降幂的写法，这里所用的EXP函数的方法，或者...
0 点赞 评论 收藏
转发
头像
nagisa_菜鸡
2021-02-26 13:22
已编辑
华南师范大学 计算机类
0 点赞 评论 收藏
转发
头像
nagisa_菜鸡
2021-02-17 11:54
已编辑
华南师范大学 计算机类
【2021牛客寒假算法基础集训营1】H 幂塔个位数的计算（欧拉降幂）
虽然可以找规律，但是太难了Orz蒟蒻只能选择欧拉降幂。我们先来看下扩展欧拉定理：截自oiwiki 欧拉降幂就是用第三条式子来降低幂次，方便计算的。PS：这里为什么不会出现第二条式子的情况？我大概算了下，a取1的情况我们会特判掉，a取2以上大概就不会发现第二条式子的情况了。所以，不需要考虑第二条式子。UPD:保险起见，我还是加了判断是否使用第二条式子的部分。例如，我们按照样例1：我们要求的其实就是： 而如果层数再多:任何数mod 1都为0，直接返回0即可。这可能也是存在规律的依据。大数，写python呀！ from math import log def phi(x): if x == ...
0 点赞 评论 收藏
转发
头像
nagisa_菜鸡
2021-01-21 19:19
华南师范大学 计算机类
[HNOI2017]礼物 解题报告（数学常识+FFT）
估计多项式会吓到不少人，写个题解装个b。我们数学题嘛，我们把原式写出来：题目要求的就是：设x序列都加u，y序列都加v，则 我们可以令u-v=t,则： 运用初中数学知识，我们我们可以把上式子看作一个二次函数,变量为t。那么，我们就可以知道当u-v取多少的时候，相同x,y下，res能够最小。因此，亮度调整并不是本题的难点所在。但是，题目还允许我们使得x对应的y不一样。观察上式子，我们发现：只有是同时关联x和y的，我们需要求出的是这个式子的最小值。我们可以把这个式子变一下：,这里的x是原来的x反转之后的。我们发现，这是个一个卷积的形式。那么，对于卷积，我们自然想到多项式算法（FFT，NTT），因为没...
0 点赞 评论 收藏
转发
工具箱
牛客网
牛客企业服务