【清北学堂国庆刷题班】 Day4

2024-03-28 19:29:04

【清北学堂国庆刷题班】 Day4

T1 油箱

【问题描述】

有 n个城市，每个城市都有加油站，有 m 条单向道路，距离为 x 的道路需要消耗 x 升的汽油。请问你的车辆可以携带的最小油箱容量，使得不限加油次数的情况下，无论你在哪个城市都可以到达任意的城市。

【输入格式】

第一行两个正整数n,m。

接下来 m 行，每行三个正整数x,y,z 表示一条 x 到 y 的有向边，边权为 z。

【输出格式】

输出符合条件的最小油箱容量，如果无法满足输出 −1

【样例输入】

【样例输出】

‮4

【样例解释】

油箱容量为4时，1→2,1→3,3→1,2→3 道路可以通行，此时满足无论你在哪个城市都可以到达任意的城市。

【数据规模与约定】

20% 的数据 \(n\le 5 ,m\le 20\)

40% 的数据 \(n\le 50,m\le 200\)

60% 的数据 \(n\le 5*10^2,m\le 2*10^3\)

100% 的数据 \(n\le 5*10^4,m\le 2*10^9\)保证 \(1\le z \le 10^9\)

思路

这道题目我们可以看出来要求油箱的最小容量，这个油箱的容量是刚好大于某个数，因此我们需要在整个定义域中找到这个刚好的容量，所以题目要求的是将最大值最小化，所以我们使用二分算法

问题变成判断一个有向图是否任意两点联通

相当于判断点1是否能到达所有点并且所有点都能到达点1

可以建立正向图和反向图，并从点1开始dfs遍历

也可以直接使用tarjan

（这两个我只会第一个）

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 50010
#define M 200010
using namespace std;
int n,m,x[M],y[M],z[M];
struct edge{int next,to;};
struct Graph
{
	int head[N],tot;
	bool vis[N];
	edge e[M];
	void clear()//初始化
	{
		tot=0;
		memset(head,0,sizeof(head));
		memset(vis,0,sizeof(vis));
	}
	void add(int u,int v)//加一条从u到v的边
	{
		e[++tot]=(edge){head[u],v};
		head[u]=tot;
	}
	void dfs(int x)
	{
		if(vis[x])return;
		vis[x]=1;
		for(int i=head[x];i;i=e[i].next)
			dfs(e[i].to);
	}
	bool check()//遍历整个图；
	{
		dfs(1);
		for(int i=1;i<=n;i++)
			if(!vis[i])
				return false;
		return true;
	}
}E1,E2;
bool check(int cost)//二分判断函数
{
	E1.clear();
	E2.clear();
	for(int i=1;i<=m;i++)
		if(z[i]<=cost)
		{
			E1.add(x[i],y[i]);
			E2.add(y[i],x[i]);
		}
	return E1.check()&&E2.check();
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&x[i],&y[i],&z[i]);
	int l=1,r=1e9,ans=2e9;
	while(l<=r)//开始二分
	{
		int mid=l+r>>1;
		if(check(mid))ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%d\n",ans==2e9?-1:ans);
    return 0;
}

T2 求和

【问题描述】

给定一颗n个点组成的树，根节点为1号节点，每个点上有两个权值ai, bi。共有m次询问，每次询问给出两个正整数x, y，从x到y的路径设为t1,t2,…,tk 要求输出

\[\sum_{1\le i\le j \le k} a_{ti}*b_{tj} \]

【输入格式】

第一行两个正整数n,m

第二行n-1个数 f2,f3,…,fn，表示点i的父亲(fi< i)

接下来两行，每行n个数分别表示ai,bi

接下来m行，每行两个正整数xi,yi ，表示第i次询问

【输出格式】

对于每个询问操作，输出答案。

【样例输入】

【样例输出】

【数据规模与约定】

20% \(n,m\le 100\)

40% \(n,m \le 2000\)

另20% 保证 \(a_i=b_i\)

另20% 保证\(f_i=i-1\),\(x\le y\)

100% \(n,m\le 10^5\)保证 \(1\le a_i,b_i\le 10^4\)

思路

20%：

\(O(n^2m)\)暴力，~~我暴力都不知道怎么解决怎么办？~~

40%:

和式可以优化成O(n)每次多一个点，新增的为\(\sum_{1\le i<j}a_{t_i}*b_{t_j}\)

