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$就好了。

代码

#include<bits/stdc++.h>
using namespace std;
int n,maxf[405][25],a[405],K,f[405][405],Sum[405];
void rmq_max(){
    for(int i=1;i<=n;i++) maxf[i][0]=a[i];
    for(int j=1;(1<<j)<=n;j++)
      for(int i=1;i+(1<<j)-1<=n;i++)
        maxf[i][j]=max(maxf[i][j-1],maxf[i+(1<<(j-1))][j-1]);
} 
int answer_max(int l,int r){
    int k=trunc(log2(r-l+1));
    return max(maxf[l][k],maxf[r-(1<<k)+1][k]);
}
inline int read()
{
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
int main()
{
    freopen("pa.in","r",stdin);
    freopen("pa.out","w",stdout);
    n=read();K=read();K++;
    for(int i=1;i<=n;i++) a[i]=read(),Sum[i]=Sum[i-1]+a[i];
    rmq_max();
    memset(f,63,sizeof(f));
    f[0][0]=0;
    for (int i=1;i<=n;i++)
    {
        for (int j=0;j<=i-1;j++)
        {
            for (int k=1;k<=K;k++)
            {
                f[i][k]=min(f[i][k],f[j][k-1]+answer_max(j+1,i)*(i-j)-(Sum[i]-Sum[j]));
            }
        }
    }
    int Min=2e9;
    for (int i=1;i<=K;i++) Min=min(Min,f[n][i]);
    cout<<Min<<endl;
    return 0;
}

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$代码如下

#include<bits/stdc++.h>
#define Maxn 7505 
using namespace std;
struct edge{int a,b;long long c;}e[Maxn*Maxn];
bool vis[Maxn*Maxn];
int N,K,cnt=0;
bool cmp(edge x,edge y){return x.c<y.c;}
bool check(int x)
{
    int ans=0;
    if (x>1) ans++;
    memset(vis,0,sizeof(vis));
    for (int i=1;i<=x-1;i++) vis[e[i].a]=1,vis[e[i].b]=1;
    for (int i=x;i<=cnt;i++) 
    {
        if (!vis[e[i].a]) ans++,vis[e[i].a]=1;
        if (!vis[e[i].b]) ans++,vis[e[i].b]=1;
    }
    if (ans>=K) return 1;
    return 0;
}
int main()
{
    freopen("pb.in","r",stdin);
    freopen("pb.out","w",stdout);
    scanf("%d%d",&N,&K);
    for (int i=1;i<=N-1;i++)
    {
        for (int j=i+1;j<=N;j++)
        {
            long long x=(1LL*2019201913*i+1LL*2019201949*j)%2019201997;
            e[++cnt].a=i,e[cnt].b=j,e[cnt].c=x;
        }
    }
    sort(e+1,e+cnt+1,cmp);
    //for (int i=1;i<=cnt;i++) cout<<e[i].c<<endl;
    int l=1,r=cnt;
    while (l<=r)
    {
        int mid=l+r>>1;
        if (check(mid)) l=mid+1;
        else r=mid-1;
    } 
    cout<<e[r].c<<endl;
    return 0;
}  

满分代码如下

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL p1=2019201913,p2=2019201949,TT=2019201997;
int n,k;LL f[7505];
int main(){
    freopen("pb.in","r",stdin);
    freopen("pb.out","w",stdout); 
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++) f[i]=TT;
    for (int i=1;i<=n;i++)
    for (int j=i+1;j<=n;j++){
        LL sum=(p1*i+p2*j)%TT;
        f[i]=min(f[i],sum);
        f[j]=min(f[j],sum);
    }
    sort(f+1,f+n+1);
    printf("%lld\n",f[n-(k-2)]);
    return 0;
}

然后你甚至可以打表找规律，$O(1)$出奇迹！$LYP$%%%

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int red=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') red=red*10+ch-48,ch=getchar();
    return red*f;
}
typedef long long LL;
const int maxn=7505;
const LL mod=2019201997,first=2019201769;
int n,m,k;
LL f[maxn][maxn];
int main(){
    freopen("pb.in","r",stdin);
    freopen("pb.out","w",stdout);   
    n=read()-3,m=read()-2;
    printf("%lld\n",(first-n*48-m*84+mod)%mod);
//    printf("%lld\n",f[n][m]);
    return 0;
}//LYPjulao%%%

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

输出一个整数，为所有山谷的大小之和

思路

打不来，黑题，告辞。

要看的可以去这里看。