反 向 登 顶
9.15比赛
T1
Description
传说,数千年前圣帕特里克消灭了哞尔兰所有的蛇。然而,蛇们现在卷土重来了!圣帕特里克 节是在每年的$ 3 月 17 日$,所以 $Bessie$ 要用彻底清除哞尔兰所有的蛇来纪念圣帕特里克。$ Bessie$ 装备了一个捕网,用来捕捉 $N $组排成一行的蛇$(1≤N≤400)$。 $Bessie$ 必须按照这些组在 这一行中出现的顺序捕捉每一组的所有蛇。每当 $Bessie$ 抓完一组蛇之后,她就会将蛇放在笼子里, 然后带着空的捕网开始捕捉下一组。 一个大小为 $s $的捕网意味着$ Bessie$ 可以抓住任意包含 $g$ 条的一组蛇,其中 $g≤s$。然而,每当 $Bessie $用大小为 $s$ 的捕网抓住了一组$ g $条蛇,就意味着浪费了$ s−g $的空间。$Bessie$ 可以任意设定捕网的初始大小,并且她可以改变$ K $次捕网大小$(1≤K<N)$。 请告诉 $Bessie$ 她捕捉完所有组的蛇之后可以达到的总浪费空间的最小值。
Input
输入的第一行包含 $N$ 和 $K$。第二行包含 N 个整数 $a1,…,aN$,其中 $ai$$(0≤ai≤10^6)$为第$ i $组蛇 的数量。
Output
输出一个整数,为 Bessie 抓住所有蛇的总浪费空间的最小值。
思路
1.方程是$F[i][j]$表示捕蛇到$i$组用了$j$次改变机会。
2.每次改变一定是取区间内最多蛇的个数的,这一点是个人都想得到。
3.思路很明确了,一个分割区间$DP$+预处理也好数据结构也好大力维护区间最值。
然后千万不要像我一样$sb$地把$int$初始化为$127$,会爆的,用$63$就好了。
代码
1 |
|
Source
USACO 2019 US Open Contest, Gold Problem 1. Snakes
T2
Description
$Farmer John$ 想要将他的编号为 $1…N$ 的 $N$ 头奶牛$(N≤7500)$分为非空的 $K$ 组$(2≤K≤N)$,使 得任意两头来自不同组的奶牛都需要走一定的距离才能相遇。奶牛 $x$ 和奶牛$ y$$(其中 1≤x<y≤N)$ 愿意为了见面走$(2019201913x+2019201949y) \mod 2019201997 $英里。 给定一个将$ N $头奶牛分为$ K $个非空小组的分组方案,令$ M $为任意两头来自不同组的奶牛愿意 为了见面行走的英里数的最小值。为了测试奶牛们相互之间的忠诚度,$Farmer John $想要将 $N $头奶 牛以最佳的方式分为$ K$ 组,使得 $M$ 尽可能大。
Input
输入仅有一行,包含 $N$ 和 $K$,用空格分隔。
Output
输出最优的 $M$。
思路
考场里想法是把所有的路全挑出来,然后从小到大排序,二分断点$x$,前面$n-x$条放一组$(很显然)$,后面只要点不在前面集合内就$cnt++$,$cnt>=k$就返回$1$,否则返回$0$。
然而$sort$超时了$(噔噔咚)$,$TLE 58pts$。
考完后看了题解才发现,只要把前$n-k$条放一组,后$k$条放一组就是最优的了$(好显然啊,哭了)$。
所以$TLE$代码如下
1 |
|
满分代码如下
1 |
|
然后你甚至可以打表找规律,$O(1)$出奇迹!$LYP$%%%
1 |
|
Source
USACO 2019 US Open Contest, Gold Problem 2. I Would Walk 500 Miles
T3
Description Bessie 喜欢观光,而今天她正在寻找景色优美的山谷。 她感兴趣的是一个 N×N 的方阵,其中每个格子都有一个高度。所有在此正方形方阵之外的格 子的高度可以被看作是无限大。 山谷指的是一块连续、不含洞的一块区域,并且每个相邻的包围该区域的格子都高于这块区域 中的所有格子。 更形式化地说: 一组格子被称作是“沿边相邻的”,如果可以从其中任意一个格子出发,经过一些沿上、下、左、 右方向的移动,到达其中所有其他格子。 一组格子被称作是“沿点相邻的”,如果可以从其中任意一个格子出发,经过一些沿上、下、左、 右、对角线方向的移动,到达其中所有其他格子。 一个“区域”指的是一组非空并且沿边相邻的格子。 一个区域被称作是“有洞的”,如果这个区域的补集(包括在 $N \times N$ 方阵之外的无限 高格子)不是沿点相邻的。 区域的“边界”指的是所有与该区域内的某个格子正交相邻(上、下、左、右),但本身不在该区 域内的格子。 一个“山谷”指的是某个非有洞区域,满足区域内的任意格子的高度低于该区域边界上任意格子 的高度。 Bessie 的目标是求出所有山谷的大小之和。
一些例子
这是一个区域:
oo.
ooo
..o
这不是一个区域(中间的格子和右下角的格子不沿边相邻):
oo.
oo.
..o
这是一个非有洞区域:
ooo
o..
o..
这是一个有洞的区域(“甜甜圈”中间的格子与区域外的格子不沿点相邻):
ooo
o.o
ooo
这是另一个非有洞区域(中间的格子与右下角的格子沿点相邻):
ooo
o.o
oo.
Input
输入的第一行包含 $N$,其中 $1≤N≤750$ 。 以下 $N$ 行每行包含 $N$ 个整数,为方阵每个格子的高度。所有高度 h 满足 $1≤h≤10^6$。所有 高度均为不同的整数。
Output
输出一个整数,为所有山谷的大小之和
思路
打不来,黑题,告辞。
要看的可以去这里看。