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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

Feyat Cup 1.0 出题思路啥的  

2013-03-12 19:57:05|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这是当时出题的草稿之内的。。。题解里写得有,可以看看

FFT是必须的,考虑和什么东西嵌套吧。。

某题加强一下吧。。。最大数与最小数异或值最大的区间(似乎被lyy虐掉了。。。没关系,反正lyy是神犇无视之)如果加入修改操作或者询问某个区间呢?似乎还是可做的样子吧。。。不确定,仔细想一想。用来当水题出吧。修改操作太蛋疼了,出数据也挺麻烦的,等等,修改似乎可以用分块乱搞?不明中,算了,比较麻烦。如果改成树上询问呢?也太麻烦了。
博弈问题,砍线段,使得最终存在必胜策略,并且使得区间和一定限制范围,然后要求第一步尽可能的多? 设答案为ans,当前的棍子长度为k,即要求ans^k^(k-l)==0 k-l==ans^k,那么最大k-ans^k。没感觉可做的样子啊。。。显然可做,确定k,那么最小化ans^k。。。否决。。。我需要找到一个区间,使得k-ans^k最大。。k变大的话,那么ans^k的最小值肯定变大。。。确定k的下界,那么可以得出此时的一个较优解。。。随机化。。。放在这儿吧。。。那么确定选择的一个为k,包含k的一个区间。。。还是不可做。。。算了,还是确定k是区间的最后一个元素。。。确定区间和在一定的范围内吧。。那么就是询问在l-r之前求一个值,使得p^c最小。这个在线段树里面直接套个trie即可。。。实在太水了,加个修改还是很水怎么办。。。纯粹送分吧。哈哈,如果加入插入操作就可以烦死人了。。。强制在线没意思。。。所以离线线段树。但是修改就比较麻烦了,每次是将一段区间内的所有数都异或上了一个值。。。还是不会,放弃线段树分块吧,这样暴力得多。对,就用分块来搞,部分是有修改,部分没有修改。。。反正我没想到什么好的算法,就用算法组合吧。。。有神犇教了我比较好的,就和维护区间和一样的维护吧。。。恩,觉得可以。。。可以你妹的,如果是持久化trie就太麻烦了,合并的时间复杂度也不确定,还是分块简单暴力。。。但是卡暴力就很难了的说。最终还是水题啊

最后最好来道插头dp什么的。。。看看可不可以嵌套上别的。算了,插头dp太无聊了,放弃
或者去具体数学上找个原题吧,最好来个数论方向的。如果可以和树结合就好了
可以暴力构建的的voronoi图,用此生成平面图。。。平面图应该可以考比较多的东西吧,考虑一条直线与多少个域有交,得到一个0,1的区间。。。嗯,这个也暴力吧。。。似乎可以对于每个凸多边形进行旋转卡壳,然后距离最远和最近的x之间搞搞,应该可以用线段树暴力维护的。。。似乎不可以?好好想想吧。让暴力过了算了。那么总共100000组询问吧,得到100000个数,每个数应该不会很大。。。那么对于每个k求四元组的方案数,为(a,b,c,d),a,b为圆,c,d为直线。a与b交,c与d交,c+d==k的方案数。。。题目完成。

第三题  直接来道线段树的合并算了。。。但是裸的也没意思啊。。。树上的最长不下降子序列似乎是道不错的题目呀。。考虑一棵树,每个点都有个权值,求一条从叶子往根的最长不下降序列。。。为了强制在线,每个点权值为以其所有儿子结尾的最长不下降序列的异或值乘以某个值再加上某个值。。。这样就爽歪歪了。。。耶!等等,这题应该还是有很多方法的。。。慢慢想想,如果对每个点维护单调队列。。然后单调队列进行合并。。。。。。。似乎不可做。但是时间真的不确定的,算了,有更好的算法就等更好的算法吧,反正我也只是yy一下而已。

尼玛,想一道题目比做出一道题目难好多好多啊。。。。
尼玛,我现在承认写这些蛋疼题目比想这些题容易多了。。。。
  评论这张
 
阅读(238)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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