\(a_i=b_i\)时：

\(\sum_{i\le i<j\le k}a_{t_i}*a_{t_j}=\frac {[(\sum_{1\le i\le k}a_{t_i})^2-\sum_{i\le i\le k}a_{t_i}^2]}{2}\)

\(f_i=i-1\)时：

序列查询，两个区间合并成一个新的区间

考虑怎么将两个区间合并

新区间中每个(i,j)都会被统计答案，每个(i,j)只有三种可能

同属左区间、同属右区间、i在左区间j在右区间

前两种的总和就是两个区间答案的和

第三种就是左区间a的和乘上右区间b的和。

100%：

将上述做法拓展到树上倍增就可以了

上面的我都不会，把题解先贴上去了，到时候再问吧。。。

代码

#include<cstdio>
#include<algorithm>
#define N 100010
#define ll long long
using namespace std;
struct node
{
	int a,b;
	ll s;
	node(){a=b=s=0;}
	node(int _a,int _b,ll _s):a(_a),b(_b),s(_s){}
};
node operator+(node x,node y)
{
	return node(x.a+y.a,x.b+y.b,x.s+y.s+(ll)x.a*y.b);
}
int n,m,head[N],tot,fa[N][17],deep[N];
node u[N][17],d[N][17];
int climb(int x,int dis)
{
	for(int i=16;~i;i--)
		if((dis>>i)&1)
			x=fa[x][i];
	return x;
}
int lca(int x,int y)
{
	if(deep[x]<deep[y])swap(x,y);
	x=climb(x,deep[x]-deep[y]);
	if(x==y)return x;
	for(int i=16;~i;i--)
	if(fa[x][i]!=fa[y][i])
	x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
node up(int x,int dis)
{
	node tmp;
	for(int i=16;~i;i--)
		if((dis>>i)&1)
		{
			tmp=tmp+u[x][i];
			x=fa[x][i];
		}
	return tmp;
}
node down(int x,int dis)
{
	node tmp;
	for(int i=16;~i;i--)
		if((dis>>i)&1)
		{
			tmp=d[x][i]+tmp;
			x=fa[x][i];
		}
	return tmp;
}
ll query(int x,int y)
{
	int t=lca(x,y);
	if(t==y)return up(x,deep[x]-deep[y]+1).s;
	if(t==x)return down(y,deep[y]-deep[x]+1).s;
	return (up(x,deep[x]-deep[t]+1)+down(y,deep[y]-deep[t])).s;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=2;i<=n;i++)
		scanf("%d",&fa[i][0]);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&u[i][0].a);
		d[i][0].a=u[i][0].a;
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&u[i][0].b);
		d[i][0].b=u[i][0].b;
	}
	for(int i=1;i<=n;i++)
	{
		deep[i]=deep[fa[i][0]]+1;
		for(int j=1;j<17;j++)
		{
			fa[i][j]=fa[fa[i][j-1]][j-1];
			u[i][j]=u[i][j-1]+u[fa[i][j-1]][j-1];
			d[i][j]=d[fa[i][j-1]][j-1]+d[i][j-1];
		}
	}
	int x,y;
	while(m--)
	{
		scanf("%d%d",&x,&y);
		printf("%lld\n",query(x,y));
	}
    return 0;
}

T3 染色

【问题描述】

一排有n个格子，染成m种颜色，相邻格子颜色不能相同。此外，允许一个长度不超过k的区间染成相同的颜色。求最小代价。

【输入格式】

第一行包含三个正整数n, m, k表示格子数量、颜色数量、区间长度。

接下来的n行，每行有m个正整数cost i,j 表示将第i个格子染成颜色j需要付出的代价。

由于输入数据过大，可能需要使用快速读入

inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'|ch>'9')ch= getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch= getchar ();
    return x;
}

【输出格式】

输出一个整数，表示合法方案的最小代价。

【样例输入】

【样例输出】

【样例说明】

颜色分别为1 2 2 2 1

【数据规模与约定】

15% n, m<=10 k<=n

40% n, m<=100 k<=10

60% n, m<=300 k<=n

另15% n, m<=2000 k=1

100% n, m<=2000 k<=n cost<=10000

思路

为什么Day4的我只能看懂一道题

40%：

动态规划

\(k=1\)

\(dp[i][j]\)表示第i个格子染成第j种颜色，前i个格子都染色的最小代价

