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,然后 ...
一周排行