AtCoder Beginner Contest 335 (Sponsored by Mynavi) --- F - Hop Sugoroku -- 题解

目录

F - Hop Sugoroku

题目大意:

思路解析:

代码实现:

        


F - Hop Sugoroku

题目大意:

        

思路解析:

        容易想到这是一个dp题,然后初始转移方程为:

         如果当a[i] 较大时,时间复杂度为 O(N*N/a[i]) 接近于N,但是当a[i]为1时,时间复杂度解决O(N^2),这是不能接受的。

观察dp转移方程可以发现 (j*a[i]+i)% a[i] == i % a[i],即只有当 j % a == i % a时才能转移,这衍生出另一个dp方程 dp2[i][j],表示当前格子在t,a[t] == i, t % a[t] == j。

根据上面分析可以发现dp[i] += dp2[j][i%j],如果dp2开很大的话会爆内存空间,所以我们应该想到,当a[i] 较小时( 我取的是500) 采用dp2进行转移,如果a[i]较大则采用第一种方式进行转移。

这样的会时间开销就变为 O(N*N/500) 约等于 O(N*400)  

代码实现:

        


import java.io.*;
import java.math.BigInteger;
import java.util.*;


public class Main {
    static int mod1 = (int) 1e9 + 7;
    static int mod2 = 998244353;
    static int BD = 500;

