codeforces round944(div4)A~F题解

文章目录

  • [A. My First Sorting Problem](https://codeforces.com/contest/1971/problem/A)
  • [B. Different String](https://codeforces.com/contest/1971/problem/B)
  • [C. Clock and Strings](https://codeforces.com/contest/1971/problem/C)
  • [D. Binary Cut](https://codeforces.com/contest/1971/problem/D)
  • [E. Find the Car](https://codeforces.com/contest/1971/problem/E)
  • [F. Circle Perimeter](https://codeforces.com/contest/1971/problem/F)
  • 模板代码

省略模版代码,模板代码在最后面
div4重拳出击(bushi),但是F题不会
更新:
·1. E题被hacked了,等一下数据
2. F题原来暴力就能解决,万万没想到,还以为会超时;更新下。

A. My First Sorting Problem

题目:
给两个整数X和Y,先输出最小值再输出最大值

思路:
模拟

static void solve() throws IOException {
    int[] a = pIntArray(0);
    int x = a[0], y = a[1];
    if (x > y) {
        out.println(y + " " + x);
    } else {
        out.println(x + " " + y);
    }
}

B. Different String

题目:
给一个仅包含小写字母的字符串S,判断重新安排顺序后的字符串能不能与S不相同,若能不相同则输出一种情况

思路:
当S仅包含一种字母时无论怎么安排都会等于S,只需要在遍历时判断是否有第二种字母出现,出现就与前面一个字母交换即可

static void solve() throws IOException {
    char[] s = in.readLine().toCharArray();
    int[] st = new int[26];
    int cnt = 0, pre = -1;
    for (int i = 0; i < s.length; i++) {
        if (st[s[i] - 'a'] == 0) {
            cnt++;
            if (pre == -1) {
                pre = i;
            }
        }

        if (cnt > 1) {
            char tmp = s[i];
            s[i] = s[pre];
            s[pre] = tmp;
            out.println("YES");
            out.println(String.valueOf(s));
            return;

        }
        st[s[i] - 'a']++;
    }
    out.println("NO");
}

C. Clock and Strings

题目:
给四个互不相同且不超过12的整数a,b,c,d,在钟表上分别连接a和b、c和d,判断这两条线是否相交

思路:
假设a<b,c<d,思考什么时候不会相交:

  1. 其中一条线在另一条线的旁边,此时b < c 或者 a < d
    在这里插入图片描述
  2. 其中一条线和另一条线类似平行,此时a < c且b>d 或者 c<a且d>b(可以理解为一条线在另一条线内部)
    在这里插入图片描述
    判断出这两种情况就是没有相交,其他的就是相交
static void solve() throws IOException {
    int[] ins = pIntArray(0);
    int a = ins[0], b = ins[1], c = ins[2], d = ins[3];
    if (a > b) {
        int t = b;
        b = a;
        a = t;
    }
    if (c > d) {
        int t = c;
        c = d;
        d = t;
    }

    if ((a < c && b > d) || (c < a && d > b) || (b < c || d < a)) {
        out.println("NO");
    } else {
        out.println("YES");
    }
    }

D. Binary Cut

题目:
给一个二进制字符串S,可以进行任意切分,然后对切分后的块进行重新排列,使得排列产生的字符串是一个有序的字符串(非递减),求切分的最小块数

思路:
观察样例 110100 可以发现,如果全是 1 的块是能够放在最后面的,全是0的块可以放在最前面,但是这两部分的中间只能放下一个包含 00..01...1 形式的块;
那么对于 0 开头的子串,仅能在后面跟一次全是 1 的子串;

static void solve() throws IOException {
    char[] s = in.readLine().toCharArray();
    int ans = 0, cnt = 0;
    for (int i = 0; i < s.length; ) {
        int j = i + 1;
        if (s[i] == '0') {
            while (j < s.length && s[j] == '0') j++;
            while (cnt == 0 && j < s.length && s[j] == '1') j++;
            if (s[j - 1] == '1') {
                cnt ++;
            }
        } else {
            while (j < s.length && s[j] == '1') j++;
        }
        ans++;
        if (j - 1 > i) i = j;
        else i++;
    }
    out.println(ans);

E. Find the Car

题目:
一辆汽车在0分钟从点0出发,已知K个信号站所在位置a和到达每个信号站的时间b,在两个相邻的信号站之间汽车行驶的速度恒定,现在给q次询问,每次询问给一个整数d,求到达d的时间。

思路:
对于 d,只需要 二分 找出前一个信号站的位置和到达时间,然后就能够求出前一个信号站到下一个信号站的速度,就能够求出到达d的时间

static void solve() throws IOException {
    int[] ins = pIntArray(0);
    int n = ins[0], k = ins[1], q = ins[2];
    int[] a = pIntArray(1), b = pIntArray(1);
    double[] speeds = new double[k + 1];
    // 从1开始,方便求取0到第一个信号站的速度
    for (int i = 1; i <= k; i ++) {
        speeds[i] = (double) (a[i] - a[i - 1]) / (b[i] - b[i - 1]);
    }
    while (q -- > 0) {
        int d = pInt();
        int l = 0, r = k;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (a[mid] <= d) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        if (a[l] == d) {
            out.print(b[l] + " ");
        } else {
            out.print((long)((b[l] + (d - a[l]) / speeds[l + 1])) + " ");
        }
    }
    out.println();
}

============ hack更新 =================
上面的被下面这个数据hack掉了

1
1000000000 2 1
999999998 1000000000
999999999 1000000000
999999997

问题出在浮点数运算上,思路是没有问题的,只是最后计算的时候因为精度导致计算结果 999999997.999999998999999998 变成 999999998,然后就wa了,改了:

 static void solve() throws IOException {
     int[] ins = pIntArray(0);
     int n = ins[0], k = ins[1], q = ins[2];
     int[] a = pIntArray(1), b = pIntArray(1);
     while (q -- > 0) {
         int d = pInt();
         int l = 0, r = k;
         while (l < r) {
             int mid = l + r + 1 >> 1;
             if (a[mid] <= d) {
                 l = mid;
             } else {
                 r = mid - 1;
             }
         }
         if (a[l] == d) {
             out.print(b[l] + " ");
         } else {
             out.print(b[l] + ((long) (d - a[l]) * (b[l + 1] - b[l])) / (a[l + 1] - a[l]) + " ");
         }
     }
     out.println();
 }

F. Circle Perimeter

题目:
求圆心为(0,0)且半径分别为整数 rr+1 的同心圆之间有多少个整数点,即有多少个点 (x, y) 满足 r ≤ x 2 + y 2 < r + 1 r \le \sqrt{x^2+y^2} \lt r+1 rx2+y2 <r+1

思路:
因为圆是对称的,可以只看第一象限, 假设y从r+1 开始,右边的 A、B、C、D四个点都是比(0, 4)这个点低的,同时它们到(0,0)的距离都是 r+1;也就是说,当x遍历 0r+1 的时候,满足条件的点的纵坐标必定小于 y ,而这个 y 随着 x 的增大不断减小,直到0;
那么可以通过该方法来统计第一象限的整数点个数,最后乘上4即可
在这里插入图片描述

static void solve() throws IOException {
    long r = pInt();
    long ans = 0;
    long y = r;
    long max = (r + 1) * (r + 1);
    long min = r * r;
    for (long i = 0; i <= r; i ++) {
   		// 找到第一个距离为r+1的点(边界)
        while (i * i + y * y >= max) y --;
        // 此时(i, t)点满足条件
        long t = y;
        while (i * i + t * t >= min && t > 0) {
            ans ++;
            t --;
        }
    }
    out.println(ans * 4);
}

模板代码

import java.io.*;
import java.nio.file.Files;
import java.nio.file.Paths;

public class Example {

    static void solve() throws IOException {

    }

    public static void main(String[] args) throws IOException {
        int t = 1;
//        t = Integer.parseInt(in.readLine());
        while (t -- > 0) {
            solve();
        }
        in.close();
        out.flush();
        out.close();
    }

    private static InputStream is = System.in;
    static {
        try {
            is = Files.newInputStream(Paths.get("F:\\Notes\\Algorithm\\Problems\\java\\java\\src\\main\\java\\input.txt"));
        } catch (Exception e) {
            is = System.in;
        }
    }
    private static final BufferedReader in = new BufferedReader(new InputStreamReader(is));
    private static final PrintWriter out = new PrintWriter(System.out);
    private static int pInt(String s) {
        return Integer.parseInt(s);
    }
    private static int pInt() throws IOException {return Integer.parseInt(in.readLine());}
    private static long pLong(String s) {
        return Long.parseLong(s);
    }
    private static long pLong() throws IOException {return Long.parseLong(in.readLine());}
    private static String[] pStringArray() throws IOException {
        return in.readLine().split(" ");
    }
    private static int[] pIntArray(int start) throws IOException {
        String[] s = pStringArray();
        int[] arr = new int[start + s.length];
        for (int i = start, j = 0; i < arr.length; i++, j ++) {
            arr[i] = Integer.parseInt(s[j]);
        }
        return arr;
    }

    private static long[] pLongArray(int start) throws IOException {
        String[] s = pStringArray();
        long[] arr = new long[start + s.length];
        for (int i = start, j = 0; i < arr.length; i++, j ++) {
            arr[i] = Long.parseLong(s[j]);
        }
        return arr;
    }
}

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

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

相关文章

5.10.10 用于图像识别的深度残差学习

1. 介绍 深度卷积神经网络为图像分类带来了一系列突破。深度网络自然地以端到端的多层方式集成低/中/高级特征和分类器&#xff0c;并且特征的“级别”可以通过堆叠层的数量&#xff08;深度&#xff09;来丰富。 学习更好的网络是否像堆叠更多层一样容易&#xff1f; 这个问…

网络工程师----第二十七天

计算机基 第四章&#xff1a;网络层 网络层提供服务的特点&#xff1a;网络层向上只提供简单的、无连接的、尽最大努力交付的数据报服务&#xff0c;不保证可靠通信。 网际协议IP&#xff1a; *地址解析协议ARP(Address Resolution Protocol) *网际控制报文协议ICMP(Inter…

分享一个非常好用的安装包下载网站

当我们需要下载linux下的某些包,以便在自己的环境下进行编译自己的安装包的时候,可能需要用到一些各种版本的依赖包,从网上 百度会很麻烦。 这里分享一个很好用的安装包下载网站,记得点赞收藏 网站: Red Hat Enterprise Linux Repositories - pkgs.org 找到对应系统,然…

【Java的抽象类和接口】

1. 抽象类 1.1 抽象类概念 在面向对象的概念中&#xff0c;所有的对象都是通过类来描绘的&#xff0c;但是反过来&#xff0c;并不是所有的类都是用来描绘对象的&#xff0c;如果 一个类中没有包含足够的信息来描绘一个具体的对象&#xff0c;这样的类就是抽象类。 以上代码中…

4.Jmeter阶梯加压Stepping Thread Group

1. 先去Jmeter下载地址下载PluginsManager&#xff0c;放置在Jmeter的lib/ext 目录下 &#xff0c;重启Jmeter 2. 在插件管理器查找并安装jpgc - Standard Set,重启Jmeter 3.右键测试计划->添加->Threads(Users)->jpgc - Stepping Thread Group 然后设置阶梯加压参数…

【保姆级教程】如何将火爆全网的Kimi接入微信公众号,成为你的专属AI智能客服

【保姆级教程】如何将火爆全网的Kimi接入微信公众号&#xff0c;成为你的专属AI智能客服 在数字化转型的浪潮中&#xff0c;企业越来越重视利用人工智能技术提升客户服务的效率和质量。Kimi 作为一款功能强大的AI智能助手&#xff0c;能够理解自然语言、提供信息搜索、解析网址…

图像/视频恢复和增强CodeFormer

github&#xff1a;https://github.com/sczhou/CodeFormer 尝试增强旧照片/修复人工智能艺术 面部修复 面部色彩增强和恢复 脸部修复

[XYCTF]-PWN:Intermittent解析(pop栈内数据构造shellcode,自己编写shellcode)

查看ida 这里程序只会把输入的前12字节内容移到虚拟地址里&#xff0c;然后执行&#xff0c;大小不足以让执行shellcode&#xff0c;只能用pop寄存器调用read&#xff0c;再把gets hell的shellcode输入进去 完整exp&#xff1a; from pwn import* context(log_leveldebug,arc…

【数据结构】平衡二叉树(插入、查找、删除)解析+完整代码

3.2 平衡二叉树 3.2.1 定义 平衡二叉树&#xff0c;简称平衡树&#xff08;AVL树&#xff09; 树上任一结点的左右子树高度差不超过1。 结点的平衡因子左子树高-右子树高 3.2.2 插入操作 插入结点后&#xff0c;可能造成不平衡 要调整最小不平衡子树&#xff0c;使其恢复平衡。…

Python以docker形式部署,flask简易服务器。

公司大部分都是springboot 服务器&#xff0c;有时候用到python写的一些模型&#xff0c;部署在linux上进行处理 首先项目这样&#xff1a; flask就不说了&#xff0c;快捷服务器&#xff0c; # -*- coding: utf-8 -*-from flask import Flask, request# 实例化Flask对象 app…

齐护K210系列教程(二十六)_口罩检测

口罩检测 1.下载模型1.1使用机器码下载模型1.2将模型文件下载到SD卡1.3 烧录基本固件 2.程序解释3.课程资源联系我们 要实现此程序的功能需要&#xff1a; 支持 kmodelv4 支持固件 人脸口罩检测模型的模型 模型下载地址为&#xff1a;https://maixhub.com/model/zoo/64 机器码…

简单4步教你电脑摄像头怎么打开!

电脑摄像头是现代计算机的一个重要组件&#xff0c;它为我们提供了进行视频通话、视频会议、拍摄照片和录制视频等功能。然而&#xff0c;对于一些用户来说&#xff0c;不清楚电脑摄像头怎么打开。在本文中&#xff0c;我们将介绍几个简单的步骤&#xff0c;帮助您在电脑上轻松…

易康001:易康多尺度分割结果异常

前言 易康是一种在遥感领域常用的数据处理软件&#xff0c;它主要是用于面向对象的分类&#xff0c;涵盖了分割、模糊分类、监督分类等流程。但是在进行多尺度分割时&#xff0c;往往会遇到一些问题&#xff0c;例如下面图片所示&#xff1a; 1 多尺度分割问题 这种问题一般是…

【C++】AVL

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 目录 前言 一、AVL 树 1.1、AVL树的概念 1.2、AVL树节点的定义 1.3、AVL树的插入 1.4、AVL树的旋转 1.4.1、新节点插入较高左子树的左侧---左左&#xff1a;右单旋 1…

深度论证-高速走线控制100欧姆阻抗一定是最好的选择吗?

高速先生成员--黄刚 对于高速差分信号到底需要控制多少欧姆的阻抗&#xff0c;高速先生相信大部分工程师首先都会看下例如信号的协议文档或者芯片的文档&#xff0c;看看里面有没有推荐的控制阻抗值。例如像PCIE信号&#xff0c;在4.0之后的阻抗会明确要求按照85欧姆来控制&…

240W 宽电压输入 AC/DC 导轨式开关电源——TPR/SDR-240-XS 系列

TPR/SDR-240-XS 导轨式开关电源&#xff0c;额定输出功率为240W&#xff0c;产品输入范围&#xff1a;85-264VAC。提供24V、48V输出&#xff0c;具有短路保护&#xff0c;过载保护等功能&#xff0c;并具备高效率&#xff0c;高可靠性、高寿命、更安全、更稳定等特点&#xff0…

Docker容器中的SSH免密登录

简介&#xff1a;在日常的开发和测试环境中经常需要创建和管理Docker容器。有时&#xff0c;出于调试或管理的目的&#xff0c;可能需要SSH到容器内部。本文将介绍如何创建一个Docker容器&#xff0c;它在启动时自动运行SSH服务&#xff0c;并支持免密登录。 构建支持SSH的Doc…

对于fastjson之rmi利用问题的解决

前言 也是被一个问题困扰了好久&#xff0c;都要崩溃了&#xff0c;就为了一个问题调试半天的代码&#xff0c;最后终于解决了&#xff0c;现在做一个记录&#xff0c;幸好没有放弃&#xff0c;感觉学java是比较慢的&#xff0c;但是学java就是重在分析能力的提升&#xff0c;…

关于使用git拉取gitlab仓库的步骤(解决公钥问题和pytho版本和repo版本不对应的问题)

先获取权限&#xff0c;提交ssh-key 虚拟机连接 GitLab并提交代码_gitlab提交mr-CSDN博客 配置完成上诉步骤之后&#xff0c;执行下列指令进行拉去仓库的内容 sudo apt install repo export PATHpwd/.repo/repo:$PATH python3 "实际路径"/repo init -u ssh://gitxx…

是谁,又被分布式锁给锁住了?(上)

大家好&#xff0c;我是徒手敲代码。 今天来介绍一下分布式锁。首先思考下这些问题&#xff1a; 为什么需要分布式锁&#xff1f; 基于 Redis 如何实现分布式锁&#xff1f; 单纯使用setNx命令来加锁&#xff0c;会存在什么问题&#xff1f; 经常听到的RedLock&#xff0c;…