7 broxin

尚未进行身份认证

暂无相关简介

等级
TA的排名 5w+

寒假期间出的两个有意思的数论题

这个博客很久没更新了,我不希望它沦为僵尸博客。。所以今天更新一下,近期没有比较好的素材,于是就随便写了。还是关于OI题目的。也许以后会更cs相关的?寒假期间给学弟出了一套数论题,一共四道,其中有两道是我觉得比较创新或者不错的,于是放在最前面,对于初学数论的同学来讲可能难度有点高。第一题,小球碰撞;数据范围:0 <

2019-03-16 22:08:56

【cf666e Forensic Examination】(后缀自动机+线段树合并)

这个题确实思维方向非常重要!如果用后缀数组做,就转化为区间众数,一脸不可做。(当然莫对+堆还是可以的。。)这个题应该用后缀自动机或者后缀树来做。这样问题就是子树众数,就可以用线段树合并一个log搞定。(为什么我一个log比别人一个log+一个根号还慢啊)#include#include#include#include#include#define rep(i,a,b) for

2016-07-06 16:39:48

【UOJ #210】【UER #6】寻找罪犯 (2-SAT)

考试的时候死磕第一题去了,这个题没多想,其实是个裸题。。2-SAT模型显然,注意要对每个人是否是骗子,每句话是否是真话都要建点,然后暴力连边裸上就可以得40分了。瓶颈在于这种关系:若一个人说的某一句话是假话,则他说的其它话都是真话。这个暴力连边是不合适的,我们只需要增加两个信息,表示一个人的前i句话都是真话,以及后i句话都是真话,所以一个点是假话的话向他的前缀和后缀为真话连边就好了。看了下

2016-07-02 23:26:49

【UOJ #209】【UER #6】票数统计

做比赛的时候完全没想到怎么处理同时有前缀和后缀的限制。。智商不够啊QAQ。。其实根据数据范围就能猜出来,因为直接做的复杂度O(n)很明显n不可能给5000,所以应该枚举一下总人数,这样对后缀的限制就转化为对前缀的限制了。。然后x=y的限制取最大那一个,然后简单容斥一下即可。。这个题确实妙啊,几个转弯都很巧妙。。这个题复杂度应该写成Tmn的,然后我偷懒写了个桶,就是Tn^2的,常数大了一点。。

2016-07-02 23:19:01

[Noi2016十连测第二场]幻想(后缀平衡树)

题意:给一个字符串,三种操作,末尾插入一个字符,弹出末尾的字符,查询区间内一个给定字符串出现了多少次。卡常神题。。500万的数据规模什么鬼。。假如没有区间限制,就是后缀平衡树的裸题。查询一个字符串s出现了多少次,就是在后缀平衡树上找出由于替罪羊的删除不是很方便,这里可以用treap,删除一个节点的时候直接重构这个节点所在的子树。以前重构操作都是直接写在rotate里面的,用起来非常方便

2016-06-17 12:19:11

[BZOJ3864]Hero meet devil(状压dp)

题意:给一个长度这个题让我想起了之前做过的一个数位dp,问有多少个数的数字组成的最长上升子序列长度为x。那个题中显然最长上升子序列不超过10,我们用状态压缩来模拟那个做lis时的栈即可。这个题|S|#include#include#include#include#define rep(i,a,b) for(int i=a;i<=b;++i)#define erp(i,a,b)

2016-06-14 20:16:57

[BZOJ3295][Cqoi2011]动态逆序对(分块重建)

题意:一个排列,每次删除一个数,求每次删除后的逆序对的数量。正确姿势请移步 http://blog.csdn.net/u011542204/article/details/50571409将操作分成根号M段,然后每段内的操作按下标排序,计算它前面的比他小的和它后面的比他大的。有一个问题就是同一个块当中的没有被减掉,由于一个块内只有根号M个操作,暴力减掉即可。如果要在线的话将那个排序变成

2016-06-02 11:13:01

COI2016 Palinilap(manacher+后缀数组)

题意:给出一个小写字母组成的字符串,修改一个字符(或者不改),使得字符串中所有回文串的长度之和最大(本质相同的回文串算多个)。好神的题。。题意简单易懂但是做起来非常麻烦。。以后如果只是求求lcp之类的最好写二分+hash,写个后缀数组简直是自讨苦吃。。很显然回文串的长度之和就是manacher算法中半径数组之和。修改一个字符有可能破坏一些回文串,也有可能引入一些新的回文串,只要我们

2016-05-31 22:04:18

[BZOJ2162]男生女生(二分图带权独立集+dp)

题意:懒得写了,比较麻烦。强行嵌套的题真没意思。。开始我看见数据范围n=50,第一问求什么完全子图,我以为是个搜索减枝,然后第二问那个dp我想了想,列了几个方程发现不是很对,然后又没有部分分,我就弃疗了。。其实想一想应该是想得出来的,主要是考试的时候写了第二题的很麻烦的做法,被折腾得没精力了,就没怎么想。。第一问其实很简单,二分图完全子图是P类的。我们求出这个二分图的补图,补图中的边就

2016-05-30 22:01:52

[BZOJ2161]布娃娃(扫描线+线段树)

题意:若干个点,对每个点求能覆盖住它的线段的权值的第k大。强制在线的题做多了,作死写了个主席树套平衡树,两个log常数炸了,只得了40分暴力分。正解显然扫描线+线段树,把每个线段拆成起点和终点,代表插入和删除,线段树维护第k大权值就好了。。

