首页 > 其他分享 >2024.9.2-CSP模拟赛1

2024.9.2-CSP模拟赛1

时间:2024-09-25 15:35:58浏览次数:8  
标签:frac 2024.9 sum long times 括号 端点 CSP 模拟

考试:

大约在 9:40 左右发了题。

9:45

把所有的题目都快速看了一遍,T1 感觉模拟可能会 T,T2 最小生成树的板子,T3 又是追及问题感觉要挂,T4 感觉像是区间 DP。

9:50

开始做 T1,先是手搓了一个 gcd 又手动模拟了取模(想起了 xqy 因为取模导致的 TLE),样例输出得都挺快的。

  • 但是看了一眼数据范围:\(1\le a,b \le 10^{12}\)。

这……感觉会 TLE,尝试推一下公式,看一看有什么规律,结果推了一半,后面的没有推完。

当时差不多推到了这里:

还是没有写出 \(g\) 和 \(a\) 之间的关系。

打表找规律!但好像也没有什么特殊的地方,导致 TLE(当然还有一些特殊优化)。

10:00

模拟写得很快,想着等一会在回去优化。

T2 最小生成树的板子题,由于忘记提前将 \(m\) 条边连接的点先放入一个集合中,导致调了 5 分多钟,期间一直输出的 6.25。

发现了在进行长度计算时,长度会爆 int,于是就先定义了一个 long long 型的 \(Dis\),然后再进行开根(其实在 \(ans\) 计算时在开也可以)。

  • 十年 OI 一场空,不开 long long 一场空。

虽然在计算时开了 long long 但是在其他的地方也有会爆 int 的。

挂 40 分。

10:20

先看了一眼 T4,发现在边界的计算有点难办,选择做了自己不太擅长的 T3(有 double 的题经常由于精读问题做错)。

不管什么,先把基础的输入打进去。

果老师说过,先把求出的问题表示出来,然后再考虑进行优化。

以下是当时思考的过程:

先表示时间:

\[maxt=\frac{L\times C}{Vmax} \]

求解答案:

\[\sum_{i=1}^{n}\sum_{k=1}^{i-1}\frac{maxt}{\frac{C}{v_i-v_k}}=\sum_{i=1}^{n}\sum_{k=1}^{i-1}\frac{\frac{L\times C}{Vmax}}{{\frac{C}{v_i-v_k}}}=\sum_{i=1}^{n}\sum_{k=1}^{i-1}\frac{L\times(v_i-v_k)}{Vmax} \]

而对于每个速度我想得是都要进行一遍求值,所以对于每个 \(i\),求出它能超过的奶牛就是:

\[\sum_{k=1}^{i-1}\frac{L\times(v_i-v_k)}{Vmax} \]

接着就很兴奋,直接用前缀和优化了一波,但是输出的答案是 6。

找了 10 分钟,把所有的过程全部都输出了一遍,结果发现在 \(i=4\) 的时候出了错。

又推了几遍公式结果就发现了巨大的错误:

正确答案(对于 \(i\)):

\[L\times(\lfloor v_i-v_1 \rfloor+\lfloor v_i-v_2 \rfloor+\lfloor v_i+v_3 \rfloor)+...+\lfloor v_i+v_{i-1} \rfloor \neq L\times [v_i\times (i-1)-\sum_{k=1}^{i-1}v_k] \]

当时已经过了很久,想着要把 T3 过了,但最后还是没有很好的方法,于是就只能乱写了一个做法,样例也没有过。

11:20

时间花得有点久了,但是样例没有过。

如果现在就去做 T4,那 T3 完全就保龄了。

当时其实有点小慌,那就先把 \(n\le 5000\) 的暴力打了再说吧。

double 的精度问题又调了一会。

11:35

要没有时间了,赶紧写了一遍区间DP 的板子,结果发现在 \(i,j\) 处有 5 中情况。想了一下写完了。

