2018-team11-002

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 [[Image(hw4.png)]]
== 超简短总结 ==
虽然成绩不是很好，但是也没有什么遗憾，能做的都做出来，剩下的也都是不会做的题，尽力补吧。
== 超简易题解 ==
A.Assigning Workstations
做法：优先队列随便维护一下。
C.Cleaning Pipes
题意：有若干条线段，相交的线段必须选且只能选一个。
做法：线段求交，然后跑二分图匹配即可。
D.Debugging
题意：给定n行代码，插入print语句和运行都要一定的时间，求找出bug的最短时间。
做法：dp，只考虑有意义的转移，即可优化到O(nlogn)
E.Elementary Math
题意：给出n个数对，添加加减乘号使得结果各不相同。
做法：网络流建图随便跑一下。
G.Guessing Camels
题意：给定三个排列，求有多少个公共有序对。
做法：三个的序列不好处理，考虑俩俩之间求解，定义俩个序列的逆为俩个序列中相对位置不同的数对，那么一个公共有序对不会产生逆，反之则会产生俩个逆，那么问题转化为求逆的个数，直接重排序求逆序对即可。
I.Identifying Map Tiles
题意：模拟题
J.Jumbled Communication
题意：签到题
K.Kitchen Combinatorics
题意：随便模拟一下。
做法：乘的时候可能会爆long long，稍微处理一下即可。

超简短总结

虽然成绩不是很好，但是也没有什么遗憾，能做的都做出来，剩下的也都是不会做的题，尽力补吧。

超简易题解

A.Assigning Workstations

做法：优先队列随便维护一下。

C.Cleaning Pipes

题意：有若干条线段，相交的线段必须选且只能选一个。

做法：线段求交，然后跑二分图匹配即可。

D.Debugging

题意：给定n行代码，插入print语句和运行都要一定的时间，求找出bug的最短时间。

做法：dp，只考虑有意义的转移，即可优化到O(nlogn)

E.Elementary Math

题意：给出n个数对，添加加减乘号使得结果各不相同。

做法：网络流建图随便跑一下。

G.Guessing Camels

题意：给定三个排列，求有多少个公共有序对。

做法：三个的序列不好处理，考虑俩俩之间求解，定义俩个序列的逆为俩个序列中相对位置不同的数对，那么一个公共有序对不会产生逆，反之则会产生俩个逆，那么问题转化为求逆的个数，直接重排序求逆序对即可。

I.Identifying Map Tiles

题意：模拟题

J.Jumbled Communication

题意：签到题

K.Kitchen Combinatorics

题意：随便模拟一下。

做法：乘的时候可能会爆long long，稍微处理一下即可。

附加文件