牛客周赛 Round 2 解题报告 | 珂学家 | 字符串hash + 打家劫舍型DP + 离线双指针

前言

alt

在黎明到来之前，必须有人稍微照亮黑暗。

整体评价

比赛的时候，A题用了字符串Hash，哭了。B题是经典题，C是模拟题，很怕的. D也是经典题，离散双指针，套路满满。

A. 小红的环形字符串

因为长度为1000，所以理论上 O ( n 2 ) O(n^2) O(n2)能接受

对于这种环形，最好的处理方式: 复制并追加 \color{blue}复制并追加 复制并追加

方法一: 暴力

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

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

        String str = sc.next();
        String p = sc.next();

        int ans = 0;
        int idx = 0, n = str.length();
        str = str + str;
        while ((idx = str.indexOf(p, idx)) != -1 && idx < n) {
            ans++;
            idx++;
        }

        System.out.println(ans);

    }

}

#include <bits/stdc++.h>

using namespace std;

int main() {
    string a, b;
    cin >> a >> b;
    
    int n = a.length();
    a = a + a;
    
    int res = 0;
    int p = 0;
    // string的fing方法
    while ((p = a.find(b, p)) != -1 && p < n) {
        p += 1;
        res++;
    } 
    
    cout << res << endl;
    
    return 0;
}

方法二: 字符串hash

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    static class StringHash {
        public static final long mod = 10_0000_0007l;
        long p = 13, h = 0, b = 1l;

        int window;
        String s;
        int cur;

        public StringHash(String s, int window, int p) {
            this.s = s;
            this.window = window;
            ready();
        }

        private void ready() {
            for (int i = 0; i < window; i++) {
                h = ((h * p) % mod + (s.charAt(i) - '0')) % mod;
                b = b * p % mod;
            }
            this.cur = window;
        }

        long hash() {
            return h;
        }

        boolean hashNext() {return this.cur < this.s.length();}
        int start() {return this.cur - this.window;}
        int end() {return this.cur;}

        public void next() {
            if (this.cur >= this.s.length()) return;
            h = (h * p % mod + s.charAt(this.cur) - '0') % mod;
            h = h - b * (s.charAt(this.cur - window) - '0');
            h = (h % mod + mod) % mod;
            this.cur++;
        }

    }

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

        String str = sc.next();
        String p = sc.next();

        StringHash phash = new StringHash(p, p.length(), 13);

        int ans = 0;
        int n = str.length();
        str = str + str;

        StringHash shash = new StringHash(str, p.length(), 13);
        if (phash.hash() == shash.hash()) {
            ans++;
        }

        while (shash.hashNext()) {
            shash.next();
            if (shash.start() >= n) break;
            if (phash.hash() == shash.hash()) {
                ans++;
            }
        }

        System.out.println(ans);

    }

}

B. 相邻不同数字的标记

这题就是打家劫舍型的DP

设计状态 o p t [ i ] opt[i] opt[i]为前i个元素，累计得分最大值

状态转移为

o p t [ i ] = m a x ( o p t [ i − 2 ] + a r r [ i ] + a r r [ i − 1 ]   i f   c o l o r [ i ] ≠ c o l o r [ i − 1 ] , o p t [ i − 1 ] ) ; opt[i] = max(opt[i - 2] + arr[i] + arr[i - 1]\ if\ color[i] \ne color[i - 1] , opt[i - 1]); opt[i]=max(opt[i−2]+arr[i]+arr[i−1] if color[i]=color[i−1],opt[i−1]);

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(new BufferedInputStream(System.in));

        int n = sc.nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextLong();
        }
        char[] str = sc.next().toCharArray();

        if (n <= 1) {
            System.out.println(0);
        } else {
            long[] opt = new long[n];
            opt[0] = 0;
            opt[1] = (str[0] != str[1]) ? (arr[0] + arr[1]) : 0;

            for (int i = 2; i < n; i++) {
                opt[i] = opt[i - 1];
                if (str[i] != str[i - 1]) {
                    opt[i] = Math.max(opt[i - 2] + arr[i] + arr[i - 1], opt[i]);
                }
            }

            System.out.println(opt[n - 1]);
        }

    }
    
}

#include <bits/stdc++.h>

using namespace std;

using int64 = long long ;

