Look-and-say sequence is a sequence of integers as the following:
D, D1, D111, D113, D11231, D112213111, ...
where D
is in [0, 9] except 1. The (n+1)st number is a kind of description of the nth number. For example, the 2nd number means that there is one D
in the 1st number, and hence it is D1
; the 2nd number consists of one D
(corresponding to D1
) and one 1 (corresponding to 11), therefore the 3rd number is D111
; or since the 4th number is D113
, it consists of one D
, two 1's, and one 3, so the next number must be D11231
. This definition works for D
= 1 as well. Now you are supposed to calculate the Nth number in a look-and-say sequence of a given digit D
.
Input Specification:
Each input file contains one test case, which gives D
(in [0, 9]) and a positive integer N (≤ 40), separated by a space.
Output Specification:
Print in a line the Nth number in a look-and-say sequence of D
.
Sample Input:
1 8
Sample Output:
1123123111
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <set>
using namespace std;
const int maxn=;
int n,m,k;
int seq[][maxn];
int cnt;
int main(){
scanf("%d %d",&n,&m);
seq[][]=n;
if(m==)printf("%d",n);
cnt=;
for(int i=;i<m;i++){
k=;
int now=seq[i-][],num=;
for(int j=;j<cnt;j++){
if(seq[i-][j]==now){
num++;
}
else{
seq[i][k]=now;
seq[i][k+]=num;
now=seq[i-][j];
num=;
k+=;
}
}
seq[i][k]=now;
seq[i][k+]=num;
k+=;
cnt=k;
}
for(int j=;j<k;j++){
printf("%d",seq[m-][j]);
}
}
注意点:题目看了半天没懂,后来看懂了点理解的是前一个序列有几个什么然后输出,然后第六个样例怎么看都不对。看了大佬的思路,原来是有几个连续的数字,然后输出来。那既然n最大就40,设个二维数组直接枚举就好了,maxn一开始只设了10010,发现最后一个测试点错了,最后一个测试点应该是n=40,结果很大,maxn为1e5就够了
PAT A1140 Look-and-say Sequence (20 分)——数学题的更多相关文章
-
PAT (Advanced Level) Practice 1035 Password (20 分) 凌宸1642
PAT (Advanced Level) Practice 1035 Password (20 分) 凌宸1642 题目描述: To prepare for PAT, the judge someti ...
-
PAT (Advanced Level) Practice 1008 Elevator (20 分) 凌宸1642
PAT (Advanced Level) Practice 1008 Elevator (20 分) 凌宸1642 题目描述: The highest building in our city has ...
-
PAT甲级:1152 Google Recruitment (20分)
PAT甲级:1152 Google Recruitment (20分) 题干 In July 2004, Google posted on a giant billboard along Highwa ...
-
PAT乙级:1072开学寄语(20分)
PAT乙级:1072开学寄语(20分) 题干 下图是上海某校的新学期开学寄语:天将降大任于斯人也,必先删其微博,卸其 QQ,封其电脑,夺其手机,收其 ipad,断其 wifi,使其百无聊赖,然后,净面 ...
-
PAT乙级:1057 数零壹 (20分)
PAT乙级:1057 数零壹 (20分) 题干 给定一串长度不超过 105 的字符串,本题要求你将其中所有英文字母的序号(字母 a-z 对应序号 1-26,不分大小写)相加,得到整数 N,然后再分析一 ...
-
PAT乙级:1082 射击比赛 (20分)
PAT乙级:1082 射击比赛 (20分) 题干 本题目给出的射击比赛的规则非常简单,谁打的弹洞距离靶心最近,谁就是冠军:谁差得最远,谁就是菜鸟.本题给出一系列弹洞的平面坐标(x,y),请你编写程序找 ...
-
PAT乙级:1084 外观数列 (20分)
PAT乙级:1084 外观数列 (20分) 题干 外观数列是指具有以下特点的整数序列: d, d1, d111, d113, d11231, d112213111, ... 它从不等于 1 的数字 d ...
-
PAT乙级:1063 计算谱半径 (20分)
PAT乙级:1063 计算谱半径 (20分) 题干 在数学中,矩阵的"谱半径"是指其特征值的模集合的上确界.换言之,对于给定的 n 个复数空间的特征值 { a1+b1i,⋯,a** ...
-
PAT 乙级 1044 火星数字 (20 分)
1044 火星数字 (20 分) 火星人是以 13 进制计数的: 地球人的 0 被火星人称为 tret. 地球人数字 1 到 12 的火星文分别为:jan, feb, mar, apr, may, j ...
-
PAT 甲级 1041 Be Unique (20 分)
1041 Be Unique (20 分) Being unique is so important to people on Mars that even their lottery is desi ...
随机推荐
-
tomcat启动后ids页面无法访问
修改servers-->tomcat6.0-->server.xml <Context docBase="/tds7030-web" path="&qu ...
-
编程算法 - 二部图确定 代码(C)
二部图确定 代码(C) 本文地址: http://blog.csdn.net/caroline_wendy 题目: 给定一个具有n个顶点的图. 要给图上每一个顶点染色, 而且要使相邻的顶点颜色不同. ...
-
js-权威指南学习笔记9
第九章 类和模块 1.在JS中,类的实现是基于其原型继承机制的,如果两个实例都从同一个原型对象上继承了属性,我们说它们是同一个实例. 2.常见的编程约定:定义构造函数既是定义类,并且类名首字母要大写. ...
-
uiautomator +python 实现安卓自动化
很多人看到这个题目我相信他们可能会说,uiautomator不是java开发的吗?python怎么用呢,其实呢 ,一开始我也是这么想的,看了金阳光老师的视频,也是用java写的,我表示不服,我要科学上 ...
-
分析业务模型-类图(Class Diagram)
分析业务模型-类图(Class Diagram) 分析业务模型-类图(Class Diagram)(上) 摘要:类图(Class Diagram)可能是用得最多的一种UML图.类图的基本语法并 ...
-
golang 通过exec Command启动的进程如何关闭的解决办法 以及隐藏黑色窗口
golang 通过exec Command启动的进程如何关闭的解决办法 在用exec包调用的其他进程后如何关闭结束,可以使用context包的机制进行管理,context包的使用详见:https:// ...
-
Python3正则表示式(3)
正则表示式对象 对象1: 案例1: import re example = 'ShanDong Institute of Business and Technology' pattern = re.c ...
-
【转】通过js获取系统版本以及浏览器版本
function getOsInfo() { var userAgent = navigator.userAgent.toLowerCase(); var name = 'Unknown'; var ...
-
Delphi编程实现是否开启“平滑屏幕字体边缘“
在Windows高级设置中的视觉效果中可以设置是否开启“平滑屏幕字休边缘”,可以通过编程的方式来实现: if SystemParametersInfo(SPI_SETFONTSMOOTHING, 1, ...
-
算法之杨辉三角形(Java语言)
杨辉三角形, 又称贾宪三角形.帕斯卡三角形. 前9层写出来如下: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 ...