Forewords
今年 USACO 的比赛变化挺大的，有部分分了，而且不再是固定十个点了（部分分只说这几个点满足这几个性质，以为十个点的我还高兴了一会，一提交，...），除此之外居然赛后还排名了。这场打得意外的顺手，但是还是有点小遗憾吧。样例强度还是有点不够高的，但 IOI 赛制嘛，也不能说啥。
T1 Milk Pumping
上来看错题，打了个最小生成树，结果别人只要一条路径给弄出个树来妥妥的超过最优解爆零。仔细看题了以后发现还行，就是个有限制的最短路，每个限制枚举一遍很暴力但是数据不是很大就不管这么多了。但是有两个点硬是 WA 了，有时间再调吧。
code
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
const int MAXN=1000+5;
struct Edge{int u,v,w,f,next;};
struct data
{
int u,w;
bool operator < (const data &b) const
{
return w==b.w?u<b.u:w<b.w;
}
};
int n,m,dis[MAXN],cnt;Edge edge[MAXN*2];int head[MAXN],u,v,w,f;bool vis[MAXN],visit[MAXN];
std::priority_queue<data>pq;
void AddEdge(int u,int v,int w,int f)
{
edge[++cnt].u=u;edge[cnt].v=v;edge[cnt].w=w;edge[cnt].f=f;
edge[cnt].next=head[u];head[u]=cnt;
}
void Dijkstra(int limit)
{
data tmp,temp;
memset(dis,0x3f3f3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[1]=0;tmp.u=1;tmp.w=0;
pq.push(tmp);
while(!pq.empty())
{
temp=pq.top();pq.pop();
if(vis[temp.u]) continue;
vis[temp.u]=1;
for(int i=head[temp.u];i;i=edge[i].next)
{
//printf("*%d ",edge[i].v);
if(edge[i].f<limit) continue;
if(dis[edge[i].v]>dis[edge[i].u]+edge[i].w)
{
dis[edge[i].v]=dis[edge[i].u]+edge[i].w;
tmp.u=edge[i].v;tmp.w=dis[edge[i].v];
pq.push(tmp);
}
}
}
}
int main()
{
freopen("pump.in","r",stdin);
freopen("pump.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d %d %d %d",&u,&v,&w,&f);
AddEdge(u,v,w,f);AddEdge(v,u,w,f);
}
long long ans=0;
for(int i=1;i<=cnt;i++)
if(!visit[edge[i].f])
{
visit[edge[i].f]=1;
Dijkstra(edge[i].f);
//printf("[%lld]",dis[n]);
if(dis[n]==dis[0]) continue;
ans=std::max((double)ans,(double)((double)edge[i].f/dis[n])*1e6);
}
printf("%lld\n",ans);
return 0;
}
T2 Milk Visits
一眼树剖，打的时候发现还要加个主席树，于是就套上去了。第一次在比赛的时候写树套树诶。然后不知道想什么老是觉得 \(dep[x]<dep[y]\) 可以推出 \(id[x]<id[y]\)，花了大量时间调，虽然也修了几个 bug 但是还是只过了那几个点。今天改完 A 了。
另外官方题解看上去很简洁的样子，找时间研究一下。
code
#include<cstdio>
#include<vector>
#define MID (root->l+root->r)>>1
const int MAXN=1e5+5;
struct Edge{int u,v,next;};
struct Tree{int l,r,val;Tree* ls;Tree* rs;};
int n,m,u,v,x,y,z,linkid[MAXN],lcnt,dep[MAXN],t[MAXN],top[MAXN],heavy[MAXN],id[MAXN],type[MAXN];int head[MAXN],siz[MAXN],cnt,fa[MAXN];Edge edge[MAXN*2];Tree* root[MAXN];
std::vector<int>son[MAXN];
std::vector<int>nums[MAXN];
void AddEdge(int u,int v)
{
edge[++cnt].u=u;edge[cnt].v=v;edge[cnt].next=head[u];head[u]=cnt;
}
int dag(int now,int fa)
{
int siz=0,maxid,maxv=0;
// printf("depth of %d is %d\n",now,dep[now]);
for(int i=head[now];i;i=edge[i].next)
{
if(edge[i].v!=fa)
{
::fa[edge[i].v]=now;
son[now].push_back(edge[i].v);
dep[edge[i].v]=dep[now]+1;
int ret=dag(edge[i].v,now);
if(ret>maxv)
{
maxv=ret;
maxid=edge[i].v;
}
siz+=ret;
}
}
heavy[now]=maxid;
siz++;
::siz[now]=siz;
return siz;
}
void split(int now,int top,int lid)
{
id[now]=++cnt;
type[cnt]=t[now];
nums[t[now]].push_back(cnt);
linkid[now]=lid;
::top[now]=top;
if(!son[now].size()) return;
split(heavy[now],top,linkid[top]);
for(int i=0;i<son[now].size();i++)
if(son[now][i]!=heavy[now]) split(son[now][i],son[now][i],++lcnt);
}
Tree* getNode()
{
Tree* ret=new Tree;
ret->ls=ret->rs=NULL;
ret->l=ret->r=ret->val=0;
return ret;
}
void BuildTree(int l,int r,Tree* root)
{
root->l=l;root->r=r;root->val=0;
if(l==r) return;
Tree* ls=getNode();Tree *rs=getNode();int mid=MID;
root->ls=ls;root->rs=rs;
BuildTree(l,mid,ls);BuildTree(mid+1,r,rs);
}
void cpNode(Tree* src,Tree* to){to->l=src->l;to->r=src->r;to->val=src->val;to->ls=src->ls;to->rs=src->rs;}
void Update(int target,Tree* base,Tree* root)
{
if(root->l==root->r) {root->val++;return;}
int mid=MID;
if(target<=mid)
{
root->ls=getNode();
root->rs=base->rs;
cpNode(base->ls,root->ls);
Update(target,base->ls,root->ls);
}
else
{
root->ls=base->ls;
root->rs=getNode();
cpNode(base->rs,root->rs);
Update(target,base->rs,root->rs);
}
root->val=root->ls->val+root->rs->val;
}
int Query(int l,int r,Tree* root)
{
if(l==root->l&&r==root->r) return root->val;
int mid=MID;
if(r<=mid) return Query(l,r,root->ls); else if(l>mid) return Query(l,r,root->rs); else return Query(l,mid,root->ls)+Query(mid+1,r,root->rs);
}
bool getResult(int x,int y,int z)
{
while(x!=y)
{
if(dep[x]<dep[y]) std::swap(x,y);
if(linkid[x]==linkid[y]) return Query(id[y],id[x],root[z])-Query(id[y],id[x],root[z-1]);
if(Query(id[top[x]],id[x],root[z])-Query(id[top[x]],id[x],root[z-1])) return 1;
x=fa[top[x]];
}
return type[id[x]]==z;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&t[i]);
for(int i=1;i<n;i++)
{
scanf("%d %d",&u,&v);
AddEdge(u,v);AddEdge(v,u);
}
fa[1]=1;
dep[1]=1;
linkid[1]=1;
lcnt=1;
dag(1,-1);
cnt=0;
split(1,1,1);
root[0]=getNode();
BuildTree(1,n,root[0]);
for(int i=1;i<=n;i++)
{
root[i]=root[i-1];
if(!nums[i].size()) {continue;}
for(int j=0;j<nums[i].size();j++)
{
Tree* tmp=getNode();
cpNode(root[i],tmp);
Update(nums[i][j],root[i],tmp);
root[i]=tmp;
}
}
for(int i=1;i<=m;i++)
{
scanf("%d %d %d",&x,&y,&z);
printf("%d",getResult(x,y,z));
}
return 0;
}
T3 Moortal Cowmbat
一半的部分分给了字符串 DP，后面那一半怎么写就不知道了。
code
#include<cstdio>
#include<algorithm>
#include<cstring>
const int MAXN=30000+5;
const int MAXK=50+5;
const int MAXM=26+5;
int dp[MAXN][MAXM][MAXK],minstart[MAXN],n,m,p,cost[MAXM][MAXM],a[MAXN];char str[MAXN];
int main()
{
freopen("cowmbat.in","r",stdin);
freopen("cowmbat.out","w",stdout);
scanf("%d %d %d",&n,&m,&p);
scanf("%s",str+1);
if(p==1) {printf("0");return 0;}
for(int i=1;i<=n;i++)
a[i]=str[i]-'a'+1;
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
scanf("%d",&cost[i][j]);
for(int k=1;k<=m;k++)
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
cost[i][j]=std::min(cost[i][j],cost[i][k]+cost[k][j]);
memset(dp,0x3f3f3f,sizeof(dp));
memset(minstart,0x3f3f3f,sizeof(minstart));
minstart[1]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=0;k<p;k++)
{
//printf("%d %d %d %d %d\n",i,j,k,dp[i][j][k],minstart[i]);
if(k==0)
{
dp[i+1][j][k+1]=std::min(dp[i+1][j][k+1],minstart[i]+cost[a[i]][j]);
}
else dp[i+1][j][k+1]=std::min(dp[i+1][j][k+1],dp[i][j][k]+cost[a[i]][j]);
if(k==p-1) {minstart[i+1]=std::min(minstart[i+1],dp[i][j][k]+cost[a[i]][j]);dp[i+1][j][k]=std::min(dp[i+1][j][k],dp[i][j][k]+cost[a[i]][j]);}
}
printf("%d",minstart[n+1]);
return 0;
}