ABC-257

D – Jumping Takahashi 2(图论、最短路变形)

Problem

有/(N/)个跳床在二维平面上，第/(i/)个跳床的坐标是/(X_i,Y_i/)，弹跳力是/(P_i/)，你有一个初始能力值/(S/),从一个跳床/(i/)可以跳到另一个跳床/(j/)的条件是/(SP_i/ge |X_i-X_j|+|Y_i-Y_j|/)，现在要求你选择一个点起跳，使得可以从这个点跳到其他所有点时的最小的/(S/)

Solve

条件可以从上取整转换，然后每两个点之间就有一个权值。/(/lceil /frac{x}{y} /rceil=/frac{x+y-1}{y}/)

题意转换后就是要给定一个有向图，求从哪个点出发可以到达其他所有点，并且使得经过路径上的最大边最小

由于这是有向图，并且要求从一个点出发可以到达其他点，所以不能直接求最小生成树，利用迪杰斯特拉的思想去对边进行松弛操作即可

Code

package main
import(
	"bufio"
	."fmt"
	"os"
)
func min(a,b int64)int64{
	if a>b{
		return b
	}else{
		return a
	}
}
func max(a,b int64)int64{
	if a>b{
		return a
	}else{
		return b
	}
}
func abs(a int64)int64{
	if a<0{
		return -a
	}else {
		return a
	}
}
func main(){
	in:=bufio.NewReader(os.Stdin)
	out:=bufio.NewWriter(os.Stdout)
	defer out.Flush()
	const N int=205
	var n int
	Fscan(in,&n)
	x,y,p:=make([]int64,n+1),make([]int64,n+1),make([]int64,n+1)
	for i:=1;i<=n;i++{
		Fscan(in,&x[i],&y[i],&p[i])
	}
	var dist [N][N]int64
	for i:=1;i<=n;i++{
		for j:=1;j<=n;j++{
			dist[i][j]=(abs(x[i]-x[j])+abs(y[i]-y[j])+p[i]-1)/p[i]
		}
	}
	const inf int64=1e18
	vis:=make([]bool,n+1)
	f:=make([]int64,n+1)
	ans:=inf
	for s:=1;s<=n;s++{
	    for j:=1;j<=n;j++{
			vis[j]=false
			f[j]=inf
		}
		f[s]=0;
		var res int64
		for i:=1;i<=n;i++{
			x:=-1
			for j:=1;j<=n;j++{
				if(!vis[j]&&(x==-1||f[j]<f[x])){
					x=j
				}
			}
			vis[x]=true
			res=max(res,f[x])
			for j:=1;j<=n;j++{
				f[j]=min(f[j],dist[x][j])
			}
		}
		for i:=1;i<=n;i++{
			ans=min(ans,res)
		}
	}
	Fprintln(out,ans)
}

E- Addition and Multiplication 2

Problem

一开始有一个数/(x=0/)，现在有/(N/)元，可以进行以下操作若干次：选择一个整数/(i/)(/(1/le i/le 9/))，并且支付/(C_i/)元去把/(x/)替换成/(10x+i/)。求出/(x/)最大可能的值

Solve

一个贪心的思想，对于当前选择的/(i/),肯定越大越好，但会出现一种情况，就是你选择这个大的可能会使得钱减少的比较多，从而损失较多的操作机会，然而一次操作机会可以扩大/(10/)倍，显然多一次操作机会会比当前选择最大的更优。所以考虑在选择当前最大的时候，判断当前的钱数是否会使得操作次数减少，直到找到不会减少的/(i/)为止，此时可以保证较大且不会减少扩大次数。至于如果快速判断当前选择会不会使得操作次数不优，可以利用背包的方法，求出对于每个面值的钱可以操作的最大次数即可。

Code

package main
import(
	"bufio"
	."fmt"
	"os"
)
func max(a,b int)int {
	if a>b{
		return a
	}else{
		return b
	}
}
func main(){
	in:=bufio.NewReader(os.Stdin)
	out:=bufio.NewWriter(os.Stdout)
	defer out.Flush()
	var n int
	Fscan(in,&n)
	c:=make([]int,10)
	for i:=1;i<=9;i++{
		Fscan(in,&c[i])
	}
	f:=make([]int,n+1)
	for i:=1;i<=9;i++{
		for j:=c[i];j<=n;j++{
			f[j]=max(f[j],f[j-c[i]]+1)
		}
	}
	for f[n]>0{
		x:=9
		for c[x]>n || f[n-c[x]]!=f[n]-1{
			x--
		}
		Fprint(out,x)
		n-=c[x]
	}
}

F – Teleporter Setting

Problem

给定/(N/)个点/(M/)条边的无向图，但其中一条边的一个端点因为某种原因不知道具体是哪个点，记未知的点为/(0/)，假设丢失的点为/(u/)，假设/(u/)取/(1,/cdots,N/)，对于每种情况求出从/(1/)到/(N/)的最短路，如果不可以抵达，输出/(-1/)

Solve

在原图上求一遍从/(1/)出发的最短路，再求一遍从/(N/)出发的最短路。