11:55

测样例第 2 个没有过,是有初始化吗?不知道。

怎么办,只能写个骗分的代码交上去,死马当活马医。

总结:

  1. 在第一题的处理没有做好,平时学的数论知识没有全部用上,对于数论的运用还不够熟练。
  2. 如果有可能会爆 int 的情况下就一定要开 long long!
  3. 第三题耗时间太多了,导致第四题应该可以多得分。
  4. 对于以前学的区间DP 的掌握程度还不够,应该要多练习和思考。
  5. 对于像 T3 最后化出来了式子可以用逆序对的方式解决。

题解:

T1:

  1. 如果直接暴力的话,当 \((a,b)=1\) 出现多次时,就会导致下降的速度变慢,所以有可能会 TLE。
  2. 那么考虑将连续 \((a,b)=1\) 的次数求出来,及当 \((a,b)=1\) 时,求出 \((a-x,b-x)\neq 1\)(\(x\) 最小),这样就可以快速合并。

假设 \((a-x,b-x)=d\),则有:

\[a-x \equiv b-x( \mod{d} )\Rightarrow a \equiv b (\mod{d}) \Rightarrow d \mid a-b \]

所以只用枚举找到 \(a-b\) 的因子找到 \(d\),并求出 \(x\) 即可。

又因为:

\[a-x \equiv 0(\mod{d}) \Rightarrow x \equiv a(\mod{d}) \]

这样便可以通过 \(d\) 进而快速求出 \(x\),其余的就模拟即可。

特殊情况:

  1. \(a=b\) 步数为 1。
  2. \(a=1\) 或 \(b=1\) 则步数也为 1。
  3. \(\left| a-b \right| = 1\),则步数为 \(\min(a,b)\)。

T2:

最小生成树板子题。

T3:

其实也可以考虑每头牛对于答案的贡献是多少。

发现如果多算了 1,则 \(l_i\) 的小数部分一定小于 \(l_j\) 的小数部分。

\(l_i=\frac{v_i\times(L\times C)\div v_n}{C},d_i=(v_i\times L) \mod{v_n} +1\)

将 \(d\) 数组求一遍逆序对即可。

注意:\(d\) 数组 +1 是因为怕出现有 0 的情况。

T4:

\(f_{i,j}\) 表示从 \(i\) 到 \(j\) 这一段合法的最小代价。

那么可以从小区间推广到大区间,求出最小值:

\[f_{i,j}=\min(f_{i,j},f_{i,k}+f_{k+1,j}) \]

考虑端点情况。

如果 \(s_i\) 和 \(s_j\) 匹配,直接转移。

否则就会有:

  • 若尾端点为前括号,首端点为后括号,则首尾端点一定都要修改。
  • 若尾端点为前括号,首端点也为前括号,则尾端点一定修改。
  • 若尾端点为后括号,但首端点为后括号,则首端点一定要修改。
  • 若尾端点为后括号,但首端点为前括号,则首尾修改一个即可,取最小值。

标签:frac,2024.9,sum,long,times,括号,端点,CSP,模拟
From: https://www.cnblogs.com/Merge-Change230/p/18431484

