设为首页 加入收藏

TOP

poj 1721 CARDS(置换)
2015-07-24 05:56:32 【大 中 小】 浏览:7851次
Tags：poj 1721 CARDS 置换

大致题意：原始序列通过洗牌机洗牌s次后变为当前序列，已知当前序列，求原始序列。

在置换群快速幂运算 研究与探讨中最后有详解，有两种解法，一种是求出置换的长度a（即一副牌洗a次后变回原来的位置）,现已知原始序列置换s次变为当前序列，那么当前序列再置换a-s次就是原始序列了。求a就是直接模拟每个置换的过程，直到某序列与当前序列相等。另一种是置换的开方，相当于原始序列的2^s幂是当前序列，将当前序列开2^s次方便是原始序列。

第二种方法暂时还不会，先贴第一种。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include
       #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #define LL long long #define _LL __int64 #define eps 1e-8 #define PI acos(-1.0) using namespace std; const int maxn = 1010; const int INF = 0x3f3f3f3f; int n,s; int a[maxn],b[maxn],c[maxn]; //求置换的长度a int solve() { int cnt = 0,i; while(1) { for(i = 1; i <= n; i++) b[i] = c[c[i]]; cnt++; for(i = 1; i <= n; i++) if(a[i] != b[i]) break; if(i > n) break; for(i = 1; i <= n; i++) c[i] = b[i]; } return cnt; } int main() { while(~scanf(%d %d,&n,&s)) { for(int i = 1; i <= n; i++) { scanf(%d,&a[i]); b[i] = a[i]; c[i] = a[i]; } int cnt = solve(); s %= cnt; s = cnt - s; while(s--) { for(int i = 1; i <= n; i++) b[i] = a[a[i]]; for(int i = 1; i <= n; i++) a[i] = b[i]; } for(int i = 1; i <= n; i++) printf(%d ,b[i]); } return 0; }


【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
上一篇：BZOJ 2878([Noi2012]迷失游乐园-.. 下一篇：HDU 1061 Rightmost Digit题解

最新文章

KMP 字符串匹配 学习笔记
2.10 PE结构：重建重定位表结构
【Qt6】列表模型——抽象基类
2.12 PE结构：实现PE字节注入
学习笔记

热门文章

谈VC++对象模型
effectiveC++(十)
基础动画显示游戏循环的使用
C++ 语言基础(1)
effectiveC++(七)

Hot 文章

谈VC++对象模型
effectiveC++(十)
基础动画显示游戏循环的使用
C++ 语言基础(1)
effectiveC++(七)

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目