智子 的博客

智子 的博客

面对我们的骨灰,高尚的人们将洒出热泪。

2020年3月22日小测赛后总结

posted on 2020-03-29 13:41:03 | under 未分类 |

赛后总结

这次比赛我的分数还挺尴尬的……其实主要是时间问题,题目基本来不及实现

话说为什么这次测试的题目背景都这么奇怪

第一题:神炎皇

题面

【问题描述】

神炎皇乌利亚很喜欢数对,他想找到神奇的数对。

对于一个整数对(a,b),若满足a+b<=n且a+b是ab的因子,则成为神奇的数对。请问这样的数对共有多少呢?

【输入格式】

一行一个整数n。

【输出格式】

一行一个整数表示答案,保证不超过64位整数范围。

【数据范围与约定】

对于20%的数据n<=1000;

对于40%的数据n<=100000;

对于60%的数据n<=10000000;

对于80%的数据n<=1000000000000;

对于100%的数据n<=100000000000000。

思路

首先,看一眼数据范围,放弃模拟

因为 $gcd(a, b)$ 能同时整除 $a + b$ 与 $ab$ ,设 $d = gcd(a, b)$ , $a = xd,b = yd$ ,有 $$x + y | dxy$$ 又因为 $gcd(x, y) = 1$ $$x + y | d$$

设 $d = k(x + y)$ ,因为 $a + b \leq n$

$$k(x + y)^2 \leq n$$ $$k \leq \frac{n}{(x + y)^2}$$

因为 $k(x + y)^2 \leq n$

$$(x + y) \leq \sqrt{n}$$

因此 $(x + y)$ 的范围为 $1$ ~ $\sqrt{n}$ , $(x, y)$ 的对数为:

$$\sum_{i=1}^{\sqrt{n}} \phi(i)$$

则 $(a, b)$ 的对数为:

$$\sum_{i=1}^{\sqrt{n}} \frac{\phi(i)n}{i^2}$$

评测结果

样例错,原地爆炸

第二题:降雷皇

题面

【问题描述】

降雷皇哈蒙很喜欢雷电,他想找到神奇的电光。

哈蒙有n条导线排成一排,每条导线有一个电阻值,神奇的电光只能从一根导线传到电阻比它大的上面,而且必须从左边向右传导,当然导线不必是连续的。

哈蒙想知道电光最多能通过多少条导线,还想知道这样的方案有多少。

【输入格式】

第一行两个整数n和type。type表示数据类型

第二行n个整数表示电阻。

【输出格式】

第一行一个整数表示电光最多能通过多少条导线。

如果type=1则需要输出第二行,表示方案数,对123456789取模。

【数据范围与约定】

对于20%的数据n<=10;

对于40%的数据n<=1000;

对于另外20%的数据type=0;

对于另外20%的数据保证最多能通过不超过100条导线;

对于100%的数据n<=100000,电阻值不超过100000。

思路

最长上升子序列的题

第一问是最长上升子序列模版;

第二问卡住了

总结

菜是原罪