ACWing.第 128 场周赛 (B、C题解)

B、5286. 翻倍(思维+推导)

一、题目要求

给定两个正整数,初始时两数均为 1。

你可以进行任意次(也可以不进行)翻倍操作,每次操作任选一个非负整数 k,令两数中的一个数乘以 k,另一个数乘以 k^2。

请你计算,是否能够通过一系列操作,使得最终第一个数变为 a,第二个数变为 b。

输入格式

第一行包含整数 T,表示共有 T�组测试数据。

每组数据占一行,包含两个整数 a,b。

输出格式

每组数据输出一行结果,如果任务可以达成,则输出 Yes,否则输出 No

数据范围

前 33 个测试点满足 1≤T≤5。
所有测试点满足 1≤T≤350000,1≤a,b≤10^9。

输入样例:
4
2 4
75 45
8 8
16 16
输出样例:
Yes
Yes
Yes
No

二、思路(推导)

 根据算术基本定理 :每个正整数都可以唯一地分成若干质数的乘积 
考虑k>=2范围 ,且只需考虑k为质数的情况  
p1 p2 p3 ... pn
假设用了x1个p1,x2个p2 ...xn个pn
总的操作次数=x1+x2+..+xn
次数       a            b               c
              1            1                1
x1          p1^2      p1              p1^3      相当于有x1个p1的3次方相乘,即p1^(3*x1),以此类推
x2         p2          p2^2           p2^3
xn         pn         pn^2          pn^3
a*b=p1^(3x1)+p2^(3x2)+...+pn^(3xn);
1.x1<=x等价p1^x1能够整除a  p1^(x1)|a  x1(全分1次) <=x<=2x1(全分两次) 
2.x1<=y等价p1^x1能够整除b  p2^(x2)|b  x1(全分1次) <=y<=2x1(全分两次) 
3.x+y=3x1 x1=(x+y)/3 
x:代表1变换到a所用的次数,y:代表1变换到b所用次数
若x,y在x1~2x1之间,且满足(x+y)能整除3,则说明x1有解,代表它满足条件
t=p1^(x1/3) p2(x2/3)…p3(xn/3);(pi与pj之间两两互质且独立) t就相当ab开三次方根
x1=(x+y)/3;
t=p1^(x1/3) *p2(x2/3)*...*p3(xn/3);(pi与pj之间两两互质且独立) 
等价于 p1^(x1/3)|a   p1^(x1/3)|b(x|y代表x能y整除,即y%x==0)
等价于 a能够被t整数 t|a t|b
即:如果 t为整数,且a%t==0&&b%t==0,则一定有解 

三、代码

#include<bits/stdc++.h>
#define endl '\n'
typedef long long ll;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f;
int a,b;
void solve()
{cin>>a>>b;//int t=round(pow((LL)a*b,1.0/3));/*round(),将一个浮点数四舍五入到最接近的整数 3.4=3   3.6=4
如果参数x的小数部分>=0.5,则返回大于x的最小整数,否则返回小于x的最大整数 */ int t=pow((ll)a*b,1.0/3)+1e-8;//可能会有精度问题 if(t*(ll)t*t==(ll)a*b&&a%t==0&&b%t==0){cout<<"YES"<<endl;} else{cout<<"NO"<<endl;}
}
signed main()
{int t;cin>>t;while(t--){solve();}return 0;
} 

C、5287. 数量(组合数+dfs或者组合数+手动模拟)

一、题目要求

给定两个整数 n,k。

请你计算,一共有多少个长度为 n 的整数数组 a1,a2,…,an 能够同时满足:

  1. 数组 a 恰好是一个 1∼n的排列。
  2. 至少有 n−k个索引 i(1≤i≤n)满足 ai=i。
输入格式

共一行,包含两个整数 n,k。

输出格式

一个整数,表示满足条件的整数数组数量。

数据范围

前 44 个测试点满足 4≤n≤5,1≤k≤4。
所有测试点满足 4≤n≤1000,1≤k≤4。

输入样例1:
4 1
输出样例1:
1
输入样例2:
4 2
输出样例2:
7
输入样例3:
5 3
输出样例3:
31
输入样例4:
5 4
输出样例4:
76

 二、思路

1.思路

给出n个位置,只允许k个人不在自己的位置上,又因为k<=4,所以进行考虑的情况有k=0,2,3,4,可以手动模拟,也可以利用错排列公式。

2.错排列公式:

1.定义:考虑一个有n个元素的排列,若一个排列中所有的元素都不在自己原来的位置上,
那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为D(n)

2.公式:

 

 

3.推导过程

ans=c(n,k)*dfs(1,k) (组合数(o(1))*dfs(o(1))) 
1.k=0,则说明每个人都在自己的座位上说明只有一种情况
2.k=1,不可能只有1个人不在自己的座位上
3.k=2,c(n,2)*1
4.k=3,c(n,3)*2 
    1 2 3
  a.2 3 1
  b.3 1 2
