bzoj 4195: [Noi2015]程序自动分析 离散化 并查集

真TMD被自己蠢哭了!!!!!!!

离线一下,暴力先把相等的用并查集连起来,然后在判一遍不等就好了嘛!!!!!

干嘛脑子抽了在那在线搞了半天。。。mdzz。。。。

bzoj 2753: [SCOI2012]滑雪与时间胶囊 kruskal

看复杂度就不是最小树形图。显然是MST魔改以下。这个图相当于很大一部分是有向边,有一些小部分是无向边。按照从上(1号点高度)向下的顺序来,自然也就保证了正确性,保证了每次是从1号点的联通快连出去,用MST处理就行了,

以下为正解;

第一个问宽搜解决。

第二个问,按照第一关键字有向边[……]

Read more

bzoj 3884: 上帝与集合的正确用法 欧拉定理

欧拉定理:

a^n % p = a ^ (n % phi(p)) % p(gcd(n,p) == 1)

欧拉定理的推广:

a^n % p= a ^ (n % phi(p)+phi(p)) % p

bzoj 4199: [Noi2015]品酒大会 后缀自动机

弃疗了,,,还是不太理解后缀自动机,依旧是理解型默写,,QAQ。。不想碰后缀自动机了。

bzoj 3998: [TJOI2015]弦论 SAM

第一次写SAM,(准确说是第一次照着hzwer抄SAM) 想看我讲SAM可以走了。

我们维护在后缀自动机上求下拓扑序,然后DP一下。然后像平衡树找第K大那样找就可以了。

bzoj 4813: [Cqoi2017]小Q的棋盘 贪心

xjb贪心了一下。没有证明正确性。。。

最长链走不完,就默默走最长链。

否则保证最长链一次走完的同时,顺带着在周围把步数走满就行。

然后就过了。。。?。。。

bzoj 1086: [SCOI2005]王室联邦 贪心

看起来应该是奇怪的贪心。这题逻辑好奇怪,一个省的省会竟然可以在其他省……

大概说一下,就是子树不小于b就成为一个省。省会为当前点。

这样子每个省都不超过2b。

然后最后可能还有不超过b的城市没有处理。

直接丢尽最后一个省。不超过3b。

dfs处理下就好了。注意每[……]

Read more

bzoj 3709: [PA2014]Bohater 贪心

mmp!数据范围有问题,z要开longlong,WA了一页。

我们将怪物分成两组,一组为打完不会损失血量的。一组为打完会损失血量的。

然后第一组按照d升序打。第二组按照a降序打。

开始第二组按照净费血降序打,然后不对。

后来认为要按一开始扣多少血从大到小排,因为把先打扣血少的[……]

Read more

bzoj 3158: 千钧一发 最小割

看到这道题 是没什么思路的。查了一句话题解说是最小割。让我想到了魔术球那题。想找二分图的性质,然而失败了。真是可惜。后来查了题解恍然大悟。

两个偶数显然满足gcd>1的条件。

两个奇数 (2a+1)^2 + (2b+1)^2 = 4a^2 + 4a + ab^2 + 4b + 2[……]

Read more