1. Toy模板网首页
  2. > Toy博客

2023/05/02~07 刷题记录

8月前 作者：PP_2022 分类：Toy博客 阅读(25) 违法举报

这篇具有很好参考价值的文章主要介绍了2023/05/02~07 刷题记录。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

A - AABCC

2023/05/02~07 刷题记录

 题义：

2023/05/02~07 刷题记录

 题解：

        读完题目可以想到直接暴力，但是肯定超时别想了。

        因为 a b c 都是素数，所以我们可以先求出所有的素数 进行减少循环的次数，然后遍历。在遍历过程中，我们也要去进行剪枝 ，如果说 a 的五次方大于了目标值，那后面肯定就都大于了，以此类推。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long n = sc.nextLong();

        // 求素数 并放入集合中
        ArrayList<Integer> primeNumbers = new ArrayList<>(1000);
        getPrimeNumbers(n, primeNumbers);

        // 使用 HashSet 集合存储答案
        HashSet<Long> ans = new HashSet<>();
        long a, b, c, e;
        // 遍历所有可能 并使用if剪枝，如果说 a 的五次方大于了目标值，那后面肯定就都大于了
        for (int i = 0; i < primeNumbers.size(); i++) {
            a = primeNumbers.get(i);
            if (a * a * a * a * a > n)
                break;

            for (int j = i + 1; j < primeNumbers.size(); j++) {
                b = primeNumbers.get(j);
                if (a * a * b * b * b > n)
                    break;

                for (int k = j + 1; k < primeNumbers.size(); k++) {
                    c = primeNumbers.get(k);

                    e = a * a * b * c * c;
                    if (e <= n)
                        ans.add(e);
                    else
                        break;
                }
            }
        }

        // Set 集合中的个数 为答案的数量
        System.out.println(ans.size());
    }

    // 求素数，埃筛
    private static void getPrimeNumbers(long n, ArrayList<Integer> primeNumbers) {
        int len = (int) Math.sqrt(n) >> 1;

        // 初始化素数
        int[] temp = new int[len];
        temp[0] = 1;
        temp[1] = 1;

        for (int i = 2; i < len; i++) {
            if (temp[i] == 0) {
                for (int j = i * 2; j < len; j += i) {
                    temp[j] = 1;
                }

                primeNumbers.add(i);
            }
        }
    }
}

B - Same Map in the RPG World

2023/05/02~07 刷题记录

题义：

2023/05/02~07 刷题记录

 题解：
        我们还是可以第一眼想到暴力求解，但是这个暴力不能太直接了。

        我们可以把每一个点，当作是起点，然后根据这个点 去和 B 矩阵从(0, 0)开始比对。完全相同则为Yes。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int h = sc.nextInt();
        int w = sc.nextInt();
        sc.nextLine();

        // 存放数据矩阵
        char[][] a = new char[50][50];
        char[][] b = new char[50][50];
        for (int i = 0; i < h; i++)
            a[i] = sc.nextLine().toCharArray();
        for (int i = 0; i < h; i++)
            b[i] = sc.nextLine().toCharArray();

        // 先设为 false，遍历每一个点，把这些点当作为起点，然后和 B 矩阵对比
        boolean k = false;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (judge(a, b, i, j, h)) {
                    k = true;
                    break;
                }
            }
        }

        if (k)
            System.out.println("Yes");
        else
            System.out.println("No");
    }

    static boolean judge(char[][] a, char[][] b, int x, int y, int h) {
        int t = y;
        for (int i = 0; i < h; i++) {
            // 遍历 如果 x 大于了高度 h 则说明 A 矩阵已经从起点遍历到了最后 需要把 x+i 放到第一行
            x = x + i >= h ? x - h : x;
            y = t;
            for (int j = 0; j < a[i].length; j++) {
                // y 同理
                y = y + j >= a[i].length ? y - a[i].length : y;

                if (a[x + i][y + j] != b[i][j]) {
                    return false;
                }
            }
        }

        return true;
    }
}

 C - Cross

