2019.9.15 线下比赛

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

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

思路

打不来,黑题,告辞。

要看的可以去这里看。

暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