模拟 nbut1225 NEW RDSP MODE I
2024-08-27 04:15:32
传送门:点击打开链接
题意:输入n。m,x。刚開始有一个1~n的排列。然后定义了一种操作。是将数组中的偶数位数字选出来,依照顺序放到数组最前面,奇数位依照顺序放到偶数位的后面,进行m次这种操作。输出之后前x个数字
思路:找到循环节T,利用T去约m,然后再将非常小的m拿去模拟,输出前x个
一開始就想到找循环节,,刚開始仅仅想到去用找规律的方法去找到通项公式,可是找了好久就是没找到。尽管感觉理论上肯定是有的T^T
可是找规律的时候发现了非常多特点:T一定小于等于n。还有就是最刚開始的时候数字1是在第一个位置。当数字1再次出如今第一个位置的时候,刚好就是一个循环节!
所以。我们仅仅须要模拟1的位置,一直模拟到1出如今第一个位置时,循环节就算出来了。复杂度O(n)。1的位置还是非常好模拟的,由于仅仅研究了一个数字而已,还是非常好找到递推式子的。
找到循环节T之后。我们令m=m%T.这样m就变成<=n的了。然后就能够再次模拟
接下来,我们对前x个数字,分别倒着模拟m次。由于如今的m<=n,所以复杂度O(xn),倒着模拟的公式也是非常好找的
最后看别人的代码才发现,,事实上模拟的时候。就是一个高速幂(fuck)
总之。还是有些感慨。有时候不一定模拟就非要找到通项公式。找到办法能在较短的时间内算出通项公式,这样也并不算差~
#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout) using namespace std;
typedef long long LL;
typedef pair<int, int> PII; const int MX = 1e5 + 5;
const int INF = 0x3f3f3f3f; int find_t(int n) {
int p = 1, ret = 0;
while(true) {
ret++;
if(p % 2) p = n / 2 + (p + 1) / 2;
else p = p / 2; if(p == 1) return ret;
}
}
int solve(int p, int n, int m) {
for(int i = 1; i <= m; i++) {
if(p * 2 <= n) p = p * 2;
else p = (p - n / 2 - 1) * 2 + 1;
}
return p;
} int main() {
int n, m, x;//FIN;
while(~scanf("%d%d%d", &n, &m, &x)) {
int t = find_t(n); for(int i = 1; i <= x; i++) {
printf("%d%c", solve(i, n, m % t), i == x ? '\n' : ' ');
}
}
return 0;
}
最新文章
- window.open
- JavaScript异步编程(1)- ECMAScript 6的Promise对象
- 51Nod-1212 无向图最小生成树
- 深入分析@Transactional的用法
- XML代码生成器——XMLFACTORY 简介(三)
- 如何从eclipse中下载并导入Github上的项目
- Android前端人员与后台开发的撕逼(一)
- WPF,Silverlight与XAML读书笔记第四十五 - 外观效果之模板
- Trie树-可持久化
- C#对 Dictionary进行排序 转
- div 并排
- ASP.NET页面生命周期与控件生命周期
- java基础(七)面向对象(二)
- FreeCodeCamp:Truncate a string
- 长安大学ACM竞赛部
- boolean attribute(布尔值属性) attribute vs property
- 分布式存储 CentOS6.5虚拟机环境搭建FastDFS-5.0.5集群(转载)
- 导航栏项目滑过时子菜单显示/隐藏jquery代码
- hadoop in hue的搭建(基于cdh版本)
- PS 滤镜——运动模糊