Codeforces Round (Div.3) C.Sort (前缀和的应用)

news/2024/9/17 3:39:52/ 标签: 算法, 前缀和, codeforces, c++, 观察力

原题:

time limit per test:5 seconds

memory limit per test:256 megabytes

You are given two strings a and b of length n. Then, you are (forced against your will) to answer q queries.

For each query, you are given a range bounded by l and r. In one operation, you can choose an integer i (l≤i≤r) and set ai=x where x is any character you desire. Output the minimum number of operations you must perform such that sorted(a[l..r])=sorted(b[l..r]). The operations you perform on one query does not affect other queries.

For an arbitrary string c, sorted(c[l..r]) denotes the substring consisting of characters cl,cl+1,...,cr sorted in lexicographical order.

Input

The first line contains t (1≤t≤1000) – the number of test cases.

The first line of each test case contains two integers nn and q (1≤n,q≤2⋅10^5) – the length of both strings and the number of queries.

The following line contains a of length n. It is guaranteed aa only contains lowercase latin letters.

The following line contains b of length n. It is guaranteed bb only contains lowercase latin letters.

The following q lines contain two integers l and r (1≤l≤r≤n) – the range of the query.

It is guaranteed the sum of n and q over all test cases does not exceed 2⋅10^5.

Output

For each query, output an integer, the minimum number of operations you need to perform in a new line.

翻译:

问题描述:

你被给定了两个长度为 n 的字符串 ab。然后,你需要(虽然是被迫的)回答 q 个查询。

对于每个查询,你会得到一个由 lr 确定的范围。在一个操作中,你可以选择一个整数 il ≤ i ≤ r)并将 a[i] 设置为你希望的任何字符。输出你必须执行的最小操作次数,以确保 sorted(a[l..r]) = sorted(b[l..r])。你对一个查询执行的操作不会影响其他查询。

对于任意字符串 csorted(c[l..r]) 表示在 c[l]c[r] 的子字符串中按字典序排序后的子字符串。

输入:

第一行包含 t1 ≤ t ≤ 1000)—— 测试用例的数量。

每个测试用例的第一行包含两个整数 nq1 ≤ n, q ≤ 2⋅10^5)—— 两个字符串的长度和查询的数量。

接下来一行包含长度为 n 的字符串 a。字符串 a 只包含小写字母。

接下来一行包含长度为 n 的字符串 b。字符串 b 只包含小写字母。

接下来 q 行,每行包含两个整数 lr1 ≤ l ≤ r ≤ n)—— 查询的范围。

保证所有测试用例中 nq 的总和不超过 2⋅10^5

输出:

对于每个查询,输出一个整数,表示你需要执行的最小操作次数,每个查询输出一行。

Cf的题属于是想到就出结果,想不到就卡死,没有很多的模板可以套用,必须要先观察,千万不要上来就暴力,很可能连签到都过不去哦

观察发现,这道题其实就是求在一个区间当中,两个字符串有多少个字符不同的数量,那可以假设一下,如果暴力来敲,先截取[l,r]的字符串,然后排序,然后去遍历一遍看有多少不同

如果是这样想基本就陷入到坑里面出不来了,因为的话按照字典序排序之后,你没办法要求两个字符串中相同的字符的字符位置一一对应,不同的一一对应,是有这种情况的,那么在看题目本身的需求,就是求有多少不同的个数,那其实对每个字符串求前缀和,记录第i个位置的26字母分别出现的次数,然后在给出区间之后在去对比前缀和中26字母数量的差异,相同就不用管,不同就加上不同的个数,最后除以2(因为两个字符串都加了一遍)

代码:

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>using namespace std;void solve() {int n, q;cin >> n >> q;vector<vector<int>> pre1(n + 1,vector<int>(26,0));vector<vector<int>> pre2(n + 1,vector<int>(26,0));for(int i = 1;i <= n;i ++){char ch;cin >> ch;pre1[i][ch - 'a'] ++;for(int j = 0;j < 26;j ++){pre1[i][j] += pre1[i - 1][j];}}for(int i = 1;i <= n;i ++){char ch;cin >> ch;pre2[i][ch - 'a'] ++;for(int j = 0;j < 26;j ++){pre2[i][j] += pre2[i - 1][j];}}  while(q --){int l,r;int res = 0;cin >> l >> r;for(int i = 0;i < 26;i ++){int A = pre1[r][i] - pre1[l - 1][i];int B = pre2[r][i] - pre2[l - 1][i];res += abs(A - B);}cout << res / 2 << endl; }
}int main() {int t;cin >> t;while (t--) {solve();}return 0;
}

