☆北极星☆

题解

/ 注册

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

心跳调试

首先对于当前栈里面最大的数是i，那么我们设投中i的概率是p1,投中i+1的概率是p2设不断往下投，能够投中i+1而不投中后面的数的概率为t，那么就有p1*t+p2=t，因此有t=p2/(1-p1)= #include<iostream> using namespace std; ty...

2021-03-20

3 360

#NC25044 Tallest Cow

对于奶牛L到r，要让奶牛L能看到R的话，就必须得[L+1,r-1]这段区间都要-1，差分数组维护就行。假设A能看到B，此时修改的是区间【A+1,B-1】，我们不难证明如果下一次的L在【A+1,B-1】里面，那么R也必定在【A,B】里面，因此让[L+1,r-1]这段区间都要-1是最优，无论如果要么是无...

2021-03-10

0 528

NC200195 区区区间

线段树区间覆盖问题，主要难点在于lazy标签要怎么用，我们可以定义lazy标签标示对于根节点now来说，他的整个区间也就是[now.l,now.r]是以now.lazy为首项的等差数列，以及作为区间覆盖的标准的话，那这道题和普通的区间覆盖就没有区别了，当然还有别的做法。 #include<io...

2021-03-08

0 684

Perfect Security

这个题目和上一个基本是一样的，就是统计经过节点的次数，查询的时候没经过一次，就把计数-1，直到减不了了或者不存在这条边可以走，我们就走另一条边就好了！ #include<iostream> #include<cstdio> using namespace std; const...

2020-11-03

0 577

Vitya and Strange Lesson

其实a^b^c=a^(b^c)，那么对于后面的q次请求，我们都可以利用一开始建立的树来进行求解。因为对一个数进行多次异或操作的值，就等于这个数异或上后面多次异或和的值。那么原问题就转换为了在01字典树里面找到一个数异或上x最小并且没有在树当中出现过，显然是好找的，我们只需要判断走到这个节点它的0边是...

2020-11-03

1 483

牛客练习赛71-C数学考试

首先我们要明白dp[i]表示的是什么，看了好久的别人的代码才看懂了(i am vegetable),dp[i]表示的是长度为p[i]，满足前i-1个限制条件的合法子串的个数！（看不懂就看例子）举个例子，此时的限制条件有3个，分别是p[1]=3,p[2]=5,p[3]=7,那么dp[1]就是表示满足前...

2020-10-10

4 570