刷题记录(240613)

aliyun0512

1. 小红定义一个数组是好数组,当且仅当所有奇数出现了奇数次,所有偶数出现了偶数次。现在小红拿到了一个数组,她希望取一个该数组的非空子序列(可以不连续),使得子序列是好数组。你能帮小红求出子序列的方案数吗?由于答案过大,请对1e9+ 7取模。

示例:

输入:
4
1 2 3 2
输出: 7

思路:数学问题

设奇数出现x次,那么所有可能的情况就是:

C_x^1+C_x^3+...+C_x^x=2^{x-1}

但也可能一次不出现,所以还要加一

设一个偶数出现x次,那么所有可能的情况就是

C_x^0+C_x^2+...+C_x^x=2^{x-1}

那么要求的结果就是全部情况相乘,再减1,剪掉空串的情况(题中要求了是非空子串)

1.将数组 a[i] 元素输入map = < a[ i ] , 出现次数>

2.遍历map,计算乘积,最后减1

3.取模mod

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int a[100010],pow2[100100];
map<int,int>mp;
signed main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];mp[a[i]]++;}pow2[0]=1;int ans=1;for(int i=1;i<=n;i++)pow2[i]=pow2[i-1]*2%mod;for(auto i:mp){if(i.first%2!=0)ans=ans*(pow2[i.second-1]+1)%mod;else ans=ans*pow2[i.second-1]%mod;}cout<<ans-1;
}

2.定义一个01串为“交错串”,当且仅当任意两个相邻的字符都是不同的。例如,"10101"是交错串. 现在小红拿到了一个01串,她有若干次询问,每次询问一个区间,你需要回答将该区间代表的连续子串修改为“交错串”的最小修改次数。每次修改可以修改任意一个字符。

示例:

输入:
6 3
101101
1 3
3 5
1 6
输出:
0
1
3

输入描述

第一行输入两个正整数n,q,代表字符串长度和询问次数。
第二行输入一个长度为n的、仅由'0'和'1'组成的字符串。
接下来的q行,每行输入两个正整数l,r,代表询问的是第l个字符到第r个字符组成的子串,
1≤n,q≤1e5
1<=l,r<=n

输出描述

输出q行,每行输出一个整数代表询问的答案。

思路:

只有两种形式:101010和010101

1. 两个数组sum1,sum2统计前缀和

sum1---101010--遍历字符串,统计不满足奇数位是1偶数位是0的数量

sum2---010101--遍历字符串,统计不满足奇数位是0偶数位是1的数量

2. 最后输出l-1和r差值较小的那个

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int sum1[100010],sum2[100010];
signed main(){int n,q;cin>>n>>q;string s;cin>>s;s=" "+s;for(int i=1;i<s.size();i++){sum1[i]=sum1[i-1];sum2[i]=sum2[i-1];if(i&1){if(s[i]!='1')sum1[i]++;if(s[i]!='0')sum2[i]++;}else {if(s[i]!='0')sum1[i]++;if(s[i]!='1')sum2[i]++;}}while(q--){int l,r;cin>>l>>r;cout<<min(sum1[r]-sum1[l-1],sum2[r]-sum2[l-1])<<endl;}
}

小红拿到了一棵树,她希望选挥两个不相邻且不相同的节点,满足编码的乘积为偶数。请你帮小红求出合法的方案数。我们认为 <x,y> 和<y,x>为同一种方案。

输入描述:

第一行输入一个正整数n,代表节应数量.
接下来的n-1行,每行输入2个正整数u,v.代表节点u和节点v有一条边连接。
1<=n<=1e5
1<=u,v<=n

输出描述:

一个整数,代表取点的方案数

示例

输入: 
3
1 3
2 3
输出: 
1

思路:

先算出总共的方案,然后拿总的减去相邻节点的方案。

总共的方案数 = 偶数点的数量 * 奇数点的数量 + 取两个偶数点的取法数量 - 相邻的乘积为偶数的情况

num0--偶数数量,num1--奇数数量,ans---计算树中节点值乘积为偶数的边的数量,负数

遍历当前节点的所有子节点 v,如果子节点 v 等于父节点 f,则跳过(避免回到父节点, 题目中写了<x,y> 和<y,x>为同一种方案)。如果当前节点 u 和子节点 v 的乘积是偶数,则减少 ans 的计数(因为不能取相邻节点)。最后,对每个子节点递归调用 dfs