2023/05/02~07 刷题记录

题义：

2023/05/02~07 刷题记录

题解：

        遍历每一个点，把该点当作 X 图形的中心，求出这个点最大的 X 图形长度。既然是求最大，那么就不用考虑是否会交叉等问题。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        h = sc.nextInt();
        w = sc.nextInt();
        sc.nextLine();

        for (int i = 0; i < h; i++) 
            mp[i] = sc.nextLine().toCharArray();

        // 遍历每一个点当作中心
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++)
                if (mp[i][j] == '#')
                    fun(i, j);
                
        // 输出答案
        for (int i = 1; i <= Math.min(h, w); i++) 
            System.out.print(ans[i] + " ");
    }

    static int[] ans = new int[110];
    static char[][] mp = new char[110][100];
    static int h, w;

    // 求以(x, y)为中心，最大的 X 图像为多大
    static void fun(int x, int y) {
        int i = 1;
        while (true) {
            // 越界 就退出循环
            if (x - i < 0 || y - i < 0 || x + i >= h || y + i >= w)
                break;
            // 不能抵达 就退出循环
            if (mp[x - i][y - i] != '#' || mp[x + i][y - i] != '#' || mp[x - i][y + i] != '#' || mp[x + i][y + i] != '#')
                break;

            i++;
        }

        // 存进答案数组中
        ans[i - 1]++;
    }
}

D - Find by Query

2023/05/02~07 刷题记录

2023/05/02~07 刷题记录

题解：
        交互题。

        已知 s1 = 0，sn = 1。则不管中间是什么值，肯定会有一个分界的点，我们就是要求出这个点（任求一个）。很容易我们想到二分的方法，注意临界条件和判断条件。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        // 二分 每次询问中间的值，如果是 0，则往右边靠，因为最右边是 1。
        // 那肯定有一个分界点。如果是 1，同理。
        int l = 1, r = n, mid, res;
        while (l <= r) {
            mid = (l + r) / 2;
            System.out.println("?" + mid);
            res = sc.nextInt();
            if (res == 0)
                l = mid + 1;
            else
                r = mid - 1;
        }

        System.out.println("!" + r);
    }
}

E - Dango

2023/05/02~07 刷题记录

题义：
2023/05/02~07 刷题记录

题解：

        简单模拟题，注意细节就好了。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        sc.nextLine();

        String s = sc.nextLine();
        int ans = -1, l, r = -1;
        for (int i = 0; i < s.length(); i++) {
            // 如果该点为 -，则看是否为最大值 尝试存入答案
            if (s.charAt(i) == '-') {
                l = r;
                r = i;

                ans = Math.max(ans, r - l - 1);
            }
        }

        // 特殊情况，当 r == -1 则说明没有 -
        // 不为 r != -1 则求 从字符串最后到 倒数第一个 - 的距离 也可能为答案
        if (r != -1)
            ans = Math.max(ans, s.length() - r - 1);
        // 如果答案为 0，则没有 o，输出 -1
        if (ans == 0)
            ans--;
        System.out.println(ans);
    }
}

F - Cards Query Problem

2023/05/02~07 刷题记录

题义：

2023/05/02~07 刷题记录