int main() {
    
    int n;    
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    string s;
    cin >> s;

    // 力扣打家劫舍问题
    // dp[n][2]
    // dp[n] -> 
    vector<vector<int64>> dp(n, vector<int64>(2, 0LL));
    
    int64 res = 0;
    for (int i = 1; i < n; i++) {
        if (s[i] != s[i - 1]) {
            dp[i][1] = dp[i - 1][0] + arr[i] + arr[i - 1];
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
        } else {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
        }  
        res = max(res, max(dp[i][0], dp[i][1]));
    }
    
    cout << res << endl;
    
    return 0;
}

C. 小红的俄罗斯方块

不用考虑消除，而且只有’L’字母，求最终每列的高度。

这题就是纯粹的模拟，以及找规律。

import java.io.BufferedInputStream;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();

        // 从1开始计数
        int[] cols = new int[9];
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();

            if (a == 0) {
                int low = Math.max(cols[b], cols[b + 1]);
                cols[b] = low + 3;
                cols[b + 1] = low + 1;
            } else if (a == 90) {
                int t2 = Math.max(cols[b + 1], cols[b + 2]);
                if (t2 >= cols[b] + 1) {
                    cols[b] = t2 + 1;
                    cols[b + 1] = t2 + 1;
                    cols[b + 2] = t2 + 1;
                } else {
                    t2 = cols[b];
                    cols[b] = t2 + 2;
                    cols[b + 1] = t2 + 2;
                    cols[b + 2] = t2 + 2;
                }
            }  else if (a == 180) {
                if (cols[b] >= cols[b + 1] + 2) {
                    int low = cols[b];
                    cols[b] = low + 1;
                    cols[b + 1] = low + 1;
                } else {
                    int low = cols[b + 1];
                    cols[b] = low + 3;
                    cols[b + 1] = low + 3;
                }
            } else if (a == 270) {
                int low = Math.max(Math.max(cols[b], cols[b + 1]), cols[b + 2]);
                cols[b] = low + 1;
                cols[b + 1] = low + 1;
                cols[b + 2] = low + 2;
            }
        }

        String res = IntStream.range(0, 9)
                .filter(x -> x > 0)
                .mapToObj(x -> String.valueOf(cols[x]))
                .collect(Collectors.joining(" "));

        System.out.println(res);

    }
    
}

D. 小红打怪

经典的离线+双指针解法

预处理计算每个怪物的需要的最低血量

然后排序（从小到大），构建前缀和

离散双指针即可

