【蓝桥杯第十三届C++B组】真题训练(5/8)-java写法-创新互联

目录

成都创新互联是专业的湖里网站建设公司,湖里接单;提供成都做网站、网站设计,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行湖里网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!

4402.刷题统计 - 数学模拟

4403. 修剪灌木 - 思维

4404. X 进制减法 - 进制运算 + 贪心

4405. 统计子矩阵 - 前缀和 + 双指针

1、一维前缀和

2、二维前缀和

4406. 积木画 - dp

1、找规律dp

2、状态压缩DP


4402.刷题统计 - 数学模拟

4402. 刷题统计 - AcWing题库

思路:

共n题,周一到周五5天刷a题,周六到周日2天刷b题

则一周7天刷5*a+2*b题

res+=n/(5*a+2*b)*7  //整周

剩下的题不到一周就能刷完

开辟一个数组存入一周的刷题数 day={a,a,a,a,a,b,b}

看最后还要x天能刷完

res+=x

import java.util.*;

class Main
{
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        long a=sc.nextLong(),b=sc.nextLong(),n=sc.nextLong();
        long x=a*5+b*2;
        long res=n/x*7;
        n%=x;
        long[] day={a,a,a,a,a,b,b};
        for(int i=0;n>0;i++)
        {
            n-=day[i];
            res++;
        }
        System.out.print(res);
    }
}

4403. 修剪灌木 - 思维

4403. 修剪灌木 - AcWing题库

思路:

灌木先长高再被修剪

比如第4棵,它刚刚被修剪完时高度为0

爱丽丝去修剪3时,其高度为1

去修剪2时,其高度为2

去修剪1时,其高度为3

去修剪2时,其高度为4

去修剪3时,其高度为5

因为先长高再修剪,所以在爱丽丝修剪4之前,4先长到大高度6 

所以res就是max(i-1,n-i)*2

import java.util.*;

class Main
{
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        for(int i=1;i<=n;i++)
        {
            int x=Math.max(n-i,i-1);
            System.out.println(2*x);
        }
    }
}

4404. X 进制减法 - 进制运算 + 贪心

4404. X 进制减法 - AcWing题库

思路:

根据题目要求,X进制定义:每一位进制都不同

比如X进制数321  高位进制为8 第二位进制为10 低位进制为2

321_{X}= 3×10×2+2×2+1 = 65

解释:

  • 十位的2由个位进位2次得到,所以是2×2;
  • 百位的3由十位进位3次得到,十位又由个位进位得到,所以是3×10×2

由此可以得出:

  • X进制中第 i 位的权重是所有 j (0 ≤ j< i)位进制的乘积
  • 而转化为十进制的结果为:(每一位数×权重)之和
  • 所以要让A-B最小,也就是让权重最小,也就是让每一位的进制在合法的情况下最小

题目保证A≥B,A和B的位数可能不同,需要个位数对齐,高位补零

所以我们逆向存储,低位在前,高位在后

让每一位的进制在合法的情况下最小,合法情况:进制数≥该位上的数 且 不低于2进制

因此 每一位上的最小进制数=max(a[i]+1,b[i]+1,2)

然后计算每一位的权重,其中第一位权重为1,其余位权重等于之前位的权重之积

接着计算A值和B值(位数×权重 之和),输出A-B

import java.util.*;

class Main
{
    static int N=100010;
    static int mod=1000000007;
    static long[] a=new long[N],b=new long[N],jin=new long[N],w=new long[N]; //jin存每一位数的进制 w存每一位数的权重
    
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int ma=sc.nextInt();
        for(int i=ma;i>=1;i--) a[i]=sc.nextInt(); //若两数位数不同 逆序储存-低位在前高位在后能保证个位对齐
        int mb=sc.nextInt();
        for(int i=mb;i>=1;i--) b[i]=sc.nextInt();
        
        int m=Math.max(ma,mb);
        
        for(int i=1;i<=m;i++)
            jin[i]=Math.max(Math.max(a[i]+1,b[i]+1),2); //在合法范围内(进制数应该>该位上的数)的最小进制 最小进制不能低于2 

        w[1]=1; //第一位的权重为1
        for(int i=2;i<=m;i++) w[i]=w[i-1]*jin[i-1]%mod; //计算每一位的权重
        
        long A=0,B=0;
        for(int i=1;i<=ma;i++) A=(A+a[i]*w[i])%mod;
        for(int i=1;i<=mb;i++) B=(B+b[i]*w[i])%mod;
        
