HDOJ-1041 Computer Transformation(找规律+大数运算)

http://acm.hdu.edu.cn/showproblem.php?pid=1041

有一个初始只有一个1的串 每次都按①0 -> 10;②1 -> 01;这两条规则进行替换

形如:n = 1  1

   n = 2  01

   n = 3  1001

   ...

求经过n步替换之后 串中只含复数个0的连续子串(不难发现,这种子串只能是‘00’)的出现次数

因为0<n<=1000的限制 在最坏情况下(n==1000)串的长度将达到2^1000位 排除了直接模拟上述替换过程的可能

列出前几项的替换结果:

n = 0                       1  ‘00’=0  ‘01’=0
n = 1                       01  ‘00’=0  ‘01’=1
n = 2                     1001  ‘00’=1  ‘01’=0
n = 3                   01101001  ‘00’=1  ‘01’=2
n = 4              1001011001101001  ‘00’=3  ‘01’=2
n = 5   01101001100101101001011001101001  ‘00’=5  ‘01’=6

在上面的数据 不仅给出结果串 还统计出了串中‘00’对和‘01’对的个数【注:‘01’的个数是取出全部的‘00’对后才统计】

从n = 3开始 观察可以发现 01 -> 1001    即每个00对(1001)都是由01对转化而来

而每个00对(1001)又将产生一个 00对 和 两个 01对(见n=2->3)

由上述可得 n步时00对的个数 = n-1步的00对的个数 + n-1的01对的个数(即n-2步的00对的个数 * 2)

所以可以推得 f(n) = f(n - 1) + f(n - 2) * 2

如果细心的话,可以发现,当n大到一定程度时,由于上面给出的公式有着与斐波拉契数列相似的递增效应, 最终结果的数值会非常大大大大大,用__int64都远远无法满足

所以采用字符数组来模拟大数加法运算

# include <stdio.h>
# include <string.h>
# define MAX 1001
# define LEN 1001

char Number[MAX][LEN];

void BigNumPlus()
{
	for(int i = 3; i < MAX; i++)
	{
		memset(Number[i], ‘0‘, LEN);//初始化

		for(int j = 0; j < LEN; j++)//模拟公式
		{
			Number[i][j] += (Number[i - 1][j] - ‘0‘) + (Number[i - 2][j] - ‘0‘) + (Number[i - 2][j] - ‘0‘);
		}

		for(int j = 0; j < LEN; j++)//处理进位
		{
			if(Number[i][j] > ‘9‘)
			{
				Number[i][j + 1] += (Number[i][j] - ‘0‘) / 10;
				Number[i][j] = (Number[i][j] - ‘0‘) % 10 + ‘0‘;
			}
		}
	}
}

int main()
{
	//初始值
	memset(Number[1], ‘0‘, LEN);
	memset(Number[2], ‘0‘, LEN);
	Number[1][0] = ‘0‘;
	Number[2][0] = ‘1‘;

	BigNumPlus();

	int n;
	while(scanf("%d",&n) != EOF)
	{
		if(n == 1)//特殊处理
		{
			printf("0\n");
			continue;

		}
		for(int i = LEN - 1; i >= 0; i--)
		{
			if(Number[n][i] != ‘0‘)//格式输出
			{
				while(i >= 0) printf("%c",Number[n][i--]);
				printf("\n");
				break;
			}
		}
	}

	return 0;
}

  

时间: 02-18

HDOJ-1041 Computer Transformation(找规律+大数运算)的相关文章

hdu 4952 Number Transformation (找规律)

题目链接 题意:给你个x,k次操作,对于第i次操作是:要找个nx,使得nx是>=x的最小值,且能整除i,求k次操作后的数 分析: 经过打表找规律,会发现最后的x/i,这个倍数会趋于一个固定的值,求出这个固定的值和K相乘就可以了, 为什么会趋于固定的值呢,因为最后虽然i在不断增长,但是x也是在增长的,每次的倍数会回退一个发现 有余数,然后再加上一个,所以趋于稳定. 官方题解: 1 #include <iostream> 2 #include <cstdio> 3 #includ

H - Computer Transformation(简单数学题+大数)

H - Computer Transformation Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit Status Practice _ Appoint description:  System Crawler  (Oct 10, 2016 1:02:59 PM) Description A sequence consisting of one digit, the numb

Acdream 1210 Chinese Girls&#39; Amusement(大数模板运算 + 找规律)

传送门 Chinese Girls' Amusement Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others) Submit Statistic Next Problem Problem Description You must have heard that the Chinese culture is quite different from that of Europe or Rus

Codeforces Round #242 (Div. 2)C(找规律,异或运算)

一看就是找规律的题.只要熟悉异或的性质,可以秒杀. 为了防止忘记异或的规则,可以把异或理解为半加运算:其运算法则相当于不带进位的二进制加法. 一些性质如下: 交换律: 结合律: 恒等律: 归零律: 典型应用:交换a和b的值:a=a^b^(b=a); #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<

找规律/数位DP HDOJ 4722 Good Numbers

题目传送门 1 /* 2 找规律/数位DP:我做的时候差一点做出来了,只是不知道最后的 is_one () 3 http://www.cnblogs.com/crazyapple/p/3315436.html 4 数位DP:http://blog.csdn.net/cyendra/article/details/11606209 5 */ 6 #include <cstdio> 7 #include <iostream> 8 #include <algorithm> 9

UVALive 6270 Edge Case(找规律,大数相加)

转载请注明出处:http://blog.csdn.net/u012860063?viewmode=contents 找规律,前两个数的和等于后一个数的值: 其实就是大菲波数: 代码如下: #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #include<cstdio> #include<cst

大数+找规律 ACdream1210 Chinese Girls&#39; Amusement

传送门:点击打开链接 题意:对于n个点围成的圈.从一个点出发,顺时针数K个位置,一直进行这个操作直到回到最初的那个点时,恰好把所有的点都访问了一遍,问最大的K(K<=n/2) 思路:很容易就想到了一种方法,找到K<=n/2,且gcd(K,n)=1,有人是用java从n/2向1去枚举的,感觉好暴力,所以当时不敢这样写 后来发现其实是有规律的,从n=3一直算下去,会得到一个这样的序列1 1 2 1 3 3 4 3 5 5 6 5 7 7 8 7 9 9 10 9..... 很明显以4个为一组,一下

2016(胡赛复现)_大数找规律

Time Limit: 5 Sec  Memory Limit: 128 MB Description 给出正整数 n 和 m,统计满足以下条件的正整数对 (a,b) 的数量: 1. 1≤a≤n,1≤b≤m;  2. a×b 是 2016 的倍数. Input 输入包含不超过 30 组数据. 每组数据包含两个整数 n,m (1≤n,m≤109). Output 对于每组数据,输出一个整数表示满足条件的数量. Sample Input 32 63 2016 2016 1000000000 1000

HDOJ 1248 寒冰王座(找规律)

[思路]:找规律,参考的别人的,自己写的挂了.http://blog.csdn.net/appte/article/details/8227632 [AC代码]: #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; int main() { //freopen("in.txt", "r&q