【HDOJ】2065 “红色病毒”问题

【HDOJ】2065 “红色病毒”问题

刚开始看这道题目的时候,完全没看出来是递推。看了网上大牛的分析。立刻就明白了。
其实无论字符串长度为多少,都可以将该长度下的组合分成四种情况S1(A偶数C偶数)、S2(A偶数C奇数)、S3(A奇数C偶数)、S4(A奇数C奇数)。因此,可以由n-1长度情况下的各种情况数目推导出n长度下的数目。
fn(S1) = 2*fn-1(S1) + fn-1(S2) + fn-1(S3),同理可推导其它状态的数目
fn(S2) = 2*fn-1(S2) + fn-1(S1) + fn-1(S4)
fn(S3) = 2*fn-1(S3) + fn-1(S1) + fn-1(S4)
fn(S4) = 2*fn-1(S4) + fn-1(S2) + fn-1(S3)
由以上公式可以推导出 fn(S1) + fn(S4) = fn(S2) + fn(S3) = 4^n / 2 = 2*4^(n-1)
又因为f0(S1) = 2, f0(S2) = 1, f0(S3) = 1, f0(S4) = 0
f0(S2) = f0(S3),并且两式的推导公式相同,因此有fn(S2) = fn(S3) = 4^(n-1) = 2^(2n-2)
将其代入S1的推导式,并且递推可得fn(S1) = 2^(n-1) + 2^(2n-2)
下面就是推导规律,发现2的幂%100的周期为1,2,4,8,16,32,64,28,56,12,24,48,96,92,84,68,36,72,44,88,76,52,
然后注意讨论长度为1、2的情况,可求解。

 1 #include <stdio.h>  2  3 #define PAT2NUM 20  4 #define PAT4NUM 10  5  6 int pattern[] = { 1,2,4,8,16,32,64,28,56,12,24,48,96,92,84,68,36,72,44,88,76,52};  7  8 void find(int base) {  9 int i, j, flg, n; 10 11 pattern[0] = 1; 12 printf("1 "); 13 n = 1; 14 for (i=1; i<50; ++i) { 15 pattern[i] = pattern[i-1]*base%100; 16 flg = 0; 17 for (j=0; j<i; ++j) 18 if (pattern[i] == pattern[j]) { 19 flg = 1; 20 break; 21  } 22 if (flg) 23 break; 24 ++n; 25 printf("%d ", pattern[i]); 26  } 27 } 28 29 int main() { 30 int case_n; 31  __int64 n; 32 int i, a, b; 33 34 while (scanf("%d", &case_n)!=EOF && case_n) { 35 for (i=1; i<=case_n; ++i) { 36 scanf("%I64d", &n); 37 printf("Case %d: ", i); 38 if (n == 1) { 39 printf("2\n"); 40 continue; 41  } 42 if (n == 2) { 43 printf("6\n"); 44 continue; 45  } 46 a = pattern[(n-1-2)%PAT2NUM+2]; 47 b = pattern[(2*n-2-2)%PAT2NUM+2]; 48 printf("%d\n", (a+b)%100); 49  } 50 printf("\n"); 51  } 52 53 return 0; 54 }

 

转载于:https://www.cnblogs.com/bombe1013/p/3651062.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/109857.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 静态测试和动态测试的区别在哪里?_软件测试中的静态测试

    静态测试和动态测试的区别在哪里?_软件测试中的静态测试1.静态测试静态测试(statictesting)就是不实际运行被测软件,而只是静态地检查程序代码、界面或文档中可能存在的错误的过程。包括对代码测试、界面测试和文档测试三个方面:    对于代码测试,主要测试代码是否符合相应的标准和规范。    对于界面测试,主要测试软件的实际界面与需求中的说明是否相符。    对于文档测试,主要测试用户手册和需求说明是否符合用户的实际需求。…

    2022年10月25日
  • 查看端口占用的进程_cmd查看端口占用

    查看端口占用的进程_cmd查看端口占用在开发中经常会遇到端口占用问题,例如下面,npmstart报的错误:1.查看端口占用情况命令lsof-itcp:8080输出结果:字段说明:字段名说明COMMAND进程名称PID进程标识符USER进程所有者FD文件描述符,应用程序通过文件描述符识别该文件TYPE文件类型,文件REG、目录DIR、字符CHR、块设备…

  • 基于PS2手柄的Arduino遥控小车

    基于PS2手柄的Arduino遥控小车前言本文利用PS2手柄和Arduino开发板制作了一个简易的遥控小车,利用蓝牙进行通信,可以实现前后左右的移动。(原理掌握之后可以自己拓展相关功能)一、零件1.ArduinoUNO开发板:ArduinoUNO是ArduinoUSB接口系列的最新版本,作为Arduino平台的参考标准模板。UNO的处理器核心是ATmega328,同时具有14路数字输入/输出口(其中6路可作为PWM输出),6路模拟输入,一个16MHz晶体振荡器,一个USB口,一个电源插座,一个ICSPheader和一个复位按钮。2

  • OSG与CEGUI集成过程

    OSG与CEGUI集成过程最近做了一段时间的CEGUI和OSG之间的结合,有一点小小的收获。写一篇文章来记录所做的一点点事情。下面写一点CEGUI和OSG之间结合的东西。一.整体过程概述:CEGUI作为OSG的Drawable集成到OSG中。CEGUI继承osg::Drawable类,作为一个Drawable完成初始化,加入到一个节点中(osg::Geode)。然后将该节点在Viewerd执行realize()

  • 页面跳转的两种方式(转发和重定向)区别及应用场景分析「建议收藏」

    页面跳转的两种方式(转发和重定向)区别及应用场景分析「建议收藏」转发和重定向区别详解作为一名程序员,特别是javaweb开发的程序员,在使用servlet/jsp的时候,我们必须要知道实现页面跳转的两种方式的区别和联系:即转发和重定向的区别。1、RequestDispatcher.forward方法只能将请求转发给同一个WEB应用中的组件;而HttpServletResponse.sendRedirect方法不仅可以重定…

  • vue.js 三种方式安装(vue-cli)

    vue.js 三种方式安装(vue-cli)Vue.js(读音/vjuː/,类似于view)是一个构建数据驱动的web界面的渐进式框架。Vue.js的目标是通过尽可能简单的API实现响应的数据绑定和组合的视图组件。它不仅易于上手,还便于与第三方库或既有项目整合。下面介绍三种Vue.js的安装方法:1.独立版本我们可以在Vue.js的官网上直接下载vue…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号