【纪中受难记】——C2Day4：水题大赏

三道水题，但还有水人。

40/100/100

---

3810. 【USACO2014 3月】Watering the Fields (Standard IO)

Time Limits: 1000 ms  Memory Limits: 262144 KB  Detailed Limits  

Goto ProblemSet

Description

由于缺少雨水，FJ 想要建造一个在他的N（1 N 2000）块田之间送水的灌溉系统。
每块田地i 由一个二维平面上独一无二的点(xi; yi) 描述，这里有0 <= xi; yi <=1000。在两块田地i 和j 之间建造水管的费用等于它们之间欧几里得距离的平方：(xi-xj)^2+(yi-yj)^2
FJ 希望建造一个连接所有田地并且花费最小的管道系统——满足从任意田地出发，水可以通过一系列管道到达另外的任意一块田地。
不幸的是，帮助FJ 安装灌溉系统的承包商拒绝安装任何花费（欧几里得长度平方）小于C（1 C 1; 000; 000）的管道。
请帮助FJ 计算他最少需要为连接他所有田地的管道网络支付多少钱。
 

 

Input

第一行：整数N 和C。
第2 至N + 1 行：第i 行包含整数xi 和yi。

Output

输出单独一行一个整数——连接所有田地的管道网络的最小费用，或者当满足条件的网络不可能建造时输出-1。

 

Sample Input

3 11
0 2
5 0
4 3

Sample Output

46
样例解释：
有三块田地，分别在坐标(0; 2); (5; 0) 和(4; 3)。承包商将只会安装费用不少于11 的管道。
FJ 不能建造连接分别在(4; 3) 和(5; 0) 的田地的管道，因为它的费用只有10。
故他只得建造连接(0; 2) 和(5; 0) 且费用为29 的管道，以及连接(0; 2) 和(4; 3)且费用为17 的管道。
 

 

Data Constraint

对于20% 的数据，有N <= 10。
对于30% 的数据，有N <= 100。
对于40% 的数据，有N <= 200。

最小生成树板题，至于为什么没AC，因为数组开小了。。。

给出两种写法，稠密图所以最好用prim。

Kruskal：

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
typedef long long ll;
const int N=201000;
int n,c,cnt;
int x[N],y[N],fa[N];
ll ans;
struct node{
    int x,y,len;
}e[N<<4];
bool cmp(node t1,node t2){
    return t1.len<t2.len;
}
int findf(int x){
    return fa[x]==x?x:fa[x]=findf(fa[x]);
}
int main(){
    n=read();c=read();
    for(int i=1;i<=n;i++){
        x[i]=read();y[i]=read();
        fa[i]=i;
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            ll len=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
            if(len<c) continue;
            e[++cnt]=(node){i,j,len};
        }
    }
    sort(e+1,e+cnt+1,cmp);
    for(int i=1;i<=cnt;i++){
        if(findf(e[i].x)!=findf(e[i].y)){
            ans+=e[i].len;
            fa[findf(e[i].x)]=e[i].y;
        }
    }
    int t=findf(1);
    for(int i=2;i<=n;i++){
        if(findf(i)!=t){
            printf("-1");
            return 0;
        }
    }
    printf("%lld",ans);
    return 0;
}

Prim：

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
typedef long long ll;
const int M=2010;
const ll inf=1e16;
int n,c,cnt,tot,now=1;
int x[M],y[M],vis[M],head[M*M];
ll dis[M];
struct edge{
    int to,next;
    ll w;
}e[M*M];
void addedge(int from,int to,ll w){
    e[++cnt]=(edge){to,head[from],w};
    head[from]=cnt;
}
ll ans;
void prim(){
    for(int i=2;i<=n;i++) dis[i]=inf;
    for(int i=head[1];i;i=e[i].next){
        ll w=e[i].w;
        int v=e[i].to;
        dis[v]=min(w,dis[v]);
    }
    
    while(++tot<n){
        bool flag=1;
        ll minn=inf;
        vis[now]=1;
        for(int i=1;i<=n;i++){
            if(!vis[i]&&minn>dis[i]){
                minn=dis[i];
                now=i;
                flag=0;
            }
        }
        ans+=minn;
        for(int i=head[now];i;i=e[i].next){
            int v=e[i].to;ll w=e[i].w;
            if(!vis[v]&&dis[v]>w){
                dis[v]=w;
            }
        }
        if(flag){
            printf("-1");
            exit(0);
        }
    }
    
}
int main(){
    n=read();c=read();
    for(int i=1;i<=n;i++){
        x[i]=read();y[i]=read();
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            ll len=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
            if(len<c) continue;
            addedge(i,j,len);
            addedge(j,i,len);
        }
    }
    prim();
    printf("%lld",ans);
    return 0;
}

---

3811. 【USACO2014 3月】The Lazy Cow (Standard IO)

Time Limits: 2000 ms  Memory Limits: 262144 KB  Detailed Limits  

Goto ProblemSet

Description

夏天很热，贝茜越发地懒散了。她想要使自己位于她的田里一个尽可能在短距离内够到美味的青草的位置。
贝茜居住的田野被描述为一个N 乘N 方格组成的棋盘（1 <= N <= 400）。
在第r 行第c 列的格子（1 <= r; c <= N）包含G(r; c)（0 <= G(r; c) <= 1000）单位的青草（节操）。从她在棋盘内的初始方格出发，贝茜只愿意走K 步路（0 <= K <= 2* N）。每一步路她从当前的位置向正北，正南，正东或正西移动一格。
举个例子，假如棋盘如下，这里(B) 描述贝茜的初始位置（在第三行第三列）：