相关文章

  • 2024.9.3-CSP模拟赛2
    考试:9:00开题:第一题第一眼数据范围\(1\len\le5\times10^7\),感觉有T的风险。第二题littlebird,记得在以前做过这道题。第三题不太会,没有给部分分的比值,感觉只能写个暴搜。\(O(n^2)\)的暴力肯定会,正解先待会再想。9:10做T1,直接写暴力,5分钟写完了。试了一下500......
  • 2024.9.5-CSP模拟赛4
    考试:9:00~9:10看题:T1:很久之前做过,没有什么印象了。T2:感觉是广搜,但有可能要爆。T3:搜索题,猛加优化。T4:不知道是什么类型的题目。9:10~9:50写T1,已经忘了怎么写的,只能当做一道新题来做。写了个贪心,分了2中情况进行讨论,样例和自造样例都过了,但肯定会WA。其实在写计算的......
  • 2024.9.4-CSP模拟赛3
    考试:9:00~9:25怎么还不发卷啊,等得有点慌了,这是在考验心态吗?原来是极域出了点问题9:25~9:35发卷了,先看题。T1:相对距离,这不是原题吗,这题能做。T2:平衡队列,数据有点大,要不要离散化?好像不用,先等会在仔细看看。T3:第一眼数据范围:\(1\leN\le100\),直接弗洛伊德呀。T4:是并查集吗......
  • 2024.9.6-CSP模拟赛5
    考试:9:00~9:10发卷:T1有想法但要思考一下。T2水题,秒切。T3状压,昨天晚上就在看,但没看完只听了思路。T4看上去是原题,可以做一做。9:10~9:30先做T4,真是原题,直接写。直接写了归并排序,前面又补了一个0,然后求了逆序对。样例很快就过了就放了。9:30~9:50直接写了T2,T2......
  • 模拟船舶的货物卸载过程,并计算总物流时间和转弯次数 python代码
    一个模拟物流操作的脚本,它处理船舶货物的卸载,并将货物运送到堆场。代码主要包含以下几个部分:1.**参数设置**:  -`NUM_FORKLIFTS`:每个堆场的叉车数量。  -`SHIP_CARGO`:每艘船舶的货物量(吨)。  -`CARGO_PER_TRUCK`:每辆叉车能运输的货物(吨)。  -`LOADING_TIME......
  • uniapp精仿支付宝UI界面,首页/理财/消息/生活/口碑/我的,还有模拟支付宝扫码支付/收付款
    uniapp精仿支付宝UI界面,首页/理财/消息/生活/口碑/我的,还有模拟支付宝扫码支付/收付款等功能,界面漂亮颜值高,视频商城小工具等,蚂蚁森林种树养鸡农场偷菜样样齐用于视频,商城,直播,聊天等sumer-alipay介绍uniapp精仿支付宝UI界面,首页/理财/消息/生活/口碑/我的,还有模拟支付宝......
  • C++模拟真人鼠标轨迹
    一.API跨语言平台支持`鼠标轨迹API`[https://winsdk.cn/]()底层实现采用C/C++语言,利用其高性能和系统级访问能力,开发出高效的鼠标轨迹模拟算法。通过将算法封装为DLL(动态链接库),可以方便地在不同的编程环境中调用,实现跨语言的兼容性。通过DLL封装,开发者可以在C++、Pytho......
  • Python模拟鼠标轨迹
    一.鼠标轨迹模拟简介传统的鼠标轨迹模拟依赖于简单的数学模型,如直线或曲线路径。然而,这种方法难以捕捉到人类操作的复杂性和多样性。AI大模型的出现,能够通过深度学习技术,学习并模拟更自然的鼠标移动行为。二.鼠标轨迹算法实现AI大模型通过学习大量的人类鼠标操作数据,能够识别......
  • C++模拟真人鼠标轨迹
    一.API跨语言平台支持鼠标轨迹API底层实现采用C/C++语言,利用其高性能和系统级访问能力,开发出高效的鼠标轨迹模拟算法。通过将算法封装为DLL(动态链接库),可以方便地在不同的编程环境中调用,实现跨语言的兼容性。通过DLL封装,开发者可以在C++、Python、易语言、按键精......
  • 2024.9.24 LGJ Round
    C第\(i\)个同学一开始有第\(i\)份礼物,每个同学对礼物的喜爱度都有排序。\(q\)次询问把所有人划分为两个集合,集合里的人可以互相交换礼物,问方案数使得每个人喜爱度不降。\(n\le18\)。若\(i\)能将礼物给\(j\)那么连一条\(i\toj\)的边,相当于最后求置换环组成图的方......