2023 年 CCF 春季测试赛模拟赛 - 1
T1
个人思路:
询问:求 \(1\) 到 \(t_i\) 路径上离 \(1\) 最远的 \(p\),使得 \(dis_{1,p} \times 2 \le d_i\)。即 \(dis_{1,t} \times 2 \le d_i + dis_{p,t} \times 2\)。
等价于:\(dis_{p, t} \ge dis_{1,t} - \lfloor \frac{d_i}{2} \rfloor\)。
维护从 \(u\) 往上走 \(2^j\) 步的距离,倍增往上跳。
T2
对于固定前缀 \(T_{1\sim i}\),第 \(i+1\) 次操作所有方案都对答案有贡献,新生成的前缀互不相同。
我们把 \([1,m]\) 和 \([m,1]\) 看成一段可插入的区间,可以插入 \(2\sim m-1\) 各一个。\([1,1],[m,m]\) 不可插入。
状态:\(dp_{i,j,0/1}\) 表示前 \(i\) 次操作,有 \(j\) 个可插入区间,结尾为 \(1/m\) 的方案数。
初始化:\(dp_{0,0,0} = 1\)。
转移:炸裂,因为需要储存当前剩余可填的位置,再加一维直接 GG。
但是可以储存已经填掉的数的个数,即 \(dp_{i,j,k,0/1}\) 表示前 \(i\) 次操作,有 \(j\) 个可插入区间,填入 \(k\) 个数,结尾为 \(1/m\) 的方案数。状态 \(\Theta(n^3)\),时间复杂度 \(\Theta(n^3)\)。
如果不考虑 \(1,1\) 和 \(m,m\),也就是说,只填和上一个结尾不同的数。
最后计算答案时,我们把这些 \(1,1\) 和 \(m,m\) 补回去。好像可以。
状态:\(dp_{i,j}\) 表示表示前 \(i\) 次操作,有 \(j\) 个可插入区间。即插入了 \(i-j\) 个数。
转移:\(dp_{i,j} = dp_{i-1,j-1} + dp_{i-1,j} \times (j \times (m-2) - i + j + 1)\)。注意,需要满足 \(j * (m-2) \ge i - j\)。
答案:
把 \(n - i\) 个数分配给 \(i + 1\) 个点,允许有点为空,插板方案为 \(C_n^i\)。
\]
寄了,过不去样例 \(3\),去写暴力。
状态:\(dp_{i,j,k,0/1}\) 表示前 \(i\) 次操作,有 \(j\) 个可插入区间,填入 \(k\) 个数,结尾为 \(1/m\) 的方案数。
转移:
上一个填的数相同:\(dp_{i,j,k,0} = dp_{i-1,j,k,0}\)
上一个填的数不同:\(dp_{i,j,k,0} = dp_{i-1,j-1,k,1}\)
上一个插入:\(dp_{i,j,k,0} = dp_{i-1,j,k-1,0} \times (j\times(m-2)-k+1)\)
合法状态:\(i\ge j\) 且 \(j\times(m-2) \ge k\)。
答案:\(\sum dp_{n,j,k,0/1}\)。
wssb,正解样例 \(3\) 过了,但是样例 \(4\) 卡死???
数组开小了。。。
T3
暴力删,删完暴力改,时间复杂度 \(\Theta(n\cdot m^2)\)。
最新文章
- jQuery弹出窗口浏览图片
- Moon.Orm 5.0(MQL版)分页功能的设计(求指教,邀请您的加入)
- [转]jqGrid 属性、事件全集
- 利用session做国际化引起的old区内存爆满及修复方法
- linux常见问题集锦
- spring 依赖注入 小结
- C#获取ip的示例
- Java内存管理原理及内存区域详解
- 查看ORACLE事务隔离级别方法(转)
- C++中的endl
- Linux下的压力测试工具:ab、http_load、webbench、siege
- ribbon 详解
- java中lamda表达式的应用
- kali入门
- 推荐写作平台gitbook——让我们换一种形式写作
- CSS样式学习-3、轮廓、伪类/元素、display-flex布局
- 安装phpredis扩展
- pyspark数据准备
- Android WebView清空缓存
- MongoDB之 复制集搭建