题解：

        分别使用两个集合去存储数据。使用 ArrayList 集合当作一个盒子，把元素存进该集合中。

        使用 TreeSet 集合，存储对应下标卡片，在哪些盒子中存在。（其中 因为实现了 Set 接口 所以可以自动去重，又是 TreeSet 可以自动排序）

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int q = sc.nextInt();
        int i, x;

        // 创建两个集合，分别存放一个盒子中有的卡片
        ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>(n);
        // 存放一个卡片的值 在哪些盒子中存在于 哪些盒子中，因为需要去重所以选择Set集合，又因为TreeSet自带排序
        ArrayList<TreeSet<Integer>> treeSets = new ArrayList<>(200010);
        for (i = 0; i < 200010; i++)
            treeSets.add(new TreeSet<>());
        for (i = 0; i < n; i++)
            arrayLists.add(new ArrayList<>(100));

        while (q-- != 0) {
            switch (sc.nextInt()) {
                case 1:
                    x = sc.nextInt();
                    i = sc.nextInt();

                    // 放入对应的集合
                    treeSets.get(x).add(i);
                    arrayLists.get(i - 1).add(x);
                    break;
                case 2:
                    i = sc.nextInt();

                    // 排序后输出 盒子中的全部卡片
                    ArrayList<Integer> integers = arrayLists.get(i - 1);
                    Collections.sort(integers);
                    for (Integer integer : integers)
                        System.out.print(integer + " ");
                    System.out.println();
                    break;
                case 3:
                    x = sc.nextInt();

                    // 输出对应卡片的集合里的 所有盒子（已经自动排序了）
                    TreeSet<Integer> treeSet = treeSets.get(x);
                    for (Integer integer : treeSet)
                        System.out.print(integer + " ");
                    System.out.println();
                    break;
            }
        }
    }
}

H - Writing a Numeral

2023/05/02~07 刷题记录

 题义：

2023/05/02~07 刷题记录

题解：

        全程使用一个 long 类型维护。

        操作一：加一个数后，进行对这个值取模。

        操作二：删除最前面的数，删除时考虑 当时的位数（队列的位数），而不是维护的数值的位数。因为维护的数会被取模。而在进行减的时候，也要先进行取模，否则可能会数字过大，这里还可以使用预处理进行减少计算的时间与次数。

        操作三：输出维护的这个数值。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long n = sc.nextLong();

        // 需要 mod 的值
        final int INF = 998244353;
        // 初始化数值为 1，待会用来做乘法
        long ans = 1;
        // 预处理
        long[] div = new long[600005];
        div[0] = 1;
        for (int i = 1; i < 600005; i++)
            div[i] = div[i - 1] * 10 % INF;

        // 使用 LinkedList 集合来存储各个位上的数字，方便尾插和弹出队头
        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.add(1);
        for (long i = 0; i < n; i++) {
            switch (sc.nextInt()) {
                case 1:
                    // 插入队尾
                    int a = sc.nextInt();
                    linkedList.addLast(a);
                    ans = ans * 10 + a;
                    ans = myMod(ans, INF);
                    break;
                case 2:
                    // 移除头节点，并将维护的数字减去这个头节点对应的值
                    Integer first = linkedList.removeFirst();
                    ans -= (long) first * div[linkedList.size()];
                    // 减去之后可能为负数，改为自己定义的 mod 方法
                    ans = myMod(ans, INF);
                    break;
                case 3:
                    // 输出维护的数值
                    System.out.println(ans);
                    break;
            }
        }
    }

    // mod 可能为负数，自定义 mod
    static long myMod(long x, long mod) {
        x %= mod;
        while (x < 0)
            x += mod;
        return x;
    }
}

 J - M<=ab

2023/05/02~07 刷题记录

 题义：

2023/05/02~07 刷题记录

 题解：

        阅读完题目很容易想到暴力，也就是从 M 开始，一个一个试看是否有两个数字可以相乘的值为它，并且这两个值都小于 N。但是肯定超时。。。

        改变思路，我们可以从 1 开始 (设为 i)，求出一个与 i 相乘 大于等于 M 且最接近 M 的值。推导出 

(m + i - 1) / i;

        为什么要 +i ？因为 M / i * i 的值可能会小于 M，加了 i 之后，计算出来的结果一定会使得 求出来的值 乘以 i 大于等于 M。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long n = sc.nextLong();
        long m = sc.nextLong();
        long k, ans = Long.MAX_VALUE;

        for (long i = 1; i <= n; i++) {
            // 求出一个 与 i 相乘 大于等于 M 的值，且该值为最接近 M 的
            k = (m + i - 1) / i;

            // 剪枝，如果 i 大于了 k 的话，其实后面的值 之前都遍历过了，break 跳出
            if (i <= k) {
                // 如果 k 在答案的范围内（1-n），则对比一下结果
                if (k <= n)
                    ans = Math.min(ans, i * k);
            } else {
                break;
            }
        }

        if (ans == Long.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(ans);
    }
}

