主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
CSP-J游记
最后更新于 2025-07-31 11:05:02
作者
PokerKing
分类
个人记录
复制 Markdown
查看原文
删除文章
更新内容
语文老师告诉我们游记要写时间人物地点 ### 时间:2023年10月21日 ### 地点:华中师范大学 ### 人物:我 # 审题环节 开始考试了,我们老师告诉我们先审题30分钟 先看**时间和内存限制** | 题目名称 | 时间限制 | 内存限制 | | :------: | :-----------: | :--------------: | | 小苹果 | 1.0秒 | 512 MiB | | 公路 | 1.0秒 | 512 MiB | | 一元二次方程 | 1.0秒 | 512 MiB | | 旅游巴士 | 1.0秒 | 512 MiB | 还挺正常的,只不过看见一个**一元二次方程**有点慌 开始看题目 ## First question 小 Y 的桌子上放着 $n$ 个苹果从左到右排成一列,编号为从 $1$ 到 $n$。 小苞是小 Y 的好朋友,每天她都会从中拿走一些苹果。 每天在拿的时候,小苞都是从左侧第 $1$ 个苹果开始、每隔 $2$ 个苹果拿走 $1$ 个苹果。随后小苞会将剩下的苹果按原先的顺序重新排成一列。 小苞想知道,多少天能拿完所有的苹果,而编号为 $n$ 的苹果是在第几天被拿走的? 对于所有测试数据有:$1\leq n\leq 10^9$。 | 测试点 | $n\leq$ | 特殊性质 | | :----------: | :----------: | :----------: | | $1\sim 2$ | $10$ | 无 | | $3\sim 5$ | $10^3$ | 无 | | $6\sim 7$ | $10^6$ | 有 | | $8\sim 9$ | $10^6$ | 无 | | $10$ | $10^9$ | 无 | 特殊性质:小苞第一天就取走编号为 $n$ 的苹果。 乍一看,哎,这不是纯模拟题吗? 可是$ 10^9$是什么东西呀,就是O(n)的算法也会TLE吧 所以说我们必须要用**O(logn)或O(n)以下**的算法 让我们来看一下有哪些时间复杂度小于O(n)的算法吧 1. 二分(logn) 2. 部分数论(logn) 无非也就两种,而数论肯定不可能,所以只能是二分 ## Second question 小苞准备开着车沿着公路自驾。 公路上一共有 $n$ 个站点,编号为从 $1$ 到 $n$。其中站点 $i$ 与站点 $i + 1$ 的距离为 $v_i$ 公里。 公路上每个站点都可以加油,编号为 $i$ 的站点一升油的价格为 $a_i$ 元,且每个站点只出售整数升的油。 小苞想从站点 $1$ 开车到站点 $n$,一开始小苞在站点 $1$ 且车的油箱是空的。已知车的油箱足够大,可以装下任意多的油,且每升油可以让车前进 $d$ 公里。问小苞从站点 $1$ 开到站点 $n$,至少要花多少钱加油? 对于所有测试数据保证:$1 \leq n \leq 10^5$,$1 \leq d \leq 10^5$,$1 \leq v_i \leq 10^5$,$1 \leq a_i \leq 10^5$。 | 测试点 | $n \leq$ | 特殊性质 | | :----------: | :----------: | :----------: | | $1\sim 5$ | $8$ | 无 | | $6\sim 10$ | $10^3$ | 无 | | $11\sim 13$ | $10^5$ | A | | $14\sim 16$ | $10^5$ | B | | $17\sim 20$ | $10^5$ | 无 | - 特殊性质 A:站点 $1$ 的油价最低。 - 特殊性质 B:对于所有 $1 \leq i < n$,$v_i$ 为 $d$ 的倍数。 欸,这不纯纯动态规划吗 可是 我不会呀 所以这道题我直接弃掉了,在赛后才发现原来只是一道贪心 ## Third question 众所周知,对一元二次方程 $ax ^ 2 + bx + c = 0, (a \neq 0)$,可以用以下方式求实数解: - 计算 $\Delta = b ^ 2 - 4ac$,则: 1. 若 $\Delta < 0$,则该一元二次方程无实数解。 2. 否则 $\Delta \geq 0$,此时该一元二次方程有两个实数解 $x _ {1, 2} = \frac{-b \pm \sqrt \Delta}{2a}$。 例如: - $x ^ 2 + x + 1 = 0$ 无实数解,因为 $\Delta = 1 ^ 2 - 4 \times 1 \times 1 = -3 < 0$。 - $x ^ 2 - 2x + 1 = 0$ 有两相等实数解 $x _ {1, 2} = 1$。 - $x ^ 2 - 3x + 2 = 0$ 有两互异实数解 $x _ 1 = 1, x _ 2 = 2$。 在题面描述中 $a$ 和 $b$ 的最大公因数使用 $\gcd(a, b)$ 表示。例如 $12$ 和 $18$ 的最大公因数是 $6$,即 $\gcd(12, 18) = 6$。 ## 题目描述 现在给定一个一元二次方程的系数 $a, b, c$,其中 $a, b, c$ **均为整数且 $a \neq 0$**。你需要判断一元二次方程 $a x ^ 2 + bx + c = 0$ 是否有实数解,并按要求的格式输出。 **在本题中输出有理数 $v$ 时须遵循以下规则:** - 由有理数的定义,存在唯一的两个整数 $p$ 和 $q$,满足 $q > 0$,$\gcd(p, q) = 1$ 且 $v = \frac pq$。 - 若 $q = 1$,**则输出 `{p}`,否则输出 `{p}/{q}`**,其中 `{n}` 代表整数 $n$ 的值; - 例如: - 当 $v = -0.5$ 时,$p$ 和 $q$ 的值分别为 $-1$ 和 $2$,则应输出 `-1/2`; - 当 $v = 0$ 时,$p$ 和 $q$ 的值分别为 $0$ 和 $1$,则应输出 `0`。 **对于方程的求解,分两种情况讨论:** 1. 若 $\Delta = b ^ 2 - 4ac < 0$,则表明方程无实数解,此时你应当输出 `NO`; 2. 否则 $\Delta \geq 0$,此时方程有两解(可能相等),记其中较大者为 $x$,则: 1. 若 $x$ 为有理数,则按有理数的格式输出 $x$。 2. 否则根据上文公式,$x$ 可以被**唯一**表示为 $x = q _ 1 + q _ 2 \sqrt r$ 的形式,其中: - $q _ 1, q _ 2$ 为有理数,且 $q _ 2 > 0$; - $r$ 为正整数且 $r > 1$,且不存在正整数 $d > 1$ 使 $d ^ 2 \mid r$(即 $r$ 不应是 $d ^ 2$ 的倍数); 此时: 1. 若 $q _ 1 \neq 0$,则按有理数的格式输出 $q _ 1$,并再输出一个加号 `+`; 2. 否则跳过这一步输出; 随后: 1. 若 $q _ 2 = 1$,则输出 `sqrt({r})`; 2. 否则若 $q _ 2$ 为整数,则输出 `{q2}*sqrt({r})`; 3. 否则若 $q _ 3 = \frac 1{q _ 2}$ 为整数,则输出 `sqrt({r})/{q3}`; 4. 否则可以证明存在唯一整数 $c, d$ 满足 $c, d > 1, \gcd(c, d) = 1$ 且 $q _ 2 = \frac cd$,此时输出 `{c}*sqrt({r})/{d}`; 上述表示中 `{n}` 代表整数 `{n}` 的值,详见样例。 如果方程有实数解,则按要求的格式输出两个实数解中的较大者。否则若方程没有实数解,则输出 `NO`。 对于所有数据有:$1 \leq T \leq 5000$,$1 \leq M \leq 10 ^ 3$,$|a|,|b|,|c| \leq M$,$a \neq 0$。 | 测试点编号 | $M \leq$ | 特殊性质 A | 特殊性质 B | 特殊性质 C | | :-: | :-: | :-: | :-:| :-:| | $1$ | $1$ | 是 | 是 | 是 | | $2$ | $20$ | 否 | 否 | 否 | | $3$ | $10 ^ 3$ | 是 | 否 | 是 | | $4$ | $10 ^ 3$ | 是 | 否 | 否 | | $5$ | $10 ^ 3$ | 否 | 是 | 是 | | $6$ | $10 ^ 3$ | 否 | 是 | 否 | | $7, 8$ | $10 ^ 3$ | 否 | 否 | 是 | | $9, 10$ | $10 ^ 3$ | 否 | 否 | 否 | 其中: - 特殊性质 A:保证 $b = 0$; - 特殊性质 B:保证 $c = 0$; - 特殊性质 C:如果方程有解,那么方程的两个解都是整数。 这一看到题面就不想做呀,要不弃了吧 可是我突然看到特殊性质C,**如果方程有解,那么方程的两个解都是整数** 这不直接套用公式么 所以说只用看这个就行了 - 计算 $\Delta = b ^ 2 - 4ac$,则: 1. 若 $\Delta < 0$,则该一元二次方程无实数解。 2. 否则 $\Delta \geq 0$,此时该一元二次方程有两个实数解 $x _ {1, 2} = \frac{-b \pm \sqrt \Delta}{2a}$。 直接拿50分呀 ## Fourth question # [CSP-J 2023] 旅游巴士 ## 题目描述 小 Z 打算在国庆假期期间搭乘旅游巴士去一处他向往已久的景点旅游。 旅游景点的地图共有 $n$ 处地点,在这些地点之间连有 $m$ 条道路。其中 $1$ 号地点为景区入口,$n$ 号地点为景区出口。我们把一天当中景区开门营业的时间记为 $0$ 时刻,则从 $0$ 时刻起,每间隔 $k$ 单位时间便有一辆旅游巴士到达景区入口,同时有一辆旅游巴士从景区出口驶离景区。 所有道路均只能**单向通行**。对于每条道路,游客步行通过的用时均为恰好 $1$ 单位时间。 小 Z 希望乘坐旅游巴士到达景区入口,并沿着自己选择的任意路径走到景区出口,再乘坐旅游巴士离开,这意味着他到达和离开景区的时间都必须是 **$k$ 的非负整数倍**。由于节假日客流众多,**小 Z 在旅游巴士离开景区前只想一直沿着景区道路移动,而不想在任何地点(包括景区入口和出口)或者道路上停留**。 出发前,小 Z 忽然得知:景区采取了限制客流的方法,对于每条道路均设置了一个 “开放时间”$a _ i$,游客只有**不早于 $a _ i$ 时刻**才能通过这条道路。 请帮助小 Z 设计一个旅游方案,使得他乘坐旅游巴士离开景区的时间尽量地早。 **【数据范围】** 对于所有测试数据有:$2 \leq n \leq 10 ^ 4$,$1 \leq m \leq 2 \times 10 ^ 4$,$1 \leq k \leq 100$,$1 \leq u _ i, v _ i \leq n$,$0 \leq a _ i \leq 10 ^ 6$。 | 测试点编号 | $n \leq$ | $m \leq$ | $k \leq$ | 特殊性质 | |:-:|:-:|:-:|:-:|:-:| | $1 \sim 2$ | $10$ |$15$ | $100$ | $a _ i = 0$ | | $3 \sim 5$ | $10$ | $15$ | $100$ | 无 | | $6 \sim 7$ | $10 ^ 4$ | $2 \times 10 ^ 4$ | $1$ | $a _ i = 0$ | | $8 \sim 10$ | $10 ^ 4$ | $2 \times 10 ^ 4$ | $1$ | 无 | | $11 \sim 13$ | $10 ^ 4$ | $2 \times 10 ^ 4$ | $100$ | $a _ i = 0$ | | $14 \sim 15$ | $10 ^ 4$ | $2 \times 10 ^ 4$ | $100$ | $u _ i \leq v _ i$ | | $16 \sim 20$ | $10 ^ 4$ | $2 \times 10 ^ 4$ | $100$ | 无 | 直接放弃吧,没啥好说的 # 做题环节 ## First question 我们通过小学奥数可以知道 每一次取得个数是原来的**个数/3+1** 而取到最后一个数怎么算呢? 我们可以用当前的个数-1%3,如果余0 也就是整除,那么就可以取到最后一个数 总结 1. 每次去掉/3+1个 2. 如果-1%3==0 那么当前次可以取到最后一个数 100分 ## Second question 放弃 0分 ## Third question 定义一个sum=b*b-4ac 如果sum<0 输出NO 否则输出max(-b+sqrt(sum)/2a,-b-sqrt(sum)/2a) 50分 ## Fourth question 直接骗分,输出k*2 5分 # 总结 总分:100+0+50+5=155=一等奖 第一题正常发挥 第二题类型判断错误 第三题侥幸 第四题运气
正在渲染内容...
点赞
1
收藏
0