soj1678解题报告

昨天没事干,本来切了2道水题,可以oj又挂了就没交上。今天交WA了一次,因为一个参数写错了= =简单总结一下。

题目大意:

抽象出如下序列:

1, 1、1,2, 1、1、1,1、2,3....

第i串序列要么其和比前面的长,要么字典序比前面的大。

序列和显然从1,2,3,……,n。

序列长度为i时,其个数有

f[i] = f[i-1] + f[i-2] + ... + f[1] + f[0] ;

最左边为1的为f[i-1]个,最左边为2的为f[i-2],i的为f[0]。。

f[0] = f[1] = 1 ;

so f[i] = 1 << ( i - 1 ) ;

对于给定的n,首先确定其长度,然后dfs下去即可,保存一个二维数组可以替换掉dfs,要codejam了...附代码如下。。

代码:

#include <stdio.h>

#include <stdlib.h>

#include <ctype.h>

#include <string.h>

/************************************************************************/

/* soj1678 */

/************************************************************************/

const int maxn = 33 ;

typedef unsigned sth ;

sth f[maxn] , n , ans[maxn] , cnt ;

void init()

{

int i ;

for( i = 2 , f[0] = f[1] = 1 ; i < maxn ; i++) f[i] = f[i-1] * 2 ;

}

void dfs(int len)

{

sth i , j = 1 ;

for( i = len-1 , j = 1 ; i >= 1 ; i--,j++)

{

if( n <= f[i] ) break;

if( n > f[i] ) n -= f[i] ;

}

if( n == f[i] ) { ans[cnt++] = j ; ans[cnt++] = i ; }

else { ans[cnt++] = j ; dfs(len-j); }

}

inline void solve()

{

sth i , j ;

cnt = 0 ;

for ( i = 1 ; i < maxn ; i++)

{

if( n > f[i] ) n -= f[i] ;

else if( n <= f[i] ) break ;

}

if( n < f[i] ) dfs(i);

else ans[cnt++] = i ;

for( i = 0 ; i < cnt ; i++)

{

for( j = 0 ; j < ans[i] ; j++)

putchar('/');

for( j = 0 ; j < ans[i] ; j++)

putchar('\\');

}

puts("");

}

int main()

{

init();

while (~scanf("%u",&n),n) solve();

}

本文出自 [email protected] 博客,请务必保留此出处http://karsbin.blog.51cto.com/1156716/879320

更多相关文章
  • 题意和解决回路匹配的思路如同hdu3488 (这里我第一次想到最短路,但是对于有回路这个不知道怎么处理,后来看了别人的解题报告才知道KM匹配,但是看到KM之后就自己想...想了很久....还是不知道回路这个地方怎么匹配......其实应该这样来想....总共有N个城市....如果是要形成回路..那么 ...
  • http://poj.org/problem?id=1173 发现此题资料甚少,斗胆第一次写一份解题报告[题意]     输入 n(代表二进制位数) k(代表黑条白条总共有几条,条形码是以黑条开始的,再白黑交替出现) m(代表每条最多占多少个二进制位)     输出这种模式的条形码的有多少个?    ...
  • 题目大意:使用两个哈希表来解决哈希冲突的问题.假如现在有两个哈希表分别为:H1,H2 ,大小分别为:n1,n2:现有一数据X需要插入,其插入方法为: 1.计算index1 = X MOD N1,  若哈希表H1的index1位置没有保存数据,则直接将X保存到H1得index1:否则,若哈希表H1的i ...
  • 题目大意:输入一个偶数(x<32),输出这个偶数是由哪两个素数相加所得. 比如:一个偶数26,它可以是3+23,7+19,13+13,这些素数相加所得. 输入输出样例: Sample Input 3 4 26 100 Sample Output 4 has 1 representation(s ...
  • 本题大意: 用天平对一物品进行称重,现有重量不同的砝码,砝码的重量分别为:1,3,9,27,..,3^n.(n<20) 天平的右侧放砝码,左侧放物品或物品和砝码,使得左右两边的重量相等. 现有一个物品,计算左右两边应当分别放多少个多大的砝码才能使得天平平衡. 例如:现在有一个重量为21的物品, ...
  • 好几年没有做ACM了,感觉忘得差不多了,这个做着做着就打瞌睡了!言归正传,下面是我的解题思路: 首先的话,我们可以画一个函数图,以输入数组的下标为X轴,以数组的和为Y轴,当数组和小于零时,我们使用备用的数组和sum2和备用的最小下标min2,并用flag进行标记.具体实现可以参考代码. 需要注意的地 ...
  • 一.原题中文大意. 1      2       3      4       5      6         7     8 9     10       11    12      13     14       15    16 17    18      19    20       21 ...
  • //我是莱鸟,多多交流 //380k //94ms 题目的意思是:每种装备可由多个生产商提供,从每一种装备中选择一个厂家的设备,使得所选的总的各种装备中的最小带宽B与他们的价格之和P的比值B/P达到最大. 解题思路: 准备工作:在输入时,统计所有装备中的最小值min,和每种装备中的最大值max,然后 ...
一周排行
  • IOS開發PCH文件的使用
    PCH文件存储一些共享的数据,在其他的文件可以直接使用,这样减少程序输入,比如存储宏定义
  • SpringMVC JQuery Ajax Get Post请求在Tomcat中乱码解决方案 SpringMVC 3.12 JQuery 1.8.2 Tomcat 6.0.35 1.乱码很烦人,Spring mvc的 ...
  • 本篇中我们只讲解如何在Unity中对Protobuf-net进行序列化(Serialize)与反序列化(Deserialize),关于Unity的socket(插座)网络通信部分我们后续开篇. 首先去Protobuf
  • Week7 周三会议流程: 确定分工(20min) 开始工作(数据库初版.界面初版.写逻辑的两个人先写用户文档去吧……) 项目原型设计要求: √1. 确定应用扩展点 2. 需求分析文档: ·功能描述:用例图(中天.甲
  • 原创文章转载请注明出处:@协思, http://zeeman.cnblogs.com 后端系统中的Log是相当重要的,做过高并发服务的同学都会认同这一点.相对而言,调试已经用处不大了,对于这样的项目,我现在也习惯了这
  • hdu 4642 翻硬幣
    在一个n*m的棋盘上 每一个格子都有一枚硬币 1表示正面 0表示反面你每次可以选择一个硬币
  • 整合apache和tomcat <<<<<<<JDK安装环境 从[url]ftp://202.38.75.75/pub/linux_soft/java/jre-1_5_0_1 ...
  • 1.外连接 ·MS SQL SERVER 支持两种形式表间连接 ①从Sybase继承来的形式: 字段1 *= 字段2 (左连接) 字段1 =* 字段2 (右连接) 没有这种形式的全外连接语法 ②标准的外连接语法 le ...
  • 当你创建Pool时,其他第一台Xenserver服务器为Master角色,如果此台XenServer无法使用,会导致你所描述的问题.其次,在pool中XenServer的开.关机顺序也所讲究. 主节点故障 如果需要,
  • SelectDirectory()函數
    #include <FileCtrl.hpp>   void __fastca ...