2020.12.12【NOIP提高B组】模拟 总结
第一次来 B 组做，虚的很
T1: 容斥原理
比赛时也打了个大致，但挂了，只有 50 分。
赛后重构了一下代码，AC
\(UPDATE:2020/12/13\ \ \ 14:10\)
思路：
像前缀和一样，先求出 [1,r] 的个数，在求出 [1,l-1] 的个数，最后相减
求法就是典型的容斥原理，用深搜来看第 i 个选不选，复杂度为\(O(2^n)\)
传参时多传一个最小公倍数，注意容斥时的奇负偶正
T2: 玄学
正解应该是 Treap ，但不会
不过 WTF？暴力能对？
但是考试时看了看样例输入，于是多打了一个换行。。。
\(UPDATE:2020/12/14\ \ \ \ 20:10:00\)
打出了多余的正解：
壳用一个双向队列 deque ，剩下的用一个 stack ，翻转用一个 tag 标记，操作 3 直接 tag^=1
事实证明 STL 常数真的大，跑得比暴力还慢。
T3:规律
\(m\le 11\)据说每一种情况都有一种规律
本蒟蒻只会\(m=1\)时奇偶性和\(m=2\)时高精度+斐波那契数列
\(UPDATE:2020/12/13\ \ \ 14:10\)
打消上面的疑虑，这题其实是道分段题
1:m>5
可以看出这就是 50% 的数据，因为 n 较小，可以直接状压 DP
设 F[i][s] 为前 i 行都放满，第 i 行状态为 s 的方案数（0是被填了，1是没有）
可以枚举行数 i 和 i-1 行的状态 j ，再用 Dfs 求出合法状态。
若 S 是第 i 行状态，T 是第 i-1 行状态，可得 \(F[i][S]=\sum F[i-1][T]\)
Dfs(第几行 i，状态的第几位 j，S，T)
- 看看有没有完成 S 状态，若完成则更新 F[i][S] 并返回
- 若 T 第 j 位是 0 ，Dfs(i,j+1,S 第 j 位为 1,T)
- 否则 Dfs(i,j+1,S,T)
- 若 T 第 j 位是 0 且 T 第 j+1 位是 0 且不越界， Dfs(i,j+2,S,T)
最后输出 F[n][0] ，初始化 F 除 F[0][0]=1 其他都是 0
2:m<=5
由于 \(n\le 10^{200}\) 所以可以想到数学方法，而直接肯定会炸，想到矩阵快速幂优化递推
可以用类似上一种情况的方法，把一对合法状态 S 和 T 再矩阵 tmp 中 tmp[S][T] 赋为 1
然后用矩阵快速幂求出 \(ans=tmp^n\) 其实就是一个简单的高精除以低精和\(2^m\times2^m\)的矩阵乘法
最后输出 ans[0][0]
T4:DP
奆佬们都说事二分+单调队列优化DP
于是本蒟蒻想到了 N 个月前没做出来的题“跳房子”，选择暂时放弃
\(UPDATE:2020/12/13\ \ \ 14:10\)
思路：
先二分答案为 mid ，考虑写 check 函数
设 F[i] 为在符合条件的情况下做了前 i 题的最少时间
显然 \(F_i = \min(F_j)+a[i]\ \ \ (j\in [i-mid+1,i-1])\)
最后判断是否有\(F_i<=t\ \ \ (i\in [n-mid+1,n])\)
由于暴力求区间最小会超时，可以用常数较小的单调队列维护，总复杂度\(O(nlogn)\)
总结
这次考试成绩并不理想，虽然只是第一次，却失误比较多
希望以后能看清题目，不打挂会的题目
最新文章
- UITextFieldDelegate协议
- TCP重传率高的监控
- jQuery插件：跨浏览器复制jQuery-zclip（转载）
- 一个使用高并发高线程数 Server 使用异步数据库客户端造成的超时问题
- centos一键优化脚本
- codeforces 340A The Wall（简单数学题）
- jmeter参数化数据（_csvread函数、用户自定义变量等）
- 文本阴影:text-shadow
- 异常处理与调试 - 零基础入门学习Delphi50
- Jenkins快速搭建持续集成
- 文《左右c++与java中国的垃圾问题的分析与解决》一bug分析
- CentOS 7下安装X Window
- 移动端高清、多屏适配方案——rem
- RabbitMQ通过Exchange.fanout、不同的队列绑定同一个Exchange实现多播处理
- 初学Python(二)
- radio(单选框)反复选中与取消选中
- Servlet 转发请求与重定向，以及路径问题
- 解决win 10下git bash中文乱码
- js自定义修改复选框单选框样式，清除复选框单选框默认样式
- ideal使用eclipse快捷键