首页 > 编程语言 >优化爬树的甲壳虫的解决程序

优化爬树的甲壳虫的解决程序

时间:2024-02-29 23:45:26浏览次数:24  
标签:甲壳虫 res sum long num 3398620 爬树 优化 mod

程序来源:来自我同学在做蓝桥杯的爬树的甲壳虫问题,问题是这样的有一只甲壳虫想要爬上一颗高度为n的树,它一开始位于树根高度为0,当它尝试从高度i-1爬到高度为i的位置时有Pi的概率会掉回树根, 求它从树根爬到树顶时, 经过的时间的期望值是多少。他的程序在大量的输入数据时,运行时间会不通过。
他的程序如下:

点击查看代码
import java.util.Scanner;

public class Main {
    static long qqpow(long num,long pow,long mod){
        long res=1;
        while (pow!=0){
            if(pow%2==1){
                res=res*num;
            }
            num*=num;
            res%=mod;
            num%=mod;
            pow>>=1;
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long sum=0;
        long mod=998244353l;
        for (long i = 0; i < n; i++) {
            long a=sc.nextInt();
            long b=sc.nextInt();
            sum=((sum+1)%mod*(b%mod))%mod;
            sum*=qqpow(b-a,mod-2,mod);
            sum%=mod;
        }
        System.out.println(sum);
    }
}
![](/i/l/?n=24&i=blog/3398620/202402/3398620-20240229192733566-265383298.png) ![](/i/l/?n=24&i=blog/3398620/202402/3398620-20240229192841117-1200396392.png) ![](/i/l/?n=24&i=blog/3398620/202402/3398620-20240229233313772-1069169371.png)

这里没有大量数据,进行演示,所以只简单的说明了,程序输入和输出结果的正确。
但是代码结构基本相同的c语言却不会超时,搜索过资料后发现是用Scanner输入的问题,Scanner输入是调用的api,所以时间会比c语言的直接输入浪费更多的时间,所以结局的办法就是用Streamtokenizer读取字符串,这个适用于超大规模整数型数据的读取,能缩短程序的时间,大大提高了程序的性能。
修改后的代码如下:

点击查看代码
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Main {
    static long qqpow(long num,long pow,long mod){
     long res=1;
     while (pow!=0){
         if((pow&1)==1){
             res*=num;
         }
         num*=num;
         num%=mod;
         res%=mod;
         pow>>=1;
     }
     return res;
    }
    public static void main(String[] args) throws Exception {
        long mod=998244353l;
        long sum=0;
        StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n=(int)in.nval;
        while (n-->0){
            in.nextToken();
            int a=(int) in.nval;
            in.nextToken();
            int b=(int)in.nval;
            sum=((sum+1)%mod*b%mod)%mod;
            sum*=qqpow(b-a,mod-2,mod);
            sum%=mod;
        }
        System.out.println(sum);
    }
}
![](/i/l/?n=24&i=blog/3398620/202402/3398620-20240229233036972-850339467.png) ![](/i/l/?n=24&i=blog/3398620/202402/3398620-20240229233417436-664487257.png)

最终,成功的解决了超大量数据输入的超时问题,我也体会到了,Java语言比c语言虽然有更多写好的方法可以直接用,但是在算法的运行速度上,是不如c语言快的,也了解了Scanner输入的弊端,只能用于小规模的数据输入,大规模的数据输入,还得用Streamtokenizer.还有在streamtokenizer的输入,要先把数据静态化,才能正常读取。

标签:甲壳虫,res,sum,long,num,3398620,爬树,优化,mod
From: https://www.cnblogs.com/one111/p/18045919

相关文章

