附上线段树模版

NOIP考前练一练模版

树状数组的基本用途是维护序列的前缀和

树状数组支持的基本操作：

• 查询前缀和
• 单点修改

lowbit运算讲解

题目链接

ps：这道题是在校内模拟赛见到的，所以题目当然是模改过的啦=。= 原题提交链接在上面=。=

问题描述
一天，你进入了神仙 lzc的神仙赌场。 神仙 lzc 实在是肽聚了，他觉得用一个本体来虐人太无聊了，于是就造出了 N 个分身。 这 N 个分身每个都是庄家。 你可以到庄家那边下注，每次可以猜大猜小，猜一次一元钱。 每一次开彩前，你都可以到任意个庄家那里下赌注。 如果开彩结果是大，你就可以得到你之前猜大的庄家相应的 ai 元钱。 如果开彩结果是小，你就可以得到你之前猜小的庄家相应的 bi 元钱。 你可以在同一个庄家那里既猜大又猜小（这样是两块钱），也可以什么都不猜（这样不用 钱）。 现在你对这个整天装逼装弱的神仙 lzc 看得实在是不爽，想要从它的分身中坑走尽量多的 钱。 但是阴险狡诈爱装逼爱装弱的神仙 lzc 会根据你下注的信息控制开彩的结果，让你赢的钱 数尽量少。 问怎么样下注，才能坑走神仙 lzc 最多的钱。

最大公因数：当a，b不全为0时，再有限个公因数中最大的一个叫做a，b的最大公因数，记作（a,b）

如果a，b的最大公因数为1，那么称a，b是互素的

辗转相除法求最大公因数：
问题：如果b除a的余数为r，那么（a,b）是否等于（b,r）？

使用拓扑求最大环长度；

题目链接

有 n 个同学（编号为 1 到 n）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为 i 的同学的信息传递对象是编号为 T_i 的同学。

游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息， 但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮？

素数：仅有两个正因数的正整数，即为正因数只有1和本身的数，也称质数

合数：不是素数又不是1的正整数

• 1既不是素数(只有一个正因子)，也不是合数.
• 2是唯一的偶素数，也是最小的素数.

我们发现，每个正整数x除1外的最小正因数p是一个素数

题目链接

在有向图 G 中，每条边的长度均为 1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：

• 路径上的所有点的出边所指向的点都直接或间接与终点连通。 在满足条件1的情况下使路径最短。
• 注意：图 G 中可能存在重边和自环，题目保证终点没有出边。

请你输出符合条件的路径的长度。

Bellman Ford同样是一种单源最短路算法，它的优秀之出在于它可以处理带有负边权的图，我们先来看看核心代码：

题目链接

春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为 n 的大厦，大厦可以看成由 n 块宽度为1的积木组成，第i块积木的最终高度需要是hi。
在搭建开始之前，没有任何积木（可以看成 n 块高度为 0 的积木）。接下来每次操作，小朋友们可以选择一段连续区间[L,R]，然后将第 L 块到第 R 块之间（含第 L 块和第 R 块）所有积木的高度分别增加1。
小 M 是个聪明的小朋友，她很快想出了建造大厦的最佳策略，使得建造所需的操作次数最少。但她不是一个勤于动手的孩子，所以想请你帮忙实现这个策略，并求出最少的操作次数。