(num0 - 1) * num0 / 2---计算所有两个偶数节点组成的边的数量

涉及节点的题都会用dfs

所以上面的公式用变量表示为:

num0 * num1 + (num0 - 1) * num0 / 2 + ans

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int num0,num1,ans;
vector<int>e[100010];
void dfs(int u,int f){if(u%2==0)num0++;else num1++;for(auto v:e[u]){if(v==f)continue;if(u*v%2==0)ans--;dfs(v,u);}
}
signed main(){int n;cin>>n;for(int i=1;i<=n-1;i++){int u,v;cin>>u>>v;e[u].push_back(v);e[v].push_back(u);}dfs(1,0);ans+=num0*num1+(num0-1)*num0/2;cout<<ans;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C# Winform Datagridview控件使用和详解

DataGridView 是一种以表格形式显示数据的控件&#xff0c;由Rows(行)&#xff0c;Columns(列)&#xff0c;Cells(单元格)构成。本实例将综合利用DataGridView的属性和事件&#xff0c;展示不同的表格风格数据和操作。包含&#xff1a; 添加Datagridview行&#xff0c;列数据设…

APP IOS

APP IOS苹果源生应用程序 APP Android-CSDN博客

【Python/Pytorch 】-- K-means聚类算法

文章目录 文章目录 00 写在前面01 基于Python版本的K-means代码02 X-means方法03 最小二乘法简单理解04 贝叶斯信息准则 00 写在前面 时间演变聚类算法&#xff1a;将时间演变聚类算法用在去噪上&#xff0c;基本思想是&#xff0c;具有相似信号演化的体素具有相似的模型参数…

【开源项目】智慧北京案例~超经典实景三维数字孪生智慧城市CIM/BIM数字孪生可视化项目——开源工程及源码!

飞渡科技数字孪生北京管理平台&#xff0c; 依托实景数字孪生底座&#xff0c;以城市感知网络为硬件基础&#xff0c;以城市大数据为核心资源&#xff0c;以数字孪生、云计算、人工智能为关键技术&#xff0c;实现城市产业规划、资产安全管理、城市能耗监控等一体化空间融合。 …

实现锚点链接点击tab跳转到指定位置 并且滚动鼠标顶部锚点的样式也跟随变化

实现效果如下 不管是点击还是 滚动鼠标 顶部的样式也会跟随变化 点击会跳转到指定的位置 通过IntersectionObserver 监听是否可见 下面代码可以直接执行到vue的文件 <template><div><ul class"nav"><li v-for"tab in tabs" :key…

Java——访问修饰符

一、访问修饰符是什么 Java中的访问修饰符用于控制类、接口、构造函数、方法和数据成员&#xff08;字段&#xff09;的可见性和访问级别。 Java提供了四种访问修饰符&#xff1a; 访问修饰符同一类内同一包内不同包的子类不同包的非子类适用对象public可见可见可见可见类、…

第 7 章: 对象关系映射

在第 6 章中&#xff0c;我们大概了解了如何通过 JDBC 来进行简单的数据库操作。通过 SQL 来执行操作虽然不算复杂&#xff0c;但在面向对象的语言中&#xff0c;这类操作多少显得有些格格不入&#xff0c;毕竟我们都是在与“对象”打交道。把对象与关系型数据库关联起来&#…

【目标检测】图解 DETR 系统框图

简略版本 Backbone&#xff1a;CNN backbone 学习图像的 2D 特征Positional Encoding&#xff1a;将 2D 特征展平&#xff0c;并对其使用位置编码&#xff08;positional encoding&#xff09;Encoder&#xff1a;经过 Transformer 的 encoderDecoder&#xff1a;encoder 的输出…

光纤中的数值 2.405 是怎么一回事?

在光纤通信中,光线的传播依赖于纤芯和包层之间的折射率差异。 即,当光线从纤芯入射到界面上时,如果入射角大于临界角 θ0,将发生全反射,没有光能量透射至包层而泄漏出去,此即光纤导光原理。 反映到光纤的端面,在光纤端面的光线,当入射角必须小于光纤的孔径角 α0 ,此时…

laravel中如何向字段标签添加工具提示

首先&#xff0c;您可以使用 轻松自定义字段标签->label()。我相信您知道这一点。但您知道吗……标签输出未转义&#xff1f;这意味着您也可以在标签中包含 HTML。 为了尽快实现上述目标&#xff0c;我只是采取了一个快速而粗糙的解决方案&#xff1a; CRUD::field(nickna…

Python 修炼|人人编程手册|001 计算思维

在微信中阅读,关注公众号:CodeFit。 > 创作不易,如果你觉得这篇文章对您有帮助,请不要忘了 点赞、分享 和 关注,为我的 持续创作 提供 动力! 1. 计算思维 在我们正式开启 Python 修炼之旅前,先来了解一个关键的概念 —— 计算思维。 计算思维,其核心本质在于 抽象 …

学生护眼大路灯应该怎么选?五款护眼大路灯对比推荐

我们都知道光线无处不在&#xff0c;想要减少近视隐患&#xff0c;就不得不提一下护眼灯了&#xff0c;特别是经常坐在电脑前码字的上班族以及深夜还在学习的学生党这一类人群&#xff0c;经常用眼光线不好不仅影响视力健康&#xff0c;还会影响效率。而一款护眼灯能够提供柔和…

阐述一下Golang中defer的原理

基本用法 在Go语言中&#xff0c;defer关键字用于在函数返回前执行一段代码或调用一个清理函数。这对于处理文件关闭、解锁或者返回一些资源到资源池等操作非常有用。 其基本用法如下所示&#xff1a; package mainimport "fmt"func main() {example() }func exam…

AI穿戴设备是未来手机的终结者?中国AI商业化的未来预测

AI技术的发展正处于商业化应用的关键阶段&#xff0c;而中国在互联网时代已凭借商业化应用逆袭。AI算法大模型虽强大&#xff0c;但真正普惠民众需与设备深度结合。穿戴式智能设备就成为了新战场&#xff0c;AI算法与穿戴设备结合能释放更大工作效率。私人助理AI将成趋势&#…

AI口语练习APP的开发流程

开发AI口语练习APP是一个持续的过程&#xff0c;需要多学科团队的紧密合作&#xff0c;包括产品经理、UI/UX设计师、前后端开发者、机器学习工程师、测试工程师和市场运营人员等。随着技术的发展和用户需求的变化&#xff0c;开发流程可能需要相应地进行调整和优化。AI口语练习…

【学习笔记】Mybatis-Plus(二) :常用注解

常用注解 注解含义应用场景TableName表名注解&#xff0c;标识实体类对应的表表名和实体类名称不一致TableId主键注解&#xff0c;标识实体类的主键主键需要指定自增长TableField字段注解数据库名称和字段名称不一致TableLogic逻辑删除不是真正物理删除数据KeySequence序列主键…

任务调度框架革新:TASKCTL在Docker环境中的高级应用

Docker&#xff1a;轻量级容器化技术的魅力 Docker 作为一款开源的轻量级容器化技术&#xff0c;近年来在 IT 界掀起了一股热潮。它通过封装应用及其运行环境&#xff0c;使得开发者可以快速构建、部署和运行应用。Docker 的优势在于其轻量级、可移植性和可扩展性&#xff0c;它…

【element-ui】el-date-picker动态设置picker-options

<el-date-pickerv-model"formObj.startDate"type"date"placeholder"开始时间":picker-options"startPickerOptions"> </el-date-picker><el-date-pickerv-model"formObj.endDate"type"date"placeh…

Ubuntu安装qemu-guest-agent

系列文章目录 Ubuntu-24.04-live-server-amd64安装界面中文版 Ubuntu-24.04-live-server-amd64启用ssh Ubuntu乌班图安装VIM文本编辑器工具 文章目录 系列文章目录前言一、安装二、启用服务三、效果总结 前言 QEMU Guest Agent&#xff08;简称QEMU GA或QGA&#xff09;在虚拟…

thinkphp5使用模型删除与复杂查询EXP

模型删除 应用软删除 表中需要有字段&#xff0c;deletetime 模型中使用下面方法 use SoftDelete;protected $deleteTime delete_time;真实删除 // 软删除 User::destroy(1); // 真实删除 User::destroy(1,true); $user User::get(1); // 软删除 $user->delete(); // 真…