Codeforces 515C 题解(贪心+数论)(思维题)
题面
传送门:http://codeforces.com/problemset/problem/515/C
Drazil is playing a math game with Varda.
Let’s define f(x)f(x)for positive integer x as a product of factorials of its digits. For example, f(135)=1!∗3!∗5!f(135)=1!∗3!∗5!
First, they choose a decimal number a consisting of n digits that contains at least one digit larger than 1. This number may possibly start with leading zeroes. Then they should find maximum positive number x satisfying following two conditions:
x doesn’t contain neither digit 0 nor digit 1.
f(x)=f(a)f(x)=f(a)
Help friends find such number.
题目大意:
定义f(x)为x的每一位的阶乘之积
给出一个数a,求满足条件(x的每一位没有0或1)的最大x,使f(x)=f(a)
分析:
此题可用贪心求解
贪心的思路是很显然的,应该让x的位数尽量多,而每一位尽量小,最大的数应该排在最左边
这样,我们就可以把a的每一位拆开
如a=6
6!=6*5*4*3*2*1=6*5!=3!*5!
所以6可以被替换成35
所以我们把0~9的数字拆开(其实0,1应该直接舍去,因为不符合条件)
0!=0!
1!=1!
2!=2!
3!=3!
4!=3!*4=3!*2!*2!
5!=5!
6!=5!*6=5!*3!
7!=7!
8!=7!*8=7!*2!*2!*2!
9!=9*8*7!=7!*3!*3!*2!;
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const string convert[10]={"0","0","2","3","322","5","53","7","7222","7332"};
string s;
string ans;
int n;
int cmp(char x,char y){
return x>y;
}
int main(){
scanf("%d",&n);
cin>>s;
ans="";
for(int i=0;i<n;i++){
if(s[i]-'0'==0||s[i]-'0'==1) continue;
ans=ans+convert[s[i]-'0'];
}
// cout<<ans<<endl;
sort(ans.begin(),ans.end(),cmp);
cout<<ans<<endl;
}
最新文章
- 杂项之图像处理pillow
- 设计模式 之 命令(Command)模式
- A Year Of Books - 2016 Javaer书单
- STL--vector(转载)
- 原生Javascript实现控制DIV属性
- Java多线程——线程同步
- SQL Server索引进阶:第十五级,索引的最佳实践
- JDBC连接数据库(MySQL)
- jdbc3
- 从vultr购买到搭ss看世界
- cuda中模板的使用
- VisualSVN Server安装过程
- PyQuery详解
- HTTP请求行、请求头、请求体详解
- React 学习(五) ---- 条件和列表渲染
- go语言调用append之后是否重新分配内存?
- ghostscript远程代码执行漏洞复现
- 寻路——AI
- Flex 布局知识点梳理
- xbox360 双65厚机自制系统无硬盘 U盘玩游戏方法
热门文章
- 使用webpack搭建react开发环境
- #431 Div2 Problem B Tell Your World (鸽巢原理 &;&; 思维)
- 最近在写一些树上的东西,先发一波LCA的吧!
- Angular项目 Error: [ngRepeat:dupes] Duplicates in a repeater are not allowed.报错
- (贪心+队列)String
- flex几种多列布局
- MySQL多表查询合并结果union all,内连接查询
- 杂项-站点:SharePoint
- MVC3: 页面向服务传参(view->;controller,get,post)
- 阶段1 语言基础+高级_1-3-Java语言高级_06-File类与IO流_07 缓冲流_5_BufferedWriter_字符缓冲输出流