K - Gap Existence

2023/05/02~07 刷题记录

 题义：

2023/05/02~07 刷题记录

 题解：

        使用 HashSet 进行存储数据（包含了去重、快速查找功能）。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int x = sc.nextInt();

        // 使用 HashSet 存储，满足题目的快速查找（hash值）和去重剪枝需求
        HashSet<Integer> hashSet = new HashSet<>(n);
        for (long i = 0; i < n; i++)
            hashSet.add(sc.nextInt());

        // 判断是否含有这个值，a - x 的值
        boolean k = false;
        for (Integer a : hashSet) {
            if (hashSet.contains(a - x)) {
                k = true;
                break;
            }
        }

        if (k)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

L - 2xN Grid

2023/05/02~07 刷题记录

题义：

2023/05/02~07 刷题记录

题解：
        简单模拟题。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long len = sc.nextLong();
        long n1 = sc.nextLong();
        long n2 = sc.nextLong();

        ArrayList<Node> nodes = new ArrayList<>();
        for (int i = 0; i < n1; i++)
            nodes.add(new Node(sc.nextLong(), sc.nextLong()));

        int now = 0;
        long ans = 0, x = 0, l = 0, xx = 0, ll = 0;
        for (int i = 0; i < n2; i++) {
            x = sc.nextLong();
            l = sc.nextLong();

            // 将 B 序列的值 循环消耗完
            while (l != 0) {
                if (ll == 0) {
                    Node node = nodes.get(now++);
                    xx = node.x;
                    ll = node.l;
                }

                if (l <= ll) {
                    if (x == xx)
                        ans += l;
                    ll -= l;
                    l = 0;
                } else {
                    if (x == xx)
                        ans += ll;
                    l -= ll;
                    ll = 0;
                }
            }
        }

        System.out.println(ans);
    }

    static class Node {
        long x, l;

        Node(long x, long l) {
            this.x = x;
            this.l = l;
        }
    }
}

M - Bank

2023/05/02~07 刷题记录

题义：

2023/05/02~07 刷题记录

题解：

        该题目对 Java 选手不太友好，这样都超时。

        因为，题目只有操作二可以删除元素，而在删除之前肯定会添加该元素，所以操作一都不用管。操作三时，如果 bool 值为 true 则说明该值已经被删除了，则 ++ 判断下一个值。文章来源地址https://www.toymoban.com/news/detail-436464.html

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int q = sc.nextInt();

        // 创建一个 bool 数组判断是否删除了该元素
        boolean[] booleans = new boolean[n+1];
        int last = 1;

        for (int i = 0; i < q; i++) {
            switch (sc.nextInt()) {
                case 2:
                    // 操作二 删除一个元素
                    int a = sc.nextInt();
                    booleans[a] = true;
                    break;
                case 3:
                    // 操作三 输出一个最小的没有被删除的元素
                    while (booleans[last])
                        last ++;
                    System.out.println(last);
                    break;
            }
        }
    }
}

