HHHOJ NOIP2020模拟赛(叁)2020.02.03 题解

A. 「NOIP模拟赛 叁」木板

题意

将一个边长为$ N $的正方形裁剪成四个直角三角形。注意面积不能为$ 0$。

三个必要的切割中的两个始终从一个角落$G$进行(图中$G$位于$A$,实际上也可以是$B$、$C$、$D$),第三次切割必须垂直于前面两个之一(在图中,$AE$部分垂直于$EF$部分)。

切割机仅接受整个坐标值,这意味着$N$必须是整数的,并且点$E$和$F$的坐标必须是整数的。 有时候这可能是不可能的。

编写一个程序,根据给出的$ N$,确定是否可以将四边形的正方形三角形切割成四个矩形三角形,如果可能的话,可以采用多少种方法来完成。
对于$40\text{%}$的数据,$n\leq {10}^{7}$。
对于另$10\text{%}$的数据,$n$为质数。
对于$ 100\text{%}$的数据,$n\leq {10} ^ {14}$,不超过$5$组数据。

思路

易证$\triangle ABE \sim \triangle ECF$
所以$\frac{X}{A}=\frac{N}{N-X}$。
也就是$A=\frac{X\times (N-X)}{N}$
因为$A、X、N都是整数$
所以$\frac{X\times (N-x)}{N}$是整数。
即:$\frac{X\times N – X^2}{N}$
分式拆分下:$X-\frac{X^2}{N}$是整数。
就是$X^2 \mod N =0$。
就是$X^2$可以整除$N$。
设$N=\prod {p_i}^{q_i}$(把$N$分解质因数)
那么有$\prod {p_i}^{\lceil \frac{q_i}{2} \rceil }|X$。
由于$X$取值范围是$\text{[}1,N\text{)}$。
那么答案就是$\frac{N}{\prod {p_i}^{\lceil \frac{q_i}{2} \rceil }} -1$.
化简下就是$\prod {p_i}^{\lfloor \frac{q_i}{2} \rfloor }-1$。
那么筛下素数再弄个快速幂就好了。

Code

B. 「NOIP模拟赛 叁」卡车

题意

卡车在$ n $个城市之间运送货物,城市由$ n−1$条道路连成网络,使得任意两座城市之间存在唯一的道路。
城市网络中每个城市有一个权值$ d_i$,道路也都有一个权值$w_i$。
对于一条路径,令路径上所有城市权值$ d_i$的最小值为$ {min}_d$,路径上所有道路权值$w_i$的总和为$ {sum}_w$,则该条路径的总权值为$ {min}_d\times {sum}_w$。
路径的起点和终点可以是任意城市,且路径中不能出现重复的城市。
请求网络中所有路径总权值中的最大值。
$n\leq 2\times {10}^5 , 1 \leq d_i ,w_i \leq {10}^9$

思路

本题有多种解法。首先是点分治的思想,在点分治的时候,我们每一次选取一个中心,先统计过中心的路径最大值,然后删掉中心,递归处理其它子树。统计过中心的路径最大值,我们以中心为根深度搜索一遍,一个需要注意的地方是路径的两个端点不能在同一子树内,因为这样可能会重复统计。所以我们把路径按子树分类,然后点权排序以后更新路径按子树分类的最大值和次大值,之和与当前点权的乘积就是答案。

本题还可以用并查集来解决。将所有点按照权值从大到小排序,对于将当前点和与其相连的所有点依次合并到一个集合中。并查集需要维护当前集合中的最长路径长度和对应的两个端点。在合并两个集合后,最终集合的最长路一定只有两类情况:一类是其中一个集合的最长路,一共有 2 种;一类是由两个集合的最长路的端点互相连接而成,一共有 2×2=4 种。需要用到最近公共祖先的算法预处理求两点在树上的距离,离线处理即可。每次合并并查集之后用当前点的权值乘以最长路的总长度来更新最优结果即可。即使这个点不在当前合并后的集合的最长路上也是没有问题的,因为如果这样的话,必然已经在之前得到了对应的结果,这次合并不会对最终结果产生影响。

Code –点分治

C. 「NOIP模拟赛 叁」骆驼

题意

我们都熟悉走马步,现在我们定义一种新的移动方式——骆驼步,它在一个国际棋盘上的移动规则是这样的。

可以看出,骆驼步可以向八个方向走动,且不能走出棋盘范围。

现在给出一个$ N\times N $的棋盘,其中$ N $是$5$的倍数。

你需要从左上角出发,每步按照骆驼步的规则,经过每个格子恰好一次,且当你走了$ N^2−1$步后,你离起点恰好只有一步的距离。

请给出一种合法的方案。
$N\leq 1000$。

思路

因为$N$是$5$的倍数。
自然而然地就会想到拿$5\times 5$的矩阵来构造$N\times N$的。
然后乱拼下就好了。

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