HZOI20190902模拟35题解

题面：

A：公园

DAG上想拓扑dp

然而博主记忆化搜索了一下

设f[i][j]表示从i节点走j个点出公园所用的最小时间

则$f[u][i]=min(f[v][j-1]+dis_{u,v})$;

然后记忆化搜索

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define int long long

#define re register

#define MAXV 2005

#define MAXE 6005

using namespace std;

int v,m,n,e,l,a[MAXE],b[MAXE],ans=0;

int to[MAXE],nxt[MAXE],pre[MAXV],cnt=0,val[MAXE];

inline void add(re int u,re int v,re int w){

	++cnt,to[cnt]=v,nxt[cnt]=pre[u],pre[u]=cnt,val[cnt]=w;

}

int ent[MAXE],f[MAXV][MAXV];

bool vis[MAXV];

inline void dfs(re int x){

	if(x==v+1){

		f[x][0]=0;

		return ;

	}

	for(re int i=pre[x];i;i=nxt[i]){

		re int y=to[i];

		if(!vis[y]){

			vis[y]=1;

			dfs(y);

		}

		for(re int j=1;j<=v;j++)

			f[x][j]=min(f[x][j],f[y][j-1]+val[i]);

	}

}

signed main(){

	//freopen("ex_park3.in","r",stdin);

	scanf("%lld%lld%lld%lld%lld",&v,&m,&n,&e,&l);

	for(re int i=0;i<=v+1;++i) for(re int j=0;j<=v+1;++j) f[i][j]=0x3fffffffffffffff;

	for(re int i=1,x;i<=m;++i){

		scanf("%lld",&x);

		scanf("%lld",&a[x]);

		ent[i]=x;

	}

	for(re int i=1,x;i<=n;++i){

		scanf("%lld",&x);

		scanf("%lld",&b[x]);

		add(x,v+1,b[x]);

	}

	for(re int i=1,p,q,w;i<=e;++i){

		scanf("%lld%lld%lld",&p,&q,&w);

		add(p,q,w);

	}

	for(re int i=1;i<=m;++i){

		if(vis[ent[i]]) continue;

		vis[ent[i]]=1;

		dfs(ent[i]);

	}

	for(re int i=1;i<=m;++i){

		for(re int j=1;j<=v;++j){

			if(f[ent[i]][j]+a[ent[i]]>l) continue;

			ans=max(ans,j);

		}

	}

	printf("%lld\n",ans);

	return 0;

}

B：计划

先想一个暴力

我们预处理一个b[i]，表示由i位置之后经过b[i]后是第一次出现m个不同的数

然后对于每一个询问(x,y)，$ans=\sum\limits_{i=x}^{y}\frac{(y+b[i]-2i)*(y-b[i]+1)}{2}(b[i]<y)$

我们发现b[i]是单调增的，所以枚举到第一个b[i]>y就break

于是有80分

然后我们优化

我们发现$(y+b[i]-2i)*(y-b[i]+1)=y^2+y+b[i]-b[i]^2+2ib[i]-2i-2iy$

这个可以前缀和优化

那么重点就是找到第一个b[i]>y的位置，二分即可

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define MAXN 100005

#define re register

#define int long long

using namespace std;

int n,m,q,a[MAXN],b[MAXN],sum[MAXN],cnt[MAXN];

bool vis[MAXN];

inline int get(re int l){

	re int num=0;

	memset(vis,0,sizeof(vis));

	for(re int i=l;i<=n;++i){

		if(vis[a[i]]==0) num++;

		vis[a[i]]=1;

		if(num>=m) return i;

	}

	return n+1;

}

signed main(){

	scanf("%lld%lld%lld",&n,&m,&q);

	for(re int i=1;i<=n;++i){

		scanf("%lld",&a[i]);

	}

	for(int i=1;i<=n;++i){

		b[i]=get(i);

		if(b[i]>n) continue;

		sum[i]=sum[i-1]+b[i]-b[i]*b[i]+2*i*b[i]-2*i;

		cnt[i]=cnt[i-1]+i;

	}

	while(q--){

		re int x,y,res=0,l,r,mid;

		scanf("%lld%lld",&x,&y);

		l=x,r=y;

		while(l<=r){

			mid=(l+r)>>1;

			if(b[mid]<=y) l=mid+1;

			else r=mid-1;

		}

		res+=(sum[l-1]-sum[x-1]+(l-x)*(y*y+y)-2*y*(cnt[l-1]-cnt[x-1]))/2;

		printf("%lld\n",res);

	}

	return 0;

}

巴特西

HZOI20190902模拟35题解

最新文章

热门文章