\(dp[i][j]=min_(j!=j’)dp[i-1][j’]+cost[i][j]\)

\(min_(j!=j’)dp[i-1][j’] = min(min_(j’<j) dp[i-1][j’] , min_(j’>j) dp[i-1][j’] )\)

同时维护\(dp[i][j]\)的前缀最小值和后缀最小值

时间复杂度为\(O(n^2)\)，也可以使用数据结构查询区间最小值复杂度多一个log

60%:

枚举相同颜色的区间(l,r)和颜色t，枚举量为O(nmk)

中间的代价已经固定，剩余变成了(1,l-1)和(r+1,n)并且l、r不能染色成t和k=1相同，所以只需要提前预处理前缀dp和后缀dp，O(1)得出代价

时间复杂度O(nmk)

100%:

先枚举颜色t，将上述做法枚举区间进行优化

代价为\(dpL[l-1][t]+Sum[r][t]-Sum[l-1][t]+dp[r][t]=(dpL[l-1][t] -Sum[l-1][t])+(Sum[r][t]+dp[r][t])\) 单调队列优化

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 3005
using namespace std;
int n,m,k,cost[N][N],sum[N][N];
int f[N][N],fl[N][N],fr[N][N];
int g[N][N],gl[N][N],gr[N][N];
int A[N],B[N],q[N],l,r;
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&cost[i][j]);
			sum[i][j]=sum[i-1][j]+cost[i][j];
		}
	memset(f,0x3f,sizeof(f));
	memset(fl,0x3f,sizeof(fl));
	memset(fr,0x3f,sizeof(fr));
	for(int j=1;j<=m;j++)
		f[0][j]=fl[0][j]=fr[0][j]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			f[i][j]=cost[i][j]+min(fl[i-1][j-1],fr[i-1][j+1]);
		for(int j=1;j<=m;j++)
			fl[i][j]=min(f[i][j],fl[i][j-1]);
		for(int j=m;j;j--)
			fr[i][j]=min(f[i][j],fr[i][j+1]);
	}
	memset(g,0x3f,sizeof(g));
	memset(gl,0x3f,sizeof(gl));
	memset(gr,0x3f,sizeof(gr));
	for(int j=1;j<=m;j++)
		g[n+1][j]=gl[n+1][j]=gr[n+1][j]=0;
	for(int i=n;i;i--)
	{
		for(int j=1;j<=m;j++)
			g[i][j]=cost[i][j]+min(gl[i+1][j-1],gr[i+1][j+1]);
		for(int j=1;j<=m;j++)
			gl[i][j]=min(g[i][j],gl[i][j-1]);
		for(int j=m;j;j--)
			gr[i][j]=min(g[i][j],gr[i][j+1]);
	}
	int ans=1e9;
	for(int j=1;j<=m;j++)
	{
		l=1,r=0;
		for(int i=1;i<=n;i++)
		{
			A[i]=sum[i][j]+min(gl[i+1][j-1],gr[i+1][j+1]);
			B[i]=min(fl[i-1][j-1],fr[i-1][j+1])-sum[i-1][j];
		}
		for(int i=1;i<=n;i++)
		{
			while(l<=r&&i-q[l]>=k)l++;
			while(l<=r&&B[q[r]]>=B[i])r--;
			q[++r]=i;
			ans=min(ans,A[i]+B[q[l]]);
		}
	}
	printf("%d\n",ans);
    return 0;
}

T4 数字

【问题描述】

给出n个好数和m个坏数，求包含所有好数但不包含任何坏数，并且只由1-4组成的数中，各位数字之和最小值是多少。(好数和坏数均为k位数，且由1-4组成)

【输入格式】

第一行包含三个正整数n, m, k

接下来n行包含每行1个正整数，表示好数

接下来m行包含每行1个正整数，表示坏数

【输出格式】

输出一个正整数，表示最小的值。输入数据保证一定存在解。

【样例输入】

【样例输出】

【样例说明】

12223331111

【数据规模与约定】

20% n<=5 m=0 k=2

30% n<=10 m<=10 k<=5

40% n<=17 m<=20 k<=5

50% n<=18 m<=20 k<=5

60% n<=19 m<=20 k<=5

70% n<=20 m<=20 k<=5

100% n<=20 m<=10000 k<=8

思路

看成不断添加一个新数字