    public static void main(String[] args) throws IOException {
        int n = input.nextInt();
        int[] dp = new int[n];
        dp[0] = 1;
        int ans = 0;
        int[][] dp2 = new int[505][505];
        for (int i = 0; i < n; i++) {
            int a = input.nextInt();
            for (int j = 1; j <= BD; j++) {
                dp[i] = (dp[i] + dp2[j][i % j]) % mod2;
            }
            if (a <= BD){
                dp2[a][i % a] = (dp2[a][i%a] + dp[i]) % mod2;
            }else {
                for (int j = 1; j * a + i < n; j++) {
                    dp[j * a + i] = (dp[j * a + i] + dp[i]) % mod2;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            ans = (ans + dp[i]) % mod2;
        }
        out.println(ans);
        out.flush();
        out.close();
        br.close();
    }

    // -------------------------------- 模板 ---------------------------
    static boolean nextPermutation(int[] arr) {  // 排列数循环模板    记得使用 do while 循环
        int len = arr.length;
        int left = len - 2;
        while (left >= 0 && arr[left] >= arr[left + 1]) left--; // 从升序 一直往降序排列。
        if (left < 0) return false;
        int right = len - 1;
        // 找到第一个升序的位置,将其改为降序。
        while (arr[left] >= arr[right]) right--;
        {
            int t = arr[left];
            arr[left] = arr[right];
            arr[right] = t;
        }
        // 修改后它的前面仍然为降序,将前面全部修改为升序,这样能保证不会漏算,也不会算重
        left++;
        right = len - 1;
        while (left < right) {
            {
                int t = arr[left];
                arr[left] = arr[right];
                arr[right] = t;
            }
            left++;
            right--;
        }
//        System.out.println(Arrays.toString(arr));
        return true;
    }

    public static long qkm(long a, long b, long mod) { // 快速幂模板
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = (res * a) % mod;
            a = (a * a) % mod;
            b >>= 1;
        }
        return res;
    }

//    // 线段树模板
//    public static int lowbit(int x){
//        return x & (-x);
//    }
//
//    public static void bulid(int n){
//        for (int i = 1; i <= n; i++) {
//            t[i] = a[i];
//            int j = i + lowbit(i);
//            if (j<=n) t[j] += t[i];
//        }
//    }
//
//    public static void updata(int x, int val){
//        while (x <= n){
//            t[x] += val;
//            x += lowbit(x);
//        }
//    }
//
//    public static int query(int l, int r){
//        int res = 0;
//        while (l <= r){
//            res += a[r];
//            r--;
//            while (r - lowbit(r) >= l){
//                res += t[r];
//                r -= lowbit(r);
//            }
//        }
//        return res;
//    }


    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static Input input = new Input(System.in);
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static class Input {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public Input(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextLine() {
            String str = null;
            try {
                str = reader.readLine();
            } catch (IOException e) {
                // TODO 自动生成的 catch 块
                e.printStackTrace();
            }
            return str;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

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

        public Double nextDouble() {
            return Double.parseDouble(next());
        }

        public BigInteger nextBigInteger() {
            return new BigInteger(next());
        }
    }

}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/387919.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【AI视野·今日NLP 自然语言处理论文速览 第七十九期】Thu, 18 Jan 2024

AI视野今日CS.NLP 自然语言处理论文速览 Thu, 18 Jan 2024 Totally 35 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Computation and Language Papers Deciphering Textual Authenticity: A Generalized Strategy through the Lens of Large Language Semantics …

MySQL数据库-MVCC多版本并发控制

mvcc,多版本并发控制&#xff08;Multi-Version Concurrency Control&#xff09;,是一种用于数据库管理系统中的并发控制方法. 在传统的并发控制方法中,如锁定机制,当一个事务修改数据时,会对相关的数据对象进行锁定,其他事务需要等待该锁释放才能进行操作。这种方法存在着事…

操作系统-408

一、操作系统概述 1、定义 负责协调软件和硬件的计算机资源的工作为上层应用提供简易的服务操作系统是系统软件 2、功能&#xff1a; 操作系统是系统资源的管理者 处理机管理存储器管理文件管理设备管理向上层提供方便易用的服务 命令接口程序接口对硬件机器的扩展 3、特征…

详解tomcat中的jmx监控

目录 1.概述 2.如何开启tomcat的JMX 3.tomcat如何实现JMX的源码分析 1.概述 本文是博主JAVA监控技术系列文章的第二篇&#xff0c;前面一篇文章中我们介绍了JAVA监控技术的基石——jmx&#xff1a; 【JMX】JAVA监控的基石-CSDN博客 本文我们将从使用和源码实现两个方面聊…

springboot743二手交易平台

springboot743二手交易平台 获取源码——》公主号&#xff1a;计算机专业毕设大全

Python面向对象学习小记——面向过程VS面向对象

【面向过程就好比你是一个工人&#xff0c;你得亲自去做一个个任务 面向对象就好比你一个包工头&#xff0c;你可以差遣你下面的工人去做】

日期类运算符重载以及const成员详细解析

个人主页&#xff1a;点我进入主页 专栏分类&#xff1a;C语言初阶 C语言进阶 数据结构初阶 Linux C初阶 算法 欢迎大家点赞&#xff0c;评论&#xff0c;收藏。 一起努力&#xff0c;一起奔赴大厂 目录 一.前言 二.运算符重载 2.1概念 2.2比较的符号重载 2.2.1…

linux 安装docker

目录 环境 操作步骤 1 下载脚本 2 执行脚本 3 检查docker版本&#xff0c;证明安装成功 环境 阿里云 ubuntu 22.04 64位 操作步骤 参考linux系统安装docker-腾讯云开发者社区-腾讯云 (tencent.com) 1 下载脚本 curl -fsSL https://get.docker.com -o get-docker.sh …

JavaWeb学习|Filter与ThreadLocal

学习材料声明 所有知识点都来自互联网&#xff0c;进行总结和梳理&#xff0c;侵权必删。 引用来源&#xff1a;尚硅谷最新版JavaWeb全套教程,java web零基础入门完整版 Filter 1、Filter 过滤器它是 JavaWeb 的三大组件之一。三大组件分别是&#xff1a;Servlet 程序、Liste…

RH850从0搭建Autosar开发环境【2X】- Davinci Configurator之XCP模块配置详解(上)

XCP模块配置详解 - 上 一、XCP模块配置项处理1.1 Tx Pdu配置项二、XCP模块其他配置项2.1 参数XcpMainFunctionPeriod2.2 参数XcpOnCanEnabled2.3 容器XcpOnCan总结从本节开始先专注与配置项错误处理以及构建Autosar Rh850的最小系统搭建。 XCP模块在汽车电子各控制器中处于十分…

使用ShardingJDBC实现分库分表

一、测试环境 JDK&#xff1a;1.8SpringBoot&#xff1a;2.7.17MySQL驱动&#xff1a;5.1.49MyBatis&#xff1a;2.3.1shardingJDBC&#xff1a;5.1.0 二、核心依赖 <!-- mysql 驱动 --> <dependency><groupId>mysql</groupId><artifactId>mysq…

Django学习笔记教程全解析:初步学习Django模型,初识API,以及Django的后台管理系统(Django全解析,保姆级教程)

把时间用在思考上是最能节省时间的事情。——[美]卡曾斯 导言 写在前面 本文部分内容引用的是Django官方文档&#xff0c;对官方文档进行了解读和理解&#xff0c;对官方文档的部分注释内容进行了翻译&#xff0c;以方便大家的阅读和理解。 概述 在上一篇文章里&#xff0…

【Python】高级数据类型

&#x1f6a9; WRITE IN FRONT &#x1f6a9; &#x1f50e; 介绍&#xff1a;"謓泽"正在路上朝着"攻城狮"方向"前进四" &#x1f50e;&#x1f3c5; 荣誉&#xff1a;2021|2022年度博客之星物联网与嵌入式开发TOP5|TOP4、2021|2222年获评…

8.JS中的== 操作符的强制类型转换规则

对于 来说&#xff0c;如果对比双方的类型不一样&#xff0c;就会进行类型转换。假如对比 x 和 y 是否相同&#xff0c;就会进行如下判断流程&#xff1a; 首先会判断两者类型是否相同&#xff0c;类型相同的话就比较两者的大小&#xff1b;类型不相同的话&#xff0c;就会进…

Compose低级别API动画指南

Google官方为Compose提供的动画API与原生View体系的动画API相差甚远&#xff0c;目前总共分为四类&#xff1a;高级别动画API、低级别动画API、自定义动画、手势和动画&#xff08;其他&#xff09;&#xff0c;下图是官方提供的流程指示图&#xff0c;以供根据不同使用场景来选…

PMDG 737

在Simbrief中生成计划后下载两个文件 放到A:\Xbox\Community\pmdg-aircraft-738\Config\Flightplans中

深度学习疆界:探索基本原理与算法,揭秘应用力量,展望未来发展与智能交互的新纪元

目录 什么是深度学习 深度学习的基本原理和算法 深度学习的应用实例 深度学习的挑战和未来发展方向 挑战 未来发展方向 深度学习与机器学习的关系 深度学习与人类的智能交互 什么是深度学习 深度学习是一种基于神经网络的机器学习方法&#xff0c;旨在模仿人类大脑分析…

LabVIEW虚拟测试与分析仪

LabVIEW虚拟测试与分析仪 在现代工程技术领域&#xff0c;虚拟仪器的开发和应用已成为一种趋势。利用LabVIEW软件平台开发的虚拟测试与分析仪器进行展开&#xff0c;实现工程测试和分析中的实际需求。通过结合LabVIEW的强大功能和灵活性&#xff0c;成功实现了一套高效、精确的…

各指针含义区分

一、char *a P109: (1)(变量)指针变量&#xff1a;指针变量&#xff0c;即指针的定义&#xff1a;用来存放指针的变量。指向的是变量&#xff0c;且可以改变其指向的地址。P104 char *a (2)(变量)指针常量&#xff1a;指针常量&#xff0c;指向的是变量首字节的地址&#xff…

算法基础——单调栈,单调队列

目录 1.单调栈 例题&#xff1a;【模板】单调栈 例题:求和 2.单调队列 例题&#xff1a;滑动窗口 1.单调栈 例题&#xff1a;【模板】单调栈 可以想象出一个柱状图&#xff0c;值越大&#xff0c;这个柱子越高 以此题的样例为例&#xff1a; 第一个数为7&#xff0c;想…