蓝桥算法赛3——入门场

Xing_ke309

已于 2024-01-15 16:03:58 修改

阅读量445

点赞数 7

文章标签：算法 java 数据结构

于 2024-01-15 02:29:02 首次发布

本文链接：https://blog.csdn.net/Xing_ke/article/details/135584871

版权

题目地址

1.召唤坤神

$max\ \left \lfloor \frac{W_i+W_k}{W_j} \right \rfloor$

枚举i（1~n-2），从i+1开始到n-1找j，用while找到所有的峰谷为j，对于k则预处理j~n的max。

之后while找比当前i的值大的作为下一个i



import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int n=input.nextInt();
		int[] w=new int[n+1];
		int[] mx=new int[n+1];
		
		
		for(int i=1;i<=n;++i) {
			w[i]=input.nextInt();
		}
		mx[n]=w[n];
		for(int i=n-1;i>=1;--i)mx[i]=Math.max(mx[i+1], w[i]);
		long ans=0;
		for(int i=1;i<n-1;) {
			long res=w[i];
			long wj=w[i+1];
			for(int j=i+2;j<n;) {
				while(j<n&&w[j]<=wj) {
					wj=w[j];j++;
				}
				ans=Math.max(ans, (res+(long)mx[j])/wj);
				while(j<n&&w[j]>wj)j++;
			}
			i++;
			while(i<n-1&&w[i]<=res) {
				i++;
			}
		}
		System.out.println(ans);
	}
}

3.怪兽突击

考虑1~i只怪兽打满k次，代价为 $Sum[i]+min (a_i+b_i)*(k-i)$




import java.util.Arrays;
import java.util.Scanner;


public class Main{
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		
			int n=input.nextInt();
			int k=input.nextInt();
			long[] a=new long[n+1];
			long[] b=new long[n+1];
			for(int i=1;i<=n;++i) {
				a[i]=input.nextLong();
			}
			for(int i=1;i<=n;++i){
				b[i]=input.nextLong();
			}
			long[] mi=new long[n+1];
			mi[1]=a[1]+b[1];
			for(int i=2;i<=n;++i) {
				mi[i]=Math.min(mi[i-1], a[i]+b[i]);
			}
			long[] sum=new long[n+1];
			sum[1]=a[1];
			for(int i=2;i<=n;++i) {
				sum[i]=sum[i-1]+a[i];
			}
			long ans=Long.MAX_VALUE;
			for(int i=1;i<=Math.min(n, k);++i) {
				ans=Math.min(ans,sum[i]+(k-i)*mi[i]);
			}
			System.out.println(ans);
		
	}

}

5.奇怪的段

超时想法： $f[i][j]$ 表示第i组以j结尾，则转移为

$f[i][j]=max(f[i-1][t])+(Sum[i]-Sum[t])*p[i]$

要枚举j和k，复杂度接近 $O(n^2*k)$

正确做法： $f[i][j]$ 表示前i个数分了j段，则转移为

$f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i]*p[j]$

表示分j段，i是不是段头

$ans=f[n][k]$




import java.util.Arrays;
import java.util.Scanner;


public class Tx1{
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int n=input.nextInt();
		int k=input.nextInt();
		long[] a=new long[n+1];
		for(int i=1;i<=n;++i)a[i]=input.nextLong();
		long[] p=new long[n+1];
		for(int i=1;i<=k;++i)p[i]=input.nextLong();
		long[][] f=new long[n+1][k+1];//前i个数分j段
		for(int i=1;i<=n;++i)Arrays.fill(f[i], Long.MIN_VALUE);
		for(int i=1;i<=n;++i) {
			for(int j=1;j<=Math.min(i, k);++j) {
				f[i][j]=Math.max(f[i-1][j], f[i-1][j-1])+a[i]*p[j];
			}
		}
		System.out.println(f[n][k]);
		
	}

}

6.小蓝的反击

$ans=NumA-NumA\cup B=NumA-Num\ Lcm(A,B)$

枚举区间左端点 $i$ ，若 $i\rightarrow n$ 有区间满足条件，则通过二分找到最小的右端点 $j$ ， $ans+=n-j+1$

由于 $a$ 之间相乘得数爆 $long long$ ，所以对于每个 $a$ 统计 $A$ 和 $Lcm(A,B)$ 的相应素数因子个数，用前缀和优化，判断区间因子个数是否满足 $Sum[r][j]-Sum[l-1][j]>=num$