2016-05-30 21:51:49

[BZOJ2160]拉拉队排练(回文树)

题意:求一个字符串的长度前k的奇数长度回文串的长度的乘积模一个数。和APIO那个回文串的题差不多,可以先manacher搞出所有本质不同的回文串,再用后缀数组查查出现了多少次即可。这里偷懒写的回文树,注意跑完了之后那个cnt需要沿着后缀链接向上传递一下。注意那个K是10^12不是10^9。。。开的int丢了5分,还好出题人比较良心只有一个点的K超了int。#include#inclu

2016-05-30 21:44:23

[BZOJ2629]binomial (高精度+Lucas定理+离散对数+FFT)

题意:对于给定的n和p,求对于所有的0注:p虽然要输入,但是题目标注了所以测试点的p是固定的。首先需要用正确的姿势理解lucas定理,比如求C(n,r)%p,就是将n和r分别转换为p进制,然后依次算组合数乘起来。n是一个高精度数,求C(n,r)的过程中,n不断模p得到的数(即n的p进制表示)是固定的。就是长这样:n0!/((n0-k0)!*k0!) * n1!/((n1-k1)!*k1

2016-05-29 23:11:11

CodeChef FNCS(分块)

分成根号n块,每一块上记录每个点在这一块出现了多少次,以及这个块当中当前f函数的和。这一部分可以用n*sqrt(n)的时空复杂度求出来。修改的时候扫描每一个块,对每个块可以O(1)求出这次修改后这个块的和。回答询问的时候,对于整块中的和,直接读块中的信息,对于剩下的部分暴力即可。注意暴力求一个点的f值需要维护一个动态前缀和,即sum(r[i])-sum(l[i]-1)。这道题上面修改的数量和查

2016-05-26 20:55:54

[BZOJ2122]工作评估(分块)

题意:给序列D和L。假设有一个初始价值x0,则经历第i天后价值变为min(x0+D[i],L[i]),记F(i,j,x0)表示以初始代价x0依次经过第i天到第j天后的价值。每次询问给出l,r,x0,求max(F(i,j,x0)),其中[i,j]是子串[l,r]的子串。这个题的最重要的性质在于:一、对于a>=b,F(i,j,a)>=F(i,j,b);二、记G(i,j)为F(i,j,inf

2016-05-26 10:43:20

[BZOJ4605]崂山白花蛇草水(主席树套kd-tree)

题意:两种操作,在二维平面插入一个点及其权值,查询矩形区间第k大,强制在线。之前考试考过一个矩形区间第k大的题。。当时想了各种树套树套树,算了算复杂度都没有暴力快。。后来憋了个kd-tree套主席树,就是把若干个kd-tree上的节点上的主席树弄来一起走,时间复杂度logn*sqrt(n),空间复杂度俩log(由于那个题是离线的,我当时写的kd-tree上自底向上的线段树合并,所以实际空间复杂

2016-05-24 22:55:18

[BZOJ2117][2010国家集训队]Crash的旅游计划

题意:给一棵树,求从每个点开始走向其它n-1个点的距离中第k大值。又是第k大简直cqoi既视感23333其实我一开始看到这个第k大就想起了cqoi那个k光滑数,那个题是用持久化可并堆做dp,然后这个题我就想能不能写个主席树合并然后用主席树跑树dp来表示每个点走到其它点的距离什么的,然后发现不可做。。然后再想了想,发现就是紫荆花弱化版,然后看了看时限,150秒,就觉得非常靠谱。考虑二

2016-05-21 12:39:15

[BZOJ2145]悄悄话

题意:给出用凯撒加密法加密后的密文,求原文。这道题让我想起了三年前做的唐教出那个提交答案题,那道题的加密是一个全排列,破解起来非常困难,当时和lzm他们一群人在机房开黑搞这题搞了一整场考试的时间,得了60分23333这个题凯撒加密的方法只有26种,可以枚举判断。其实APIO上讲课时提到过这个题的。但是我看了题目后发现他保证句子长度大于等于3,又没有保证是从哪里截取的自然英文还是出题人刻

2016-05-19 22:05:53

[BZOJ4521][Cqoi2016]手机号码

题意:一个手机号码被定义为幸运的当且仅当其中不同时出现4和8,并且要有连续三个一样的数字(slj!!!)。求一个区间内合法的手机号码数量。CQOI考试的时候我写了个爆搜乱搞过的。。。如果这题的乱搞没写出来我就滚粗了。。。正确的姿势是数位DP,设6维状态,分别记录当前是第几位,当前位是哪个数字,当前数字连续出现了几次(超过3次视作3次),是否已经出现过三连击,是否出现过4,是否出现过8。dp

2016-05-16 19:13:17

APIO2016游记

刚到北京时我们打了个出租车,然后就被司机坑了。本来路过了80中,我想酒店应该近了,然后就开始记路,结果连拐了十多个弯然后我就记不住了,到酒店被收了70多块钱,结果听说另一辆车只收了40多(什么玩意)。然后入住,感觉酒店环境还不错。有一个挺萌的小哥来和我们坐一个电梯,和我们说了几句话,我瞟了一眼他的胸牌——卧槽mxh大爷!!!当时吓得我嘴巴就张开了。。。       然后我们去80中,结果发现只

2016-05-09 15:40:03

利用后缀数组构造后缀树

由于蒟蒻azui前段时间忙着准备省选,并在省选中成功闷声滚大粗,博客停更了好久。。

2016-04-24 19:06:49

查看更多

勋章 我的勋章
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。