BZOJ1016 | JSOI2008 最小生成树计数

题面不放

这是道好题 一开始还以为是\rm{Matrix Tree}定理,后来发现不是QAQ

其实暴搜可过

先一遍Kruskal,顺便把权值相等的边们分到一个块里面,随便怎么实现都行 记录一下每个块有多少边在MST中出现过

然后重置一下并查集,枚举块,每个块跑DFS选哪些边(注意连通性,如果这条边加入成环就不能选,这很显然qwq),答案是所有块的方案数的乘积。

这里用了一个性质就是不同的MST中边权相等的边出现次数相等,证明?

开始时,每个点单独构成一个集合。

首先只考虑权值最小的边,将它们全部添加进图中,并去掉环,由于是全部尝试添加,那么只要是用这种权值的边能够连通的点,最终就一定能在一个集合中。

那么不管添加的是哪些边,最终形成的集合数都是一定的,且集合的划分情况一定相同。那么真正添加的边数也是相同的。因为每添加一条边集合的数目便减少1.

那么权值第二小的边呢?我们将之间得到的集合每个集合都缩为一个点,那么权值第二小的边就变成了当前权值最小的边,也有上述的结论。

因此每个阶段,添加的边数都是相同的。我们以权值划分阶段,那么也就意味着某种权值的边的数目是完全相同的。

上文不是我写的。引用一下。

然后就能愉快的切掉这个水题。

 

点击图片跳转原题

 

 

 

 

 

哦,还有,这段代码BZOJ编译会CE,不知道为什么她就是不支持C++11   [摊手]

 

BZOJ1033 | ZJOI2008 杀蚂蚁 AntBuster

<论一次杀蚂蚁的经历>

<论如何优雅地用工程代码风格写出杀蚂蚁>

引子:

前天(也就是2018-3-18)的时候,刷B站(BZOJ)突然想起要A这题……

于是怂恿WHY一起做……

然鹅种种原因,拖到昨天(2018-3-19)下午才开始做

于是在CYYZ群里开起了校车……

然后

因为巨长的变量名不想手残于是换了VSCode……

然后疯狂盖楼……

 

注意这已经是今天的中午了……,而我交了一遍得了30

下午来了遂调试……发现了几个zz错误

等级没算对啦……sort忘记+1啦……蚂蚁位置忘记更新啦……以及更为严重的,没算点积判断附加攻击到底能不能打到。

晚上开始怀疑人生……此时代码量超过10k

下载了测试数据本地测……开Lemon却不小心点了O2

结果最后半个小时在静态查错,然而并没有什么错,后来的手动测试也证明了这一点

是Lemon开了O2之后,把程序跑错了

我果然花了几乎1h试图卡掉通过开了O2的Lemon……(滑稽)

管他的,进入正题

 

 

 

 


继续阅读“BZOJ1033 | ZJOI2008 杀蚂蚁 AntBuster”

BZOJ4241 历史研究

Mo’s Algorithm with Roll-Back

回滚莫队算法

对于删除操作难维护答案但添加易维护的或者 添加难维护但是删除易维护的莫队题,可以使用回滚莫队算法。

历史研究是第一种

对于这种,我们选择

1.对于在同一个块内的询问,O\left( \sqrt{n} \right)暴力计算

2.对于不在同一块的询问,莫队排序后,形成了左端点在同一个块内的若干询问,

对于这些询问,我们只维护这个同块的下一个块的起点到这些询问的右端点的答案情况,因为右端点递增,左面固定在一处,所以只有添加。

然后回答每一个询问的时候暴力统计左端点到下一个块左端对答案的影响,统计完再改回去,

还有一个问题就是如果这个询问的左端点和上个的不在一个块,那直接重置答案统计变量和答案统计数组,暴力重新统计。

这样把复杂度压回了O\left( n\sqrt{n} \right)的级别

·

下一点是添加难维护但是删除易维护的莫队题

对于这类我们采取和上面相同的思想,但是我没见过任何这样的题,属于有解法无题的东西。

对于同块询问当然还是暴力

非同块询问你需要这么做,莫队思想排序完后倒序处理。

对于左端点同块的若干询问,维护这个同块的起点到目前询问右端点的答案情况。倒序处理只有删除操作。

每次回答时暴力删除到询问的左端点,然后改回去。

对于目前询问和上一个询问左端点不同块的情况,做法和第一类问题一样。

·

最后是这个题的代码,全开longlong结果跑了大概20s……大概是ll太慢了。你可以少开几个ll

#洛谷 P1860 新魔法药水

神奇的DP

大概是用DP预处理要预处理的内容

然后用DP预处理

最后DP背包跑答案

 

卡了我很久有必要详细讲一下

题目描述

商店里有N种药水,每种药水都有一个售价和回收价。小S攒了V元钱,还会M种魔法,可以把一些药水合成另一种药水。他一天可以使用K次魔法,问他一天最多赚多少钱?

输入输出格式

输入格式:

第一行四个数N、M、V、K

接下来N行,每行两个数,表示药水的售价和回收价。

接下来M行,每行若干个数,第一个数表示魔法的成品,第二个数是原料的种数,接下来为各种原料的编号

