4
8
2015
17

【除草】BZOJ泛做②

刷题速度奇慢无比


upd 4.8

2320: 最多重复子串:后缀数组好题,详见Seter题解,把hash+二分改成SA。。跑得没hash快。。

3922: Karin的弹幕:考虑分块,公差大于S暴力,小于S分块,信息记在起始端,[tex]a_{i,j,k}[/tex]表示第i个节点开始公差给j的序列第k项是什么,考虑空间可能不够,对k再分块,复杂度依然是不变的,对k分块的每块可以用个堆,然而我用了set,复杂度是[tex]O(n\sqrt{n\log n})[/tex]

2176: Strange string:最小表示法,感性地理解一下还是挺水的。

2662: [BeiJing wc2012]冻结:分层图最短路

2882: 工艺:最小表示法

3037: 创世纪:环套外向树DP

3926: [Zjoi20150]诸神眷顾的幻想乡:SAM裸题啊啊啊啊。。。说好的不考SAM呢。。T T。。。

3925: [Zjoi20150]地震后的幻想乡:解法多样。。标算多项式啦。。其实转化为计数问题更好一点,假设我们在做kruskal,[tex]f_{S,j}[/tex]表示点集为S时仅用前j小的边就使S的联通的方案数,转移枚举从小到大点集,枚举子集和补集,找出子集和补集之间的边,枚举子集用了u条边,补集用了v条边,加上之间的一条边转移到[tex]f_{S,u+v+1}[/tex],然后考虑一些不是用来构成mst的边,之后做个背包就可以了,设全集为U,总边数m,最后[tex]f_{U,i}-f_{U,i-1}*(m-i+1)[/tex]就代表以第i小的边为mst中最大边的方案数,计算贡献即可。复杂度[tex]O(3^nm^2)[/tex]

3913: Jabby's newwork:cc原题?23333,有点神的,爆推

3931: [CQOI2015]网络吞吐量:倒着跑一边最短路,对最短路径图建反向边并拆点,跑最大流

3932: [CQOI2015]任务查询系统:函数式线段树

3930: [CQOI2015]选数:容斥递推,先把L,H都除K,[tex]f_i[/tex]表示GCD恰为i的方案数,先统计为i的倍数的方案数,那就是[tex](\lfloor\frac{H}{i}\rfloor -\lfloor \frac{L-1}{i}\rfloor)^n-(\lfloor\frac{H}{i}\rfloor -\lfloor\frac{L-1}{i}\rfloor)[/tex],然后减去[tex]\sum_{i=2}^{i*k<=H-L+1}{f_{i*k}}[/tex],最后特判L=1的情况,全选K也是可行的,答案+1

2144: 跳跳棋:HZWER的题解很详细。。中间可以往外跳,两个儿子,外面只有一个能往里跳,一个父亲,我们发现往里跳的过程类似辗转相除法,终态是固定的,然后我们判一下两个状态的终态是否相等,不等就是无解,否则即为寻找LCA求最短路径,倍增。两个log。

2555: SubString:SAM套LCT,即加入一个字符后对fail的所有节点贡献+1,暴力能过。。

3924: [Zjoi2015]幻想乡战略游戏:考场上的做法。。3个log,点分+点分+树剖

3938: Robot:lc线段树大法好!线段树维护折线。

3862: Little Devil I:LCT。。挺无脑的。。第一个操作直接做,第二个操作只需要在链上打个标记,access拼接和断开的时候翻转儿子就可以了。说到这里我再来宣传一下3914: Jabby's shadows,大水题。


upd 4.9

3868: The only survival/3864: Hero meet devil/3905: Square:详见陈老师WC课件


upd 4.10

3840: ZCC Loves COT:把xOy,yOz的平分平面和xOy平面以及垂直于xOz平面且垂直于x轴于(n,0,0)点处的平面交出来一个正四面体,脑补一下大概是这样的

然后按照x轴分开看,每块是一个直角三角形,对于每个更改每块打个标记,做几次前缀和就好辣,复杂度nq

3939: [Usaco2015 Feb]Cow Hopscotch:线段树动态开点。。

3943: [Usaco2015 Feb]SuperBull:最小生成树

3940: [Usaco2015 Feb]Censoring:AC自动机?。trie图,新姿势get

