BZOJ 1021 :[SHOI2008]Debt 循环的债务 (DP)

题目链接

真是蒟蒻,已经连续几题沦落到不看题解写不出的地步了,最近不太想写题了,学习新的算法吧

用f[i][j][k]表示算到第i种钱,乙有j元,丙有k元的最小方案数,记录可以转移的方案以及去掉不可以转移的方案就行了

Code:

 

BZOJ 1009 :[HNOI2008]GT考试(KPM算法+dp+矩阵快速幂)

题目链接

这道到是不用看题解,不过太经典了,早就被剧透一脸了

这道题很像ac自动机上的dp(其实就是)

然后注意到n很大,节点很小,于是就可以用矩阵快速幂优化了

时间复杂度为 $o(m^3 *log n)$ ;

蒟蒻kpm写得少,改了好久= =

Code:

 

BZOJ 1085: [SCOI2005]骑士精神(A*算法)

题目链接

第一次写A算法(这就是A?如果这就是A*的话,那不就只是搜索的一个优化了= =,不过h函数如果弄难一点真的有些难设计)

其实就是判断t+h(x)(t为当前步数,h(x)为达到当前状态的最小步数) 是否小于当前答案k罢了

已经连续几道题因为一些小问题而调了很久了,不能这样啊QAQ

Code:

 

wikioi 3132 高精度乘法(FFT)

第一次学FFT,先膜拜一下法法塔大神ORZ

关于FFT的话,有一篇博文特别赞http://z55250825.blog.163.com/blog/static/150230809201431274653644/

他后面还有关于高精度和jsoi2014 力的题解写的特别好

其次算导讲的真的不错

不过这篇博文讲得更算导差不多了ORZ

直接上代码吧

尼玛重载运算符老写错QAQ

好吧突然发现以前有一点错误,然后插了别人的代码来check,后来自己的就没了= = sorry

Code:

 

BZOJ 3527: [Zjoi2014]力(FFT)

题目链接

我们看一下这个函数,很容易就把他化为 $E=\sum_{i>j}{\frac{a_j}{(i-j)^2}}-\sum_{j>i}{\frac{a_j}{(i-j)^2}}$

把它拆成两半,可以发现分子与分母下标相加总为i

也就是说,例如左边, 可以表示成$g(x)= f(i)*F(x-i)(i<x)$ 也就是卷积了

可以轻易的构造出 $f(i)= a_i$ $F(i)=\frac{1}{i^2}$ FFT就行了

右边的话,吧$f(i)$给倒过来就行了 ($f(i)=a_{n-i}$)

最后的答案 $ans_i=g(i)-G(n-i-1)$

ok了

最近发现自己写环套树老写渣,找几道题来练练~~

Code:

 

BZOJ 1033: [ZJOI2008]杀蚂蚁antbuster(模拟)

题目链接:

坑爹的模拟题QAQ DEBUG多了1kb QAQ

按题意做就行了

注意理解题意啊啊啊啊

尼玛输出忘换行wa了3次QAQ

 

纪中集训 Day 0?

好吧昨天的等到今天才来写,现在超不想刷题,来写下blog吧= =

坐了近10H的火车终于来到了中山市

火车上在看空之境界,等有时间补下动画吧= =

到了宿舍各种不习惯(现在才发现还是母校好QAQ)然后就去机房了,各种膜拜大神,一堆金牌爷什么的蒟蒻没人权啊QAQ

然后晚上了,一道机房没多少人在玩,在玩的至多10分钟之后就去刷题了,真的是神多啊QAQ

晚上做了他们早上做的NOIP模拟题,T1真的脑残了,没想到减掉之后具有单调性然后就贪心了

T2挺水的,两次spfa就行了,不过空间是硬伤,改了好久才不MLE QAQ (还是想了很久真是蒟蒻)

T3挺神的,枚举素数然后爆搜就80了,100的话再加上个挺吊的优化就行了

要说我去考的话估计真得跪啊QAQ

不过不得不说纪中的氛围真好,他们一直都在讨论题目,坐在我前面的同学也很耐心的给我讲题(那位估计是未来的进队爷啊ORZ)

然后回宿舍了,发现舍友是GDOI出题人+银牌爷,无线膜拜ORZ

这几天的获益应该会好多,但是应该交不到一个纪中的朋友So sad 我终于明白云神的孤独了,在参加比赛时,如果没有一个好机油,真的是很痛苦的

但这是我选择的路,不管前面有多困难,只要向前走就行了,加油!!

题目什么的= =,由于版权啊QAQ

PS:舍友是MoreD+z+yangle

纪中集训 Day1

今天早上起来吃饭,发现纪中伙食真的是太差了!!!什么都不热,早餐的面包还好,然后就迎来了美好的早晨= =

早上做一套题,T1T2果断秒,T3一看就是noi原题,还好看过题解会写,然后就愉快的码+Debug了1h(其实是很水的一题,不过我真的太弱了)顺便把bzoj上的也交了(其实要不是去bzoj上交我才过不了呢~~~)T4一开始以为是水的一道DP,打完才发现不是,然后我觉得应该是搜索,不过2^200次方太恶了,不敢写,所以就不写了(我现在发现我根本懒得写暴力怎么办QAQ)然后比赛就愉快的结束了

接下来就看了其他人做的A组题(BZOI 2014 Day2)太丧病了,T1是什么随机算法什么的,T2 LCT应该能过(不过根本写不好啊QAQ),T3想不出要怎么做QAQ

然后就出结果了 我300,rank2 rank1 324 ORZ(大神都去做A组了我会说QAQ)

