HDU 3130 17多校7 Kolakoski(思维简单)

时间:2022-03-08 10:08:31
Problem Description
This is Kolakosiki sequence: 1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1……. This sequence consists of 1 and 2, and its first term equals 1. Besides, if you see adjacent and equal terms as one group, you will get 1,22,11,2,1,22,1,22,11,2,11,22,1……. Count number of terms in every group, you will get the sequence itself. Now, the sequence can be uniquely determined. Please tell HazelFan its nth element.
 
Input
The first line contains a positive integer T(1≤T≤5), denoting the number of test cases.
For each test case:
A single line contains a positive integer n(1≤n≤107).
 
Output
For each test case:
A single line contains a nonnegative integer, denoting the answer.
 
Sample Input
2
1
2
 
Sample Output
1
2
 
题意:
Kolakoski序列是一个仅由1和2组成的无限数列,是一种通过“自描述”来定义的数列[1]  。他的前几项为
1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,…
它的定义很简单,若把数列中相同的数定为一组,令a(1)=1,a(2)=2,则a(n)等于第n组数的长度。
可以根据这个定义来推算第三项以后的数:例如由于a(2)=2,因此第2组数的长度是2,因此a(3)=2,;
由于a(3)=2,所以第三组数的长度是2,因此a(4)=a(5)=1;由于a(4)=1,a(5)=1,所以第四组数和第五组数的长度都为1,因此a(6)=2,a(7)=1,以此类推。
给出n求第n项的数字是多少
题解:
直接预处理根据性质算出序列
 #include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1e7+;
int a[maxn];
int b[maxn]; void pre()
{
int cnta=,cntb=;
a[]=;b[]=;b[]=;
for(cnta=,cntb=;cnta<maxn&&cntb<maxn;cnta++)
{
a[cnta]=b[cnta];
if(a[cnta]==)
{
if(b[cntb]==)
{
b[cntb+]=;
}
else
{
b[cntb+]=;
}
cntb++;
}
else
{
if(b[cntb]==)
{
b[cntb+]=;
b[cntb+]=;
}
else
{
b[cntb+]=;
b[cntb+]=;
}
cntb+=;
}
}
} int main()
{
pre();
int T,n;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
printf("%d\n",b[n]);
}
return ;
}
 

HDU 3130 17多校7 Kolakoski(思维简单)的更多相关文章

  1. HDU 6140 17多校8 Hybrid Crystals(思维题)

    题目传送: Hybrid Crystals Problem Description > Kyber crystals, also called the living crystal or sim ...

  2. HDU 6124 17多校7 Euler theorem(简单思维题)

    Problem Description HazelFan is given two positive integers a,b, and he wants to calculate amodb. Bu ...

  3. HDU 6034 17多校1 Balala Power&excl;(思维 排序)

    Problem Description Talented Mr.Tang has n strings consisting of only lower case characters. He want ...

  4. HDU 6098 17多校6 Inversion(思维&plus;优化)

    Problem Description Give an array A, the index starts from 1.Now we want to know Bi=maxi∤jAj , i≥2. ...

  5. HDU 6092 17多校5 Rikka with Subset(dp&plus;思维)

    Problem Description As we know, Rikka is poor at math. Yuta is worrying about this situation, so he ...

  6. HDU 6090 17多校5 Rikka with Graph(思维简单题)

    Problem Description As we know, Rikka is poor at math. Yuta is worrying about this situation, so he ...

  7. HDU 6095 17多校5 Rikka with Competition(思维简单题)

    Problem Description As we know, Rikka is poor at math. Yuta is worrying about this situation, so he ...

  8. HDU 6049 17多校2 Sdjpx Is Happy(思维题difficult)

    Problem Description Sdjpx is a powful man,he controls a big country.There are n soldiers numbered 1~ ...

  9. HDU 6143 17多校8 Killer Names(组合数学)

    题目传送:Killer Names Problem Description > Galen Marek, codenamed Starkiller, was a male Human appre ...

随机推荐

  1. BZOJ2883 &colon; gss2加强版

    首先离散化颜色 设pre[x]表示与x颜色相同的点上一次出现的位置,对于每种颜色开一个set维护 修改时需要修改x.x修改前的后继.x修改后的后继 询问[l,r]等价于询问[l,r]内pre[x]&l ...

  2. &lbrack;转&rsqb; 强大的python字符串解析

    1.python字符串通常有单引号('...').双引号("...").三引号("""...""")或('''...'' ...

  3. EJB系列 - EJB高级概念

    本人博客文章网址:https://www.peretang.com/ejb-advanced-concepts/ EJB内幕 幕后的EJB:容器会为每一个bean实例自动生成称为EJB对象的代理, 由 ...

  4. AutoCAD&period;net支持后台线程-Socket服务端

    最近因为公司项目的需求,CAD作为服务端在服务器中常驻运行,等待客户端远程发送执行任务的指令,最终确认用Socket-tcp通讯,CAD需要实时监听客户端发送的消息,这时就需要开启线程执行Socket ...

  5. PHP-CGI进程占用过多CPU

    一般情况下,PHP-CGI只在用户访问的时候会占用CPU资源,但是最近有同事反映,服务器上的的PHP-CGI进程占用了非常多的CPU,但是访问流量却非常少.这显然是一个不正常的现象,说有些地方存在故障 ...

  6. redmine 安装(Centos 6&period;5 x64)

    参考:http://www.linuxidc.com/Linux/2015-03/115545.htm 平台搭建 1)基础环境 yum -y install libyaml-devel zlib-de ...

  7. 03 整合IDEA&plus;Maven&plus;SSM框架的高并发的商品秒杀项目之web层

    Github:https://github.com/nnngu 项目源代码:https://github.com/nnngu/nguSeckill 前端交互流程设计 对于一个系统,需要产品经理.前端工 ...

  8. 洛谷 P1088 火星人

    https://www.luogu.org/problemnew/show/P1088 这个题一开始是很蒙的 感觉很麻烦,每次都要交换balabala..... 后来才知道有这么一个神奇的stl 真是 ...

  9. 使用Future停止超时任务

    今天学了下多线程中超时任务的处理,这里和大家分享下,遇到了点问题没能解决,留下来希望大家帮我解疑啊. 在JAVA中停止线程的方法有多种,有一种是结合ExecutorService和Future的使用, ...

  10. python 路径和文件的遍历

    python发现文件夹下所有的jpg文件,并且安装文件排放的顺序输出 glob模块是最简单的模块之一,内容非常少.用它可以查找符合特定规则的文件路径名.跟使用windows下的文件搜索差不多.查找文件 ...