原题传送门:http://acm.hdu.edu.cn/showproblem.php?pid=2604
Queuing
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2538 Accepted Submission(s): 1194
Problem Description
Queues and Priority Queues are data structures which are known to most computer scientists. The Queue occurs often in our daily life. There are many people lined up at the lunch time.
Now we define that ‘f’ is short for female and ‘m’ is short for male. If the queue’s length is L, then there are 2L numbers of queues. For example, if L = 2, then they are ff, mm, fm, mf . If there exists a subqueue as fmf or fff, we call it O-queue else it is a E-queue.
Your task is to calculate the number of E-queues mod M with length L by writing a program.
Now we define that ‘f’ is short for female and ‘m’ is short for male. If the queue’s length is L, then there are 2L numbers of queues. For example, if L = 2, then they are ff, mm, fm, mf . If there exists a subqueue as fmf or fff, we call it O-queue else it is a E-queue.
Your task is to calculate the number of E-queues mod M with length L by writing a program.
Input
Input a length L (0 <= L <= 10 6) and M.
Output
Output K mod M(1 <= M <= 30) where K is the number of E-queues with length L.
Sample Input
3 8
4 7
4 8
Sample Output
6
2
1
Author
WhereIsHeroFrom
Source
Recommend
F(n)表示为L=n,时候E序列的数目;
分析:如果长度n的序列中 1)如果最后一个m,那么只要长度为n-1的序列中所有E序列的最后加上m,就可以构成长度为n的E序列(+=F(n-1))。2)如果最后一个是f,那么长度n-1的序列没有能保证如果n-1长度序列为E,再加上f还是E序列的,也不能保证加上f一定是O序列,所以我接着深入!2.1 如果长度n序列中最后两个为mf、ff、貌似都不能保证一定是E或者O序列,我们继续深入!如果长度n序列中最后3个为mmf、fmf、mff、fff,显然fff、fmf一定是O序列!!而mff不能保证一定是E或者O序列,而mmf如果长度n-3的序列是E序列,那么序列后加上mmf也一定是E序列(+=F(n-3)); 对于mff序列,我们继续深入,长度n序列中最后4个为,mmff、fmff 对于fmff一定是O序列,而mmff一定是E序列,那么很显然了(+=F(n-4))
因此可以推出递推公式F(n) = F(n-1) + F(n-3) + F(n-4);
那么很容易想到循环递推;
#include<cstdio> #define MAXN 1000010 int L,M; int F[MAXN]; int main() { F[1] = 2; F[2] = 4; F[3] = 6; F[4] = 9; while(~scanf("%d%d",&L,&M)) { for(int i=5;i<=1000000;i++) F[i] = (F[i-1]+F[i-3]+F[i-4])%M; printf("%d\n",F[L]%M); } }我会告诉你OJ上的结果,
Run ID | Submit Time | Judge Status | Pro.ID | Exe.Time | Exe.Memory | Code Len. | Language |
11164180 | 2014-07-24 10:45:23 | Time Limit Exceeded | 2604 | 5000MS | 4104K | 293 B | G++ |
其实对于这种超时,很容易想到用矩阵快速幂
构造矩阵
/* 1,0,1,1 1,0,0,0 0,1,0,0 0,0,1,0*/ #include<cstdio> #include<cstring> int L,M,ans; int init[4] = {2,4,6,9}; struct Matrix{ int mat[4][4]; Matrix operator * (const Matrix rhs) const{ Matrix temp; for(int i=0;i<4;i++){ for(int j=0;j<4;j++){ temp.mat[i][j] = 0; for(int k=0;k<4;k++) { temp.mat[i][j] += this->mat[i][k]*rhs.mat[k][j]%M; temp.mat[i][j] %= M; } } } return temp; } }; Matrix mt,ret; int main() { while(~scanf("%d%d",&L,&M)) { memset(mt.mat,0,sizeof(mt.mat)); memset(ret.mat,0,sizeof(ret.mat)); for(int i=0;i<4;i++)mt.mat[0][i] = i==1?0:1; for(int i=0;i<3;i++)mt.mat[i+1][i] = 1; for(int i=0;i<4;i++)ret.mat[i][i] = 1; ans = 0; if(L<=4){ printf("%d\n",L==0?0:init[L-1]%M); }else{ L = L-4; for(int i=0;i<4;i++) ret.mat[i][i] = 1; while(L) { if(L&1)ret = ret*mt; mt = mt*mt; L>>=1; } for(int i =0;i<4;i++){ ans = (ans+ret.mat[0][i]*init[3-i]%M)%M; } printf("%d\n",ans); } } return 0; } //超时代码 /* #include<cstdio> #define MAXN 1000010 int L,M; int F[MAXN]; int main() { F[1] = 2; F[2] = 4; F[3] = 6; F[4] = 9; while(~scanf("%d%d",&L,&M)) { for(int i=5;i<=1000000;i++) F[i] = (F[i-1]+F[i-3]+F[i-4])%M; printf("%d\n",F[L]%M); } }*/
相关推荐
HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...
### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...
hdu2101AC代码
【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...
【标题】"HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu." 暗示这是一个与HDU(杭州电子科技大学在线编程平台)相关的压缩包,其中可能包含了该平台上的编程竞赛题目或练习题目的源代码。"hdu07"可能是某个特定题目的...
HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
【ACM入门与提高:HDU ACM竞赛课程详解】 ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC或ACM/ICPC)是一项全球性的竞赛,旨在激发大学生对计算机科学的兴趣,提升他们的...
【标题】"hdu_acm_1084.rar_ACM_HDU10_acm10_hdu_hdu 1084" 提供的是一个关于杭电(HDU)ACM竞赛第1084题的解决方案。该题目可能是在编程竞赛中常见的算法问题,而ACM(国际大学生程序设计竞赛)是全球知名的编程...
HDU(Hangzhou Dianzi University)是国内外知名的在线编程竞赛平台,主要服务于ACM/ICPC(国际大学生程序设计竞赛)以及相关的算法训练。"HDU最全ac代码"这个压缩包很可能是包含了在HDU平台上解题通过的完整源代码...
根据提供的信息,我们可以总结出以下关于“hdu动态规划算法集锦”的知识点: ### 动态规划基础概念 动态规划是一种解决多阶段决策问题的方法,它通过将原问题分解为互相重叠的子问题,利用子问题的解来构建原问题...