首页 > 其他分享 >『模拟赛』暑假集训CSP提高模拟6

『模拟赛』暑假集训CSP提高模拟6

时间:2024-07-24 14:28:55浏览次数:15  
标签:10 CSP frac 集训 times 答案 mathcal 波特 模拟

Rank

image

A. 花间叔祖

签到题,但没切。

一眼出思路找最大公因数,过了大样例发现同余的情况也合法,然后开始优化,成功从 68pts 到了 88 pts。

考虑正解,首先答案不是一就是二。若答案是一,即所有数可在模某数 \(x\) 意义下同余。不妨将每个数化成 \(a_i=k\times x+d\) 的形式,则若存在一个 \(x\) 使得所有的 \(d\) 都相等,那么有 \(a_i-a_j=\left(k_i-k_j\right)\times x\),所以我们对排序后的差值进行求 gcd,复杂度为 \(\mathcal{O(n)}\)。

B. 合并r

有趣的题面,但题比较 ex。

看到题就开始想部分分了,首先对于 \(n=1\),显然 \(k\) 只能为 \(1\),那么答案也是 \(1\)。

对于 \(k=1\),赛时由于 \(n==5\) 的情况手模错了导致推出了假结论,恼。

正解是 dp。设 \(f_{i,j}\) 为共 \(i\) 个数和为 \(j\) 的方案数,显然加入一个 \(1\),即 \(f_{i-1,j-1}\) 可对答案产生贡献。

其次,由于 \(j\) 是由若干个 \(\frac{1}{2^i}\) 加和得到的,那么显然 \(\frac{j}{2}\) 可以由若干个 $$\frac{1}{2^{i+1}} 得到,因此第二个状态转移方程为 \(f_{i,j}+=f_{i,2\times j}\)。

注意边界问题,\(f_{0,0}=1\)。

C. 回收波特

很大方啊,给了 60pts 的暴力分。

首先看到 Subtask1 中 \(n\times m\le 10^8\),显然想让你用 \(\mathcal{O(nm)}\) 的做法解,最无脑的一个,每次操作枚举每个没有到达终点的波特,记录位置最后输出答案即可。

Subtask2 中给了 \(x_i\le 10^3\)。思考一下,\(3\times 10^5\) 的波特只出现在这 \(1000\) 个位置,显然可以把每个波特映射到初始位置上,按每个位置求解,复杂度为 \(\mathcal{O(x_{max}m)}\),时限两秒,可过。

正解提供了一个很厉害的思路:对于某一时刻,若两个波特的坐标关于原点对称,那么之后的所有移动二者都是对称的。

我们每次只维护一段符号相同的区间 \(\left[l,r\right]\) 的情况。

若在执行当前操作后符号不完全相同了,则利用上面的对称性,将符号不同的两边中元素数量较少的一边删去。

最后 dfs 一遍推出被扔掉的点的信息。

D. 斗篷

正解差分+扫描线。

题意倒很简单,关键是如何维护信息。

标签:10,CSP,frac,集训,times,答案,mathcal,波特,模拟
From: https://www.cnblogs.com/Ratio-Yinyue1007/p/18320835

相关文章

  • 【数据结构】队列详解和模拟实现
    大家好,今天我们学习队列,本篇博客主要涉及一般队列,环形队列和双端队列,每个队列应用场景均有所差异,下面我们一起来看看吧。队列(Queue)一,概念队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出的特性入队列:进行插入操作的一端称为队尾(Ta......
  • 2024暑假集训总结
    2024暑假集训总结知识点清单:树状数组拓展:(1)k维前缀和(2)树状数组+倍增没码过,小慌线段树:(1)线段树不仅仅是一个维护区间和、区间最值或者类似于方差那道题,维护区间的平方等等信息,它的深层是将区间拆分为\(O(logn)\)个子区间从而将修改与查询降为\(O(logn)\)级别,因此对于线......
  • 2024 暑假集训
    树状数组&线段树线段树合并,主席树等知识点是第一次接触。同时对扫描线能解决的问题有了些更好的认知。毕竟是之前学过的东西,还是比较好的。掌握程度:\(85\%^+\)离线分治算法具体是:线段树分治\(80\%^+\)就是个线段树上二分。CDQ分治基于时间的分治\(75\%^+\)基本......
  • 0207-pnet 模拟链路层数据
    环境Time2022-11-20WSL-Ubuntu22.04Rust1.65.0pnet0.31.0前言说明参考:https://docs.rs/pnet_datalink/0.31.0/pnet_datalink/dummy目标使用pnet_datalink包中的dummy模拟数据链路层的数据交换。Cargo.toml[package]edition="2021"name="network"versi......
  • 0208-模拟发送链路层数据
    环境Time2022-11-20WSL-Ubuntu22.04Rust1.65.0pnet0.31.0前言说明参考:https://docs.rs/pnet_datalink/0.31.0/pnet_datalink/dummy目标使用pnet_datalink包中的dummy模拟数据链路层发送一个数据包。网络接口letinterface=dummy::dummy_interface(44);创......
  • 0210-模拟发送构建的数据
    环境Time2022-11-20WSL-Ubuntu22.04Rust1.65.0pnet0.31.0前言说明参考:https://docs.rs/pnet_datalink/0.31.0/pnet_datalink/dummy目标使用pnet_datalink包中的dummy模拟数据链路层发送数据包。网络接口letinterface=dummy::dummy_interface(44);创建通......
  • 0209-模拟发送多个数据包
    环境Time2022-11-20WSL-Ubuntu22.04Rust1.65.0pnet0.31.0前言说明参考:https://docs.rs/pnet_datalink/0.31.0/pnet_datalink/dummy目标使用pnet_datalink包中的dummy模拟数据链路层发送多个数据包。网络接口letinterface=dummy::dummy_interface(44);创......
  • [2024JZYZ暑期集训]知识点总结
    前言第三次暑期集训了,与前两次不同,这次没有前两次的激动了,所以也能够更深入地学习算法。闲话宿舍挺好,有空床能住。捡了三块钱,史上最灵异事件。R班好热闹。认识了几个郑州那边的大佬知识点Day1讲了几个基础数据结构(树状数,线段树),作业里面的题目很多之前都做过,就当复习了。......
  • 2024年pt市S组暑假集训游记
    记录而已,不必在意Day1上午第一天,一中的lzy老师把我们分配到一楼的机房,好,有沙发,有三个大空调,听说原来是一中的监控室。结果,我们去6楼等了好久,还是没有开课,然后我们就被叫去5楼听课了,火大。幸好听完课之后还是去一楼机房耍,开心。老师上课给我们复习了一些基础的东西,这......
  • Profinet远程IO模块:模拟量模块_软件组态说明
    本章主要介绍Profinet远程IO模块XD系列与PLC配置步骤。该文举例介绍模拟量模块输入输出的组态方法。1、通信连接图,如图4-1所示。图4-1通信连接图2、硬件配置如表4-1所示3、安装XML描述文件安装XML描述文件到Twin0AT3中,如图4-2所示。示例默认文件夹为(0:\Twin0AT\3.1\0onf......