Lyz's Blog

Never Give Up

发表于 分类于 ， 阅读次数： 0 本文字数： 2.4k 阅读时长 ≈ 2 分钟

Description

题目来源
bzoj3732

Analysis

这题给的输入是一个无向连通图，说明图中会有环和一些树枝。对于一个询问在环上的两个点，有两条可以联通的道路。
一条中的边权最大值是整个环的最大值（舍弃），
另一条的边权最大值是整个环的次大值（需要）。
所以只有次大值才是我们想要的！因此，我们想到了最小生成树，将这些环中的最大边权值所属的边删掉。
最小生成树的求法就是，先让边权从小到大排序，然后依次添加并用并查集维护即可。（Kruskal 算法）

阅读全文 »

发表于 分类于 ， 阅读次数： 0 本文字数： 3.6k 阅读时长 ≈ 3 分钟

Description

用 1×2 的 砖头铺满 N*M 的区域，不能有重叠，一共有多少种方案？如下图所示：
方式

Data Constraint

20% 的数据满足 1<=N,M<=6
50% 的数据满足 1<=N<=100,1<=M<=11
另外 50% 的数据满足 1<=N<=10^200,1<=M<=5

阅读全文 »

发表于 分类于 ， 阅读次数： 0 本文字数： 3k 阅读时长 ≈ 3 分钟

Description

刚拿到驾照的 KJ 总喜欢开着车到处兜风，玩完了再把车停到阿 Q 的停车场里，虽然她对自己停车的水平很有信心，但她还是不放心其他人的停车水平，尤其是 Kelukin。于是，她每次都把自己的爱车停在距离其它车最远的一个车位。KJ 觉得自己这样的策略非常科学，于是她开始想：在一个停车场中有一排车位，从左到右编号为 1 到 n，初始时全部是空的。有若干汽车，进出停车场共 m 次。对于每辆进入停车场的汽车，会选择与其它车距离最小值最大的一个车位，若有多个符合条件，选择最左边一个。KJ 想着想着就睡着了，在她一旁的 Kelukin 想帮她完成这个心愿，但是他又非常的懒，不愿意自己动手，于是就把这个问题就留给了你：在 KJ 理想的阿 Q 的停车场中，给你车辆进出的操作序列，依次输出每辆车的车位编号。

Input

第一行，两个整数 n 和 m，表示停车场大小和操作数；

阅读全文 »
0%