USST练习赛10补题

第一次组队参赛,再多做三题就能AK了,可惜自己做题不够快,py也不熟练,总是要调好久,还是太蒻了OTZ

E. 虚无的后缀

题意: 从n个数字中选出k个数字,使得他们乘积后缀0个数最多

算法: 背包dp(贪心被群里大佬 X 了,我太难了)

思路(错误✖): 显然能产生后缀0的乘积只有2和5相乘,因此考虑先将所有数的因子中2和5个数求出,那么题意就转化为:选出k个数,使得$\min(sum2,sum5)$最大,其中$sum2、sum5$分别为这k个数的因子中2和5的总数。可以发现,正向求这个值不太好想,我们可以转换一下思路,逆向求,即先将所有的数选上,然后贪心地不断删去$n-k$个对答案造成影响最小的数,最后的$\min(sum2,sum5)$就是答案

思路(正确✔):定义状态转移方程$dp[i][j][m]$在前$i$个数中选取$j$个数,其中因子为5的个数为$m$时的因子2的最多的个数,发现m最多也就五千多点的样子,可以滚动数组压成二维的跑一遍背包dp,最后求出$\max(\min(dp[j][m],m))$即可

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
int n,k,dp[205][5205],sum5,ans;
pair<int,int> ha[205];
int main(){
read(n),read(k);
ll x;
rep(i,1,n){
read(x);
while(x%2==0){
x/=2;
ha[i].first++;
}
while(x%5==0){
x/=5;
ha[i].second++;
}
}
memset(dp,-0x3f,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=k;j>=1;j--){
for(int m=5200;m>=ha[i].second;m--){
dp[j][m]=max(dp[j][m],dp[j-1][m-ha[i].second]+ha[i].first);
}
}
}
for(int i=0;i<=5200;i++){
ans=max(ans,min(dp[k][i],i));
}
printf("%d\n",ans);
return 0;
}

J. 聚会

题意:x轴上有n个人,每个人坐标为$x_i$,同时以速度1/s往0点移动,现在可以在两点建立传送门,问所有人都到达0点时所花最少时间

算法:二分答案

思路:对x排序,然后考虑二分答案,即每次二分出一个最短时间mid,就遍历一遍x数组,找到其中第一个绝对值大于mid的点$x_p$,将传送门的一端设置在$pos=x_p+mid$处(因为这样设置能够给后面的点产生最大的贡献),那么之后如果找到绝对值大于mid的点$x_q$,就判断是否有$|x_q-pos|>mid$,如果是,则这个二分的最短时间mid无法达到,需要扩大这个mid,否则可以缩小这个mid

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
int _,n;
ll x[maxn];
inline bool check(ll k){
ll pos=-1ll<<60;
rep(i,1,n){
if(abs(x[i])>k){
if(pos==-1ll<<60) pos=x[i]+k;
else if(abs(pos-x[i])>k) return false;
}
}
return true;
}
int main(){
for(scanf("%d",&_);_;_--){
read(n);
rep(i,1,n) read(x[i]);
sort(x+1,x+1+n);
ll l=-1ll<<60,r=1ll<<60;
ll ans;
while(l<=r){
ll mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%lld\n",ans);
}
return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!