# Usaco2019 jan platinum solution

## 铂金毒瘤题

Posted by yjjr's blog on February 13, 2019

# 洛谷5202 [USACO19JAN]Redistricting

## 题目

### 题目背景

USACO 19年一月月赛铂金组第一题

### 输入输出样例

#### 输入样例#1

7 2
HGHGGHG


#### 输出样例#1

3


## Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#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 ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(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=3e5+6;
int n,K,g[maxn],que[maxn<<1],f[maxn];
char s[maxn];
inline bool cal(int x,int y){
int tmp=g[y]-g[x];
if((tmp<<1)>=y-x)return 1;else return 0;
}
int main(){
rep(i,1,n)if(s[i]=='G')g[i]=g[i-1]+1;else g[i]=g[i-1];
rep(i,1,n){
que[++tail]=i;
}
cout<<f[n]<<endl;
return 0;
}


# 洛谷5203 [USACO19JAN]Exercise Route

## 题目

### 题目背景

USACO 19年一月月赛铂金组第二题

### 输入输出样例

#### 输入样例#1

5 8
1 2
1 3
1 4
1 5
2 3
3 4
4 5
5 2


#### 输出样例#1

4


## Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#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 ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(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;
struct edge{int to,next;}e[maxn<<1];
int n,m,last[maxn],dep[maxn],fa[maxn][20],u[maxn],v[maxn],lca[maxn],s[maxn],sum[maxn],cnt=0;
ll ans=0;
map<pair<int,int>,int>mp;
void insert(int u,int v){e[++cnt]={v,last[u]};last[u]=cnt;}
void dfs(int x,int fr){
fa[x][0]=fr;
rep(i,1,18)fa[x][i]=fa[fa[x][i-1]][i-1];
reg(x){
if(e[i].to==fr)continue;
dep[e[i].to]=dep[x]+1;
dfs(e[i].to,x);
}
}
inline int getlca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
int tmp=dep[x]-dep[y];
rep(i,0,18)if((1<<i)&tmp)x=fa[x][i];
dep(i,18,0)
if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return x==y?x:fa[x][0];
}
inline int son(int lca,int x){
if(lca==x)return 0;
dep(i,18,0)if(dep[fa[x][i]]>dep[lca])x=fa[x][i];
return x;
}
void dfs2(int x,int tmp){
sum[x]=tmp;
reg(x){
if(e[i].to==fa[x][0])continue;
dfs2(e[i].to,tmp+s[e[i].to]);
}
}
int main(){
rep(i,1,n-1){
insert(u,v);insert(v,u);
}
dfs(1,1);
rep(i,n,m){
lca[i]=getlca(u[i],v[i]);
int r1=son(lca[i],u[i]),r2=son(lca[i],v[i]);
if(r1)ans-=++s[r1];
if(r2)ans-=++s[r2];
if(r1&&r2){
if(r1>r2)swap(r1,r2);
ans-=mp[make_pair(r1,r2)];
++mp[make_pair(r1,r2)];
}
}
dfs2(1,s[1]);
rep(i,n,m)ans+=sum[u[i]]+sum[v[i]]-2*sum[lca[i]];
cout<<ans<<endl;
return 0;
}


# 洛谷5204 [USACO19JAN]Train Tracking 2

## 题目

### 题目背景

USACO 19年一月月赛铂金组第三题

### 题目描述

Bessie的消息是完全可靠的；也就是说，保证存在至少一种符合要求的编号方式。

### 输入输出样例

#### 输入样例#1

4 2
999999998
999999999
999999998


#### 输出样例#1

3


## 分析

xzz的题解太神仙了tql

$f[i]=f[i-1]+f[i-2]\times x+f[i-3]\times x^2+…+f[i-k]\times x^{k-1}$

$f[i]=f[i-1]+x(f[i-1]-f[i-k-1]\times x^{k-1})$

## Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#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 ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(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 ll inf=1e9,mod=1e9+7;
const int maxn=2e5+6;
int n,k,c[maxn],tot=0,cur=0,cnt=0;ll ans=1;
struct node{int f;ll s;}comp[maxn];
inline ll Count(int mnval,int k,int len){
ll f[len+6],pows[k+6],powslow[k+6],succ=inf-mnval;
pows[0]=powslow[0]=1;
rep(i,1,k){
pows[i]=(1ll*pows[i-1]*(succ+1)%mod+mod)%mod;
powslow[i]=(1ll*powslow[i-1]*succ%mod+mod)%mod;
}
f[0]=f[1]=1;
rep(i,2,min(k,len))f[i]=pows[i-1];
if(len<k)return pows[len];
rep(i,k,len){
f[i+1]=f[i];
f[i+1]=(ll)((f[i+1]-(1ll*f[i-k]*powslow[k-1])+mod)%mod+mod)%mod;
f[i+1]=(ll)(1ll*f[i+1]*succ)%mod;
f[i+1]=(ll)(f[i+1]+f[i])%mod;
}
return f[len+1]%mod;
}
int main(){
rep(i,1,n-k+1){
if(cur==c[i])++cnt;
else{
if(cnt)comp[++tot]=(node){cur,cnt};
cur=c[i],cnt=1;
}
}
comp[++tot]=(node){cur,cnt};
if(tot==1){cout<<Count(comp[1].f,k,n)<<endl;return 0;}
rep(i,1,tot){
int a=comp[i].f,len;
if(i==1){
if(comp[2].f>comp[1].f)len=comp[1].s-1;else len=comp[1].s+k-1;
}
else if(i==tot){
if(comp[i-1].f>comp[i].f)len=comp[i].s-1;else len=comp[i].s+k-1;
}
else{
if(comp[i-1].f>comp[i].f){
if(comp[i+1].f>comp[i].f)len=max(0,(int)comp[i].s-k-1);
else len=comp[i].s-1;
}else{
if(comp[i+1].f>comp[i].f)len=comp[i].s-1;
else len=comp[i].s+k-1;
}
}
ans=(ll)((1ll*ans*Count(a,k,len))%mod+mod)%mod;
}
cout<<ans<<endl;
return 0;
}