BZOJ1016 | JSOI2008 最小生成树计数

题面不放

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

其实暴搜可过

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

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

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

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

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

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

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

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

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

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

 

点击图片跳转原题

 

 

 

 

 

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

 

BZOJ1876 | SDOI2009 SuperGCD

更相减损术+高精度板子

压位1000ms

注意对偶数优化,一奇一偶可以÷2

两个偶数同时÷2再乘回去可以优化减法次数

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基准点,推一下公式。具体怎么来的,不作解释。

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

IOI1998 Starry Night 夜空繁星

BFS,超级麻烦

推荐A这道模拟方块转换

高高的星空,簇簇闪耀的群星形态万千。一个星座(cluster)是一群连通的星组成的非空连通星系,这里的连通是指水平,垂直或者对角相邻的两个星星。一个星座不能是另一个更大星座的一部分, 星座可以相似(similar)。如果两个星座有相同的形状,而且包括相同数目的星体,那么不管其方向性如何,就算相似。一般而言,星座可能的方向有八个,如图所示。(图片搬运自Luogu Online Judge)

 

 

懒癌了,我就贴上来吧……我用了一个特殊的表来判断是不是相似

详见代码