        System.out.print((A-B+mod)%mod);
    }
}

4405. 统计子矩阵 - 前缀和 + 双指针

4405. 统计子矩阵 - AcWing题库

1、一维前缀和
import java.util.*;

class Main
{
    static int N=510;
    static int[][] s=new int[N][N];
    
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt(),k=sc.nextInt();
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++) 
            {
                s[i][j]=sc.nextInt();
                s[i][j]+=s[i-1][j]; //计算纵向的前缀和
            }
        
        long res=0;
        for(int i=1;i<=n;i++) //上界
            for(int j=i;j<=n;j++) //下界
                for(int l=1,r=1,sum=0;r<=m;r++) //双指针求左右两列
                {
                    sum+=s[j][r]-s[i-1][r];
                    while(sum>k)
                    {
                        sum-=s[j][l]-s[i-1][l];
                        l++;
                    }
                    res+=r-l+1;
                }
        System.out.print(res);
    }
}
2、二维前缀和

import java.util.*;

class Main
{
    static int N=510;
    static int[][] s=new int[N][N];
    
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt(),k=sc.nextInt();
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++) 
            {
                s[i][j]=sc.nextInt();
                s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1]; 
            }
        
        long res=0;
        for(int i=1;i<=n;i++) //上界
            for(int j=i;j<=n;j++) //下界
                for(int l=1,r=1;r<=m;r++) //双指针求左右两列
                {
                    while(l<=r&&s[j][r]-s[j][l-1]-s[i-1][r]+s[i-1][l-1]>k) l++;
                    if(l<=r) res+=r-l+1;
                }
        System.out.print(res);
    }
}

4406. 积木画 - dp

4406. 积木画 - AcWing题库

1、找规律dp

import java.util.*;

class Main
{
    static int N=10000010;
    static int mod=1000000007;
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long[] dp=new long[N];
        dp[1]=dp[0]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++) dp[i]=(dp[i-1]*2+dp[i-3])%mod;
        System.out.print(dp[n]);
    }
}
2、状态压缩DP

定义 f[i][j]为已经摆好前i-1列(前i-1列不留空),且第i列状态为j的方案数

  • j=0时,表示第i列上下均未摆积木
  • j=1时,表示下面摆了,上面没摆
  • j=2时,表示上面摆了,下面没摆
  • j=3时,表示上下均摆放

因此,答案为 f[n][3]

先考虑如何初始化

当n=0时,可以视为已经上下均摆的情况,f[0][3]=1

然后考虑如何进行状态转移

  • 当j=0时,即第i列上下均未摆放,这种情况就要求第i-1列上下均摆好

所以f[i][0]=f[i-1][3]

  • 当j=1时,即第i列上面未摆,下面摆放,此时有两种情况:

第一种如下图:f[i-1][0]

第二种如下图:f[i-1][2]

所以 f[i][1]=f[i-1][0]+f[i-1][2]

  • 当j=2时,即上面摆了,下面没摆,此时也有两种情况

第一种如下图:f[i-1][0]

第二种如下图:f[i-1][1]

所以f[i][2]=f[i-1][0]+f[i-1][1]

  • 当j=3时,即上下全摆,有四种情况:

第一种如下图:f[i-1][3]

第二种如下图:f[i-1][1]

第三种如下图:f[i-1][2]

第四种如下图:f[i-1][0]

所以f[i][3]=f[i-1][0]+f[i-1][3]+f[i-1][1]+f[i-1][2]

import java.util.*;

class Main
{
    static int N=10000010;
    static int mod=1000000007;
    static int[][] f=new int[N][4];
    
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        
        f[0][3]=1;
        for(int i=1;i<=n;i++) 
        {
            f[i][0]=f[i-1][3];
            f[i][1]=(f[i-1][0]+f[i-1][2])%mod;
            f[i][2]=(f[i-1][0]+f[i-1][1])%mod;
            f[i][3]=(((f[i-1][0]+f[i-1][1])%mod+f[i-1][2])%mod+f[i-1][3])%mod;
        }
        System.out.print(f[n][3]);
    }
}

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧

网站题目:【蓝桥杯第十三届C++B组】真题训练(5/8)-java写法-创新互联
网站路径:https://www.cdcxhl.com/article24/hhece.html

成都网站建设公司_创新互联,为您提供关键词优化域名注册营销型网站建设外贸建站用户体验品牌网站设计

广告

声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联

h5响应式网站建设