3942: [Usaco2015 Feb]Censoring:KMP。直接贴上一份代码了

3846: ZCC loves words:trie图建出来就可以搞出dp方程,搞成矩阵快速幂,由于有位置影响,模数是三个很小的模数乘起来,每个小模数可能的矩阵只有P个,爆搞搞出来中国剩余定理合并。


upd 4.11

1129: [POI2008]Per:先考虑模数为质数的情况,考虑从后往前放,每次放一个元素在bit里面维护前缀和,用排列的式子就是[tex]\frac{tot!}{\prod{C_i!}}[/tex]其中[tex]C_i[/tex]表示每同种元素的个数,[tex]\sum{C_i}=tot[/tex],每次维护插入一遍总的答案,求比原排列小的就是在bit里拿出这一位比原排列小的个数乘上维护的答案/tot,相当于把这一位定住的贡献。以上都是比较容易想到的,然后比较恶心的是模数非质数,其实用很老套的方法就可以了,把模数拆分,struct重定义int,把int都里拥有模数的质因数都提出来存着,每个struct存log个变量和一个和模数互质的元素,然后除法乘法都可以在log的时间内完成,bit里还是维护原来的int,因为只涉及最后乘一下,复杂度依旧是[tex]O(n\log n)[/tex]

upd 4.13:后来发现乘的时候还有快速幂囧。。复杂度是[tex]O(n\log^2 n)[/tex]

1517: [POI2006]Met:好题啊。。首先可以证明答案一定是一棵树,并且可以证明答案一定包含某条直径,于是找出直径的一个端点往下贪心找2*K-1条链,每次找到一条最长的删掉。这样爆搞是[tex]O(n\log n)[/tex],可以过了。同样的思路,比较厉害的一种想法把这棵以直径的一个端点为根的树按照深度树剖,把每个叶子表示为向上的延伸的最长长度,把叶子基数排序一下取前2*K-1个即可,这样就是[tex]O(n)[/tex]。还有一种更厉害的想法,丢掉上面所有想法,不设根,从叶子开始,每次把树最外一层叶子剥掉,记录数量,和2*K取min加入答案即可。以上三种做法,前两种证明比较显然,最后一种比较意识流,表示不会证。

upd 4.15:窝来口胡一下最后一种做法的证明(真的完完全全是口胡),首先k条路径肯定都是从叶子开始,叶子结束,我们剥掉了一层叶子,这层叶子中可以乱选2*K个,都可以和剥掉后的树构成一个解,然后剥掉后的树成为了一个子问题,所以是可行解,同时对于每层叶子我们最多只能选2*K个,也是最优解。

3843: ZCC loves Army:LCT套splay维护儿子就可以了,这是强行cosplay Toptree还是闹哪样。BZOJ上数据错的,标程没有判一个点是另外一个点祖先的情况。HUD上交了下过样例1A了。。这不科学。。


upd 4.12

好颓啊。。。。然而我还在计数问题的汪洋中挣扎。。。随便切道题签到一下吧。

3956: Count:正反用单调队列建两棵主席树就好辣


upd 4.14