50 5 25* 6 17
14 3* 2* 7* 21
99* 10* 1*(B) 2* 80*
8 7* 5* 23* 11
10 0 78* 1 9
如果K = 2，那么贝茜只能到达有星号（*）标记的位置。
请帮助贝茜确定，当她选择在棋盘中的最佳初始位置时，她能够到的最大青草总量。
 

 

Input

第一行：整数N 和K。
第2 至N + 1 行：第r + 1 行包含N 个整数用以描述棋盘的第r 行。

Output

输出单独一行一个整数——如果她在最佳初始位置（从这个位置她能够到最多的青草），那么贝茜能够到青草的最大总量。

 

Sample Input

5 2
50 5 25 6 17
14 3 2 7 21
99 10 1 2 80
8 7 5 23 11
10 0 78 1 9

Sample Output

342
样例解释：
在上面的例子里，贝茜如果位于棋盘的正中央，那么她能够到总共为342 单位的青草。

 

Data Constraint

对于20% 的数据，N<=20
对于30% 的数据，N<= 50;K<=10
对于40% 的数据，N <=100;K <= 20

简单的n^3写法：用前缀和维护即可。

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
const int N=410;
int n,k;
long long ans;
int a[N][N],s[N][N];
long long sum[N][N];
int main(){
    n=read();k=read();
    for(register int i=1;i<=n;i++){
        for(register int j=1;j<=n;j++){
            a[i][j]=read();
            s[i][j]=s[i][j-1]+a[i][j];
        }
    }
    for(register int i=1;i<=n;i++){
        for(register int j=1;j<=n;j++){
            for(register int t=max(1,i-k);t<=min(n,i+k);t++){
                int l=max(1,j-(k-abs(i-t)));
                int r=min(n,j+(k-abs(t-i)));
                sum[i][j]+=s[t][r]-s[t][l-1];
            }
            ans=max(ans,sum[i][j]);
        }
    }
    printf("%lld",ans);
    return 0;
}

正解好像可以将菱形转45度，变成正方形再做。

---

3812. 【USACO2014 3月】Mooo Moo (Standard IO)

Time Limits: 1000 ms  Memory Limits: 262144 KB  Detailed Limits  

Goto ProblemSet

Description

FJ 已经完全忘记了他有多少头奶牛！但是，跑到他的草场里数奶牛是一件很尴尬的事情，因为他不想让奶牛们知道他记忆有问题。作为替代，他决定秘密地把麦克风种在奶牛们通常聚集的草场里，然后只要从他听到的哞哞声音量中确定奶牛的数目即可。
FJ 的N 块草场（1 <= N <= 100）沿着一条笔直的路排成了一排。每块草场里可能有若干种不同的奶牛；FJ 的奶牛总共有B 种不同的种类（1 <= B <= 20），并且种类i 的一头奶牛叫起来的音量为V (i)（1 <= V (i) <= 100）。再者，沿着道路有一股强悍的风在吹，将哞哞叫的声音从路的左边传到右边：如果在某草场哞哞叫声音量为X，那么在下一个草场里会听到上边X -1 音量的叫声（并且在再下一个草场是X -2，等等）。更正式地说，一个草场的哞哞叫总音量为这个草场里奶牛哞哞的音量之和，加上X -1，这里X 是上一个草场的哞哞叫总音量。
给定FJ 从每个草场里记录的哞哞音量，请帮助他计算出他所拥有的奶牛的可能的最少数量。
任何一个草地上记录的音量值不超过100,000

 

Input

第一行：整数N 和B。
第2 至B + 1 行：第i + 1 行包含整数V (i)。
第B + 2 至B + N + 1 行：第B + i + 1 行包含第i 个草场哞哞叫的总音量。

Output

输出单独一行一个整数——FJ 最少拥有多少头奶牛；或者如果没有一种奶牛分配方案满足输入的限制，那么输出-1。

 

Sample Input

5 2
5
7
0
17
16
20
19

Sample Output

4
样例解释：
FJ 有5 块草场，哞哞音量分别为0; 17; 16; 20; 19。有两种奶牛，第一种哞哞的音量为5，另外一种音量为7.
在第二块草场，有两头种类#1 的奶牛和一头种类#2 的奶牛，并且在第4 块草场有另外一头种类#1 的奶牛。
 

 

Data Constraint

对于20% 的数据，N <= 20。
对于30% 的数据，N <= 30;B <= 5。
题目测试数据有梯度。

dp水题。

先搞出每个草场牛的数量，用dp[i]表示叫声为i最少可以有多少头牛。

dp[i]=min(dp[i],dp[i-v[j]]+1)

直接输出答案即可。

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0,f=1;
    char cc=getchar();
    while(!isdigit(cc)){
        if(cc=='-') f=-1;
        cc=getchar();
    }
    while(isdigit(cc)){
        x=(x<<1)+(x<<3)+(cc^48);
        cc=getchar();
    }
    return x*f;
}
const int N=110;
int n,b,cnt;
int v[N],a[N];
int c[N];
long long f[100010];
long long ans;
bool cmp(int t1,int t2){
    return t1>t2;
}
int main(){
    n=read();b=read();
    for(int i=1;i<=b;i++) v[i]=read();
    sort(v+1,v+b+1,cmp);
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=n;i>=2;i--){
        if(a[i-1]==0) continue;
        a[i]-=a[i-1]-1;
    }
    cnt=0;
    for(int i=1;i<=n;i++){
        if(!a[i]) continue;
        c[++cnt]=a[i];
    }
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=b;i++){
        for(int j=v[i];j<=100000;j++){
            f[j]=min(f[j],f[j-v[i]]+1);
        }
    }
    for(int i=1;i<=cnt;i++){
        ans+=f[c[i]];
    }
    printf("%lld",ans);
    return 0;
}