PAT A1140 Look-and-say Sequence (20 分)——数学题

时间:2021-10-11 20:05:23

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 分)——数学题的更多相关文章

  1. PAT &lpar;Advanced Level&rpar; Practice 1035 Password &lpar;20 分&rpar; 凌宸1642

    PAT (Advanced Level) Practice 1035 Password (20 分) 凌宸1642 题目描述: To prepare for PAT, the judge someti ...

  2. PAT &lpar;Advanced Level&rpar; Practice 1008 Elevator &lpar;20 分&rpar; 凌宸1642

    PAT (Advanced Level) Practice 1008 Elevator (20 分) 凌宸1642 题目描述: The highest building in our city has ...

  3. PAT甲级:1152 Google Recruitment &lpar;20分&rpar;

    PAT甲级:1152 Google Recruitment (20分) 题干 In July 2004, Google posted on a giant billboard along Highwa ...

  4. PAT乙级:1072开学寄语&lpar;20分&rpar;

    PAT乙级:1072开学寄语(20分) 题干 下图是上海某校的新学期开学寄语:天将降大任于斯人也,必先删其微博,卸其 QQ,封其电脑,夺其手机,收其 ipad,断其 wifi,使其百无聊赖,然后,净面 ...

  5. PAT乙级:1057 数零壹 &lpar;20分&rpar;

    PAT乙级:1057 数零壹 (20分) 题干 给定一串长度不超过 105 的字符串,本题要求你将其中所有英文字母的序号(字母 a-z 对应序号 1-26,不分大小写)相加,得到整数 N,然后再分析一 ...

  6. PAT乙级:1082 射击比赛 &lpar;20分&rpar;

    PAT乙级:1082 射击比赛 (20分) 题干 本题目给出的射击比赛的规则非常简单,谁打的弹洞距离靶心最近,谁就是冠军:谁差得最远,谁就是菜鸟.本题给出一系列弹洞的平面坐标(x,y),请你编写程序找 ...

  7. PAT乙级:1084 外观数列 &lpar;20分&rpar;

    PAT乙级:1084 外观数列 (20分) 题干 外观数列是指具有以下特点的整数序列: d, d1, d111, d113, d11231, d112213111, ... 它从不等于 1 的数字 d ...

  8. PAT乙级:1063 计算谱半径 &lpar;20分&rpar;

    PAT乙级:1063 计算谱半径 (20分) 题干 在数学中,矩阵的"谱半径"是指其特征值的模集合的上确界.换言之,对于给定的 n 个复数空间的特征值 { a1+b1i,⋯,a** ...

  9. PAT 乙级 1044 火星数字 (20 分)

    1044 火星数字 (20 分) 火星人是以 13 进制计数的: 地球人的 0 被火星人称为 tret. 地球人数字 1 到 12 的火星文分别为:jan, feb, mar, apr, may, j ...

  10. PAT 甲级 1041 Be Unique (20 分)

    1041 Be Unique (20 分) Being unique is so important to people on Mars that even their lottery is desi ...

随机推荐

  1. tomcat启动后ids页面无法访问

    修改servers-->tomcat6.0-->server.xml <Context docBase="/tds7030-web" path="&qu ...

  2. 编程算法 - 二部图确定 代码&lpar;C&rpar;

    二部图确定 代码(C) 本文地址: http://blog.csdn.net/caroline_wendy 题目: 给定一个具有n个顶点的图. 要给图上每一个顶点染色, 而且要使相邻的顶点颜色不同.  ...

  3. js-权威指南学习笔记9

    第九章 类和模块 1.在JS中,类的实现是基于其原型继承机制的,如果两个实例都从同一个原型对象上继承了属性,我们说它们是同一个实例. 2.常见的编程约定:定义构造函数既是定义类,并且类名首字母要大写. ...

  4. uiautomator &plus;python 实现安卓自动化

    很多人看到这个题目我相信他们可能会说,uiautomator不是java开发的吗?python怎么用呢,其实呢 ,一开始我也是这么想的,看了金阳光老师的视频,也是用java写的,我表示不服,我要科学上 ...

  5. 分析业务模型-类图(Class Diagram)

    分析业务模型-类图(Class Diagram)     分析业务模型-类图(Class Diagram)(上) 摘要:类图(Class Diagram)可能是用得最多的一种UML图.类图的基本语法并 ...

  6. golang 通过exec Command启动的进程如何关闭的解决办法 以及隐藏黑色窗口

    golang 通过exec Command启动的进程如何关闭的解决办法 在用exec包调用的其他进程后如何关闭结束,可以使用context包的机制进行管理,context包的使用详见:https:// ...

  7. Python3正则表示式(3)

    正则表示式对象 对象1: 案例1: import re example = 'ShanDong Institute of Business and Technology' pattern = re.c ...

  8. 【转】通过js获取系统版本以及浏览器版本

    function getOsInfo() { var userAgent = navigator.userAgent.toLowerCase(); var name = 'Unknown'; var ...

  9. Delphi编程实现是否开启&OpenCurlyDoubleQuote;平滑屏幕字体边缘&OpenCurlyDoubleQuote;

    在Windows高级设置中的视觉效果中可以设置是否开启“平滑屏幕字休边缘”,可以通过编程的方式来实现: if SystemParametersInfo(SPI_SETFONTSMOOTHING, 1, ...

  10. 算法之杨辉三角形&lpar;Java语言&rpar;

    杨辉三角形, 又称贾宪三角形.帕斯卡三角形. 前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 ...