元素的笔记

有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的 N 个城市。北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航道不相交的情况下，被批准的申请尽量多。

K(1 ≤ K ≤ 100) 只奶牛分散在 N(1 ≤ N ≤ 1000) 个牧场．现在她们要集中起来进餐。牧场之间有 M(1 ≤ M ≤ 10000) 条有向路连接，而且不存在起点和终点相同的有向路．她们进餐的地点必须是所有奶牛都可到达的地方。那么，有多少这样的牧场可供进食呢？

洛谷 P9750

众所周知，对一元二次方程 ax² + bx + c = 0, (a ≠ 0)，可以用以下方式求实数解：

• 计算 Δ = b² − 4ac，则:
  1. 若 Δ < 0，则该一元二次方程无实数解。 2. 否则 Δ ≥ 0，此时该一元二次方程有两个实数解 $x _ {1, 2} = \frac{-b \pm \sqrt \Delta}{2a}$。

例如：

• x² + x + 1 = 0 无实数解，因为 Δ = 1² − 4 × 1 × 1 = −3 < 0。
• x² − 2x + 1 = 0 有两相等实数解 x_1, 2 = 1。
• x² − 3x + 2 = 0 有两互异实数解 x₁ = 1, x₂ = 2。

在题面描述中 a 和 b 的最大公因数使用 gcd (a, b) 表示。例如 12 和 18 的最大公因数是 6，即 gcd (12, 18) = 6。

P8814 [CSP-J 2022] 解密 - 洛谷

给定一个正整数 k，有 k 次询问，每次给定三个正整数 n_i, e_i, d_i，求两个正整数 p_i, q_i，使 n_i = p_i × q_i、e_i × d_i = (p_i − 1)(q_i − 1) + 1。

P8813 [CSP-J 2022] 乘方 - 洛谷

小文同学刚刚接触了信息学竞赛，有一天她遇到了这样一个题：给定正整数 a 和 b，求 a^b 的值是多少。

a^b 即 b 个 a 相乘的值，例如 2³ 即为 3 个 2 相乘，结果为 2 × 2 × 2 = 8。

“简单！”小文心想，同时很快就写出了一份程序，可是测试时却出现了错误。

小文很快意识到，她的程序里的变量都是 int 类型的。在大多数机器上，int 类型能表示的最大数为 2³¹ − 1，因此只要计算结果超过这个数，她的程序就会出现错误。

由于小文刚刚学会编程，她担心使用 int 计算会出现问题。因此她希望你在 a^b 的值超过 10⁹ 时，输出一个 -1 进行警示，否则就输出正确的 a^b 的值。

然而小文还是不知道怎么实现这份程序，因此她想请你帮忙。

P7909 [CSP-J 2021] 分糖果 - 洛谷]

红太阳幼儿园有 n 个小朋友，你是其中之一。保证 n ≥ 2。

有一天你在幼儿园的后花园里发现无穷多颗糖果，你打算拿一些糖果回去分给幼儿园的小朋友们。

由于你只是个平平无奇的幼儿园小朋友，所以你的体力有限，至多只能拿 R 块糖回去。

但是拿的太少不够分的，所以你至少要拿 L 块糖回去。保证 n ≤ L ≤ R。

也就是说，如果你拿了 k 块糖，那么你需要保证 L ≤ k ≤ R。

如果你拿了 k 块糖，你将把这 k 块糖放到篮子里，并要求大家按照如下方案分糖果：只要篮子里有不少于 n 块糖果，幼儿园的所有 n 个小朋友（包括你自己）都从篮子中拿走恰好一块糖，直到篮子里的糖数量少于 n 块。此时篮子里剩余的糖果均归你所有——这些糖果是作为你搬糖果的奖励。

作为幼儿园高质量小朋友，你希望让作为你搬糖果的奖励的糖果数量（而不是你最后获得的总糖果数量！）尽可能多；因此你需要写一个程序，依次输入 n, L, R，并输出你最多能获得多少作为你搬糖果的奖励的糖果数量。

直播获奖 - 洛谷

NOI2130 即将举行。为了增加观赏性，CCF 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。本次竞赛的获奖率为 w%，即当前排名前 w% 的选手的最低成绩就是即时的分数线。

更具体地，若当前已评出了 p 个选手的成绩，则当前计划获奖人数为 max (1, ⌊p × w%⌋)，其中 w 是获奖百分比，⌊x⌋ 表示对 x 向下取整，max (x, y) 表示 x 和 y 中较大的数。如有选手成绩相同，则所有成绩并列的选手都能获奖，因此实际获奖人数可能比计划中多。

作为评测组的技术人员，请你帮 CCF 写一个直播程序。

洛谷P7071

一般来说，一个正整数可以拆分成若干个正整数的和。

例如，1 = 1，10 = 1 + 2 + 3 + 4 等。对于正整数 n 的一种特定拆分，我们称它为“优秀的”，当且仅当在这种拆分下，n 被分解为了若干个不同的 2 的正整数次幂。注意，一个数 x 能被表示成 2 的正整数次幂，当且仅当 x 能通过正整数个 2 相乘在一起得到。

例如，10 = 8 + 2 = 2³ + 2¹ 是一个优秀的拆分。但是，7 = 4 + 2 + 1 = 2² + 2¹ + 2⁰ 就不是一个优秀的拆分，因为 1 不是 2 的正整数次幂。

现在，给定正整数 n，你需要判断这个数的所有拆分中，是否存在优秀的拆分。若存在，请你给出具体的拆分方案。

洛谷P5661

著名旅游城市 B 市为了鼓励大家采用公共交通方式出行，推出了一种地铁换乘公交车的优惠方案：

1. 在搭乘一次地铁后可以获得一张优惠票，有效期为 45 分钟，在有效期内可以消耗这张优惠票，免费搭乘一次票价不超过地铁票价的公交车。 在有效期内指开始乘公交车的时间与开始乘地铁的时间之差小于等于 45 分钟，即：t_bus − t_subway ≤ 45

2. 搭乘地铁获得的优惠票可以累积，即可以连续搭乘若干次地铁后再连续使用优惠票搭乘公交车，但每次搭乘公交车只能使用一张优惠券。

3. 搭乘公交车时，如果可以使用优惠票一定会使用优惠票； 如果有多张优惠票满足条件，则优先消耗获得最早的优惠票。

现在你得到了小轩最近的公共交通出行记录，你能帮他算算他的花费吗?

有 1∼n 这 n（n<10）个数，现将这 n 个数组成一个 n 位的数，每个数只能用一次，例如 n=2，则 12，21 等都是符合条件的数，但 11 和 22 不行。

问，输入 n 后，将符合条件的所有的 n 位数输出，且按照从小到大顺序输出。