记/(d1_i/)为从/(1/)出发到点/(i/)的最短路，/(dn_i/)为从/(n/)出发到点/(i/)的最短路

假设未知点/(u/)取/(i/)，那么答案就是/(min(d1_n,d1_0+dn_i,d1_i+dn_0)/)，后面可以看做点/(0/)和点/(i/)之间的距离为/(0/)

Code

package main
import (
	."fmt"
    "bufio"
	"os"

)
func min(a ,b int)int{
    if a>b{
		return b
	}else{
		return a
	}
}
func main(){
	in:=bufio.NewReader(os.Stdin)
	out:=bufio.NewWriter(os.Stdout)
	defer out.Flush()
	const inf int=1e9
	var n,m int
	Fscan(in,&n,&m)
	e:=make([][]int,n+1)
	for i:=1;i<=m;i++{
		var u,v int
		Fscan(in,&u,&v)
		e[u]=append(e[u],v)
		e[v]=append(e[v],u)
	}
	d1,d2:=make([]int,n+1),make([]int,n+1)
	hh,tt:=0,0
	q:=make([]int,n+1)
	bfs:=func(s int,d []int){
	   for i := range d{
		d[i]=inf
	   }
	   hh,tt=0,0
	   vis:=make([]int,n+1)
       q[tt]=s
	   tt=tt+1
	   d[s]=0
	   for hh<tt{
          u:=q[hh]
		  hh=hh+1
		  if vis[u]>0{
			continue
		  }
		  vis[u]=1
		  for _,v := range e[u] {
			if d[v]>d[u]+1{
				d[v]=d[u]+1
				q[tt]=v
				tt=tt+1
			}
		  }
	   }
	}
	bfs(1,d1)
	bfs(n,d2)
	for i:=1;i<=n;i++{
		res:=min(d1[n],min(d1[0]+d2[i],d1[i]+d2[0]));
		if res>=inf{
			res=-1
		}
		Fprint(out,res," ")
	}
}

G – Prefix Concatenation(Z-算法、DP)

Problem

洛谷原题(P8112 [Cnoi2021]符文破译)

给定一个串/(T/)和/(S/)，问/(S/)是否可以写成/(T/)的若干个前缀相加，若可以，求出最少的前缀个数，否则输出/(-1/)

Solve

/(Z-algorithm/)可以求出字符串/(S/)以下标/(i/)开始的后缀和/(S/)的最长公共前缀

考虑先求出/(S/)的每个后缀与/(T/)的最大前缀，可以令/(A=T+’/#’+S/)，使用 1 次/(Z-algorithm/)求出。

然后考虑/(dp/)，令/(dp_i/)表示/(S/)的前/(i/)位可以由/(T/)最少的前缀组成的个数。

假设处理到了第/(i/)位，假设第/(i/)位可以匹配的最长前缀为/(k=z[n+1+i]/)，那么显然/(dp_i,/cdots,dp_{i+k-1}/)都是相等的，考虑/(i+1/)位，如果/(i+1+z[n+1+i+1]>i+k-1/)了，那么由于/(i+k-1/)后面可能会无法匹配，那么能在前面匹配过来就在前面匹配匹配过来肯定是最好的，所以每次记录一个每次可以匹配到的最远距离来更新即可。

Code

由于 Go 的快读使用bufio使用虚拟内存过多，这份 go 代码在洛谷上会 MLE。

package main

import(
	"bufio"
	."fmt"
	"os"
)
func min(a,b int)int{
	if(a>b){
		return b
	}
	return a
}
func max(a,b int)int{
	if(a>b){
		return a
	}else{
		return b
	}
}

const N int =1e6+10
const inf int=1e9
var z,dp [N]int
func main(){
	in:=bufio.NewReader(os.Stdin)
	out:=bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var s,t []byte
    Fscan(in,&s,&t)
	n,m:=len(s),len(t)
	var a []byte
	for i:=0;i<n;i++{
		a=append(a,s[i])
	}
	a=append(a,'#')
	for i:=0;i<m;i++{
		a=append(a,t[i])
	}
    // Fprintf(out,"%s",a)
	for i,l,r:=1,0,0;i<n+m+1;i++{
		if i<=r{
			z[i]=min(r-i+1,z[i-l]);
		}
		for i+z[i]<n+m+1 && a[z[i]]==a[i+z[i]]{
			z[i]++
		}
		if i+z[i]-1>r{
			l=i
			r=i+z[i]-1
		}
	}
	for i:=0;i<=m;i++{
		dp[i]=inf
	}
	dp[0]=0
	var mx int=0
	for i:=0;i<m;i++{
        x:=dp[i]
		if x>m {
			continue
		}
		k:=z[n+i+1]
		for j:=mx+1;j<=i+k;j++{
             dp[j]=x+1
		}
      mx=max(mx,i+k)
	}

    if dp[m]<inf{
		Fprintln(out,dp[m])
	}else{
		Fprintln(out,-1)
	}
}

Ex – Dice Sum 2(优化?)

Problem

Solve

Code