【清北学堂国庆刷题班】 Day2
T1 小路灯
题目描述
一条平直的公路上有n个小路灯，第ii个路灯的坐标是ai。小A需要把其中的k个点亮，使得每个小路灯与距离最近的被点亮的小路灯的距离的最大值最小。求这个最小值。
输入格式
第1行2个正整数n,k。
接下来n行，每行一个整数ai，表示第i个小路灯的坐标，保证ai是严格单调递增的。
输出格式
1行1个数表示答案。
样例数据
input
output
样例解释
点亮第2、5、6个路灯，每个路灯与距离最近的被点亮的路灯的距离分为是1,0,6,1,0,0，最大值是6。可以证明没有比6更小的方案。
数据规模与约定
对于 30% 的数据，n,k≤100。
对于 100% 的数据，1≤n≤100000,1≤k≤n,∣ai∣≤109
时间限制：1s
空间限制：512MB
思路
二分答案
看题目，最大值最小，一看就知道是二分答案
但是这道题目怎么二分答案呢，我们可以设这个最小的最大值为x，对这个x进行二分，如果一个路灯距离前一个路灯的距离ai−last不大于x的话，说明这个数小于这个最大值，所以不需要管他，直接continue ，进行下一步循环；如果一个路灯距离上一个被点亮的路灯距离ai−now大于这个最小值的话，显然不符合题意，所以我们需要更改这个点亮的路灯，直到符合题意，然后这个路灯距离上一个路灯的距离小于x的我们就会把now初始化掉，最后统计一下点亮的灯的个数就可以了。
代码
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
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
int n,k;
int a[100005];
bool check(int x)
{
long long last=-2e10;
long long now=-2e10;
int s=0;
for(int i=1;i<=n;i++)
{
if(a[i]-last<=x) continue;
if(now==-2e10) now=a[i];
else if(a[i]-now>x)
{
last=a[i-1];
if(a[i]-last<=x) now=-2e10;
else now=a[i];
s++;
}
}
if(now!=-2e10) s++;
return s<=k;
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
int l=0,r=2e9;
while(l<r)
{
int mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l<<endl;
return 0;
}
|
T2 序列
题目描述
设数列P=[p1,p2,……,pn]，定义f(p,k)=[p2,p3,……,pk,p1,pk+2,pk+3,……,p2k,pk+1,……]，也就是把P每k个分成一段（最后如果不足k个，把它们分到新的一段），然后将每段的首个元素移动到该段末尾。求f(f(……f(f([1,2,……,n],2),3),……),n)。
输入格式
1行1个正整数n。
输出格式
1行n个数表示答案。
样例数据
input
output
样例解释
P:[1,2,3,4]→[2,1,4,3]→[1,4,2,3]→[4,2,3,1]
数据规模与约定
对于 40% 的数据，1≤n≤1000
对于 60% 的数据，1≤n≤100000
对于 100% 的数据，1≤n≤1000000
时间限制：2s
空间限制：512MB
思路
没有思路
模拟？
这道题模拟n=10的情况
1 2 3 4 5 6 7 8 9 10
2 1 4 3 6 5 8 7 10 9
1 4 2 6 5 3 7 10 8 9
4 2 6 1 3 7 10 5 9 8
2 6 1 3 4 10 5 9 8 7
6 1 3 4 10 2 9 8 7 5
1 3 4 10 2 9 6 7 5 8
3 4 10 2 9 6 7 1 5 8
4 10 2 9 6 7 1 5 3 8
10 2 9 6 7 1 5 3 8 4
然后发现了一点东西，就跟四中童佬和怀哥讨论了一下，经过了1.5h的讨论与探究，我们进行了超级大的模拟，结果发现，最佳方法是空间换时间？
对于每个n直接把这个数字向后移，然后开两倍数组就够了。
无语无语。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
using namespace std;
int n;
int p[1000005*2],t;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
p[i]=i;
for(int i=2;i<=n;i++)
{
int t=0;
for(int j=i-1;j<=i-1+n-1;j+=i)
swap(p[j],t);
p[i-1+n]=t;
}
for(int i=n;i<n+n;i++)
cout<<p[i]<<" ";
cout<<endl;
return 0;
}
|
T3 路灯
题目描述
一条平直的公路上有n个路灯，第ii个路灯的坐标是ai。小A需要把其中的k个点亮，使得每个路灯与距离最近的被点亮的路灯的距离和最小。求这个最小值。
输入格式
第1行2个正整数n,k。
接下来n行，每行一个整数ai，表示第i个路灯的坐标，保证ai是严格单调递增的。
输出格式
1行1个数表示答案。
样例数据
input
output
样例解释
点亮第2、4、6个路灯，每个路灯与距离最近的被点亮的路灯的距离和是8。可以证明没有比8更小的方案。
数据规模与约定
对于 30% 的数据，k=2。
对于 50% 的数据，n≤10。
对于 100% 的数据，1≤n≤200，1≤k≤30，k≤n，|ai|≤50000。
时间限制：1s
空间限制：512MB
思路
动态规划！
这套题目非常有意思，和第一题很像，只是少了一个小字，虽然只是少了一个小字，但是题目的解法完完全全的不同了，这道题需要使用的是动态规划
f[i][j]表示前i个小路灯点亮了j个，且第j个是点亮的，之前每个路灯与距离最近的被点亮的路灯的距离的和最小是多少
状态转移方程为
f[i][j]=min(f[r][j−1]+h(r,i)))，0<=r<i
h(i,j)代表的是第i个路灯到第j个路灯中的一个路灯k，到i路灯和j路灯中的最小值的和，存的就是到i和j距离总和最近的那一个
这样就可以满分了
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 210
#define M 1010
using namespace std;
int n,m,a[N];
int f[N][N],dp[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
a[0]=-1e9;
a[n+1]=1e9;
for(int i=0;i<=n;i++) for(int j=i+1;j<=n+1;j++) for(int k=i;k<=j;k++) f[i][j]+=min(a[k]-a[i],a[j]-a[k]);
memset(dp,0x3f,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=0;k<i;k++) dp[i][j]=min(dp[i][j],dp[k][j-1]+f[k][i]);
int ans=1e9;
for(int i=1;i<=n;i++) ans=min(ans,dp[i][m]+f[i][n+1]);
cout<<ans<<endl;
return 0;
}
|
T4 匹配
题目描述
给定一颗n个点n−1条边的树，每条边的长度都是1，i号节点的权是ai。如果三个节点两两在树上的距离都是4，那么称这三个节点构成了一个“组合”，一个“组合”的权是三个节点的权的乘积。求所有“组合”的权的和。
输入格式
第1行一个整数n。
接下来1行n个正整数，第ii个数表示ai。
接下来n−1行，每行2个正整数u,v，表示u，v间有一条边。保证输入的是一颗树。
输出格式
1行1个数表示答案。
样例数据
input
1
2
3
4
5
6
7
8
| 7
1 2 3 4 5 6 7
1 2
2 3
1 4
4 5
1 6
6 7
|
output
样例解释
只有(3,5,7)构成了“组合”，这个“组合”的权是105。
数据规模与约定
对于 20% 的数据，1≤n≤100。
对于 40% 的数据，1≤n≤20001≤n≤2000。
对于 100% 的数据，1≤n≤100000，1≤ai≤10，1≤u,v≤n。
时间限制：1s
空间限制：512MB
思路
这个真的不会
引用qbxt：
可以发现三个点是“组合”当且仅当与中间点距离为2且互相在中间点的不同子树中
一次树形dp求出每个点子节点的权的和f
对于一个中间点，它的贡献就是每个子节点（包括父亲）的f值集合中任取3个的乘积的和
代码
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define dd double
#define ll long long
#define N 1000010
#define M 1010
using namespace std;
int n,u,v,a[N];
int s,to[N*2],ne[N*2],pre[N];
int fa[N],f[N];
ll ans;
void add(int u,int v)
{
to[++s]=v;
ne[s]=pre[u];
pre[u]=s;
}
void dfs(int k)
{
for(int i=pre[k];i;i=ne[i])
if(to[i]!=fa[k])
{
int x=to[i];
fa[x]=k;
dfs(x);
f[k]+=a[x];
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
dfs(1);
for(int i=1;i<=n;i++)
{
ll s1=a[fa[fa[i]]];
if(i>1) s1+=f[fa[i]]-a[i];
ll s2=0;
for(int j=pre[i];j;j=ne[j])
if(to[j]!=fa[i])
{
int x=to[j];
ans+=s2*f[x];
s2+=s1*f[x];
s1+=f[x];
}
}
cout<<ans<<endl;
return 0;
}
|
总结
通过这四道题，考察了二分，找规律？模拟？，动态规划和树上的几个算法，最后一个没看懂。明白了可以用空间换时间，这样非常值得。
