yzoj 2372 小B的数字 题解
2019-10-13 11:05:30来源:博客园 阅读 ()
yzoj 2372 小B的数字 题解
题意
判断是否存在一个序列 $ b_i $ 使得 $ \prod_{i = 1}^{n} b_i ?| b_i^{a_i}$ 恒成立,其中 $ b_i $ 中的每个数都是2的正整数次幂。
样例输入
3
2
3 2
3
3 3 3
2
1 10
样例输出
YES
YES
NO
数据范围
对于 100% 的数据有 $ n \leq 10^5,a_i \leq 10,T \leq 10$
解析
首先拿到这道题,考场一看就知道不是规律题就是数学公式题,事实上是的。
我们可以设 $ b_i=2^{x_i} $ 其中 $ x_i \(为正整数,\) lcm(a_1,a_2,a_3....a_n)=LCM $ , $ sum=\sum_{i = 0}^{n} x_i?$。
那么我们可以将原式子化为 $ 2^{sum} | 2^{x_i * a_i} $,显然要使此式恒成立,就要满足 $ a_i * x_i \geq sum $.
此式子可以转化为 $ lcm* x_i \geq sum* \frac{lcm}{a_i} $
左右两边相加可得
$ lcm* sum \geq sum * ( \sum_{i = 1}^{n} {\frac{lcm}{a_i}}?)$
即 $ lcm \geq ( \sum_{i = 1}^{n} {\frac{lcm}{a_i}}?)$
两边提出 $ lcm $约去得到 $ 1 \geq ( \sum_{i = 1}^{n} {\frac{1}{a_i}}?)$
那么我们可以得出最终公式就是 $ ( \sum_{i = 1}^{n} {\frac{1}{a_i}}?\leq 1) $
如果我们直接同分比较,很显然会超数据范围。
对于这一题,由于涉及倒数,会产生浮点误差,我们有三种方法去处理
方法一(不推荐
在最终判断的时候设置精度进行调控
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-6;
int T,n,k;
bool cheak(double a,double b){
if(a-b<=eps) return true;
else return false;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
double sum=0;
for(int i=1;i<=n;++i){
scanf("%d",&k);
sum+=1.0/(double)k;
}
if(cheak(sum,(double)1)) printf("YES\n");
else printf("NO\n");
}
return 0;
}
方法二(正解
我们可以观察数据,可以知道 $ a_i \leq 10 $ 我们最终得到得式子也只与 $ a_i $ 得倒数有关,所以我们可以将式子改造,左右两边乘以 $ 10! $,也就是
$ ( \sum_{i = 1}^{n} {\frac{10!}{a_i}}?\leq 10!) $
于是运算便变为了整数运算,便不存在浮点误差了!(常用技巧)
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
typedef long long ll;
int main(){
int t;
scanf("%d",&t);
while (t--){
int n;
scanf("%d",&n);
ll tot=0;
for(int i=0;i<n;i++){
int x;
scanf("%d",&x);
tot+=3628800/x;
}
puts(tot<=3628800 ? "YES" : "NO");
}
return 0;
}
方法三(巧妙的暴力
分析式子 $ ( \sum_{i = 1}^{n} {\frac{1}{a_i}}?\leq 1) $ 我们可以发现如果 $ n > max(a_i) $ 那么这个式子必然不成立,所以我们可以把n的范围缩小到 $ max(a_i) $ 以内,那么我们通分就不会超出范围了于是便有了一个愉快的暴力
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
scanf("%d",&t);
while (t--){
int n;bool flag=1;
scanf("%d",&n);
long long tot=0;
long long pop=1;
int maxn=0;
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
maxn=max(maxn,x);
if(x==1) flag=0;
tot+=x;
pop*=x;
}
if(!flag || n>maxn) printf("NO\n");
else puts(tot<=pop ? "YES" : "NO");
}
return 0;
}
原文链接:https://www.cnblogs.com/donkey2603089141/p/11663671.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:TinyXML2的快速实践
下一篇:C++和c语言的区别
- 括号生成 2020-04-09
- L1-007 念数字 (10分) 2020-03-22
- Qt5小Demo之猜数字游戏 2020-03-19
- 回文数字的验证 2020-03-13
- P1216 [IOI1994]数字三角形 2020-02-14
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash