Codeforces Round 930 (Div. 2) --- D. Pinball --- 题解

目录

D. Pinball：

题目大意：

思路解析：

代码实现：

代码一：

代码二：

D. Pinball：

题目大意：

思路解析：

 假设字符串为 >>><<<， 当前位置为第四位， 那我们可以想到我们如果处在 < 这个位置上，那我们应该找到左边第一个 > 位置，位移到了>位置后，我们应该找到右边第一个 <位置，每次经过的点 > 会改变为 <,  > 会改变为 <，如果这样修改肯定是复杂的，我们可以利用双指针来寻找，这样就可以省略中间将 > 修改为 < 和 < 修改为 > 的过程，但是如果出现字符串形如 <><><><>这样的双指针每次只能移动个位置，然后时间复杂度任然会退化为O(N*N)的时间复杂度。 （参考代码一)

那我们可以发现上诉的分析过程中，我们每次只需要找到<>这两个位置，那我们想到是否可以利用前缀和来求解。

假设字符串为 ><<>><，现在处于 i == 4的位置， 那么答案为 (6 - 4) + (6 - 1) + (7 - 1) 等价于 2 * (6 - 4 - 1) + 4 + (6 + 1)，我们可以发现 6 是一个前缀和，（4+1）也是一个前缀和，貌似看作为前缀和很合理，然后再结合第一个思想和举几个例子验证，发现确实可以利用前缀和假设 （参考代码二）

代码实现：

代码一：

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

public class Main {
    static int inf = (int) 2e7;
    public static void main(String[] args) throws IOException {

        int t = f.nextInt();
        while (t > 0) {
            solve();
            w.println();
            t--;
        }

        w.flush();
        w.close();
        br.close();
    }

    static int maxN = (int) 1e6 + 5;
    static int N = (int) 1e6;
    public static void solve() {
        int n = f.nextInt();
        char[] s = (" " + f.next()).toCharArray();
        int[][] l = new int[n+2][2];
        int[][] r = new int[n+2][2];
        r[n+1][0] = n + 1; r[n+1][1] = n+1;
        for (int i = 1; i <= n; i++) {
            if (s[i] == '>'){
                l[i][0] = i;
                l[i][1] = l[i-1][1];
            }else {
                l[i][1] = i;
                l[i][0] = l[i-1][0];
            }
        }
        for (int i = n; i >= 1; i--) {
            if (s[i] == '>'){
                r[i][0] = i;
                r[i][1] = r[i+1][1];
            }else {
                r[i][1] = i;
                r[i][0] = r[i+1][0];
            }
        }

        // 0 >   1 <
        for (int i = 1; i <= n; i++) {
            int p = i, q = i;
            int op = 0;
            int ned = 0;
            if (s[i] == '>'){
                op = 1;
                ned = 1;
            }
            long ans = 0;
            while (!(p == 0 || q == n + 1)){
                if (op == 1){
                    if (q == r[q][ned]) q++;
                    q = r[q][ned];
                    ans += q - p;
                    ned ^= 1;
                    op = 0;
                }else {
                    if (p == l[p][ned]) p--;
                    p = l[p][ned];
                    ans += q-p;
                    ned ^= 1;
                    op = 1;
                }
            }
            w.print(ans + " ");
        }
    }




    public static class Node{
        int l,r;
        int[] sum = new int[2];

    }

    static PrintWriter w = new PrintWriter(new OutputStreamWriter(System.out));
    static Input f = 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());
        }
    }
}

代码二：

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

public class Main {
    static int inf = (int) 2e7;
    public static void main(String[] args) throws IOException {

        int t = f.nextInt();
        while (t > 0) {
            solve();
            w.println();
            t--;
        }

        w.flush();
        w.close();
        br.close();
    }

