# Usaco2019 feb platinum solution

## 出题越来越神仙的USACO

Posted by yjjr's blog on April 18, 2019

# [USACO19FEB]Cow Dating

## Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define ll long long
#define reg(i,x) for(int i=last[x];i;i=e[i].next)
using namespace std;
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e6+6;
int n;
double p[maxn],ans=0.0,tmp1=1,tmp2;
int main(){
//rep(i,1,n)printf("%.4lf\n",p[i]);
int j=1;
rep(i,1,n){
while(j<=n&&tmp1*tmp2<tmp1*(1-p[j])*(tmp2+p[j]/(1-p[j]))){
tmp1*=(1-p[j]);
tmp2+=p[j]/(1-p[j]);
j++;
}
ans=max(ans,tmp1*tmp2);
tmp1/=(1-p[i]);
tmp2-=p[i]/(1-p[i]);
}
// cout<<ans<<endl;
cout<<(int)(ans*1e6)<<endl;
return 0;
}


# [USACO19FEB]Moorio Kart

## 分析

$f[i][0/1]$表示当前路径和为$i$的方案数/方案权值之和

$g[i][0/1]$表示当前这棵树内部的长度为$i$的方案数/方案权值之和

$f[i+j][0]=f[i][0]\times g[j][0]$

$f[i+j][1]=f[i][0]\times g[j][1] + f[i][1]\times g[j][0]$

## Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define ll long long
#define reg(i,x) for(int i=last[x];i;i=e[i].next)
using namespace std;
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=3e3+6;
const ll mod=1e9+7;
struct edge{int to,next,w;}e[maxn<<1];
int last[maxn],fa[maxn],bel[maxn],cnt=0,tot=0,n,m,now,X,Y;
ll sum[maxn][maxn],num[maxn][maxn],g[maxn][2],f[maxn][2],ans;
inline int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);}
void insert(int u,int v,int w){e[++cnt]=(edge){v,last[u],w};last[u]=cnt;}
void build(int x,int fr,int id){
bel[x]=id;
reg(i,x)if(e[i].to!=fr)build(e[i].to,x,id);
}
void dfs(int x,int fr,int l){
if(fr){sum[bel[x]][min(l,Y)]=(sum[bel[x]][min(l,Y)]+l)%mod;++num[bel[x]][min(l,Y)];}
reg(i,x)if(e[i].to!=fr)dfs(e[i].to,x,l+e[i].w);
}
int main(){
rep(i,1,n)fa[i]=i;
rep(i,1,m){
insert(u,v,w);insert(v,u,w);
int r1=find(u),r2=find(v);
if(r1!=r2)fa[r1]=r2;
}
rep(i,1,n)if(find(i)==i)build(i,0,++tot);
rep(i,1,n)dfs(i,0,0);
now=min(tot*X,Y);
f[now][0]=1;f[now][1]=tot*X;
rep(i,1,tot){
rep(j,now,Y)g[j][0]=f[j][0],g[j][1]=f[j][1],f[j][0]=f[j][1]=0;
rep(j,0,Y)
if(num[i][j])
rep(k,now,Y)
if(g[k][0]){
f[min(j+k,Y)][0]=(f[min(j+k,Y)][0]+1ll*g[k][0]*num[i][j])%mod;
f[min(j+k,Y)][1]=(f[min(j+k,Y)][1]+1ll*g[k][0]*sum[i][j]+1ll*g[k][1]*num[i][j])%mod;
}
}
ans=f[Y][1];
cout<<ans<<endl;
rep(i,1,tot-1)ans=ans*i%mod;
cout<<1ll*ans*(mod+1)/2%mod<<endl;
return 0;
}


# [USACO19FEB]Mowing Mischief

## 分析

$dp[i]=\min { dp[j]+(x_i-x_j)\times (y_i-y_j) } (x_j\leq x_i,y_j\leq y_i)$

$dp[i]=\min { dp[j]+x_jy_j-x_iy_j-x_jy_i }+x_iy_i (x_j\leq x_i,y_j\leq y_i)$

$x_i \times (y_b - y_a) + y_i \times (x_b - x_a) < dp_b + x_b \times y_b - dp[a] - x_a \times y_a$

## Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define ll long long
#define reg(i,x) for(int i=last[x];i;i=e[i].next)
using namespace std;
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=2e5+6;
const ll inf=1e18;
int n,m,tot,f[maxn];
ll dp[maxn];
vector<int> g[maxn];
struct node{
int x,y;
inline bool operator < (const node &u)const{return u.x==x?y<u.y:x<u.x;}
inline bool operator > (const node &u)const{return ((x>=u.x)&&(y>=u.y));}
}a[maxn];
namespace BIT{
#define lowbit(x) (x&(-x))
int tree[maxn<<3];
inline void modifybit(int x,int Val){
x=max(x,1);
for(int i=x;i<=m;i+=lowbit(i))tree[i]=max(tree[i],Val);
}
inline int querybit(int x){
int re=0;
for(int i=x;i;i-=lowbit(i))re=max(re,tree[i]);
return re;
}
}
using namespace BIT;
namespace SEG{
#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)
#define MID ((L+R)>>1)
vector<int>p[maxn<<2];
vector<int>now,s;
void build(int x,int l,int r){
p[x]=vector<int>();
if(l==r)return;
build(ls,l,mid);build(rs,mid+1,r);
}
void init(int x){
now=g[x];
build(1,0,now.size()-1);
}
void insert(int x,int l,int r,int k){
if(a[k].x>=a[now[r]].x&&a[k].y>=a[now[l]].y){
p[x].push_back(k);
return;
}
if(a[k].x<a[now[l]].x||a[k].y<a[now[r]].y||l==r)return;
insert(ls,l,mid,k);insert(rs,mid+1,r,k);
}
void queryseg(int l,int r,int L,int R){
if(l>r)return;
ll ans=inf;
int x=s[mid],pos=0;
rep(i,L,R){
ll re=dp[now[i]]+1ll*(a[x].x-a[now[i]].x)*(a[x].y-a[now[i]].y);
if(re<ans)ans=re,pos=i;
}
dp[x]=min(dp[x],ans);
queryseg(l,mid-1,pos,R);
queryseg(mid+1,r,L,pos);
}
void work(int x,int l,int r){
if(!p[x].empty()){
s=p[x];
queryseg(0,s.size()-1,l,r);
}
if(l==r)return;
work(ls,l,mid);work(rs,mid+1,r);
}
}
using namespace SEG;
void solve(int x){
init(x);
for(int i=0,sz=g[x+1].size(),ssz=g[x].size();i<sz;i++)insert(1,0,ssz-1,g[x+1][i]);
work(1,0,g[x].size()-1);
}
int main(){
a[++n]=(node){0,0};
a[++n]=(node){m,m};
sort(a+1,a+1+n);
rep(i,1,n){
f[i]=querybit(a[i].y)+1;
modifybit(a[i].y,f[i]);
tot=max(tot,f[i]);
g[f[i]].push_back(i);
}
rep(i,1,n)dp[i]=1ll*a[i].x*a[i].y;
rep(i,1,tot-1)solve(i);
cout<<dp[n]<<endl;
return 0;
}