  • 面试必备:一线大厂Redis缓存设计规范与性能优化
    说在前面你是否在使用Redis时,不清楚Redis应该遵循的设计规范而苦恼?你是否在Redis出现性能问题时,不知道该如何优化而发愁?你是否被面试官拷问过Redis的设计规范和性能优化而回答不出来别慌,看这篇文章就行了本文,已收录于,我的技术网站aijiangsir.com,有大厂完整面经,工作技术,架构......
  • WPF性能优化:Visual Studio性能分析工具使用介绍
    在硬件性能不断提升的现在,软件性能依旧是开发人员关注的重点。不同类型的程序关注的具体性能指标有所不同,服务器程序注重吞吐量,游戏引擎追求渲染效率,桌面程序则关注内存消耗以及界面加载效率和流畅性。当我们需要进行性能优化时,首先需要找到性能瓶颈。本文将介绍两个WPF性能优化......
  • 由POJ1821得出的一些dp优化技巧
    比如for(inti=1;i<=m;i++){ for(intj=0;j<=n;j++){ dp[i][j]=dp[i-1][j]; } for(intl=max(1,s[i]-l[i]+1);l<=s[i];l++){for(intr=s[i];r<=min(n,l+l[i]-1);r++){dp[i][r]=max(dp[i][r],dp[i-1][l-1]+p[i]*(r-l+1));......
  • 【CSS】滚动条样式的优化
    【转】https://zhuanlan.zhihu.com/p/110029332?utm_id=0前言优化后的滚动条会提亮我们的网站页面。 例如:CSS-TRICKS这个网站如果采用的是浏览器默认的滚动条,不进行优化,页面会显得很不搭。所以该网站的滚动条样式优化如下:html::-webkit-scrollbar{width:30px;......
  • 机器学习策略篇:详解满足和优化指标(Satisficing and optimizing metrics)
    满足和优化指标要把顾及到的所有事情组合成单实数评估指标有时并不容易,在那些情况里,发现有时候设立满足和优化指标是很重要的,让我告诉是什么意思吧。假设已经决定很看重猫分类器的分类准确度,这可以是\(F_1\)分数或者用其他衡量准确度的指标。但除了准确度之外,还需要考虑运行时......
  • 14 CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!)C. Tenzing and Balls(dp+前缀
    思路:dp还是挺明显的,思路可以参考最长上升子序列有点dp的感觉\(f[i]\)表示考虑前\(i\)个数,的最大值当前数有两种删或不删不删:\(f[i]=f[i-1]\);删:\(f[i]=max{f[j-1]+i-j+1}\)这个转移是\(O(n^2)\)的显然时间上来不及考虑优化,第一层循环一定是省不了的考虑优化掉第二层循环......
  • WPF性能优化:性能分析工具
    在硬件性能不断提升的现在,软件性能依旧是开发人员关注的重点。不同类型的程序关注的具体性能指标有所不同,服务器程序注重吞吐量,游戏引擎追求渲染效率,桌面程序则关注内存消耗以及界面加载效率和流畅性。当我们需要进行性能优化时,首先需要找到性能瓶颈。本文将介绍两个WPF性能优化分......
  • Go语言精进之路读书笔记第38条——尽量优化反复出现的if err != nil
    Go在最初设计时就有意识地选择了使用显式错误结果和显式错误检查38.1两种观点显式的错误处理方式让Go程序员首先考虑失败情况,这将引导Go程序员在编写代码时处理故障,而不是在程序部署并运行在生产环境后再处理。而为反复出现的代码片段iferr!=nil{...}所付出的成本已基本被......
  • 11 .Codeforces Round 891 (Div. 3)E. Power of Points(推公式+前缀和优化)
    E.PowerofPoints题解参考#include<bits/stdc++.h>#defineintlonglong#definerep(i,a,b)for(inti=(a);i<=(b);++i)#definefep(i,a,b)for(inti=(a);i>=(b);--i)#define_for(i,a,b)for(inti=(a);i<(b);++i)#definepii......
  • (笔记)FPGA设计性能优化策略漫谈(一)--时序优化
    1   速度优化 1.1 关键路径重组FPGA逻辑设计中时序路径上的组合逻辑都会给路径增加延时,从而影响设计性能的往往只有几条关键的路径而已,所以可以通过减少关键路径上的组合逻辑单元数来减小该路径上的延时,从而达到优化的目的。关键路径重组技术多用于关键路径由多个路......