【清北学堂国庆刷题班】 Day4
T1 油箱
【问题描述】
有 n个城市，每个城市都有加油站，有 m 条单向道路，距离为 x 的道路需要消耗 x 升的汽油。请问你的车辆可以携带的最小油箱容量，使得不限加油次数的情况下，无论你在哪个城市都可以到达任意的城市。
【输入格式】
第一行两个正整数n,m。
接下来 m 行，每行三个正整数x,y,z 表示一条 x 到 y 的有向边，边权为 z。
【输出格式】
输出符合条件的最小油箱容量，如果无法满足输出 −1
【样例输入】
1
2
3
4
5
6
| 3 5
1 2 1
1 3 2
2 3 5
3 1 4
2 3 1
|
【样例输出】
【样例解释】
油箱容量为4时，1→2,1→3,3→1,2→3 道路可以通行，此时满足无论你在哪个城市都可以到达任意的城市。
【数据规模与约定】
20% 的数据 n≤5,m≤20
40% 的数据 n≤50,m≤200
60% 的数据 n≤5∗102,m≤2∗103
100% 的数据 n≤5∗104,m≤2∗109保证 1≤z≤109
思路
这道题目我们可以看出来要求油箱的最小容量，这个油箱的容量是刚好大于某个数，因此我们需要在整个定义域中找到这个刚好的容量，所以题目要求的是将最大值最小化，所以我们使用二分算法
问题变成判断一个有向图是否任意两点联通
相当于判断点1是否能到达所有点并且所有点都能到达点1
可以建立正向图和反向图，并从点1开始dfs遍历
也可以直接使用tarjan
（这两个我只会第一个）
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #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)
{
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 要求输出
∑1≤i≤j≤kati∗btj
【输入格式】
第一行两个正整数n,m
第二行n-1个数 f2,f3,…,fn，表示点i的父亲(fi< i)
接下来两行，每行n个数 分别表示ai,bi
接下来m行，每行两个正整数xi,yi ，表示第i次询问
【输出格式】
对于每个询问操作，输出答案。
【样例输入】
1
2
3
4
5
6
7
8
| 5 4
1 2 3 4
1 2 3 4 5
1 2 3 4 5
1 2
1 3
1 4
1 5
|
【样例输出】
【数据规模与约定】
20% n,m≤100
40% n,m≤2000
另20% 保证 ai=bi
另20% 保证fi=i−1,x≤y
100% n,m≤105保证 1≤ai,bi≤104
思路
20%：
O(n2m)暴力，我暴力都不知道怎么解决怎么办？
40%:
和式可以优化成O(n)每次多一个点，新增的为∑1≤i<jati∗btj
ai=bi时：
∑i≤i<j≤kati∗atj=2[(∑1≤i≤kati)2−∑i≤i≤kati2]
fi=i−1时：
序列查询，两个区间合并成一个新的区间
考虑怎么将两个区间合并
新区间中每个(i,j)都会被统计答案，每个(i,j)只有三种可能
同属左区间、同属右区间、i在左区间j在右区间
前两种的总和就是两个区间答案的和
第三种就是左区间a的和乘上右区间b的和。
100%：
将上述做法拓展到树上倍增就可以了
上面的我都不会，把题解先贴上去了，到时候再问吧。。。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
| #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需要付出的代价。
由于输入数据过大，可能需要使用快速读入
1
2
3
4
5
6
7
| 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
3
4
5
6
| 5 3 3
1 5 6
1 2 3
9 1 9
9 1 9
1 2 3
|
【样例输出】
【样例说明】
颜色分别为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(n2)，也可以使用数据结构查询区间最小值复杂度多一个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]) 单调队列优化
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #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个正整数，表示坏数
【输出格式】
输出一个正整数，表示最小的值。输入数据保证一定存在解。
【样例输入】
1
2
3
4
5
6
7
| 3 3 4
1111
1222
2333
1122
1133
3122
|
【样例输出】
【样例说明】
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进制数进行运算，从而节省空间
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
| #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()
{
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 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将近，我就只能临阵磨枪，不快也光了，所以，加油吧，胜利一定属于我（我相信吗？