    static int maxN = (int) 1e6 + 5;
    static int N = (int) 1e6;
    static int[] cntR;
    static int[] cntL;
    static long[] sumR;
    static long[] sumL;
    static int n;
    public static void solve() {
        n = f.nextInt();
        char[] s = (" " + f.next()).toCharArray();
        cntL = new int[n+1];
        cntR = new int[n+1];
        sumL = new long[n+1];
        sumR = new long[n+1];
        for (int i = 1; i <= n; i++) {
            cntL[i] = cntL[i - 1];
            cntR[i] = cntR[i - 1];
            sumL[i] = sumL[i - 1];
            sumR[i] = sumR[i - 1];
            if (s[i] == '>'){
                cntR[i]++;
                sumR[i] += i;
            }else {
                cntL[i]++;
                sumL[i] += i;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (s[i] == '>'){
                if (cntR[i] > cntL[n] - cntL[i]){
                    int p = getpre(cntR[i] - (cntL[n] - cntL[i]));
                    w.print(2 * ((sumL[n] - sumL[i]) - (sumR[i] - sumR[p-1])) + n + i + 1);
                    w.print(" ");
                }else {
                    int p = getsuf((cntL[n] - cntL[i]) - cntR[i]);
                    w.print(2 * ((sumL[p] - sumL[i-1]) - sumR[i]) + i);
                    w.print(" ");
                }
            }else {
                if (cntL[n] - cntL[i-1] > cntR[i]){
                    int p = getsuf((cntL[n] - cntL[i-1]) - cntR[i] - 1);
                    w.print(2 * ((sumL[p] - sumL[i-1]) - sumR[i]) - i);
                    w.print(" ");
                }else {
                    int p = getpre(cntR[i] - (cntL[n] - cntL[i-1]) + 1);
                    w.print(2 * ((sumL[n] - sumL[i - 1]) - (sumR[i] - sumR[p - 1])) + (n+1) - i);
                    w.print(" ");
                }
            }
        }
    }

    public static int getpre(int x){
        int l = 1, r = n;
        int res = 0;
        while (l <= r){
            int m = (l + r) >> 1;
            if (cntR[m] >= x){
                r = m - 1;
                res = m;
            }else {
                l = m + 1;

            }
        }
        return res;
    }

    public static int getsuf(int x){
        int l = 1, r = n;
        int res = 0;
        while (l <= r){
            int m = (l + r) >> 1;
            if (cntL[n] - cntL[m] <= x){
                res = m;
                r = m - 1;
            }else {
                l = m + 1;
            }
        }
        return res;
    }

    public static class Node{
        int l,r;
        int[] sum = new int[2];

    }

    static PrintWriter w = new PrintWriter(new OutputStreamWriter(System.out));
    static Input f = 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/489275.html

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

相关文章

程序员35岁会失业吗？【来自主流AI的回答】

程序员35岁会失业吗？【来自主流AI的回答】

程序员35岁会失业吗&#xff1f; 35岁被认为是程序员职业生涯的分水岭&#xff0c;许多程序员开始担忧自己的职业发展是否会受到年龄的限制。有人担心随着年龄的增长&#xff0c;技术更新换代的速度会使得资深程序员难以跟上&#xff1b;而另一些人则认为&#xff0c;丰富的经…
阅读更多...
STM32CubeIDE基础学习-USART串口通信实验（轮询方式）

STM32CubeIDE基础学习-USART串口通信实验（轮询方式）

STM32CubeIDE基础学习-USART串口通信实验&#xff08;轮询方式&#xff09; 文章目录 STM32CubeIDE基础学习-USART串口通信实验&#xff08;轮询方式&#xff09;前言第1章 硬件介绍第2章 工程配置2.1 工程外设配置部分2.2 生成工程代码部分 第3章 代码编写3.1 串口发送3.1.1 发…
阅读更多...
SqlServer期末复习（数据库原理及应用）持续更新中

SqlServer期末复习（数据库原理及应用）持续更新中

一、SQL语句 1.1 SQL语句知识引入 1.DDL语言(数据定义语言&#xff09;主要是进行定义/改变表的结构、数据类型、表之间的链接等操作&#xff0c;关键字CREATE、DROP、ALTER CREATE TABLE 表面( 列名1 数据类型&#xff0c; 列名2 数据类型&#xff0c; ) ALTER TABLE 表名&a…
阅读更多...
[计算机效率] 文件查重工具：Vistanita Duplicate Finder

[计算机效率] 文件查重工具：Vistanita Duplicate Finder

3.6 文件查重工具&#xff1a;Vistanita Duplicate Finder Vistanita Duplicate Finder 是一款强大的文件查重工具&#xff0c;可以帮助用户快速查找并删除重复的文件&#xff0c;节省存储空间并提高文件管理效率。该软件支持多种文件类型&#xff0c;包括图片、文档、音频、视…
阅读更多...
el-table 表格中插入表单循环校验

el-table 表格中插入表单循环校验

<template><div>{{form}}<el-form :model"form" ref"form"><el-form-item label"呃呃呃呃呃呃呃"><el-table :data"tableData" border><el-table-column prop"time" label"日期"…
阅读更多...
cookie、localStorage、sessionStorage 详解

cookie、localStorage、sessionStorage 详解

目录 cookie 是什么&#xff1f; cookie 不可以跨域请求 cookie 的属性 会话cookie & 永久性cookie cookie 禁用 cookie 的应用 sessionStorage 是什么&#xff1f; 失效时间 存储内容的类型 存储的大小 存储的位置 sessionStorage 的应用 localStorage 是什么…
阅读更多...
Linux内核架构和基础概念

Linux内核架构和基础概念

文章目录 前言 一、简述操作系统 二、宏内核和微内核 1.宏内核 2.微内核 3.Linux内核的特点 三&#xff0c;Linux内核架构 1.整体架构图 2.Linux子系统的划分 3.Linux子系统之间的关系 4.Linux内核目录介绍 总结 前言 随着Linux内核在全球市场份额的持续扩大&#xff0c;其影…
阅读更多...
使用WebClient发起网络请求

使用WebClient发起网络请求

目录 1、导入对应的pom 2、编写WebClientUtil请求工具类 3、使用WebClientUtil发起请求 使用WebClient的优点&#xff1a;支持lambdas 的函数&#xff1b;支持更高的并发性和更少的硬件资源&#xff1b;支持同步和异步&#xff1b;支持流式传输。具体的使用方式如下&#xff1a…
阅读更多...
Redis 特性，为什么要用Redis，Redis到底是多线程还是单线程

Redis 特性，为什么要用Redis，Redis到底是多线程还是单线程

一、Redis介绍 Redis&#xff08;Remote Dictionary Server )&#xff0c;即远程字典服务&#xff0c;是一个开源的&#xff0c;使用C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库&#xff0c;并提供多种语言的API。 二、特性(为什么要用Redis&#x…
阅读更多...
51单片机入门：定时器与中断系统

51单片机入门：定时器与中断系统

定时器的介绍 定时器&#xff1a;51单片机的定时器属于单片机的内部资源&#xff0c;其电路的设计连接和运转均在单片机内部完成。根据单片机内部的时钟或者外部的脉冲信号对寄存器中的数据加1&#xff0c;定时器实质就是加1计数器。因为又可以定时又可以计数&#xff0c;又称…
阅读更多...
数据结构——排序之冒泡排序

数据结构——排序之冒泡排序

&#x1f49e;&#x1f49e; 前言 hello hello~ &#xff0c;这里是大耳朵土土垚~&#x1f496;&#x1f496; &#xff0c;欢迎大家点赞&#x1f973;&#x1f973;关注&#x1f4a5;&#x1f4a5;收藏&#x1f339;&#x1f339;&#x1f339; &#x1f4a5;个人主页&#x…
阅读更多...
HarmonyOS入门笔记1配置环境

HarmonyOS入门笔记1配置环境

文章目录 下载安装DevEco Studio配置环境先认识DevEco Studio界面工程目录工程级目录模块级目录 app.json5module.json5main_pages.json通知栏预览区 运行模拟器 下载安装DevEco Studio 去官网下载DevEco Studio完了安装 配置环境 打开已安装的DevEco Studio快捷方式进入配置…
阅读更多...
Python爬虫：爬虫基本概念、流程及https协议

Python爬虫：爬虫基本概念、流程及https协议

本文目录&#xff1a; 一、爬虫的基本概念1.为什么要学习爬虫1.1 数据的来源1.2 爬取到的数据用途 2.什么是爬虫3. 爬虫的更多用途 二、爬虫的分类和爬虫的流程1.爬虫的分类2.爬虫的流程3.robots协议 三、爬虫http和https1.http和https的概念2.浏览器发送HTTP请求的过,2.1 http…
阅读更多...
【数据结构刷题专题】—— 二分查找

【数据结构刷题专题】—— 二分查找

二分查找 二分查找模板题&#xff1a;704. 二分查找 二分查找前提&#xff1a; 有序数组数组中无重复元素 左闭右闭&#xff1a; class Solution { public:int search(vector<int>& nums, int target) {int left 0;int right nums.size() - 1;while (left <…
阅读更多...
An Experimental Study of State-of-the-Art Entity Alignment Approaches论文阅读

An Experimental Study of State-of-the-Art Entity Alignment Approaches论文阅读

最先进的实体对齐方法的实验研究综述 Title: An Experimental Study of State-of-the-Art Entity Alignment Approaches 日期: 2022 发表单位: IEEE github: https://github.com/DexterZeng/EAE 原文地址: https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber9174835 概括…
阅读更多...
启扬RK3568核心板助力智慧步道轻装健身，打造全民健康生活新方式

启扬RK3568核心板助力智慧步道轻装健身，打造全民健康生活新方式

随着物联网、AI智能等新技术的快速发展&#xff0c;智慧步道成为全国各地公园建设和全民健身公共服务设施改造的新主题。智慧步道基于物联网、人脸识别、大数据分析等技术&#xff0c;对人们的运动进行监测和数据采集&#xff0c;显示运动数据&#xff0c;包括里程统计、热量消…
阅读更多...
档案四性检测可复用组件接口说明

档案四性检测可复用组件接口说明

nhdeep提供在归档、移交与接收、长期保存等各环节根据需求进行自主配置和调用的可复用组件&#xff0c;支持客户端和接口调用两种功能使用模式。档案四性检测组件为自建档案管理系统和各种业务系统&#xff08;如OA&#xff09;&#xff0c;提供标准化的档案四性检测功能利用&a…
阅读更多...
YOLOv5改进系列：主干ConvNeXTV2结构助力涨点

YOLOv5改进系列：主干ConvNeXTV2结构助力涨点

一、论文理论 论文地址&#xff1a;ConvNeXt V2: Co-designing and Scaling ConvNets with Masked Autoencoders 1.理论思想 ConvNeXt V2 在 ConvNeXt 的基础上增加了两个创新点&#xff08;一个 framework 和一个 technique&#xff09;&#xff1a;全卷积掩码自编码器&…
阅读更多...
人工智能 框架 paddlepaddle 飞桨 使用指南 使用例子 线性回归模型demo 1

人工智能 框架 paddlepaddle 飞桨 使用指南 使用例子 线性回归模型demo 1

安装过程&使用指南&线性回归模型 使用例子 本来预想 是安装 到 conda 版本的 11.7的 但是电脑没有gpu 所以 安装过程稍有变动，下面简单讲下 conda create -n paddle_env117 python=3.9 由于想安装11.7版本 py 是3.9 所以虚拟环境名称也是 paddle_env117 activa…
阅读更多...
nuxt3使用自定义组件

nuxt3使用自定义组件

说明&#xff1a;nuxt3只有components文件夹里面的页面会自动注册为组件&#xff0c;但是有些单独的页面也需要组件&#xff0c;但是也不是全局的&#xff0c;所以写在pages里面的页面&#xff0c;需要手动注册为组件使用 1.创建组件 在pages里面创建页面文件夹&#xff0c;在…
阅读更多...
最新文章

Copyright @ 2022~2023