JZOJ.3769【NOI2015模拟8.14】A+B
2024-08-31 15:08:39
Description
对于每个数字x,我们总可以把它表示成一些斐波拉切数字之和,比如8 = 5 + 3, 而22 = 21 + 1,因此我们可以写成 x = a1 * Fib1 + a2 * Fib2 + a3 * Fib3 + … + an * Fibn, 其中,Fib1 = 1, Fib2 = 2…. Fib[i] = Fib[i – 1] + Fib[I - 2], 且a[n] > 0.那么我们称ai为x的一种斐波拉切表示,由于表示方法有很多种,我们要求最大化a[1…n],即,如果b[1…n]和a[1…m]都可以表示x,若m > n 则a更大,若 m = n, 则从高位到低位比,第一个不同处i,若ai > bi 则a比b大。
你的任务很简单,给你两个用斐波拉切数最大化表示的两个数字,输出他们相加后用斐波那契最大化表示的数字。
Input
两行,分别表示两个数字
每一行开头一个n,表示长度
然后紧接着n个数字,为从低位到高位。
Output
同输入格式。一行。
Sample Input
4 0 1 0 1
5 0 1 0 0 1
Sample Output
6 1 0 1 0 0 1
Data Constraint
对于30%的数据 长度 <= 1000
对于100%的数据 长度 <= 1000000
算出十进制值相加后再用斐波那契最大化表示显然接受不了,我们得在序列里找出规律。
这里有两个不难发现的运算法则:
1.如果有连续两位i,i-1是1,那么它们可以“运算”使得第三位i+1是1. 如 0 1 0 1 1 0 = 0 1 0 0 0 1
2.如果这个位i是2,那么它可以使它的后一位i+1和前两位i-2是1. 如 0 0 2 0 0 1 0=1 0 0 1 0 1 0
随便弄上十几次这样就可以了。
#include<cstdio>
#include<iostream>
using namespace std;
int f[],n,x,len1,len2;
int main(){
f[]=;
f[]=;
f[]=;
scanf("%d",&len1);
for (int i=;i<=len1;i++)
scanf("%d",&f[i]);
scanf("%d",&len2);
for (int i=;i<=len2;i++){
int x=;
scanf("%d",&x);
f[i]+=x;
}
int qwq=max(len1,len2);
int qoq=true;
do{
qoq=false;
int qaq=qwq;
for (int i=;i<=qwq;i++){
if ((f[i-])&&(f[i])){
f[i+]++;
qwq=max(qwq,i+);
f[i]--;
f[i-]--;
}
}
if (f[]==){
f[]++;
f[]=;
}
if (f[]==){
f[]++;
qwq=max(qwq,);
f[]++;
f[]=;
}
bool quq=true;
do{
quq=false;
for (int i=;i<=qaq;i++){
if (f[i]>=){
quq=true;
f[i+]++;
qwq=max(i+,qwq);
f[i-]++;
f[i]--;
f[i]--;
}
}
if (quq) qoq=true;
} while(quq);
} while(qoq); //直到没修改为止
printf("%d ",qwq);
for(int i=;i<=qwq;i++)
printf("%d ",f[i]);
return ;
}
神奇的代码
最新文章
- tomcat 设置jvm内存
- 简单CSS3实现炫酷读者墙
- 在线OJ实用技巧(转载)
- Android开发环境
- BugHD for JavaScript上线,轻松收集前端 Error
- 操作系统开发系列—13.b.进程之丰富中断处理程序
- LAMP 之 mysql 安装
- SAP debug的几种方式
- 关于集合的练习P235-1,2,3
- OpenJudge计算概论-错误探测
- vs 设置生成的实体为复数
- Java基础知识强化之IO流笔记11:递归之递归概述和注意事项
- new date() 函数在浏览器中的兼容问题!!
- Studious Student Problem Analysis
- java作业—3
- webpack-dev-server运行时报错
- datatables隐藏列与createdRow渲染bootstrapSwitch形成的BUG
- 局域网下Android与scoket通信的实现
- xshell使用rz/sz完成文件上传下载
- 002-打开文件管理规范-20190406.bat