Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

这里又是一次NOIPACM模拟赛(包括 整理绳子 洛谷P3068派对邀请函 洛谷P2984给巧克力 bzoj 3387: [Usaco2004 Dec]Fence Obstacle Course栅栏行动)

第一题——整理绳子

题目链接

没找到qwq

题目描述

勤劳的贝西正在晒衣服。她把 N 根绳子系在了两根平行的木杆之间,每根木杆上有 N 个绳头。
由于贝西粗心大意,挂绳子的时候没有注意位置,所以一些绳子产生了交叉,布局非常混乱。如果从左向右看,第一根木杆上第 i 个绳头是第 A i 根绳子的,第二根木杆上第 j 个绳头是第 B j 根绳子的。
贝西希望把所有的绳子恢复成不交叉的状态。她只能进行一种交换操作,就是把某一根杆子上相邻的两个绳头交换位置。请问她需要做几步交换操作才能让所有的绳子没有交叉?

输入

• 第一行:单个整数 N,1 ≤ N ≤ 1000
• 第二行到第 N + 1 行:第 i + 1 行有两个整数 A i 和 B i ,1 ≤ A i ,B i ≤ N

输出

• 单个整数:表示最少做几次交换才能让所有绳子平行

样例输入

4
4 1
2 3
1 4
3 2

样例输出

4

想说的话

这道题真是容易啊

题解

针对右侧的绳子顺序编号
映射到左面这种编号 然后逆序对

代码

第二题—— 洛谷P3068派对邀请函

题目链接

传送门

想说的话

这个题一开始我在想各种数据结构
我怕是数据结构中毒了
后来一想
我只需要暴力模拟一下下就好了
queue加上set
先建边 把牛跟集团建边 然后针对每个集团开一个set
用一个iterator扫一遍 只剩一个的集合就推进队列
之后就搞定了

题解

说完了......

代码

第三题——洛谷P2984给巧克力

题目链接

传送门

想说的话

这个题我做起来比第一题还轻松
直接dij+heap或者spfa超休闲的

题解

这个题我们针对1这个点跑最短路
然后我们直接把两个点到1的距离加起来

代码

第四题——bzoj 3387: [Usaco2004 Dec]Fence Obstacle Course栅栏行动

题目链接

传送门

想说的话

这个题我充分利用了acm赛制
想了好久
想出来两个思路
但是我只写出来一种
我真是菜

题解

我们用线段树来维护线段 维护左右端点
然后我们用dp从下往上转移状态
或者是Segtree维护之后
连图跑最短路
但是我没写出来

代码

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