输出格式:

一个数,表示小S的最大利润

·

N<=60 M<=240

V<=1000

k<=30

我们先考虑这是个背包

然后很自然的只需要求每个物品的min 购买价,然后二位费用xjb转移就可以得出答案

DP求这个部分.

因为有魔法,所以设计状态dx[i][j]表示物品i在当前用了j次魔法的情况下最小的购买价,这样才能当做背包来DP

dx怎么求呢?也不好求,所以这就是卡我的地方,我一开始还以为是DFS求

 

厚颜无耻的看题解……

你需要在枚举每个魔法w的时候都dp处理出 第w个魔法所需的前x个物品 用y次魔法 可以得到的最小购买价

设计状态ori[x][y]表示这样,每次枚举了一个魔法w都要求一次ori,注意y≤枚举的魔法次数

然后DP一波ori,这个很简单,写过几道提高水平的DP就会求

然后用ori[w需要的物品总数][枚举魔法次数-1]更新dx[w产成品][枚举的魔法次数]

·

这样我们就有了dx

xjb背包即可.XXXD

BZOJ3289 Mato的文件管理

Time Limit: 40 Sec (Total)

Memory Limit: 128 MB

莫队+树状数组维护

类(jiu)似(shi)冒泡排序的过程

注意优化时间

USACO 2007MAR Face The Right Way

Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 6005 Accepted: 2777

Description

Farmer John has arranged his N (1 ≤ N ≤ 5,000) cows in a row and many of them are facing forward, like good cows. Some of them are facing backward, though, and he needs them all to face forward to make his life perfect.

Fortunately, FJ recently bought an automatic cow turning machine. Since he purchased the discount model, it must be irrevocably preset to turn K (1 ≤ K  N) cows at once, and it can only turn cows that are all standing next to each other in line. Each time the machine is used, it reverses the facing direction of a contiguous group of K cows in the line (one cannot use it on fewer than K cows, e.g., at the either end of the line of cows). Each cow remains in the same *location* as before, but ends up facing the *opposite direction*. A cow that starts out facing forward will be turned backward by the machine and vice-versa.

Because FJ must pick a single, never-changing value of K, please help him determine the minimum value of K that minimizes the number of operations required by the machine to make all the cows face forward. Also determine M, the minimum number of machine operations required to get all the cows facing forward using that value of K.

Input

Line 1: A single integer: N 
Lines 2..N+1: Line i+1 contains a single character, F or B, indicating whether cow i is facing forward or backward.

Output

Line 1: Two space-separated integers: K and M

Sample Input

Sample Output

Hint

For K = 3, the machine must be operated three times: turn cows (1,2,3), (3,4,5), and finally (5,6,7)
呐 题意就这样
然后我们考虑枚举k做一个O(n^3)显然很简单
优化?尺取法
枚举k,从左到右对背面的牛操作
考虑能够影响当前牛的操作,是当前减去(k-1)的区间
然后统计一下这个区间有多少个操作对2取模就可以得到当前判断。
这样用一个类似前缀和的东西维护就行了 见代码
O(n^2)

#洛谷P1058 立体图

非常标准的一道思考题。

题目描述

小渊是个聪明的孩子,他经常会给周围的小朋友们将写自己认为有趣的内容。最近,他准备给小朋友们讲解立体图,请你帮他画出立体图。

小渊有一块面积为m*n的矩形区域,上面有m*n个边长为1的格子,每个格子上堆了一些同样大小的积木(积木的长宽高都是1),小渊想请你打印出这些格子的立体图。我们定义每个积木为如下格式,并且不会做任何翻转旋转,只会严格以这一种形式摆放:

每个顶点用1个加号’+’表示,长用3个”-”表示,宽用1个”/”,高用两个”|”表示。字符’+’,”-”,”/”,”|”的ASCII码分别为43,45,47,124。字符’.’(ASCII码46)需要作为背景输出,即立体图里的空白部分需要用’.’来代替。立体图的画法如下面的规则:

若两块积木左右相邻,图示为:

若两块积木上下相邻,图示为:

若两块积木前后相邻,图示为:

立体图中,定义位于第(m,1)的格子(即第m行第1列的格子)上面自底向上的第一块积木(即最下面的一块积木)的左下角顶点为整张图最左下角的点。

这题不需要一定立体几何的分析。

我们都知道透视是什么。透视让你通过二维屏幕yy出三维空间 什么xjb玩意儿。

也就是说,你如果从右前上方看的话(题目方向),右面的(离你近的)会盖住左面的(离你远的),同理高的盖住低的,前面的盖住后面的。

那么可以遵循自底向上,自后向前,自左向右的绘画准则,在虚拟画布mapx[1010][1010]上面打表(数据范围我乱写的)

1.注意横坐标上限只与从顶上看的矩阵大小有关,但是纵坐标上限还与高度以及从顶上看的矩阵长度(矩阵纵坐标最大值)有关

社会我C哥,人狠话不多,不管那么多。

直接倒着填,右下角基准点,初始化为’.’ , 最后统计上限。

将每个block右下角作为basic point基准点,推一下公式。具体怎么来的,不作解释。

然后打个表。打表还不简单。