5.k=4 c(n,4)*9
    1 2 3 4
  a.2 1 4 3
  b.2 4 1 3
  c.2 3 4 1
  d.3 1 4 2
  e.3 4 1 2
  f.3 4 2 1
  g.4 1 2 3
  h.4 3 1 2
  i.4 3 2 1

三、代码

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
const int N=1100;
const int inf=0x3f3f3f3f;
int a[N];
int n,k;
//int path[5];
bool st[5];
int dfs(int u,int n)
{if(u>n)return 1;int res=0;for(int i=1;i<=n;i++){if(i!=u&&!st[i])//不能填自己,并且这个数没有被访问过{//	patu[u]=i; st[i]=true;res+=dfs(u+1,n);//加上递归下一层的结果 st[i]=false;} }return res;
}
int c(int a,int b)
{int res=1,i,j;for(i=a,j=1;j<=b;i--,j++){res=res*i/j;}return res;
}
void solve()
{cin>>n>>k;int res=1;//c(n,0)=1 for(int i=2;i<=k;i++)//最多有k个索引不满足所以进行累加 {res+=c(n,i)*dfs(1,i);}cout<<res<<endl;
}
signed main()
{int t=1;while(t--){solve();}return 0;
}


 

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

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

相关文章

响应式项目施工装饰工程企业网站模板源码带后台

模板信息&#xff1a; 模板编号&#xff1a;647 模板编码&#xff1a;UTF8 模板颜色&#xff1a;蓝色 模板分类&#xff1a;基建、施工、地产、物业 适合行业&#xff1a;建筑施工类企业 模板介绍&#xff1a; 本模板自带eyoucms内核&#xff0c;无需再下载eyou系统&#xff…

python opencv 实现对二值化后的某一像素值做修改和mask叠加

实现对二值化后的某一像素值做修改 使用OpenCV的findNonZero函数找到所有非零&#xff08;也就是像素值为255&#xff09;的像素&#xff0c;然后遍历这些像素并修改他们的值。示例代码&#xff1a; import cv2 import numpy as np # 加载并二值化图像 img cv2.imread(…

使用 Python 进行自然语言处理第 4 部分:文本表示

一、说明 本文是在 2023 年 3 月为 WomenWhoCode 数据科学跟踪活动发表的系列文章中。早期的文章位于&#xff1a;第 1 部分&#xff08;涵盖 NLP 简介&#xff09;、第 2 部分&#xff08;涵盖 NLTK 和 SpaCy 库&#xff09;、第 2 部分&#xff08;涵盖NLTK和SpaCy库&#xf…

产品经理日常工作流程汇总

产品经理在日常的团队工作过程中&#xff0c;承担着重要的衔接作用。由于工作性质的特殊性&#xff0c;产品经理日常工作内容特别繁杂&#xff0c;导致很多产品小白刚一上手&#xff0c;会无从下手&#xff0c;经常丢三落四。这时拥有一个好的工作流程&#xff0c;很大程度上就…

C语言 用字符串比较函数cmp来做一个门禁:账号密码是否匹配 (干货满满)

#include<stdio.h> #include<string.h> void fun04() {for (int i 0; i < 3; i){char *str01 "hello";char uname[100] ;printf("请输入账号");scanf("%s",uname);char *str02 "123456";char pword[100];printf(&qu…

Chromebook文件夹应用新功能

种种迹象表明 Google 旗下的 Chromebooks 近期要有大动作了。根据 Google 团队成员透露&#xff0c;公司计划在 Chrome OS 的资源管理器中新增“Recents”&#xff08;最近使用&#xff09;文件&#xff0c;以便于用户更快找到所需要的文件。 种种迹象表明 Google 旗下的 Chro…

【移远QuecPython】EC800M物联网开发板调用网络API(使用SIM卡联网并调用高德地图API的定位坐标转换)

【移远QuecPython】EC800M物联网开发板调用网络API&#xff08;使用SIM卡联网并调用高德地图API的定位坐标转换&#xff09; 高德API使用方法&#xff1a; 文章目录 API相关配置SIM卡联网网络操作API调用 高德地图API产品介绍适用场景使用限制使用说明坐标转换 附录&#xff…

【漏洞复现】Apache_HTTP_2.4.50_路径穿越漏洞(CVE-2021-42013)

感谢互联网提供分享知识与智慧&#xff0c;在法治的社会里&#xff0c;请遵守有关法律法规 文章目录 1.1、漏洞描述1.2、漏洞等级1.3、影响版本1.4、漏洞复现1、基础环境2、漏洞扫描3、漏洞验证方式一 curl方式二 bp抓捕 1.5、修复建议 说明内容漏洞编号CVE-2021-42013漏洞名称…

Visual Studio 2010 软件安装教程(附下载链接)——计算机二级专用编程软件

下载链接&#xff1a; 提取码:2wAKhttps://www.123pan.com/s/JRpSVv-9injv.html 安装步骤如下&#xff1a; 1.如图所示&#xff0c;双击打开【Visual Studio 2010简体中文旗舰版】文件夹 2.如图所示&#xff0c;找到“Setup”文件夹打开&#xff0c;双击运行“setup” 3.如图…

RxJava/RxAndroid的基本使用方法(一)

文章目录 一、什么是RxJava二、使用前的准备1、导入相关依赖2、字段含意3、Upstream/Downstream——上/下游4、BackPressure5、BackPressure策略6、“热” and “冷” Observables7、 基类8、事件调度器9、操作符是什么&#xff1f; 三、RxJava的简单用法1、Observable——Obse…

看了“米小圈”,才知道竟然有如此宝藏的动画片

在这个竞争激烈的时代里&#xff0c;作为孩子家长&#xff0c;都希望自己的孩子将来能够出类拔萃&#xff0c;我也不例外。自从孩子上小学后&#xff0c;就将孩子的学习作为第一要务&#xff0c;不再一味地纵容他贪玩&#xff0c;不允许他浪费时间。 我家孩子很淘气&#xff0…

【网络协议】聊聊DNS协议如何域名解析和负载均衡

DNS 服务器 我们知道如果使用IP地址进行访问网站&#xff0c;很难进行记忆&#xff0c;所以DNS的作用是将域名转换成对应的IP地址。如果全世界都使用同一台DNS服务器&#xff0c;那么DNS服务器本身需要保证服务的高可用、高性能&#xff0c;以及分布式等。最好的方式就是分层。…

【MongoDB】MongoExport如何过滤数据导出

问题 使用MongoDB处理导出数据时&#xff0c;想增加数据过滤操作。 例如&#xff1a;导出所有isGirl为true的所有数据。 分析 在mongoexport说明文档中找到了query字段和queryFile字段&#xff0c;用来进行数据查询匹配导出。 query字段 后面直接跟 json格式数据。 queryF…

java高并发系列-第1天:必须知道的几个概念

同步&#xff08;Synchronous&#xff09;和异步&#xff08;Asynchronous&#xff09; 同步和异步通常来形容一次方法调用&#xff0c;同步方法调用一旦开始&#xff0c;调用者必须等到方法调用返回后&#xff0c;才能继续后续的行为。异步方法调用更像一个消息传递&#xff…

承载AI计算的数据中心网络和传统数据中心有何不同?

生成式AI正在风靡全球&#xff0c;不少企业开始研究如何在其业务流程中采用人工智能技术&#xff0c;更有一些企业客户开始考虑在数据中心和私有云中部署自己的AIGC和 GPU 扩展网络。从网络角度来看&#xff0c;用于承载这类业务的数据中心与传统的数据中心有很大不同&#xff…

JVM 内存和 GC 算法

文章目录 内存布局直接内存执行引擎解释器JIT 即时编译器JIT 分类AOT 静态提前编译器&#xff08;Ahead Of Time Compiler&#xff09; GC什么是垃圾为什么要GC垃圾回收行为Java GC 主要关注的区域对象的 finalization 机制GC 相关算法引用计数算法&#xff08;Reference Count…

Flink(一)【WordCount 快速入门】

前言 学完了 Hadoop、Spark&#xff0c;本想着先把 Kafka、Flume 这些工具先学完的&#xff0c;但想了想还是把核心的技术先学完最后再去把那些工具学学。 最近心有点累哈哈哈&#xff0c;偷偷立个 flag&#xff0c;反正也没人看&#xff0c;明年的今天来这里还愿哈&#xff0c…

深度学习之基于Yolov5人体姿态摔倒识别分析报警系统(GUI界面)

欢迎大家点赞、收藏、关注、评论啦 &#xff0c;由于篇幅有限&#xff0c;只展示了部分核心代码。 文章目录 一项目简介 二、功能三、系统四. 总结 一项目简介 系统设计概述&#xff1a; 传感器采集&#xff1a;通过在场景中布置摄像头或红外传感器等设备&#xff0c;采集人体…

GZ035 5G组网与运维赛题第8套

2023年全国职业院校技能大赛 GZ035 5G组网与运维赛项&#xff08;高职组&#xff09; 赛题第8套 一、竞赛须知 1.竞赛内容分布 竞赛模块1--5G公共网络规划部署与开通&#xff08;35分&#xff09; 子任务1&#xff1a;5G公共网络部署与调试&#xff08;15分&#xff09; 子…

数学到底在哪里支撑着编程?

如果编程语言是血肉&#xff0c;那么数学的思想和知识就是灵魂。它可以帮助你选择合适的数据结构和算法&#xff0c;提升系统效率&#xff0c;并且赋予机器智慧。在大数据和智能化的时代更是如此。举个例子&#xff0c;我们在小学就学过的余数&#xff0c;其实在编程的世界里也…