import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {

    // 血量计算
    public static long solve(int mh, int ma) {
        long loop = mh / 4;
        long r = mh % 4;

        if (r == 0) {
            return loop * 3l * ma - ma;
        } else {
            long x1 = loop * 3l * ma;
            if (r <= 2) {
                return x1;
            } else {
                return x1 + ma;
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();
        long h = sc.nextLong();
        long r = sc.nextLong();

        // 计算打败怪物的最低血量
        long[] bags = new long[n];
        for (int i = 0; i < n; i++) {
            bags[i] = solve(sc.nextInt(), sc.nextInt());
        }
        Arrays.sort(bags);
        // 前缀和计算
        long[] pres = new long[n];
        for (int i = 0; i < n; i++) {
            pres[i] = (i > 0 ? pres[i - 1] : 0) + bags[i];
        }

        int q = sc.nextInt();
        int[] queries = new int[q];
        for (int i = 0; i < q; i++) {
            queries[i] = sc.nextInt();
        }

        // 离线做法
        Integer[] arr = IntStream.range(0, q).boxed().toArray(Integer[]::new);
        Arrays.sort(arr, Comparator.comparing(x -> queries[x]));

        int[] res = new int[q];
        int j = 0;
        for (int i = 0; i < q; i++) {
            int x = queries[arr[i]];
            long total = h + (long)x * r;
            while (j < bags.length && total > pres[j]) {
                j++;
            }
            res[arr[i]] = j;
        }

        System.out.println(Arrays.stream(res).mapToObj(String::valueOf)
                           .collect(Collectors.joining(" ")));

    }

}

写在最后

在夜空所有星星熄灭的时候，所有梦想、所有溪流，都能汇入同一片大海中，那时我们终会相见。

alt

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

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

相关文章

识别卷子怎么弄？分享3款神奇的试卷识别软件！

识别卷子怎么弄？分享3款神奇的试卷识别软件！

在当今信息爆炸的时代&#xff0c;随着科技的飞速发展&#xff0c;人工智能已经深入到我们生活的方方面面。其中&#xff0c;试卷识别软件作为教育领域的一大亮点&#xff0c;正逐渐受到越来越多的关注。这类软件不仅能帮助教师减轻批改试卷的负担&#xff0c;还能提高工作效率…
阅读更多...
创建YonBIP模块项目

创建YonBIP模块项目

设置UAP HOME&#xff1a; 新建项目&#xff1a;File > New > Other > YonBuilder Premium Development 创建工程和模块成功 新建业务组件currtype 新建业务组件成功
阅读更多...
Docker容器（二）安装与初体验wordpress

Docker容器（二）安装与初体验wordpress

一、安装 1.1关闭SeLinux SeLinux&#xff08;Security-Enhanced Linux&#xff09;是一种基于Linux内核的安全模块&#xff0c;旨在提供更严格的访问控制和安全策略。它通过强制实施安全策略来限制系统资源的访问&#xff0c;从而保护系统免受恶意软件和未经授权的访问。 在…
阅读更多...
探索金融管理硕士项目：中国社科院与美国杜兰大学携手培养未来金融精英

探索金融管理硕士项目：中国社科院与美国杜兰大学携手培养未来金融精英

在当今竞争激烈的金融行业中&#xff0c;拥有卓越的专业知识和技能是取得成功的重要因素。而中国社科院与美国杜兰大学金融管理硕士项目&#xff0c;以其严谨的学术要求和实践导向的教学方法&#xff0c;为学生提供了绝佳的学习和成长机会。 中国社科院与美国杜兰大学金融管理硕…
阅读更多...
深度探讨 Golang 中并发发送 HTTP 请求的最佳技术

深度探讨 Golang 中并发发送 HTTP 请求的最佳技术

&#x1f482; 个人网站:【 海拥】【神级代码资源网站】【办公神器】&#x1f91f; 基于Web端打造的&#xff1a;&#x1f449;轻量化工具创作平台&#x1f485; 想寻找共同学习交流的小伙伴&#xff0c;请点击【全栈技术交流群】 在 Golang 领域&#xff0c;并发发送 HTTP 请求…
阅读更多...
Java学习（十八）--网络编程

Java学习（十八）--网络编程

介绍 需求 如何准确地定位网络上一台或多台主机&#xff1b; 定位主机上的特定的应用 找到主机后如何可靠高效地进行数据传输 目的 直接或间接地通过网络协议与其它计算机实现数据交换&#xff0c;进行通讯&#xff1b; 网络通信 网络&#xff1a;两台或多台设备通过一…
阅读更多...
详解SpringCloud微服务技术栈：Nacos服务搭建及服务分级存储模型

详解SpringCloud微服务技术栈：Nacos服务搭建及服务分级存储模型

&#x1f468;‍&#x1f393;作者简介&#xff1a;一位大四、研0学生&#xff0c;正在努力准备大四暑假的实习 &#x1f30c;上期文章&#xff1a;详解SpringCloud微服务技术栈&#xff1a;强推&#xff01;源码跟踪分析Ribbon负载均衡原理、Eureka服务部署 &#x1f4da;订阅…
阅读更多...
MIT 6s081 lab 1.Xv6 and Unix utilities

MIT 6s081 lab 1.Xv6 and Unix utilities

Lab1: Xv6 and Unix utilities 作业网址&#xff1a;https://pdos.csail.mit.edu/6.828/2020/labs/util.html Boot xv6(easy) 下载&#xff0c;启动xv6系统 $ git clone git://g.csail.mit.edu/xv6-labs-2020 Cloning into xv6-labs-2020... ... $ cd xv6-labs-2020 $ git …
阅读更多...
解决jmeter响应乱码的问题

解决jmeter响应乱码的问题

HTTP请求响应乱码 方法一&#xff1a;添加后置处理器BeanShell PostProcessor&#xff0c;写入【prev.setDataEncoding("utf-8")】 方法二&#xff1a;修改bin目录下的配置文件jmeter.properties&#xff0c;将配置修改为【sampleresult.default.encodingUTF-8】 J…
阅读更多...
【LeetCode每日一题】82. 删除排序链表中的重复元素 II

【LeetCode每日一题】82. 删除排序链表中的重复元素 II

2024-1-15 文章目录 [82. 删除排序链表中的重复元素 II](https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/) 82. 删除排序链表中的重复元素 II 思路&#xff1a; 创建一个虚拟节点 dummy 作为头节点的前置节点。使用两个指针 pre 和 cur 分别指向前一个非…
阅读更多...
光纤和光缆有何不同之处？

光纤和光缆有何不同之处？

很多人会有这样的疑问&#xff0c;光纤和光缆有何不同之处&#xff1f;主要是因为光纤和光缆这两个名词容易引起混淆。在严格的定义下&#xff0c;光纤和光缆是两种不同的东西&#xff0c;然而在现实生活中&#xff0c;许多人仍然会混淆这两者。为了更好地理解光纤和光缆之间的…
阅读更多...
通信算法之196: SIMO模式信道均衡算法及代码

通信算法之196: SIMO模式信道均衡算法及代码

详细参考文章192。
阅读更多...
全国博物馆数据， shp+excel数据，数据来源可靠，基于国家文物局发布的《2021年度全国博物馆名录》

全国博物馆数据， shp+excel数据，数据来源可靠，基于国家文物局发布的《2021年度全国博物馆名录》

数据名称: 全国博物馆数据 数据格式: shpexcel 数据几何类型: 点 数据坐标系: WGS84 数据来源&#xff1a;网络公开数据&#xff0c;数据名录来源于国家文物局发布的《2021年度全国博物馆名录》 数据字段&#xff1a; 序号字段名称字段说明1province省份名称2city城市名…
阅读更多...
GoZero微服务个人探索之路（三）Go-Zero官方rpc demo示例探究

GoZero微服务个人探索之路（三）Go-Zero官方rpc demo示例探究

官方网址&#xff1a;https://go-zero.dev/docs/tasks/cli/grpc-demo 项目结构 demo包 两个文件均为protoc-gen-go-grpc自动生成构成一个完整的 gRPC 服务的定义和实现 democlient包 demo.go goctl生成的客户端代码 Request 和 Response 别名&#xff1a; 定义了 Request 和…
阅读更多...
知识付费saas租户平台：揭秘成功的密码

知识付费saas租户平台：揭秘成功的密码

明理信息科技知识付费saas租户平台 随着互联网的快速发展&#xff0c;人们越来越重视知识的获取和价值的挖掘。在这个信息爆炸的时代&#xff0c;知识付费已经成为了一种新的商业模式&#xff0c;为知识的传播和价值的转化提供了更加高效和便捷的途径。本文将探讨知识付费的发…
阅读更多...
UI设计入门：解析用户界面的基础概念

UI设计入门：解析用户界面的基础概念

UI设计是什么&#xff1a;用户界面设计的基础 用户的视觉体验。一个好的用户界面需要强大、可靠和良好的使用感。用户界面设计应尽量减少用户与产品互动的能量&#xff0c;使用户更容易实现目标。 以我们最熟悉的应用程序界面为例。通常&#xff0c;手机软件的UI用户界面设计…
阅读更多...
LeetCode刷题---基本计算器

LeetCode刷题---基本计算器

解题思路&#xff1a; 根据题意&#xff0c;字符串中包含的运算符只有和- 使用辅助栈的方法来解决该问题 定义结果集res和符号位sign(用于判断对下一数的加减操作),接着对字符串进行遍历。 如果当前字符为数字字符&#xff0c;判断当前字符的下一个字符是否也是数字字符&#x…
阅读更多...
样式集-发布，发表页面完整代码及示意图

样式集-发布，发表页面完整代码及示意图

发表页面完整代码示意图 完整代码 wxml代码&#xff1a; <!--pages/publish/publish.wxml--> <view class"biaoqing" catchtap"showEmoji"><text>&#x1f60a;</text></view> <view class"fabiao" catchtap…
阅读更多...
Jmeter分布式性能测试

Jmeter分布式性能测试

在做后端服务器性能测试中&#xff0c;我们会经常听到分布式。哪你&#xff0c;是否了解分布式呢&#xff1f;今天&#xff0c;我们就来给大家讲讲&#xff0c;在企业实战中&#xff0c;如何使用分布式进行性能测试&#xff0c;实战过程中&#xff0c;又有哪些地方要特别注意&a…
阅读更多...
引领安全创新 | 安全狗方案入选工信部《2023年工业和信息化领域数据安全典型案例名单》

引领安全创新 | 安全狗方案入选工信部《2023年工业和信息化领域数据安全典型案例名单》

近日&#xff0c;工业和信息化部网络安全管理局公布了2023年工业和信息化领域数据安全典型案例名单。 安全狗与厦门卫星定位应用股份有限公司、中移 (上海) 信息通信科技有限公司联合申报的智慧交通云数据安全与隐私保障典型案例也成功入选。 厦门服云信息科技有限公司&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023