2023年百度之星程序设计竞赛初赛1题解java

成为她曾经期待的样子 / 2023-08-08 / 原文

每次出题都出其不意---->群友蓝桥国三ac一道题

根据官方的视频题解整理

依据难度的划分

第五题：促销糖果

分析：从答案出发想吃K个糖果，必定有k个糖纸，考虑换购，则有一张糖纸是不可以换的（因为你必须至少要买一颗糖果）则换购的数量为（k-1）/减去换购的糖果则是买的糖果

package Li2209;
import java.util.Scanner;
import java.math.*;
import java.util.ArrayList;
public class Main{
    static ArrayList<Integer>list=new ArrayList<>();
    public static void main(String[]args)
    {
        ArrayList<Integer>ans=new ArrayList<>();
        Scanner input=new Scanner(System.in);
        int t=input.nextInt();
        while(t-->0)
        {
            int p=input.nextInt();
            int k=input.nextInt();
            k-=(k-1)/p;
            ans.add(k);
        }
        for(int i:ans)
        {
            System.out.println(i);
        }
    }
}

第一题公园

思路：T 和F汇合与点g然后一起到达N,用三段dfs.然后枚举三段值求最小

package Li2209;
import java.util.Scanner;
import java.math.*;
import java.util.ArrayList;
import java.util.Arrays;
public class Main{
    static int a,b,c;
    static int s1,s2,n,m;
    static ArrayList<Integer>[]son=new ArrayList[40010];
    static int [][]dis=new int[3][40010];
    static int[]que=new int[40010];
    public static void main(String[]args)
    {
        Scanner input=new Scanner(System.in);
        a=input.nextInt();
        b=input.nextInt();
        c=input.nextInt();
        s1=input.nextInt();
        s2=input.nextInt();
        n=input.nextInt();
        m=input.nextInt();
    
        for(int i=1;i<=m;i++)
        {
            int u=input.nextInt();
            int v=input.nextInt();
            son[u].add(v);
            son[v].add(u);
        }
        calc(dis[0],s1);
        calc(dis[0],s2);
        calc(dis[0],n);
        long ans=0;
        for(int i=0;i<n;i++)
        {
            if(dis[0][i]!=-1&&dis[1][i]!=-1&&dis[2][i]!=-1)
            {
                ans=Math.min(ans, 1l*dis[0][i]*a+1l*dis[1][i]*b+1l*dis[2][i]*(a+b-c));
            }
        }
        long op=ans==0? -1:ans;
        System.out.println(op);
        
        
        
    }
    public static void calc(int []dis,int s)
    {
        int tall=1;
        Arrays.fill(dis, -1);
        dis[s]=0;
        que[1]=s;
        for(int i=1;i<=tall;i++)
        {
            int cur=que[i];
            for(int  v: son[cur])
            {
                if(dis[v]==-1)
                {
                    dis[v]=dis[cur]+1;
                    que[++tall]=v;
                }
            }
            
        }
    }
    
}