注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

最近水的几套省选题  

2014-04-21 20:01:15|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
为了准备HNOI……水了几套省选题
按照贴吧某人说法这样子的话HNOI会跪?

先贴下一句话题解吧
FJOI day1
第一题先用最短路预处理出树然后是裸的点分治
第二题先求重心,如果有两个重心中间加一个点。我们知道一个点是重心那么以他为根最大的子树大小不得超过n/2。
先把他当做个根,预处理dp[i][j]表示子树i选连通的j个点的方案数……注意到这个不是O(n^3)的是O(n^2)的。
然后我们可以把他的每个子树拿出来用dp数组当价值做背包,复杂度不是很好估计,反正达不到O(n^3)就是了
第三题数据水三分是可过的……我是求偏导做的
(不知道FJOI的题有没有版权,我就假设大家拿到了FJOI的题吧)
cqoi
第一题裸的高斯消元+bitset可过……
其实这种题是很经典的题了确定了第一行后面的都唯一确定,于是给第一行设方程,算出最后一行每个元素关于第一行的关系,拿最后一行做高斯消元。由于只要一组解,自由元全部设置为1即可。复杂度很低
第二题结论题不会证T_T。
错误的网络流方法好想,但是无法满足一条无向边顺着走和倒着走加起来不超过两次。结论是先用错误的网络流方法做一遍,再交换Sb,Tb再做一遍,不明觉厉
第三题是时空穿梭的超级弱化版……
无语的是WC上我竟然没想到部分分,难道做WC的时候由于心理暗示智商降低了?反正做法是极水的……nm log n的枚举向量即可。
最优复杂度能做到n^(2/3)
第四题是经典题,我学splay打标记的时候就是拿这题练手的,感觉时光流逝啊
第五题挺常规的……
注意到通配符很小,拿这个当突破口把整个串给分开然后hash一下就行了,由于通配符很小所以这部分暴力一点是没关系的
我的复杂度应该是字符串长度*"?"个数*"*"个数
zjoi day1
第一题是手速题……
学校考试的时候这题写了好久最后第三题就不得不弃疗了,幸好花半个小时写了下T2。
我的做法是开一大堆set,结果被卡常数了只有90分,反正bzoj上能过就不管了
第二题是FFT
第三题用FJOI的方法可以知道你要得到的是Σx^2,Σy^2,Σx,Σy,Σxy,Σ1。所以树的话倍增就行了,环套树把环摆到根的位置倍增分两种情况讨论也就行了
sdoi
day1T1是数论题……
用一些经典的方法搞一下。我们知道一个数的因子和以及这个数出现多少次都是可以推的,最后推出来的式子还要求一个变量<=输入的那个东西,我们只要离线一下用树状数组维护前缀和就能做到n log^2 n+qsqrt(n)*log n的复杂度
day1T2是经典题。AC自动机dp+数位dp,没了
day1T3是数据结构题……
刚开始yy了一个树链剖分套树套树的在线做法感觉不是我的代码能力能做的……
cmg教我开大招:离线。
对每个颜色抽象出一堆事件,按颜色顺序做。这样就很好搞了,整个就是在修改一个点的权值。保证任意时刻只会有当前颜色的点有权值。因为改成这个颜色就代表把权值修改为这个值;改成别的颜色代表把权值变成0;改权值就是普通的改权值。
然后1h左右1A了……
结果被dzy怒打脸:树链剖分套主席树直接碾压。T_T,树链剖分套树套树的我到底是在想什么啊
day2 T1转一下模型就是最小字典序最小割,直接朴素的删边有60
我看了范爷的做法,不过没看懂,乱搞了一下莫名其妙A掉了……感觉我的那份代码是有问题的只是数据水,考试的时候我就写60好了
day2 T2由于做过共点圆,所以在凸包上能二分的结论是去年就知道的。
秒想分块……感觉不可能跑得过
就想二进制分组,不过二进制分组不知道怎么处理[l,r]区间。因为二进制分组说白了就是树状数组套凸包,而树状数组需要维护的是具有区间减的,于是这个思路只好放弃。
既然树状数组不行就想线段树?嗯,线段树能很方便的把[l,r]划分成若干个不相交区间……线段树套XXX不能用传统的合并左右儿子的方法,所以单点修改操作得用在每个节点插入一个元素的方法来写……这样的话就要写线段树套平衡树维护动态凸包……查询的时候在平衡树里二分,应该是可做的,但是代码量有点可怕啊……不敢写
其实我还特地去写了个分块碰碰运气的……当然没跑过
跑去问delayyy,delayyy教我开大招:很显然一个节点在区间满之前是不会被用到的,所以先丢进去,直到插满了就建立凸包……很开心的A掉了
(我有种错觉:那个线段树套平衡树维护动态凸包的算法我好像写的出来?算了就当我是在高估自己好了吧。何况那个做法常数肯定过不掉)
day2 T3是结论题
度数矩阵-邻接矩阵的行列式是生成树计数问题……而带权图的话,度数矩阵-邻接矩阵的行列式是Σπ W[T[ei]]。T是一棵生成树,e是一条边,w是权值
考虑将输入矩阵当做邻接矩阵来做……得到了生成树概率和,但是有可能有非树边
考虑G(i,j)=P(i,j)/(1-P(i,j)),base=π(1-P(i,j)),行列式*base就是答案
但是有的P(i,j)=1……那么你的G(i,j)就是not a number……用并查集把概率为1的边连接的点缩掉……一开始就有环输出0,缩点之后再做

话说今天补了下noi2012 T_T
不过题解网上满天飞所以不打算讲什么了
接下来如果bzoj上添了什么省选题就再看看好了,HNOI遥遥无期啊……
其实还做了下usaco open的,不过T3不会做人太弱
接下来继续补noi吧……其实看到CF上一堆一堆的没做的题很伤感的,补完了noi的话旧赶快去做CF

update: on 2014年10月30日
因为集训队作业得原因……usaco open T3我终于会做了
  评论这张
 
阅读(621)| 评论(16)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017