2018-team11-021

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(summer4.png)]]

== 总结 ==

=== zb ===

今天我又当了一天老板，感觉很开心

想到了一个题就可以丢给周哥去写

但是这个吊人听不懂我抽象的题意，还得我亲自出马

大体上打的没毛病，但是签到题做的太慢，导致难题没有时间去开

=== zyh ===

依旧是给人打工的一天，感觉很开心（

J爆int，幸亏一眼就发现了，应该在交之前就查查的

听了半天I没听懂，等孙哥写完才明白（然而他线段树空间开小气坏我了

=== sj ===


== 题解 ==

A. Three Servers

题意：给三个服务器、n(400)个任务，每个任务有负载t(30)，求如何分配任务使负载最大值与最小值差最小，输出最小差值与 方案

题解：(bitset)

G. Maximum Product

题意：给区间[L,R]，求区间内的一个数，数位乘积最大

题解：枚举R的后i位添9，前面的数-1，判断是否在区间内，符合条件计算结果更新答案

H. Biathlon 2.0

题意：给若干(x,y)、(a,b)，求ax+by最小值

题解：点集求下凸壳，直线按斜率排序

I. Archaeological Research 

题意：给n个位置，每个位置有c个限制x_i,j，第j个限制表示a[x_i,j]这个数在[i+1,x-1]区间内不能出现，构造字典序最小的情况

题解：设b_i为限制i最早出现的位置，l_i为目前i最后出现的位置，对l_i建线段树，从前到后枚举位置，每次到线段树里找最小的i，l_i<b_i

J. Sockets

题意：给出n个插排和m个电器，每个插排有插口数量，每个电器有距离限制，求最大接入电器数量

题解：插排按照插口数量、电器按照距离限制从大到小排序，二分电器数量，check按照距离限制从小到大扫，尽可能插插排，电器不够插了返回false

总结

zb

今天我又当了一天老板，感觉很开心

想到了一个题就可以丢给周哥去写

但是这个吊人听不懂我抽象的题意，还得我亲自出马

大体上打的没毛病，但是签到题做的太慢，导致难题没有时间去开

zyh

依旧是给人打工的一天，感觉很开心（

J爆int，幸亏一眼就发现了，应该在交之前就查查的

听了半天I没听懂，等孙哥写完才明白（然而他线段树空间开小气坏我了

sj

题解

A. Three Servers

题意：给三个服务器、n(400)个任务，每个任务有负载t(30)，求如何分配任务使负载最大值与最小值差最小，输出最小差值与 方案

题解：(bitset)

G. Maximum Product

题意：给区间[L,R]，求区间内的一个数，数位乘积最大

题解：枚举R的后i位添9，前面的数-1，判断是否在区间内，符合条件计算结果更新答案

H. Biathlon 2.0

题意：给若干(x,y)、(a,b)，求ax+by最小值

题解：点集求下凸壳，直线按斜率排序

I. Archaeological Research

题意：给n个位置，每个位置有c个限制x_i,j，第j个限制表示a[x_i,j]这个数在[i+1,x-1]区间内不能出现，构造字典序最小的情况

题解：设b_i为限制i最早出现的位置，l_i为目前i最后出现的位置，对l_i建线段树，从前到后枚举位置，每次到线段树里找最小的i，l_i

J. Sockets

题意：给出n个插排和m个电器，每个插排有插口数量，每个电器有距离限制，求最大接入电器数量

题解：插排按照插口数量、电器按照距离限制从大到小排序，二分电器数量，check按照距离限制从小到大扫，尽可能插插排，电器不够插了返回false

附加文件