加油


http://www.ppmy.cn/news/1522321.html

相关文章

【重学 MySQL】十四、显示表结构

【重学 MySQL】十四、显示表结构 使用DESCRIBE或DESC命令使用SHOW COLUMNS命令查询information_schema数据库使用SHOW CREATE TABLE命令总结 在MySQL中&#xff0c;查看或显示表结构是一个常见的需求&#xff0c;它可以帮助你了解表中包含哪些列、每列的数据类型、是否允许为空…

DUFS 文件服务器,简单好用的http文件共享服务器

DUFS 文件服务器&#xff0c;简单好用的http文件共享服务器 0b6eabb13654 sigoden/dufs:latest "/bin/dufs" 4 months ago Up 8 days 0.0.0.0:5000->5000/tcp, :::5000->5000/tcp dufs_server 1. 拉取Dufs Docker镜像 docker pull sigoden/dufs …

【机器学习】机器学习引领未来:赋能精准高效的图像识别技术革新

&#x1f4dd;个人主页&#x1f339;&#xff1a;Eternity._ &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; ❀目录 &#x1f50d;1. 引言&#x1f4d2;2. 机器学习基础与图像识别原理&#x1f341;机器学习概述&#xff1a;监督学习、无监督学习与强化学…

自定义Stater

一 什么是stater&#xff1f; 我们平时在导入依赖的时候&#xff0c;大部分导入的都是xxx-spring-boot-stater。那是因为它们都基于spring的规则将写好的框架定义成一个stater&#xff0c;这样方便springboot引用它们写好的功能。 那我们为什么也要自定义stater呢&#xff1f…

zabbix6.4连接邮箱发出警告

