当前位置: 首页 > news >正文

公式推导+dfs简版

写在前面的话:心可以冷,但手不能停
第一题:C. Flexible String
题目大意:给一个aaa字符串和bbb字符串和数字kkk,首先设置一个计数器cntcntcnt,其中可以对aaa字符串做以下操作:替换aaa中的一个字母xxx,将字母xxx加入到集合QQQ,如果这个字母已经在集合QQQ中了,则cntcntcnt不动,否则cnt++cnt++cnt++,记s[l,r]s[l,r]s[l,r]为在[l,r][l,r][l,r]区间中aaabbb的字母全相等。达到的目标为在cnt≤kcnt \leq kcntk的情况下,让s[l,r]s[l,r]s[l,r]的数量最大。
解题思路: 这个题可以这样想,对于任意一个a[i]≠b[i]a[i] \neq b[i]a[i]=b[i],可以将这个位置记作一个断点,被断点隔开的若干个区间可以用这样的形式来表达s[l,r]s[l,r]s[l,r]的数量:len∗(len+1)/2len*(len+1)/2len(len+1)/2,其中len为区间内的字母数量。我们注意到如果将某个满足a[i]≠b[i]a[i] \neq b[i]a[i]=b[i]的字母加入到集合QQQ中,则区间可能被连上,注意可能断点是由两个字母组成的。这样的话,考虑k最大可能为101010,则可以用数位dpdpdp或者dfsdfsdfs等,来枚举所有可能性。枚举出一种可能性,之后只要用O(n)O(n)O(n)判断即可,大概是10810^8108这样的级别,那么这里的枚举状态可以用这种形式表达:

for(int i=0;i<1024;i++)

