nagisa_菜鸡

分类

题解(34)

/ 注册

全部文章（共10篇）

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

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

每日一题

2021-03-01

0 823

[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

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

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

每日一题图论

2020-08-01

0 745

Forsaken喜欢数论解题报告(素数筛求最小值因子)

这道题需要了解素数筛的原理，而不是只是套模板。需要明白一点，我们在欧拉筛中筛掉合数用的是这个合数的最小值因子。还记得那一步if(i%primes[j]==0) break;吗？这一步就保证我们用的是最小值因子筛掉所有的合数。我们可以这么理解，当i%primes[j]的时候，i=k*primes[j]...

每日一题数论

2020-06-23

1 659

[SCOI2012]滑雪与时间胶囊结题报告（最小生成树）

看到这道题，发现不会最小生成树，遂昨晚熬夜补了prim算法，今天来写这道题。看到时间胶囊能回溯，因此确实可以想得到是最小生成树，其实就是最小生成树后求路径长度和最小的问题。这道唯一特别一点的地方就是只能从高处到低处，并且要保证能去的地方最多，所以贪心策略需要加一条：以边终点高的优先选择，保证高度高（...

最小生成树每日一题图论贪心

2020-05-04

0 656

NC 43625717 换个角度思考解题报告（主席树/离线+树状数组/莫队（随缘更新））

wa/tle了三页才写出来。。。菜鸡果然是菜鸡主席树这个昨晚刚看的数据结构，敲的时候敲错了n多次。。在树里，把数的版本号当作数组下标，树内记录每个区间内的数的出现次数，学过之后还是比较好理解的。 #include <iostream> #include <cstdio> ...

树状数组每日一题离线数据结构主席树

2020-04-30

1 825

NC14704 美味菜肴解题报告（DP(01背包)、贪心）

思路分析看到每一道菜有选和不选两种决策，我们想到了01背包。但是，和普通的01背包相比有个区别，就是做每一个决策是具有后效性的：选了i道菜会影响i+k道菜的价值，也就是说，菜的价值会和选的顺序有关。因此，我们需要利用一个贪心确定一个选择的顺序，令按照这一顺序选择答案最优。通过证明我们可以得到可以按...

每日一题背包贪心 dp

2020-04-28

0 1068