2017 Multi-University Training Contest 10 solutions BY 朝鲜

1001

1

1002

2

1003

3

1004

4

1005

5

1006

6

1007

7

1008

In this problem, we must remove edges as many as possible and assign each of the K monkeys to the vertices so that all the monkeys are directly connected to at least one another monkey by the remaining edges. So, we must work out the maximum bipartite matching of all the vertices first. Let’s denote the size of maximum bipartite matching S. Then, we can choose T= min(K / 2, S) pairs of matched vertices and assign 2 * T monkeys to that vertices and assign all the other monkeys to the remaining vertices which are directly connected to already occupied vertices. Hence, the optimal answer is T + (K – 2 * T) = K - T.

1009

The number of points in the left side of the line is not changed. (we assume this number is p.) We call the points are P1, P2, … Pn and the line is L and one line vertical with L is L1. If we project the points P1, P2, … Pn to the line L1, then we can get n points Q1, Q2, … Qn on the line L1. (some points can be same.) We can sort Q1, Q2, … Qn from left to right and we can get n points R1, R2, … Rn. The point from P1, P2, … Pn corresponding with Rp is the rotating centre. So you must find this points array R1, R2, … Rn every time. Initially you can get this array sorting all points by x coordinate, then every time some pairs of points can be swapped, so you must find and swap these pairs. After the line rotates 2π, then the rotating centres array will be repeated, so you may find the rotating centres array until the line rotates 2π. Every pair of points will swap exactly two times so the time complexity is O(n*n).

1010

In this problem, we must assign each task in optimal way so that minimize the number of working machines first and when we use minimum number of machines, also minimize the total working time of all machines. So, we can use greedy method to solve this problem. First, we must sort all the tasks in increasing order of their starting time. Then, selecting the tasks in that order, we must choose the machine which is available to assign current task and most recently finished its working, and assign current task to that machine. When there isn’t such machine, we must assign current task to a new machine. By doing so, we can minimize both the number of working machine and total working time.

1011

11  

2017 Multi-University Training Contest 9 solutions BY 北京邮电大学

1001

考虑dp,f(x)表示从点x开始向下走得到的最大的点权和,查询直接从x开始向上走更新答案即可。
考虑快速算 f(x) 对于子树内没有被修改过的点的 f(x) 可以快速分类讨论算出,而不满足本条件的点只有 O(mlogm) 个,在hash上dp即可。

1002


由于没有修改操作,一个显然的想法是离线处理所有问题
将询问拆成1-x,1-y,1-LCA(x,y),则处理的问题转化为从根到节点的链上的问题。
解决这个问题,我们可以在dfs时向treap插入当前的数,在退出时删除这个数,并且每次维护在该点上的答案。
当然也可以将所有的查询和点权排序,用树链剖分做这个题,在线段树上面插入就ok。

1003


平面上有一些点和一些线段,保证这些线段互不相交,点不在线段上。
每次问从一个点能看到多少个点。一个点能看到另一点当且仅当这两点连线的线段不和任何一个已知的线段相交。(这里的相交均指非规范相交)
每次以询问点为极点极角排序。线段两端点拆成两个事件,一次出现,一次消失。对于枚举的某一个角度,能否看见当前角度的点仅取决于当前角度上离极点最近的线段,由于保证线段不相交,一条线段在插入时和还存在线段的相对位置是不会改变的,所以可以用set维护,每次先处理当前角度上所有的点是否被线段遮挡就可以了。复杂度是O(Q(N + M)log(N + M))。

1004


由于LsF一开始不再镜子上,按题面模拟即可。
由于反射率<=0.9 0.9^100<1e-4,所以反射次数不会超过100次。
每次暴力判断和哪个镜子相交,以及有没有在镜子焦点上。

1005


缩点为DAG,则如果在拓扑序中出现了有两个及以上入度为0的点则不合法

1006


类比cf 835E,枚举二进制位按照标号当前位为1 和当前位为0分为两个集合,每次求解两个集合之间的最短路即可覆盖到所有的点对。时间复杂度20*dijstla时间

1007 


题意:某国国防部知道地图上有$n$个点有导弹发射点。国防部想在地图上的某一个点建造一个防御导弹发射基地,使得每当有地方发射导弹时,都能尽快将那枚导弹击落,即被击落时间最长的这个时间最短。当然,我们知道每个点发射的导弹的速度和方向,且当一枚导弹发射的时候,国防部可以在它发射之后的任意时间发射防御导弹。为了简化题目,我们将地图简化为二维平面,且最后只要输出那个最长时间即可。
题解:考虑二分最长时间$t$,对于这个时间我们可以知道每颗导弹所能到达的最远位置。对于这些最远位置,我们可以以它们为圆心,作$n$个半径为$t*V$的圆,如果这$n$个圆有公共部分,则这个时间我们认为是可行的,否则不可行。那么这显然就是一个圆的面积交问题。
考虑这$n$个圆如果有公共面积,那么围城这个公共面积的边的定点一定是某(至少)两个圆所形成的交点。那么我们暴力枚举两个圆的交点,判断点到任意一个圆的圆心的距离是否会超过半径,如果都不超过,则一定存在公共面积。复杂度$O(n^3)$。

1008


将b数组排序,取出最小的两项作为\(a_1,a_2\),删除\(a_1,a_2,a_1+a_2\),再取出最小项作为\(a_3\),再删除\(a_3,a_1+a_3,a_2+a_3\),再取出最小项作为\(a_4\),依次列推。

1009

当$K$大于$320000$时,显然至多只会有一个满足条件的数字
当$K$小于$320000$时,首先可以将原问题转化为1~n之间满足条件的数字之和
考虑dp,$f(i,j)$表示对于$1-i$的数字用前$j$个质数筛去剩余的数字的和 $f(i,j) = f(i,j-1) - prime(j)f(i/prime(j),j-1)$

1010


定义dp[i][j][k],k = 0,表示A串从0~i 的子串A[0,i],能否匹配B串从0~j的子串B[0,j];k = 1,表示A[0,i] + A[i]能否匹配B[0,j]。
转移时考虑几种特殊情况,"a*" 可以匹配 "" ,"a","aa"...,".*"可以匹配"","a","b","aa","bb"...,注意 ".*" 不能匹配 "ab"这种串。