$Sum[i][j]$ 表示 $1\rightarrow i$ 区间内第 $j$ 个素数因子的个数

java被卡常，加速还过不了最后一个点

import java.io.*;
import java.util.HashMap;
import java.util.Scanner;
import java.util.StringTokenizer;


public class Main{
    public static void main(String[] args) throws IOException{
        
        AReader input=new AReader();
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        int n=input.nextInt();
        long A=input.nextLong();
        long B=input.nextLong();
        long lcm=A*B/gcd(A, B);

        Node[] afac=new Node[1000001];
        getFactor(A, afac);

        Node[] lfac=new Node[1000001];
        getFactor(lcm, lfac);

        int[] a=new int[n+1];
        for(int i=1;i<=n;++i) {
            a[i]=input.nextInt();
        }

        int[][] SumA=new int[n+1][afac[0].t+1];
        for(int i=1;i<=n;++i) {
            for(int j=1;j<=afac[0].t;++j) {
                int c=0;
                int x=a[i];
                while(x%afac[j].x==0) {
                    x/=afac[j].x;
                    c++;
                }
                SumA[i][j]=SumA[i-1][j]+c;
            }
        }
        long c1=0;
        for(int i=1;i<=n;++i) {
            if(check(i, n, afac, SumA)==false) break;
            int l=i,r=n;
            while(l<=r) {
                int mid=(l+r)>>1;
                if(check(i, mid, afac, SumA))r=mid-1;
                else l=mid+1;
            }
            c1+=n-l+1;
        }
        
        int[][] SumL=new int[n+1][lfac[0].t+1];
        for(int i=1;i<=n;++i) {
            for(int j=1;j<=lfac[0].t;++j) {
                int c=0;
                int x=a[i];
                while(x%lfac[j].x==0) {
                    x/=lfac[j].x;
                    c++;
                }
                SumL[i][j]=SumL[i-1][j]+c;
            }
        }
        long c2=0;
        for(int i=1;i<=n;++i) {
            if(check(i, n, lfac, SumL)==false) break;
            int l=i,r=n;
            while(l<=r) {
                int mid=(l+r)>>1;
                if(check(i, mid, lfac, SumL))r=mid-1;
                else l=mid+1;
            }
            c2+=n-l+1;
        }

        System.out.println(c1-c2);
    }

    public static long gcd(long a,long b) {
        long res;
        while(b!=0) {
            res=a%b;
            a=b;
            b=res;
        }
        return a;
    }

    public static void getFactor(long x,Node[] fac) {
        HashMap<Integer, Integer> cnt=new HashMap<Integer, Integer>();
        for(int i=2;i<=x/i;++i) {
            if(x%i==0) {
                while(x%i==0) {
                    if(cnt.get(i)==null)cnt.put(i, 1);
                    else cnt.put(i, cnt.get(i)+1);
                    x/=i;
                }
            }
        }
        if(x!=1)cnt.put((int)x, 1);
        int t=0;
        for(int i:cnt.keySet()) {
            int j=cnt.get(i);
            t++;
            fac[t]=new Node(i, j);
        }
        fac[0]=new Node(0, t);
    }

    public static boolean check(int l,int r,Node[] fac,int[][] Sum) {
        for(int j=1;j<=fac[0].t;++j) {
            int v=fac[j].t;
            if(Sum[r][j]-Sum[l-1][j]<v) return false;
        }
        return true;
    }

    static
    class AReader {
        private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        private StringTokenizer tokenizer = new StringTokenizer("");
        private String innerNextLine() {
            try {
                return reader.readLine();
            } catch (IOException ex) {
                return null;
            }
        }
        public boolean hasNext() {
            while (!tokenizer.hasMoreTokens()) {
                String nextLine = innerNextLine();
                if (nextLine == null) {
                    return false;
                }
                tokenizer = new StringTokenizer(nextLine);
            }
            return true;
        }
        public String nextLine() {
            tokenizer = new StringTokenizer("");
            return innerNextLine();
        }
        public String next() {
            hasNext();
            return tokenizer.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }

}
class Node{
    int x;
    int t;
    public Node(int X,int T) {
        x=X;
        t=T;
    }
}