注意,由于我把集合中的字母用mapmapmap映射,所以所有字母不能映射到000,否则wronganswerontest3wrong\space answer \space on\space test3wrong answer on test3
代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<map>
using namespace std;
typedef long long ll;
const int length = 1e5 + 5;
char a[length];
char b[length];
ll max(ll a, ll b)
{if (a > b)return a;else return b;
}
ll solve(int i, map<char, int> &mp,int n,int k)
{vector<int> flag(20, 0);int q = 0;for (int j = 1; j <= 10; j++){if (i&(1 << j)){flag[j] = 1;q++;}}if(q>k)return 0;int s = 0;ll res = 0;while (s < n){int tmp = s;while (a[s] == b[s]||flag[mp[a[s]]]==1){s++;if (s >= n)break;}int len = s - tmp;res = res + (ll)(len + 1)*len / 2;s++;}return res;}
int main(void)
{int t;scanf_s("%d", &t);for (int i = 0; i < t; i++){int n;int k;scanf_s("%d%d", &n, &k);getchar();//收\nscanf_s("%s", a,sizeof(a));getchar();//收\nscanf_s("%s", b,sizeof(b));getchar();map<char,int> mp;int cnt = 0;for (int i = 0; i < n; i++){if (a[i] != b[i]){if (mp[a[i]] == 0){mp[a[i]] = ++cnt;}}}if (cnt <= k){ll tmp = (ll)n*(n + 1) / 2;printf("%lld\n", tmp);continue;}vector<ll> dp(1500, 0);ll ans = -1;for (int i = 0; i < 1024; i++){ll a=solve(i*2, mp,n,k);ans = max(ans, a);}printf("%lld\n", ans);}
}

第2题:D. Flexible String Revisit
这个题比较有意思
题目大意: 给一个由0和1组成的两个字符串,对字符串a可以做以下操作:可以任选一个数字对其进行反转,问达到两个字符串第一次相等所需要的操作次数期望。
解题思路
参考文章
代码:

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long ll;
int mod = 998244353;
const int length = 1e6 + 5;
int f[length][2];
int dp[length];
char a[length];
char b[length];
int ksm(int k)
{int tmp = mod-2;int base = k;int ans = 1;while (tmp){if (tmp % 2 == 1){ans = (ll)ans*base%mod;}base = (ll)base*base%mod;tmp = tmp >> 1;}return ans;
}
int solve(int n, int k)
{f[n][0] = 1;f[n][1] = 1;for (int i = n-1; i >= 0; i--){int now = ((ll)1 - (ll)(n - i)*f[i + 1][1]%mod *ksm(n) % mod + mod) % mod;f[i][0] = ((ll)1 + (ll)(f[i+1][0])*(n-i)%mod*ksm(n) % mod) % mod*ksm(now)%mod;f[i][1] = (ll)i*ksm(n) % mod*ksm(now) % mod;}dp[0] = f[0][0];for (int i = 1; i <= k; i++){dp[i] = (ll)((ll)dp[i - 1] * f[i][1] % mod + f[i][0]) % mod;}return dp[k];
}
int main(void)
{int t;scanf_s("%d", &t);for (int i = 0; i < t; i++){int n;scanf_s("%d", &n);int k = 0;getchar();scanf_s("%s", a,sizeof(a));//a.push_back(t);getchar();scanf_s("%s", b, sizeof(b));getchar();for (int i = 0; i < n; i++){if (a[i] != b[i])k++;}int a1=solve(n, k);printf("%d\n", a1);}
}

相关文章:

公式推导+dfs简版

写在前面的话&#xff1a;心可以冷&#xff0c;但手不能停 第一题&#xff1a;C. Flexible String 题目大意&#xff1a;给一个aaa字符串和bbb字符串和数字kkk&#xff0c;首先设置一个计数器cntcntcnt,其中可以对aaa字符串做以下操作&#xff1a;替换aaa中的一个字母xxx&#…...

论文笔记 | 标准误聚类问题

关于标准误的选择&#xff0c;如是否选择稳健性标准误、是否采取聚类标准误。之前一直是困惑的&#xff0c;惯用的做法是类似主题的文献做法。所以这一次&#xff0c;借计量经济学课程之故&#xff0c;较深入学习了标准误的选择问题。 在开始之前推荐一个知乎博主。他阅读了很…...

银行管理系统--课后程序(Python程序开发案例教程-黑马程序员编著-第7章-课后作业)

实例1&#xff1a;银行管理系统 从早期的钱庄到现如今的银行&#xff0c;金融行业在不断地变革&#xff1b;随着科技的发展、计算机的普及&#xff0c;计算机技术在金融行业得到了广泛的应用。银行管理系统是一个集开户、查询、取款、存款、转账、锁定、解锁、退出等一系列的功…...

【18】组合逻辑 - VL18 实现3-8译码器①

VL18 实现3-8译码器① 1 题目 【这题我的思路非常绝境】奈斯 !! 看真值表的思路:Yi所在列【0仅一个其余全1】,故【以0为对象求解】 观察发现:E3 E2_n E1_n = 100 时 是 译码的使能信号 ; 并且E3 E2_n E1_n为其他值时,都不使能译码 然后就很简单,没有仿真就成功了 2 代…...

2020蓝桥杯真题最长递增 C语言/C++

题目描述 在数列a_1 ,a_2,⋯,a_n 中&#xff0c;如果a_i <a_i1 <a_i2<⋯<a_j&#xff0c;则称 a_i至 a_j为一段递增序列&#xff0c;长度为 j−i1。 定一个数列&#xff0c;请问数列中最长的递增序列有多长。 输入描述 输入的第一行包含一个整数 n。 第二行包含…...

华为OD机试题 - 寻找连续区间(JavaScript)| 机考必刷

更多题库,搜索引擎搜 梦想橡皮擦华为OD 👑👑👑 更多华为OD题库,搜 梦想橡皮擦 华为OD 👑👑👑 更多华为机考题库,搜 梦想橡皮擦华为OD 👑👑👑 华为OD机试题 最近更新的博客使用说明本篇题解:寻找连续区间题目输入输出示例一输入输出说明示例二输入输出Cod…...

一次疲惫的调试--累了及时透气

原创 射频清茶 深山小老虎 2023-03-11 14:32发表于广东 收录于合集 #射频调试3个 #网分4个 #Wi-Fi 2个 进来透透气 道不尽红尘舍恋 诉不完人间恩怨 世世代代都是缘 喝着相同的水 留着相同的血 这条路漫漫又长远 红花当然配绿叶 这一辈子谁来陪 渺渺茫茫来又回 往日情景再…...

综合练习7 摄氏度转华氏温度(“\t“的使用,循环语句)

综合练习7 摄氏度转华氏温度 使用do…while循环&#xff0c;在控制台输入摄氏温度与华氏温度的对照表。 对照表从摄氏温度-30℃到50℃&#xff0c;每行间隔10℃&#xff0c;运行如下&#xff1a; 摄氏温度&#xff1a;-30℃ 华氏温度&#xff1a;-22.0℉ 摄氏温度&#xff1a;…...

AWS数据库总结

RDS – 联机事务处理OLTP&#xff08;Online Transaction Processing&#xff09;&#xff0c;包括&#xff1a; SQL ServerOracleMySQL ServerPostgreSQLAuroraMariaDB非关系数据库DynamoDB数据仓库RedShift – 联机分析处理OLAP&#xff08;Online Analytics Processing&…...

2个步骤就能批量给视频添加滚动字幕

现在很多小伙伴在剪辑视频的时候都会给自己的视频添加适配的字幕&#xff0c;但是有很多的视频想要添加一样的滚动字幕时&#xff0c;有一个能批量添加剪辑的工具非常重要&#xff0c;今天小编就给大家分享一个可以批量剪辑大量视频的工具&#xff0c;下面一起看看具体的操作步…...

PHP 的运行方式有哪些?

PHP本质上的运行方式可以分为两种&#xff1a; 基于命令行的基于PHP-FPM的 但实际上&#xff0c;PHP能做的事很多&#xff0c;很多场景下&#xff0c;不同的运行方式能让开发更方便&#xff0c;减轻各种工作。 测试开发 PHP内置了一个HTTP 的server。这意味着&#xff0c;很…...

Web学习3_JavaScript

1.1 JS的调用方式与执行顺序 使用方式 HTML页面中的任意位置加上<script type"module"></script>标签即可。 常见使用方式有以下几种&#xff1a; 直接在<script type"module"></script>标签内写JS代码。script type"modu…...

「MySQL基础」不可重复读和幻读的区别

「MySQL基础」不可重复读和幻读的区别 文章参考&#xff1a; 在数据库中不可重复读和幻读到底应该怎么分&#xff1f; 作者&#xff1a;暖猫Suki、普通熊猫 文章目录「MySQL基础」不可重复读和幻读的区别一、概述二、小结一、概述 正好在琢磨这个问题&#xff0c;也被搞得头昏…...

CorelDRAW2023最新版新增功能200多个新模板

CorelDRAW是一款平面矢量绘图排版软件&#xff0c;CorelDRAW运用涵盖企业VI设计&#xff0c;广告设计&#xff0c;包装设计&#xff0c;画册设计&#xff0c;海报、招贴设计&#xff0c;UI界面设计&#xff0c;网页设计&#xff0c;书籍装帧设计&#xff0c;插画设计&#xff0…...

springboot自定义日志以及行号正确展示

在开发springboot项目时&#xff0c;我们可能需要自定义日志实现。需要对slf4j的日志实现进行一次外层包装 这个很简单&#xff0c;按照org.slf4j.Logger方式定义一个类Logger类MyLogger。 让后实现MyLoggerImpl&#xff1a; public class MyLoggerImpl implements CoreLogge…...

【GAOPS055】verilog 乘法、除法和取余

乘法硬件原理 结论 可以将乘法A x B转为A的移位相加。 利用乘2n就是左移n位的特性乘2^n就是左移n位的特性乘2n就是左移n位的特性&#xff0c;将数拆分为2n2^n2n表示 思路1 原始列竖式计算方法ref例2.9 思路2 B总是可以拆分为&#xff1a;B(an2nan−12n−1...a121a020)B(…...

TCP UPD详解

文章目录TCP UDP协议1. 概述2. 端口号 复用 分用3. TCP3.1 TCP首部格式3.2 建立连接-三次握手3.3 释放连接-四次挥手3.4 TCP流量控制3.5 TCP拥塞控制3.6 TCP可靠传输的实现3.7 TCP超时重传4. UDP5.TCP与UDP的区别TCP UDP协议 1. 概述 TCP、UDP协议是TCP/IP体系结构传输层中的…...

金三银四、金九银十 面试宝典 MySQL面试题 超级无敌全的面试题汇总(超万字的面试题,让你的MySQL无可挑剔)

MySQL数据库 - 面试宝典 又到了 金三银四、金九银十 的时候了&#xff0c;是时候收藏一波面试题了&#xff0c;面试题可以不学&#xff0c;但不能没有&#xff01;&#x1f941;&#x1f941;&#x1f941; 一个合格的 计算机打工人 &#xff0c;收藏夹里必须有一份 MySQL 八…...

【Java】初识Java

Java和C语言有许多类似之处&#xff0c;这里就只挑不一样的点来说&#xff0c;所以会比较杂乱哈~ 目录 1.数据类型 2.输入与输出 2.1三种输出 2.2输入 2.3循环输入输出 //猜数字小游戏 //打印乘法口诀表 3.方法 //交换两个数&#xff08;数组的应用&#xff09; //模…...

JVM相关知识

JVM类加载过程类什么时候被加载什么情况下会发生栈内存溢出JVM内存模型常量池回收方法区垃圾回收流程圾收集算法分代收集理论标记-清除算法标记-复制算法标记-整理算法类加载过程 加载–验证–准备–解析–初始化–使用–卸载 ​ 加载&#xff1a;通过全类名获取类的二进制流…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

redis和redission的区别

Redis 和 Redisson 是两个密切相关但又本质不同的技术&#xff0c;它们扮演着完全不同的角色&#xff1a; Redis: 内存数据库/数据结构存储 本质&#xff1a; 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能&#xff1a; 提供丰…...

MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释

以Module Federation 插件详为例&#xff0c;Webpack.config.js它可能的配置和含义如下&#xff1a; 前言 Module Federation 的Webpack.config.js核心配置包括&#xff1a; name filename&#xff08;定义应用标识&#xff09; remotes&#xff08;引用远程模块&#xff0…...