旭日临窗

数据结构专题班题解

/ 注册

全部文章 / 数据结构专题班题解（共4篇）

G 牛牛的Link Power I

考虑每个点的贡献。因为题目说和算一组，所以我们不妨令。然后我们发现点对后面节点的贡献为一个首相为1 公差为1 的等差数列。于是我们便可以愉快地二阶差分了，最后遍历每个1答案加上其位置上的权值即可。 my code: #include <bits/stdc++.h> #de...

2021-08-18

0 465

F 牛牛的猜球游戏

我们可以用一个数组记录下前次操作后第杯子里球的颜色，也可用一个 vector 存储。那么每个询问到后的结果，我们可以对于每一个找到对应的，这里的对应指杯子里球的颜色相等，并将。那么为什么呢？原因如下：如果那么就说明如果颜色在第号杯子里，那么无论如何经过...

2021-08-18

0 381

I,J [NOIP2013]积木大赛, [NOIP2018]道路铺设

直接上结论，对数组差分以后所有正数或所有负数的绝对值即为答案。 my code: #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; int n,ans; int a[maxn]; int ...

2021-08-18

0 429

A 智乃酱的区间乘积

考虑前缀积。令表示，则可表示为，预处理出数组，查询的时候套上一个乘法逆元即可。下面是关于乘法逆元，我们可以利用费马小定理如果是质数，且即互质，则所以可推出。又因为对比两个式子即可得出在模意义下和同余。 my code: #include ...

2021-08-18

0 567