这样相当于好数组成一个哈密顿通路

只需要求出两两好数之间最短距离，然后状压dp求出哈密顿通路

好数之间距离可以使用最短路算法求出，数据范围较小时可能有些其他的求法

由于边权均为1~4，可以拆边使用bfs求最短路，直接最短路可能会被卡时间

8位1-4组成的数可以看作4进制数进行运算，从而节省空间

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100010
#define pa pair<int,int>
using namespace std;
int n,m,k;
int good[25],bad[10005];
int dis[N][4];
bool vis[N];
int trans(int x)
{
	int y=0;
	for(int i=0;i<k;i++)
	{
		y|=(x%10-1)<<(2*i);
		x/=10;
	}
	return y;
}
queue<pa>q;
void bfs(int x)
{
	memset(dis,0x3f,sizeof(dis));
	if(vis[x])return;
	dis[x][0]=0;
	q.push(pa(x,0));
	while(!q.empty())
	{
		pa x=q.front();
		q.pop();
		int now=dis[x.first][x.second];
		if(x.second)
		{
			if(dis[x.first][x.second-1]>1e9)
			{
				dis[x.first][x.second-1]=now+1;
				q.push(pa(x.first,x.second-1));
			}
			continue;
		}
		for(int i=1;i<=4;i++)
		{
			int y=((x.first<<2)|(i-1))&((1<<(2*k))-1);
			if(dis[y][i-1]>1e9&&!vis[y])
			{
				dis[y][i-1]=now+1;
				q.push(pa(y,i-1));
			}
		}
	}
}
int dist[25][25];
int f[21][1<<20];
int calc(int x)
{
	int y=0;
	for(int i=0;i<k;i++)
	{
		y+=x%10;
		x/=10;
	}
	return y;
}
int main()
{
//	freopen("num8.in","r",stdin);
//	freopen("num2.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&good[i]);
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&bad[i]);
		vis[trans(bad[i])]=1;
	}
	for(int i=1;i<=n;i++)
	{
		bfs(trans(good[i]));
		for(int j=1;j<=n;j++)
			dist[i][j]=dis[trans(good[j])][0];
	}
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;i++)
		f[i][1<<(i-1)]=calc(good[i]);
	for(int S=0;S<(1<<n);S++)
	for(int i=1;i<=n;i++)
	if((S&(1<<(i-1))))
	{
		for(int j=1;j<=n;j++)
		if(!(S&(1<<(j-1))))
		f[j][S|(1<<(j-1))]=min(f[j][S|(1<<(j-1))],f[i][S]+dist[i][j]);
	}
/*	int I[25],ii,J[25],jj;
	for(int S=1;S<(1<<n);S++)
	{
		ii=jj=0;
		for(int i=1;i<=n;i++)
			if((S>>(i-1))&1)
			{
				if(f[i][S]<1e9)
					I[++ii]=i;
			}
			else
				J[++jj]=i;
		for(int i=1;i<=ii;i++)
		{
			int iii=I[i];
			for(int j=1;j<=jj;j++)
				f[J[j]][S|(1<<(J[j]-1))]=min(f[J[j]][S|(1<<(J[j]-1))],
					f[iii][S]+dist[iii][J[j]]);
		}	
	}*/
	int ans=1e9;
	for(int i=1;i<=n;i++)
		ans=min(ans,f[i][(1<<n)-1]);
	printf("%d\n",ans);
    return 0;
}

总结

这一篇写得我非常郁闷，总而言之一句话：

什么都不会，什么都得学，特别是图论和DP，然而csp将近，我就只能临阵磨枪，不快也光了，所以，加油吧，胜利一定属于我（我相信吗？

码农公寓

【清北学堂国庆刷题班】 Day4

T1 油箱

【问题描述】

【输入格式】

【输出格式】

【样例输入】

【样例输出】

【样例解释】

【数据规模与约定】

思路

代码

T2 求和

【问题描述】

【输入格式】

【输出格式】

【样例输入】

【样例输出】

【数据规模与约定】

思路

代码

T3 染色

【问题描述】

【输入格式】

【输出格式】

【样例输入】

【样例输出】

【样例说明】

【数据规模与约定】

思路

代码

T4 数字

【问题描述】

【输入格式】

【输出格式】

【样例输入】

【样例输出】

【样例说明】

【数据规模与约定】

思路

代码

总结

相关文章