3962: [WF2011]Coffee Central:可以直接维护那个菱形。。然而我转了一下坐标,维护正方形就方便许多了(可转坐标不方便啊

3953: [WF2013]Self-Assembly:26*2个节点,一个节点向同块另一类节点的配对节点连单向边,表示可以走出去,然后传递闭包跑一下有环就是unbounded

3972: [WF2013]Pirate Chest:枚举上下界限,左右用单调队列找出左右界限,然后就是[tex]O(n^3)[/tex],要卡常数

3969: [WF2013]Low Power:排个序就可以二分贪心了,能放就放,不能放就塞到前面的机器人不用的电池去

3960: [WF2011]Ancient Messages:数联通块个数

3944: Sum:筛筛筛!网上有题解。有必要补到数论专题去?


upd 4.15

3983: [WF2012]Takeover Wars:显然只有最大的干掉另外一个最大的才有意义,但是也不一定是最优的,所以一方能保证合并第二大以后依然比另一方最大大或者最大的比另一方最大的小的话就合并,用个堆维护就好了。

1912: [Apio2010]patrol 巡逻:最长路+次长路

3136: [Baltic2013]brunhilda:应该不是标解把。。直接用筛法+堆跑一遍,复杂度是[tex]O(n\ln n \log n)[/tex],或者更小?因为不需要更新的时候可以跳着更新。。

3841: ZCC Loves Intersection:数学题。。

3844: ZCC loves cards:爆搜,然后用线性基判一些元素是否存在进行剪枝

3851: 2048:暴力+背包


upd 4.16

2749: [HAOI2012]外星人:奇数求phi一定是偶数,偶数除了2求phi还是偶数,如果一个数有一堆2的质因子,每次求phi只能删去一个,所以就是数每种质因子求phi分解出来的2的个数,预处理dp,然后如果初始为奇数特判+1

3971: [WF2013]Матрёшка:区间DP,[tex]f_{i,j}[/tex]表示区间[tex](i,j)[/tex]合并起来最少需要几次拆分,非法区间不用管,最后统计答案不会算进去,对于两个区间a,b合并,就是数一数a区间比b区间最小值大的有几个,b区间比a区间最小值大的有几个,这个可以预处理,最后再做个dp把合法区间的状态转移一下即可。

2141: 排队:归并排序求出初始解,然后每次操作都可以[tex]O(n)[/tex]维护

3979: [WF2012]infiltration:因为是完全图,答案不会很大,直接爆搜,剪枝加几个就可以了。


 

Category: BZOJ | Tags: Problem sets | Read Count: 6177
Avatar_small
icerupt said:
Wed, 07 Oct 2015 10:56:26 +0800

您好,可不可以看一下您3922是怎么用set做的,不是很理解,看了王悦同的论文只想到了用线段树的做法。谢谢。我的邮箱是icerupt@126.com

Avatar_small
south university stu said:
Sat, 20 Aug 2022 00:50:31 +0800

Student Portal Homepage. If you require assistance with an Existing Username or Password, please call the Technical Support Center: South University Online 2021. Welcome to Brightspace by D2L. Log in to view your courses, south university student portal explore tools and features, and customize your e-Learning experience. Username Password. Student Portal Homepage. If you require assistance with an Existing Username or Password, please call the Technical Support Center: South University Online 2021. Welcome to Brightspace by D2L. Log in to view your courses

Avatar_small
meidir said:
Tue, 06 Dec 2022 05:23:20 +0800

There may be noticeably a bundle to learn about this. I assume you made sure nice points in features also. 승무패

 

===============

 

When I originally commented I clicked the -Notify me when new comments are added- checkbox now every time a comment is added I get four emails sticking with the same comment. Will there be by any means you’ll be able to eliminate me from that service? Thanks! 攝影器材

Avatar_small
meidir said:
Mon, 26 Dec 2022 22:48:58 +0800

Undeniably believe that which you stated. Your favorite justification appeared to be on the internet the easiest thing to be aware of. I say to you, I certainly get irked while people consider worries that they just do not know about. You managed to hit the nail upon the top and also defined out the whole thing without having side-effects , people could take a signal. Will probably be back to get more. Thanks .Chlebek Dukana مكاتب محاماة في جدة

 

============

 

Hello there, Can I copy that photograph and apply that on my personal blog? ابحث عن محامي

 

============

 

Howdy! Someone in my Myspace group shared this site with us so I came to take a look. I’m definitely loving the information. I’m book-marking and will be tweeting this to my followers! Superb blog and great style and design. المكتب العربي للقانون

 

=============

 

Can I simply say what a relief to search out someone who actually knows what theyre talking about on the internet. You positively know tips on how to deliver an issue to gentle and make it important. More people must read this and understand this aspect of the story. I cant believe youre no more widespread because you positively have the gift. محامي

 

=============

 

construction jobs are on the rise again these days because the recession is almost over, محامي في جدة

Avatar_small
meidir said:
Sat, 31 Dec 2022 01:38:38 +0800

Nice post. I find out some thing harder on distinct blogs everyday. It will always be stimulating to study content using their company writers and exercise something from their website. I’d would rather apply certain using the content in my weblog regardless of whether you do not mind. Natually I’ll provide you with a link with your web weblog. Many thanks for sharing. 강남셔츠룸

 

==============

 

Sweet website , super design , very clean and utilise pleasant. 노래방알바

Avatar_small
meidir said:
Sun, 01 Jan 2023 21:50:18 +0800

Hey, you used to write wonderful, but the last few posts have been kinda boring… I miss your tremendous writings. Past few posts are just a little out of track! come on! 바카라사이트

Avatar_small
meidir said:
Fri, 06 Jan 2023 22:19:32 +0800

Everything you need to know about News is very much imptortant to us. 메이저바카라

 

 

=================

 

 

I truly appreciate this post. I?ve been looking everywhere for this! Thank goodness I found it on Bing. You have made my day! Thanks again 토토사이트

Avatar_small
meidir said:
Mon, 09 Jan 2023 18:10:04 +0800

Does your blog have a contact page? I’m having a tough time locating it but, I’d like to shoot you an email. I’ve got some ideas for your blog you might be interested in hearing. Either way, great website and I look forward to seeing it grow over time. 여우알바

 

=============

 

certainly like your web site but you need to check the spelling on several of your posts. Many of them are rife with spelling issues and I find it very bothersome to tell the truth nevertheless I will surely come back again. 룸알바

Avatar_small
meidir said:
Tue, 10 Jan 2023 00:02:19 +0800

Online Quran Learning for Kids & Adults with Expert Male & Female Quran Teachers. 100% Free Trial Classes & Up to 10% Siblings Discounts. https://livelearningquran.com/

Avatar_small
meidir said:
Wed, 11 Jan 2023 17:48:55 +0800

Thanks , I have recently been looking for info approximately this subject for a long time and yours is the best I’ve discovered till now. But, what about the conclusion? Are you sure concerning the source? 바카라사이트

Avatar_small
meidir said:
Sat, 18 Feb 2023 23:27:29 +0800

Hello, Today in the new directory of blogs. I don’t learn how your blog came up, need to have been a typo. Your website looks good, possess a nice day. 슈어맨

Avatar_small
meidir said:
Sat, 22 Apr 2023 18:02:33 +0800

I would like to consider the opportunity of thanking you for your professional instruction I have constantly enjoyed viewing your site. I am looking forward to the particular commencement of my school research and the entire groundwork would never have been complete without surfing your web site. If I can be of any assistance to others, I might be delighted to help as a result of what I have gained from here. Help desk support singapore

Avatar_small
meidir said:
Fri, 30 Jun 2023 01:23:34 +0800

Nice post. I was checking constantly this blog and I am impressed! Very useful information specifically the last part I care for such information a lot. I was seeking this particular information for a long time. Thank you and best of luck. printer servicing

Avatar_small
Uttarakhand 10th Qu said:
Fri, 11 Aug 2023 18:05:35 +0800

UK Board Students with the Help of This Article we are Trying to Provide a UBSE 10th Class Model Paper 2024. So All Those Students who want to get Question Paper 2024 they can Download Previous Paper Solved Question Paper Pdf Format. These Model Test Paper are Basically Previous year Question Paper Provided by the Uttarakhand Board of School Education.UBSE 10th Model Paper 2024 is Very Important Uttarakhand 10th Question Paper 2024 for Public Exam Preparation, Each Student adopts All sorts of ways to get a good Score in the UBSE, Good News Students who are Searching for the UK Board 10th Model Test Paper 2024 has been Uploaded the All Subject Wise Download to the Students who are Going to Appear in the UBSE

Avatar_small
meidir said:
Fri, 13 Oct 2023 14:30:36 +0800

Wow, wonderful blog layout! How long have you ever been blogging for? you made running a blog glance easy. The full look of your website is great, let alone the content! cancer

Avatar_small
meidir said:
Sun, 14 Jan 2024 05:10:50 +0800

Appreciate it for this post, I am a big big fan of this internet site would like to continue updated. BIO MEDICAL WASTE SOLID LIQUID WASTE INCINERATOR SYSTEM MANUFACTURER

 

 

=================

 

 

I had been honored to obtain a call from a friend as he found the important guidelines shared on the site. Browsing your blog post is a real wonderful experience. Thanks again for thinking of readers like me, and I hope for you the best of achievements as being a professional discipline. SHELL AND TUBE HEAT EXCHANGER DESIGNER MANUFACTURER FPSO FLNG

Avatar_small
meidir said:
Sun, 21 Jan 2024 06:04:24 +0800

I really love your idea, great post, looking forward to read your next post! AI Agent Collaboration Tools


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com