添加告警媒介 默认接收人: 故障级别:{TRIGGER.STATUS}。 服务器:【{HOSTNAME1} 】 发生:{TRIGGER.NAME} 故障! 注:默认接收人:相当于邮件的主题 默认信息:邮件的主题 告警主机:{HOSTNAME1} 告警时间:{EVENT.DATE} {EVENT.TIME} 告警等级:{TRIGGER.SEVERITY} 告警信息:{TRIGGER.…

Java开发笔记--通用消息组件设计(移动短信、华为短信、163邮件)

最近项目开发完了&#xff0c;整理梳理了一下框架&#xff0c;总结记录一下通用消息组件的设计。 项目中的消息的存在种类多样性&#xff1a;APP消息、短信、邮件、站内消息&#xff0c;短信的服务商又有多种。我们项目采用的是spirng cloud alibaba,于是把消息这块抽出来做成…

【OpenCV3】图像的翻转、图像的旋转、仿射变换之图像平移、仿射变换之获取变换矩阵、透视变换

1 图像的放大与缩小 2 图像的翻转 3 图像的旋转 4 仿射变换之图像平移 5 仿射变换之获取变换矩阵 6 透视变换 1 图像的放大与缩小 resize(src, dsize[, dst[, fx[, fy[, interpolation]]]]) src: 要缩放的图片dsize: 缩放之后的图片大小, 元组和列表表示均可.dst: 可选参数, 缩…

前端跨域问题详解与解决方案指南

什么是跨域问题 跨域问题通常是由浏览器的同源策略&#xff08;Same-OriginPolicy&#xff0c;SOP&#xff09;引起的访问问题 同源策略是浏览器的一个重要安全机制&#xff0c;它用于限制一个来源的文档或脚本如何能够与另一个来源的资源进行交互 同源策略的定义 同源策略要…

尚品汇-支付宝介绍、跳转支付订单页面实现(四十六)

目录&#xff1a; &#xff08;1&#xff09;支付宝介绍 &#xff08;1&#xff09;支付宝介绍 &#xff08;3&#xff09;显示付款页面信息 &#xff08;5&#xff09;创建支付控制器PaymentController &#xff08;1&#xff09;支付宝介绍 支付宝简介 支付宝&#xf…

DAY53

字符串接龙 import java.util.*;public class Test {public static int bfs(String beginStr,String endStr,List<String> wordList){HashSet<String> setnew HashSet<>(wordList);Queue<String> quenew LinkedList<>();HashMap<String,Inte…

图形语言传输格式glTF和三维瓦片数据3Dtiles(b3dm、pnts)学习

文章目录 一、3DTiles二、b3dm三、glTF1.glTF 3D模型格式有两种2.glTF 场景描述结构和坐标系3.glTF的索引访问与ID4.glTF asset5.glTF的JSON结构scenesscene.nodes nodesnodes.children transformations对外部数据的引用buffers 原始二进制数据块&#xff0c;没有固有的结构或含…

[论文笔记] LLM大模型剪枝篇——1、调研

Attention Is All You Need But You Don’t Need All Of It For Inference of Large Language Models LLaMA2在剪枝时,跳过ffn和跳过full layer的效果差不多。相比跳过ffn/full layer,跳过attention layer的影响会更小。 跳过attention layer:7B/13B从100%参数剪枝到66%,平…

【Linux】Linux常见指令以及权限理解(上)

【Linux】Linux常见指令以及权限理解 &#x1f955;个人主页&#xff1a;开敲&#x1f349; &#x1f525;所属专栏&#xff1a;Linux&#x1f34a; &#x1f33c;文章目录&#x1f33c; 1. Linux背景 1.1 Linux发展史 1.1.1 Unix发展历史 1.1.2 Linux发展历史 1.2 开源 1.3 企…

PostgreSQL常用函数用法

在PostgreSQL中&#xff0c;函数是处理和操作数据的强大工具。以下是一些常用函数的用法示例。 1. 字符串函数 字符串函数用于操作和处理文本数据&#xff0c;常见操作包括字符串连接、截取、替换、转换大小写等。 LENGTH: 返回字符串的长度。-- 查询语句 SELECT LENGTH(Post…

【word导出带图片】使用docxtemplater导出word,通知书形式的word

一、demo-导出的的 二、代码操作 1、页面呈现 项目要求&#xff0c;所以页面和导出来的word模版一致 2、js代码【直接展示点击导出的js代码】 使用插件【先下载这五个插件&#xff0c;然后页面引入插件】 import docxtemplater from docxtemplater import PizZip from pizzip …

Linux基础入门 --8 DAY

文件权限管理 设置文件的所有者chown 格式&#xff1a; chown [OPTION]... [OWNER][:[GROUP]] FILE... chown [OPTION]... --referenceRFILE FILE... 示例&#xff1a; chown admin&#xff08;所有者&#xff09;&#xff1a;admin&#xff08;所属组&#xff09;f1.txt cho…

Linux下构建Docker镜像

Docker在Linux构建镜像 Docker是一种轻量级的容器化技术&#xff0c;可以让开发者将应用程序及其所有依赖项打包到一个独立的容器中&#xff0c;从而实现跨平台和快速部署&#xff0c;在Linux系统上&#xff0c;我们可以使用D0cker来构建自己的镜像&#xff0c;并且可以通过简…

Win32函数调用约定(Calling Convention)

平常我们在C#中使用DllImportAttribute引入函数时&#xff0c;不指明函数调用约定(CallingConvention)这个参数&#xff0c;也可以正常调用。如FindWindow函数 [DllImport("user32.dll", EntryPoint"FindWindow", SetLastError true)] public static ext…

SpringBoot实现前后端传输加密设计

在Web应用中&#xff0c;确保前后端之间的数据传输安全是非常重要的。这通常涉及到使用HTTPS协议、数据加密、令牌验证等安全措施。本文通过将前后端之间的传输数据进行加密&#xff0c;用于在Spring Boot应用中实现前后端传输加密设计。 一、数据加密方案 即使使用了HTTPS&…

IP地址中的子网掩码

目录 一、子网掩码的概念 二、引入子网掩码的原因 1. 网络分段&#xff08;Subnetting&#xff09; 2. IP地址的组织 3. 有效利用IP地址 4. 减少广播域 5. 支持路由 三、子网掩码的划分 例子1 例子2 1. 子网掩码的二进制表示 2. 网络地址 3. 广播地址 4. 可用主机…