【2017 Multi-University Training Contest - Team 7】Kolakoski
2024-08-31 13:20:11
【Link】:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1011&cid=765
【Description】
有一种数列叫Kolakoski:1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1……,如果将这个数组相同的数字合并成一个新数列:1,22,11,2,1,22,1,22,11,2,11,22,1……,第二个数列中第几组数中的个数就是第一个数列中的第几个数。现在要求出第一个数列第n个数。
【Solution】
相邻的相同的数字的个数这个数列f的增长速度是没有原数列a的增长速度快的.
则对于新添加在a末尾的数字,看看它改变的相应的f值的最后一项是不是和a的相应的位置相同即可。
只有1和2两个数字,两个数字都试试就好.
这样就能处理出来整个数列了,O(1)输出就好。
【NumberOf WA】
0
【Reviw】
【Code】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
#define ri(x) scanf("%d",&x)
#define rl(x) scanf("%lld",&x)
#define rs(x) scanf("%s",x+1)
#define oi(x) printf("%d",x)
#define ol(x) printf("%lld",x)
#define oc putchar(' ')
#define os(x) printf(x)
#define all(x) x.begin(),x.end()
#define Open() freopen("F:\\rush.txt","r",stdin)
#define Close() ios::sync_with_stdio(0)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 110;
int n,a[10000000+10];
int main(){
//Open();
//Close();
a[1] = 1;
int j = 1;
int now = 1;
for (int i = 2;i <= 10000000+10;i++){
a[i] = a[i-1];
if (now + 1 != a[j]){
a[i] = 3 - a[i];
now = 1;
j++;
}else{
now++;
}
}
int T;
ri(T);
while (T--){
int n;
ri(n);
oi(a[n]);
puts("");
}
return 0;
}
最新文章
- freeswitch 使用mysql替换默认的sqlite
- 【转】Java面试宝典2015版(绝对值得收藏超长版)(一)
- ecshop二次开发 给商品添加自定义字段【包含我自己进一步的开发实例详解】
- Maven基础配置—上传jar包到私服
- 写Java也得了解CPU--CPU缓存
- Redis学习一 五种基本的数据类型
- JMeter学习-005-JMeter 主要组件概要介绍及执行顺序
- 夺命雷公狗—angularjs—4—继承和修正继承
- 使用kaptcha生成验证码
- socket基础函数(2)
- linux命令行下命令参数前的一横(-)和两横(--)的区别
- 导入NGUI插件
- Toast——提醒方式
- 升级到cocos2d-x 2.0.2代码差异
- Ionic在线打包IOS平台应用
- 跟着刚哥学习Spring框架--创建HelloWorld项目(一)
- 运用GRASP原则来做uml交互类图-------pos机实例
- XAMPP重要文件目录及配置
- 究竟谁在绑架中国的4G政策?
- php 依赖注入的实现
热门文章
- C++中explicit关键字作用
- monyer教你玩电脑——CSS、HTML、JS、XML的关系
- element-ui表格控件前端分页方法
- Supervisor 的安装与配置教程
- iOS 的组件化开发
- 【Codeforces Round #425 (Div. 2) A】Sasha and Sticks
- Spring MVC学习总结(5)——SpringMVC项目关于安全的一些配置与实现方式
- 【分享】School Rumble校园迷糊大王PSP姐姐事件+PS2游戏第一,二学期【带VNR翻译教程】
- U盘版Windows 10已经在亚马逊Amazon開始接受预订啦
- STL heap部分源代码分析