Codeforces Round #252 D 置换群的简单应用 - c++编程基础

TOP

Codeforces Round #252 D 置换群的简单应用

2015-07-24 05:29:15 【大中小】浏览:8870次

题目：http://codeforces.com/contest/441/problem/D 对于这道题目，也只能用长知识来安慰自己了，数学知识面有点狭窄，一开始在往逆序数方面想，发现不行，后来又强行模拟去搞，发现有漏的情况，后来看了巨巨博客发现了新知识

会记住：

一个轮换内交换成正常顺序需要k-1次，k为轮换内元素的个数

两个轮换之间进行交换元素，可以把两个轮换合并成1个，总交换次数+1

一个轮换内部进行交换，可以把一个轮换拆分成两个，总交换次数-1

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #define ll long long #define eps 1e-8 const int inf = 0xfffffff; const ll INF = 1ll<<61; using namespace std; //vector
                
                  > G; //typedef pair
                 
                   P; //vector
                  
                    > ::iterator iter; // //map
                   
                    mp; //map
                    
                     ::iterator p; vector 
                     
                       > G; int n; int m; int nnum[3000 + 55]; int vis[3000 + 55]; int detal() { memset(vis,0,sizeof(vis)); int cnt = 1; int ans = 0; for(int i=1;i<=n;i++) { if(!vis[i]) { vis[i] = cnt++; int now = 0; for(int j=nnum[i];!vis[j];j = nnum[j]) { vis[j] = vis[i]; now++; } ans += now; } } return ans; } void init() { memset(nnum,0,sizeof(nnum)); G.clear(); } bool input() { while(scanf(%d,&n) == 1) { for(int i=1;i<=n;i++) scanf(%d,&nnum[i]); scanf(%d,&m); return false; } return true; } void cal() { while(true) { int now = detal();//原序列按照字典序排好 需要的交换步数 if(now == m)break; if(now < m) { for(int i=2;i<=n;i++) { if(vis[i] != vis[1]) { swap(nnum[1],nnum[i]); G.push_back(make_pair(1,i));break; } } }//两个轮换之间进行，可以把两个轮换给合并，按照定理+1，为了字典序跟1交换 else { int mark; for(int i=1;i<=n;i++) if(nnum[i] != i){mark = i;break;} for(int j = mark + 1;j<=n;j++) { if(vis[j] == vis[mark]) { swap(nnum[mark],nnum[j]); G.push_back(make_pair(mark,j));break; } } }//一个轮换内进行，可以把一个轮换拆成两个，按照定理要-1 } } void output() { printf(%d ,G.size()); for(int i=0;i


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】

上一篇：SGU 261. Discrete Roots （N次剩..	下一篇：C++设计模式之建造者模式(一)