nagisa_菜鸡

题解

/ 注册

全部文章 / 题解（共34篇）

2021牛客暑期多校训练营10 Game of Death（子集反演（容斥原理）+多项式优化）

链接：https://ac.nowcoder.com/acm/contest/11261/G 确实想不到这个状态设计（），估计是对于子集容斥（反演）这个概念接触不多。。我们设的状态是表示被杀的人刚好是集合S，根据各种反演的惯例我们设表示被杀的人是S的子集，这里，我们子集反演因为根据子集反演(其实就...

数学概率论数论

2021-08-17

3 920

2021牛客暑期多校训练营5（B.期望 G.暴力）

这场感觉需要记录的东西貌似不是很多，所以写个总的。 B.Boxes 根据贪心原则，其实我们可以注意到两点：1、是否要提示是开始前决定的。要么，你一开始不要提示，全部盒子都开一次。要么，先要提示，根据提示的数量开盒子。因为假若你中途再要提示，可能要到后发现盒子开多了，还不如一开始就要，花费只多不少。2...

数据结构

2021-08-01

0 773

2021牛客暑期多校训练营1 I-Increasing Subsequence（期望dp）

原来上一题是多校第二道期望题啊，我怎么没印象题目链接：https://ac.nowcoder.com/acm/contest/11166/I 这题转移就比上题容易了些，但这题的状态比较难找到。提取题目中的关键点：p是一个排列，每次选择的数需要大于所有已选的数。因为是一个排列，所以我们可以把当前选的...

数学概率论

2021-07-29

0 798

2021牛客暑期多校训练营4 B-Sample Game（概率生成函数、数学推导/期望dp）

链接：https://ac.nowcoder.com/acm/contest/11255/B 这篇题解可能会有些许错误，欢迎大佬们指正Orz 概率生成函数首先，我们定义概率生成函数(为啥这么定义？菜了，不大清楚，当一个做题方向吧)我们现在需要的出这个函数。由题意可知：我们抽到的数字的序列，除去最...

数论多项式

2021-07-27

11 1185

2021牛客暑期多校训练营3 E.Math 解题报告（结论、打表）

所以为什么会在这里出现imo题https://ac.nowcoder.com/acm/contest/11254/E 通过率非常高的一题，然而因为我太菜了，并没有过这题我认为算是一个套路，实在无法理解可以暂时就留个印象，以后还遇到类似的可以对比着看。这道题一拿到手应该大部分人和我一样想到打表。打出...

数论

2021-07-25

5 1394

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的倍数的个数，但这样统...

数论

2021-07-20

4 1285

2021牛客暑期多校训练营1-G.Game of Swapping Numbers（思维）

题目链接：https://ac.nowcoder.com/acm/contest/11166/G题目大意：给两个数组a,b，现在可以交换a中的数k次，求的最大值。看了题解。可以这样想：把要求的值看作对每个和前面放符号，满足总的+的数目=总的-的数目。那么，最后的结果就是a、b所有数*符号后的和。统...

贪心

2021-07-20

0 725

2021牛客暑期多校训练营1-H.Hash Function (同余性质、多项式加速)

题目链接：https://ac.nowcoder.com/acm/contest/11166/H 涉及到的东西其实不是很难，但是多项式加速还是比较难想到的。题目可以转化为：找到最小的mod，使得$a_i$处于mod的不同同余系中。扫一眼同余的性质，有一条：若，则。并且，若，则对于p的某一因数，...

2021-07-20

2 825

牛客练习赛78（AB.思维C.树形dp（树中两个子树最大贡献和）D容斥原理E枚举

A.CCA的词典没啥好讲的，map记录下出没出现过，然后每次查询枚举下可能的来源，叠加贡献即可。注意特判aa这种情况 map<string,int>cnt; int main(){ int n; cin>>n; for(int i=0;i<n;...

2021-03-15

0 763

CF696C PLEASE 解题报告（推式子+欧拉降幂+细节）

首先，根据题目要求，因为每一轮都需要把中间给替换掉可知，要想最终钥匙在中间，那么在最后一轮之前钥匙一定不能在中间。又因为一轮可以把中间替换成任意一个非中间元素，再加上经过n轮每轮一共有2种决策，所以共有种局面。所以，得到递推式：。之后，考虑我们要求的答案ans，则有：,要求,考虑求其通项公式，则,代...

每日一题

2021-03-01

0 823