然后午餐又吃了纪中的冷饭= =(尼玛纪中饭怎么都是冷的 QAQ) 还见识了千军万马跑去食堂的场景(太壮观了!!!),实在难忘QAQ

午睡被尿憋醒后,就开始评讲了,前3题果真是真解,脑残被人叫上去讲T3还讲不好真是蒟蒻QAQ T4果真是搜索(出题人说2^10000的都做过吓尿了)+奇葩优化QAQ

A组的题目果真丧病,T2能用树链剖分水过(不过树链剖分还是太恐怖了QAQ)T3其实是道很水的dp真是想不到QAQ,T1的做法神到太神了= =反正如果我去考肯定爆零的QAQ

说下T1怎么做吧,大意是把两个题目A和B组合在一起,那么组合而成的题目涉及到的想法的集合就是A涉及到的想法的集合和B涉及到的想法的集合的并。给每个题目都是如何组合而来的。你要回答的就是,每个题目涉及的想法的集合有多大。

然后解!法!就!是! 给每个想法一个0~1的数,然后对每个题目,保留他们的第T个数记为p,那么答案就是t/p

多做几次然后取平均值就行了ORZ

Why?

解题人的说法是,如果是随机的,那么可以看做每个题目如果有b个想法的话,那么这b个想法的值分别为1/b 2/b … 1 那么,第t个就是t/b 那答案就出来了ORZ

超神啊!!!!

正确性呢?

标称的话正确率在99%以上,答案误差在10%以内ORZ

真是蒟蒻

然后下午的时间就写了T3了,结果一直Wa 40忍不住抄了别人的代码QAQ,真的好恐怖啊QAQ

然后晚上的时间就写T2了,码了好久之后,样例一次过,交上去之后,差点以为能1A啊,结果TLE了 LCT太神还是不写的好QAQ

接下来有时间就写下T2的树链剖分吧QAQ

好吧就是这样,愉(bei)快(nue)的一天就结束了

明天加油吧

Bless All!!!

ps:总而言之就是当年自己太菜了

纪中集训 Day 2

今天(其实是昨天= =)早上起来发现好冷好冷啊= =

吃完饭就准备比赛了,好吧B组难度的题总有一道不知到怎么写QAQ 太弱了啊!!! 蒟蒻没人权啊QAQ

今天第4题不会写,在这里说说吧

题目的意思就是,给一串男女序列,要求将其分成m个部分,使其男女差值的最大值最小 并输出其字典序最大和字典序最小的方案

首先把男女设为1,-1,求前缀和,然后显而易见答案为sum[n]/m(取上整)(其实是不会QAQ)注意答案为0的情况

求字典序最小呢?扫一遍,如果当前的部分满足并且后面的部分最大值不变的话(看前面的式子),就直接切开

然后结果出来了 蒟蒻220 rank 2 居然是因为T1 的二分 r写成l了QAQ 真是弱啊QAQ

然后A组难度的题简直丧病QAQ T1概率论+插头dp(话说找个时间补下概率和排列组合了)T2 也挺神的 T3标称傲娇了,老是过不了= =

中午我没有睡觉,把空之境界看完了,写得真的不错,找时间补动画,然后决定今后中午来补番了= =

下午无所事事,把T4过了(其实T4没有特判,抄了一个数据就不理了)就颓了QAQ

晚上把A组的T2给过了,然后又颓了,干了件不太好说的事+把BZOJ上的题刷到纪中的oj上就无所事事了= =

然后老师来找我了,谈到了学习啊,学校啊,竞赛啊什么的,让我真的挺伤心的= =

之后他鼓励我说要努力,过几天看下能不能到A组去,也说如果我够好的话可以和纪中的同学们一起学习

我的环境没有他们好,在学校学习的氛围也没他们好,真的挺羡慕他们能够这样子讨论学习玩耍什么的,而我只能一个人和老师一起在空荡荡的机房里奋斗,在家每天也只有风扇什么的每天都热成dog 但是我一直都希望能够让我的oi之路走得更远,毕竟我也希望能够登上noi ioi的赛场上,能够让其他人为我自豪,能够让我这5年的奋斗不付之东流,加油,为了我自己的未来!!

纪中集训 Day 3

这几天一直坚持写blog= =加油吧!!

早上醒来,说了”我要AK”(其实只是蒟蒻的妄想罢了QAQ) 然后为了不立flag,改成了我要rank 1

然后依旧是有一题不会做QAQ 好弱,争取有一次能全会做吧QAQ

然后就230了 rank1

第3题果真是爆搜不过就算写也难写啦啦啦~~~

A组的题又是丧病,T1数学题什么的根本不会,T2到时看出来是网络流了可还是不会QAQ T3 YY了一下好像能做但是依旧恐怖QAQ

中午补了龙与虎,觉得钉宫理惠真的很厉害啊QAQ

下午讲题了,我才懂了一个求上下界最大流的一个简便的方法,就是把下界边的费用设为-inf然后强制使流量走那里就行了,求出结果后就加上那些inf就行了,然后颓废,把BZOJ上的一道题a了就滚蛋了

难得的晴天不运动都是太惨了QAQ 衣服都干了2333

晚上依旧颓废,老师让我们做CH上的题,我看了一下,果真神题,不久群上大神说T1是什么后缀平衡树,T2是什么数据结构维护最大流,T3是期望什么的根本不会,果断放弃,把今天A组T2过了之后就滚来写blog了。

好累,中午不睡觉还是不行QAQ

加油吧,为了A组,为了和大神交朋友,为了自己,加油吧!!

PS:后来呀自己后缀平衡树,数据结构维护最大流什么也都会了。。。感觉还是成长了很多啊