牛客周赛 Round 53 Java题解
推导略，答案总是0.5，时间复杂度O(1)
public class Main{
public static void main(String args[]){
System.out.println("0.5");
}
}
对应位置的字母要么正着移动，要么反着移动，取较小的距离，时间复杂度O(len(s))
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
String s=sc.next();
int ans=0;
for(int i=0,j=s.length()-1;i<j;i++,j--){
int d=Math.abs(s.charAt(i)-s.charAt(j));
ans+=Math.min(d,26-d);
}
System.out.println(ans);
}
}
容易发现，第1、3中操作只会减少0或者1的数量，从而减少了操作2的次数，因此只需要考虑最多能多少次操做2就行了，时间复杂度O(n)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
sc.next();
String s=sc.next();
sc.next();
int y=sc.nextInt(),ans=0;
Stack<Character> stack=new Stack<>();
for(char c:s.toCharArray()){
if(c=='1'){
if(!stack.isEmpty()&&stack.peek()=='0'){
stack.pop();
ans++;
}
else{
stack.push('1');
}
}
else{
stack.push('0');
}
}
System.out.println(Math.min(ans,y));
}
}
分组背包的经典题，这里是把求得东西变成了分数的可能性，其实道理一样，时间复杂度O(nm*max(target))
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),m=sc.nextInt(),a[][]=new int[n][m],ans=(int)1e9;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
a[i][j]=sc.nextInt();
}
}
int target=sc.nextInt();
boolean has[]=new boolean[5005];
has[0]=true;
for(int b[]:a){
boolean temp[]=new boolean[5005];
for(int c:b){
for(int i=5000;i>=c;i--){
if(has[i-c]){
temp[i]=true;
}
}
}
has=temp;
}
for(int i=0;i<=5000;i++){
if(has[i]){
ans=Math.min(ans,Math.abs(target-i));
}
}
System.out.println(ans);
}
}
容易想到，较大的mex可以的得到的时候，总可以消除最大数得到较小的mex，因此具有二段性，且较大的数字出现的机会较小，因此验证小于等于某个数的所有数是否可能都出现的时候需要从大到小，代码寻找出现的时候利用的是数组计数，时间复杂度O(Tnlogn*log(max(a))
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++){
int n=sc.nextInt(),a[]=new int[n],l=0,r=n-1;
for(int j=0;j<n;j++){
a[j]=sc.nextInt();
}
while(l<r){
int mid=(l+r)>>1;
if(check(a,mid)){
l=mid;
}
else{
r=mid-1;
}
if(l==r-1){
if(check(a,r)){
l=r;
}
break;
}
}
System.out.println(l+1);
}
}
static boolean check(int a[],int max){
int count[]=new int[max+1];
for(int b:a){
while(b>max){
b>>=1;
}
count[b]++;
}
for(int i=max,j=max;i>=0;i--){
while(j>i){
while(count[j]==0){
j--;
}
if(j>i){
count[j/2]+=count[j];
j--;
}
}
while(count[j]==0){
j--;
}
if(j<i){
return false;
}
count[j]--;
}
return true;
}
}
答案的上界是不运用魔法所用的时间，那么用了魔法，枚举禁止的方向，宽搜到X的位置后停止搜索，否则继续宽搜，需要从起点和终点双向搜素出到每个X的距离，之后再进行统计，时间复杂度O(nm)
import java.util.*;
public class Main{
static int move[][]={{0,1},{1,0},{0,-1},{-1,0}};
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),m=sc.nextInt();
char a[][]=new char[n][];
for(int i=0;i<n;i++){
a[i]=sc.next().toCharArray();
}
int ans=find(n,m,0,0,a,-1)[n-1][m-1];
for(int i=0;i<4;i++){
int dis1[][]=find(n,m,0,0,a,i),dis2[][]=find(n,m,n-1,m-1,a,(i+2)%4);
for(int j=0;j<n;j++){
for(int k=0;k<m;k++){
ans=Math.min(ans,dis1[j][k]+dis2[j][k]);
}
}
}
System.out.println(ans<n*m?ans:-1);
}
static int[][] find(int n,int m,int p1,int p2,char a[][],int forbid){
int dis[][]=new int[n][m];
for(int i=0;i<n;i++){
Arrays.fill(dis[i],(int)1e9);
}
dis[p1][p2]=0;
Queue<int[]> q=new LinkedList<>();
q.add(new int[]{p1,p2});
while(!q.isEmpty()){
int b[]=q.poll();
for(int i=0;i<4;i++){
if(i==forbid){
continue;
}
int x=b[0]+move[i][0],y=b[1]+move[i][1];
if(x>=0&&x<n&&y>=0&&y<m){
int d=dis[b[0]][b[1]]+1;
if(dis[x][y]>d){
dis[x][y]=d;
if(a[x][y]=='.'){
q.add(new int[]{x,y,d});
}
}
}
}
}
return dis;
}
}
见注释，时间复杂度O(n)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),maxDis[]=new int[n+5],maxPath[]=new int[n+5],ans[]=new int[n+5];
//maxPath[i]记录的是以i为根节点的树的直径长度
//maxDis[i]记录的是以i为根节点的树的所有子节点中，距离i的最远的距离
List<Integer> path[]=new List[n+5];
for(int i=1;i<=n;i++){
path[i]=new ArrayList<>();
}
for(int i=0;i<n-1;i++){
int u=sc.nextInt(),v=sc.nextInt();
path[u].add(v);
path[v].add(u);
}
find1(1,ans,maxPath,maxDis,path,new boolean[n+5]);
find2(1,0,0,ans,maxPath,maxDis,path,new boolean[n+5]);
for(int i=1;i<=n;i++){
System.out.println(ans[i]);
}
}
static int find1(int k,int ans[],int maxPath[],int maxDis[],List<Integer> path[],boolean has[]){
//本方法返回的是maxDis[k]，同时处理的是剪掉每一个子节点后，子树的最大直径
//更新每一个maxPath，同时用子节点更新ans
has[k]=true;
int dis1=0,dis2=0;
for(int a:path[k]){
if(!has[a]){
int d=find1(a,ans,maxPath,maxDis,path,has);
ans[k]=Math.max(ans[k],maxPath[a]);
maxPath[k]=Math.max(maxPath[k],maxPath[a]);//不经过k的最长路径
//经过k的最长路径是距离k最远的两个点的距离之和
if(d+1>dis1){
dis2=dis1;
dis1=d+1;
}
else if(d+1>dis2){
dis2=d+1;
}
}
}
//经过k的最长路径
maxPath[k]=Math.max(maxPath[k],dis1+dis2);
return maxDis[k]=dis1;
}
static void find2(int k,int p1,int p2,int ans[],int maxPath[],int maxDis[],List<Integer> path[],boolean has[]){
//本方法处理的是，从k子树下边剪断某个边，也就是边连接的子节点a被去掉后，上半部分的最大直径（所以更新的是a的答案值）
//需要算出经过k的向下的前两个最大距离，以及向k的父节点方向的最大距离
has[k]=true;
//需要从k的父节点p传下来：1、p以及上的部分，不含k这一支的最大直径p1（可能新加k点上，也可能在旁支的子树）；2、经过p的最大路径的值，+1后用于作为k的最大向上路径值p2
int dis1=0,dis2=0,dis3=0,path1=0,path2=0;
List<Integer> children=new ArrayList<>();
for(int a:path[k]){
if(!has[a]){
ans[a]=Math.max(ans[a],p1);
children.add(a);
if(dis1<maxDis[a]+1){
dis3=dis2;
dis2=dis1;
dis1=maxDis[a]+1;
}
else if(dis2<maxDis[a]+1){
dis3=dis2;
dis2=maxDis[a]+1;
}
else if(dis3<maxDis[a]+1){
dis3=maxDis[a]+1;
}
if(maxPath[a]>path1){
path2=path1;
path1=maxPath[a];
}
else if(maxPath[a]>path2){
path2=maxPath[a];
}
}
}
for(int a:children){
//下面需要用经过k的最大直径dis来更新ans[a]
int arr[]=new int[]{p2,0,0};
if(dis1==maxDis[a]+1){
arr[1]=dis2;
arr[2]=dis3;
}
else if(dis2==maxDis[a]+1){
arr[1]=dis1;
arr[2]=dis3;
}
else{
arr[1]=dis1;
arr[2]=dis2;
}
Arrays.sort(arr);
int p3=Math.max(arr[1]+arr[2],path1==maxPath[a]?path2:path1);
ans[a]=Math.max(ans[a],p3);
find2(a,Math.max(p1,p3),Math.max(dis1==maxDis[a]+1?dis2:dis1,p2)+1,ans,maxPath,maxDis,path,has);
}
}
}
京公网安备 11010502036488号