USACO 2019 US Open银组Silver竞赛真题(中文)

  • 格式:pdf
  • 大小:230.21 KB
  • 文档页数:6

USACO2019US O PEN C ONTEST,S ILVER
P ROBLEM1.L EFT O UT
Farmer John正在尝试给他的牛群拍照。

根据以往的经验,他知道这一工作往往结果不怎么样。

这一次,Farmer John购买了一台昂贵的无人机,想要拍一张航拍照。

为了使照片尽可能好看,他想让他的奶牛们在拍照时都朝向同一个方向。

奶牛们现在在一块有围栏的草地上排列成$N\times N$($2\leq N\leq1000$)的方阵,例如:
RLR
RRL
LLR
这里,字符'R'表示一头朝右的奶牛,字符'L'表示一头朝左的奶牛。

由于奶牛们都挤在一起,Farmer John没办法走到某一头奶牛面前让她调转方向。

他能做的只有对着某一行或某一列的奶牛喊叫让她们调转方向,使得被叫到的这一行或列内的所有L变为R,R变为L。

Farmer John可以对任意多的行或列发号施令,也可以对同一行或列多次发令。

就如同Farmer John想象的,他发现他不可能让他的奶牛们都朝向同一个方向。

他最多能做的是让所有奶牛中除了一头之外都朝向相同的方向。

请找出这样的一头奶牛。

输入格式(文件名:leftout.in):
输入的第一行包含$N$。

以下$N$行描述了奶牛方阵的第$1\ldots N$行,每行包含一个长度为$N$的字符串。

输出格式(文件名:leftout.out):
输出一头奶牛的行列坐标,满足这头奶牛被调转方向的话,Farmer John就可以使他的所有奶牛都朝向同一个方向。

如果不存在这样的奶牛,输出-1。

如果存在多头这样的奶牛,输出其中行坐标最小的,如果多头这样的奶牛具有相同的行坐标,输出其中列坐标最小的。

输入样例:
3
RLR
RRL
LLR
输出样例:
11
在这个例子中,位于第1行第1列(左上角)的奶牛是那头令人讨厌的奶牛,因为Farmer John 可以喊叫第2行和第3列来让所有奶牛都面向左侧,只有这一头奶牛面向右侧。

供题:Brian Dean
USACO2019US O PEN C ONTEST,S ILVER
P ROBLEM2.C OW S TEEPLECHASE II
在过去,Farmer John曾经构思了许多新式奶牛运动项目的点子,其中就包括奶牛障碍赛,是奶牛们在赛道上跑越障碍栏架的竞速项目。

他之前对推广这项运动做出的努力结果喜忧参半,所以他希望在他的农场上建造一个更大的奶牛障碍赛的场地,试着让这项运动更加普及。

Farmer John为新场地精心设计了$N$个障碍栏架,编号为$1\ldots N$($2\leq N\leq 10^5$),每一个栏架都可以用这一场地的二维地图中的一条线段来表示。

这些线段本应两两不相交,包括端点位置。

不幸的是,Farmer John在绘制场地地图的时候不够仔细,现在发现线段之间出现了交点。

然而,他同时注意到只要移除一条线段,这张地图就可以恢复到预期没有相交线段的状态(包括端点位置)。

请求出Farmer John为了恢复没有线段相交这一属性所需要从他的计划中删去的一条线段。

如果有多条线段移除后均可满足条件,请输出在输入中出现最早的线段的序号。

输入格式(文件名:cowjump.in):
输入的第一行包含$N$。

余下$N$行每行用四个整数$x_1$$y_1$$x_2$$y_2$表示一条线段,均为至多$10^9$的非负整数。

这条线段的端点为$(x_1,y_1)$和$(x_2,y_2)$。

所有线段的端点各不相同。

输出格式(文件名:cowjump.out):
输出在输入中出现最早的移除之后可以使得余下线段各不相交的线段序号。

输入样例:
4
2161
4015
5655
2713
输出样例:
2
注意:由于线段端点坐标数值的大小,在这个问题中你可能需要考虑整数类型溢出的情况。

供题:Brian Dean
USACO2019US O PEN C ONTEST,S ILVER
P ROBLEM3.F ENCE P LANNING
Farmer John的$N$头奶牛,编号为$1\ldots N$($2\leq N\leq10^5$),拥有一种围绕“哞网”,一些仅在组内互相交流却不与其他组进行交流的奶牛小组,组成的复杂的社交网络。

每头奶牛位于农场的二维地图上的不同位置$(x,y)$,并且我们知道有$M$对奶牛$(1\leq M< 10^5)$会相互哞叫。

两头相互哞叫的奶牛属于同一哞网。

为了升级他的农场,Farmer John想要建造一个四边与$x$轴和$y$轴平行的长方形围栏。

Farmer John想要使得至少一个哞网完全被围栏所包围(在长方形边界上的奶牛计为被包围的)。

请帮助Farmer John求出满足他的要求的围栏的最小可能周长。

有可能出现这一围栏宽为0或高为0的情况。

输入格式(文件名:fenceplan.in):
输入的第一行包含$N$和$M$。

以下$N$行每行包含一头奶牛的$x$坐标和$y$坐标(至多$10^8$的非负整数)。

以下$M$行每行包含两个整数$a$和$b$,表示奶牛$a$和$b$之间有哞叫关系。

每头奶牛都至少存在一个哞叫关系,并且输入中不会出现重复的哞叫关系。

输出格式(文件名:fenceplan.out):
输出满足Farmer John的要求的围栏的最小周长。

输入样例:
75
05
105
50
510
67
86
84
12
23
34
56
76
输出样例:
10
供题:Brian Dean。