到了这里，关于2023/05/02~07 刷题记录的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • LeetCode 周赛 344（2023/05/07）手写递归函数的固定套路

    本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。 大家好，我是小彭。 今天下午有力扣杯战队赛，不知道官方是不是故意调低早上周赛难度给选手们练练手。 往期周赛回顾：LeetCode 单周赛第 343 场 · 结合「下一个排列」的贪心构造问题 T1. 找出不同

    2024年02月03日
    浏览(27)

  • 2023/07/02_leetcode每日一题_2.两数相加

    给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。 请你将两个数相加，并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。 示例： 输入：l1 = [9,9,9,9,9,9

    2024年02月11日
    浏览(37)
  • 【Qt】插件Plugin入门之Q_PLUGIN_METADATA()宏【2023.05.07】

    【Qt】插件Plugin入门之Q_PLUGIN_METADATA()宏【2023.05.07】

    第一篇 插件Plugin入门之Q_PLUGIN_METADATA()宏 第二篇 插件Plugin入门之Q_PLUGIN_METADATA、Q_INTERFACE、Q_DECLARE_INTERFACE的功能剖析 第三篇：插件Plugin简明使用教程，未完   分析 Q_PLUGIN_METADATA 宏的设计意图，站在设计者的意图进行插件的高屋建瓴式学习。   Qt 的 Meta-Object Compiler（MO

    2024年02月03日
    浏览(24)

  • leetcode刷题记录：二叉树02（思路篇）

    参考labuladong的算法小抄：https://labuladong.online/algo/data-structure/binary-tree-part1/ 复习二叉树纲领篇，二叉树解题的思维模式分两类： 1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。 2、是否可以定义一个

    2024年02月19日
    浏览(26)

  • 2023-07-04 阿里味词汇-记录

    阿里身为有名的业界毒瘤, 将不干实事的务虚风格发扬到了极致, 尤其是生造的词汇为荣, 为了快速识别业界毒瘤的阿里味, 记录下阿里味常用的务虚词汇 二字名词:漏斗，中台，闭环，打法，纽带，矩阵，刺激，规模，场景，维度，格局，形态，生态，体系，认知，玩法，体感

    2024年02月12日
    浏览(24)
  • 机试刷题记录 2023-7-6

    机试刷题记录 2023-7-6

    题目描述 Time Limit: 1000 ms Memory Limit: 256 mb 输入A,B 输出A+B -1,000,000,000=A,B=1,000,000,000 输入输出格式 输入描述: 输出描述: 输入输出样例 输入样例: 输出样例: 题目来源 题目描述 Time Limit: 1000 ms Memory Limit: 256 mb 求Sn=a+aa+aaa+…+aa…aaa（有n个a）之值，其中a是一个数字。 例如：2+22+22

    2024年02月13日
    浏览(63)

  • 2023-07-25 monetdb-relation-关键数据结构-记录

    monetdb-relation-关键数据结构-记录

    2024年02月15日
    浏览(26)
  • 第4天-代码随想录刷题训练● 24. 两两交换链表中的节点 ● 19.删除链表的倒数第N个节点 ● 面试题 02.07. 链表相交 ● 142.环形链表II

    第4天-代码随想录刷题训练● 24. 两两交换链表中的节点 ● 19.删除链表的倒数第N个节点 ● 面试题 02.07. 链表相交 ● 142.环形链表II

    原题链接 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。 1.为什么要是用虚拟头结点 2.为什么使用前一个节点a来操作交换后两个节点b和c更好 3.循环终止条件：a的next和a的

    2024年02月04日
    浏览(41)

  • 力扣刷题|L24. 两两交换链表中的节点 、L19.删除链表的倒数第N个节点 、L面试题 02.07. 链表相交 、L142.环形链表II

    今天的刷题最大的收获，便是学会了在群里跟大家进行讨论，这样得到的答案，往往能更快的提高效率，希望自己能继续坚持下去。 L24. 两两交换链表中的节点https://leetcode.cn/problems/swap-nodes-in-pairs/submissions/ 本题主要考虑双指针法，也就是如何判断虚拟节点不动的情况，这是

    2024年02月04日
    浏览(29)

  • AI模型部署记录（一）-ChatGLM：清华开源本地部署（2023/05/06更新）

    文章首发及后续更新：https://mwhls.top/4500.html，无图/无目录/格式错误/更多相关请至首发页查看。 新的更新内容请到mwhls.top查看。 欢迎提出任何疑问及批评，非常感谢！ 服务部署汇总 本来这篇是为了打比赛写的，写着写着发现两个问题，AI部署连续几篇，等我比赛打完再发模

    2024年02月03日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包