nagisa_菜鸡

题解

/ 注册

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

2021牛客寒假算法基础集训营5 C.比武招亲（下）(拉格朗日插值法+欧拉降幂)

集训营第二次考欧拉降幂了Orz首先不管n，我们就算能选[1,m]的取值的时候的答案。和B题差不多的idea，我们能想到答案其实是,这是一个n+1次的多项式，如果说m很大的话，我们当然不能直接算，但是，我们可以利用拉格朗日插值法求出这个式的值。建议先学习下拉格朗日插值法。之后，考虑的情况，我们当然不能...

多项式数论

2021-02-27

0 801

2021寒假算法基础集训营6（A.C.D.水 I.BFSJ.MST B.F.推式子 E.dp G.dp(TSP)/贪心）

写给自己：主要要看的是B.F.E.G总结：1.对TSP问题认识不足。2.B题模3这个条件的性质不清楚。3.复数快速幂？不敢往复数想。注意：为了阅读效果，我把头文件、快读快写删了。需完整代码可以看我提交 A.回文括号序列计数 ll solve(){ if(n==0)return 1; ...

数论贪心 dp

2021-02-26

0 657

【2021牛客寒假算法基础集训营1】H 幂塔个位数的计算（欧拉降幂）

虽然可以找规律，但是太难了Orz蒟蒻只能选择欧拉降幂。我们先来看下扩展欧拉定理：截自oiwiki 欧拉降幂就是用第三条式子来降低幂次，方便计算的。PS：这里为什么不会出现第二条式子的情况？我大概算了下，a取1的情况我们会特判掉，a取2以上大概就不会发现第二条式子的情况了。所以，不需要考虑第二条式子。...

数论

2021-02-04

4 989

[HNOI2017]礼物解题报告（数学常识+FFT）

估计多项式会吓到不少人，写个题解装个b。我们数学题嘛，我们把原式写出来：题目要求的就是：设x序列都加u，y序列都加v，则我们可以令u-v=t,则：运用初中数学知识，我们我们可以把上式子看作一个二次函数,变量为t。那么，我们就可以知道当u-v取多少的时候，相同x,y下，res能够最小。因此，亮度调...

多项式每日一题

2021-01-21

0 757

老瞎眼 pk 小鲜肉解题报告（线段树+思维+前缀异或和）

看到题目，我想大家第一个想到的就是前缀异或和，因为这种询问一整段的异或和的一半都需要这样处理，不然复杂度太高。之后，题目要询问的就是找到在区间[L,R]中的存在的点sum[l]==sum[r],使得r-l+1最小。若是考虑直接让值对应整个[l,r]区间则会很麻烦，所以，考虑转化为单点维护。考虑单点维...

每日一题离线数据结构

2020-12-23

1 769

CF1141E　解题报告（数学）

这题其实不难，为啥放在cf div2的E呢？下文中，每个round对怪物造成的净伤害为sum，一个round中对这个怪物的最大伤害为mx，均为负数这题主要是有个坑点：可能在一个round中会有一个点，它大于整个round结束之后对怪物造成的净伤害。所以，我们需要找出一个round中最大的伤害的点mx...

每日一题

2020-12-23

0 734

追债之旅解题报告(最短路变形)

这道题算是一道分层图的最短路：按照天数对图进行分层，并且，在day-1层和day层，每个相连的节点(u,v)都有一条权值为w[day]的边，表示从day-1天在u到day天到v需要w[day]的路费。这样考虑的话，我们可以把每个节点拆成k个，然后每个节点u的第day-1个连到v节点的第day个，边权...

每日一题图论

2020-08-07

0 516

牛客小白月赛13——小A的回文串解题报告(马拉车算法)

回文串大家都很熟悉，但我们平常使用的方法是枚举中心点向外扩展求，复杂度是.但这道题，需要枚举n种字符串，每个最长为5e3，若找最大长度会炸，所以，需要马拉车算法优化，复杂度为。具体算法内容网上有很多。具体看代码注释吧。 #include <iostream> #include <m...

2020-08-03

0 636

小A的最短路解题报告(LCA,最短路)

首先，题目有个条件：n个节点，n-1条路径，所以，这是一棵树。之后，会再在u,v之间加入一条边权为0的边，让我们求图上任意两点的最短路。若我们忽略新加入的uv边，那直接求lca求距离就行了。但是，现在加入了uv边，但是，我们可以想到，如果真正的最短路径不经过uv边，那么答案依旧还是lca求得的结果，...

每日一题图论

2020-08-01

0 745

2020年牛客算法入门课练习赛3 解题报告(A最短路 B容斥 C线段树 D DP E 思维)

打开博客发现上次咕咕咕了写一半。。想想还是补完，顺便复习下。 A、胖胖的牛牛好像bfs也行。我这里用的是dfs，后来用了最短路解。这里主要说最短路。将每个点分成上下左右四个点，用点，其中i、j是点坐标，k为其方向：0为左，1为上，2为右，3为下，(因为当i=n,j=n时，，所以是)然后用0点作为超...

搜索 dp 数据结构

2020-07-15

1 664