「考试」noip模拟9,11,13
9.1 辣鸡
可以把答案分成 每个矩形内部连线 和 矩形之间的连线 两部分
前半部分即为\(2(w-1)(h-1)\),后半部分可以模拟求(就是讨论四种相邻的情况)
如果\(n^2\)选择暴力模拟是有\(35pts\)的
发现按横坐标排序后,如果有一矩形与当前矩形横向不相邻,则之后矩形都是没有贡献的
所以枚举时比较横坐标视情况跳出
因为会产生贡献的矩形对并不多(不超过\(4e5\),具体还会小),所以这样优化以后可以通过
9.2 模板
暴力跳祖先的话是有\(30pts\)的,经过一番纯玄学特判可以拿到45pts
类比之前主席树的某道题,我们统计答案的时候只关心每个颜色的第一次出现,所以可以以时间为值域开线段树,每个叶子节点存这个节点对球总数和颜色的贡献(0或1)
在合并时,需要考虑当前每个颜色新的最早出现位置,可以开一个存每个颜色最早出现位置的线段树,然后先合并时间线段树,再合并颜色线段树,如果出现了相同颜色就比较,并在时间线段树里修改这个颜色在较晚位置的贡献值
思路是偏的,代码能力不行,就很爽。
9.3 超级树
显然是dp,但是怎么想到这神仙转移啊
考虑k级和k+1级之间的关系:k+1级就是两个k级加一个点连起来
那么如果知道k级的方案数怎么推出k+1级呢
新的这个点可能和两棵树以几种方式建立联系:
- 不连边
- 向左连边
- 向右连边
- 左右同时连边
连边的时候,就要考虑,如果向左连边,有多少种选择方案,这样的问题
这个选择方案数,需要枚举两侧边的位置的每一种情况,再乘上一个边数
那么是不是可以按照边数分类,记录每个边数对应的情况数
就有了状态定义的雏形:\(f[i][j]\)表示\(i\)级树放\(j\)个边的方案数
又发现,在转移时,如果有左边选两条和根接起来这种情况,左边选的两条边是不能相交的
所以:\(f[i][j]\)表示\(i\)级树放\(j\)个不相交边的方案数
那么就有初始状态\(f[1][0]=f[1][1]=1\)
求\(k\)级方案,答案即为\(f[k][1]\)
状态定义想出来,再配合上面的分析过程,转移方程就会简单一些了
状态定义很重要……
11.1 方程的解
\(40pts\)做法:直接面向数据范围特判
正解:\(exgcd\),模拟一下,分类讨论
先求出方程的一组解,然后按不定方程的结论可以得到其他的解
首先得到一组正整数解,如果得不到就是没有解
然后进行一系列加加减减,直到得不到正整数解,并计数
就是基本的做法了
但是需要特判,如果解变换时xy的变化量同号,就说明他们直接并肩上天就行了,解是无限的
而如果a,b有0,就需要考虑这个方程有没有解,且如果有解就是无限个
11.2 光
大模拟
因为光在对角线上走,对角线的特点就是横纵坐标和/差为定值
那么可以用vector维护对角线上点的横坐标,每次查找反射点时二分
注意如果出现了原地折返,答案要/2
又因为起点不一定靠墙,开始时让他先撞一次墙,重新设定起点,再开始模拟
11.3 visit
考试时写出了式子,然后不会求了
发现p数量少,所以用crt合并
发现p很小,所以用lucas求组合。
13.1 入阵曲
考虑余数,先做二维前缀和
数据范围告诉我们需要写一个\(O(n^3)\)的东西
可以在纵坐标枚举每一个区间,然后枚举每一个长度的从最左端开始的矩形,记录每个余数的个数,特别的设\(cnt[0]\)初始为1
那么每个余数有\(\frac{cnt(cnt-1)}{2}\)的贡献
13.2 将军令
数据小的时候直接状压暴搜
发现最好的情况就是各点控制范围无交集,考虑贪心
按深度排序,扫到一个点若未被控制就在他的k级父亲驻扎
13.3 星空
逐个操作很麻烦,考虑差分下的操作,其实就是可以反转两个位置的值
将原序列差分,目标转化为将序列变为全0
一个长为k的操作可以将坐标差为k的两个1变为0,通过不同操作的组合可以得到需要的值,考虑背包
需要改变的位置很少,最多16个,考虑状压,记录每个不为0的数的位置,然后一次消两个,\(f[S]\)为到状态\(S\)需要的最小步数,初始\(f[all]=0\),答案即为\(f[0]\)
最新文章
- css深入理解z-index
- python学习道路(day2note)(数据类型,运算符,字符串,列表)
- JQM[jquery mobile] 实战经验汇总
- 关于Ruby的一些知识
- Java分布式处理技术(RMI,JDNI)
- 关于onpropertychange与oninput的兼容问题
- Java 找出四位数的全部吸血鬼数字 基础代码实例
- 使用Varnish+ESI实现静态页面的局部缓存(思路篇)
- System.UnauthorizedAccessException 错误
- linux下面根据不同的日期创建不同文件,一般用户数据库的备份的shell编程
- linux dns域名缓存
- 递归求i^2的和
- Java之旅_高级教程_多线程编程
- JVM Tools
- 每天一个linux命令-wc命令
- CKEditor5 基本使用
- Mac下crontab定时python任务
- Azure Linux 虚机上配置 RAID 的常见问题及解决方案
- 【BZOJ2115】Xor(线性基)
- 内联汇编实现 memcpy 和 memset