河南省第二届ACM程序设计大赛解题报告(置换群)

1.

/*
前两道题一直在纠结提议，特别是第二题，看了别人的代码才明白过来题意，由测试用例都没明白 
*/
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int maxn = 55;
int ins[maxn];
bool vis[maxn] = {false};
int N,A,B;

//假设边界在ＡＢ之间 
int solve()
{
    /*
    刚开始忘记了开标记数组，要保证每个节点只访问一次，否则会死循环 
    */
    int a = max(A,B);
    int b = min(A,B);
    queue <int > q;
    int cnt = 0;
    while(!q.empty())
        q.pop();
    q.push(A);
    vis[A] = true;
    bool flag = false;
    while(!q.empty())
    {
        cnt++;
        int head = q.front();
        q.pop();
        int left = head - ins[head];
        int right = head + ins[head];
        if(left>=b&&!vis[left])
        {
            if(left==B)
            {
                flag = true;
                break; 
            }
            vis[left] = true;
            q.push(left);
        }
        if(right<=a&&!vis[right])
        {
            if(right==B)
            {
                flag = true;
                break; 
            }
            vis[right] = true;
            q.push(right);
        }
    }
    if(flag)
        return cnt; 
    else
        return -1;     
}

int main()
{
    int i,j,k;
    int M;
    
    cin>>M;
    while(M--)
    {
        memset(vis,false,sizeof(vis));
        memset(ins,0,sizeof(ins));
        
        cin>>N>>A>>B;
        for(i=1; i<=N; i++)
        {
            cin>>ins[i];
        }
        int ans = solve();
        cout<<ans<<endl;
    }
    return 0;
    
}

2.刚开始用list写的，太恶心了，写不成，就换成直接的链表了

#include <iostream>
#include <cstring>
using namespace std;

int N,K;
typedef struct Node 
{
    int data;
    Node * next;
}Node;

Node *head;
void init()
{
    //头结点也要申请空间 
    head = new Node;
    head->data = 0;
    head->next = NULL;
    //头插法 
    for(int i=1; i<=N; i++)
    {
        Node *p = new Node;
        p->next = head->next;
        head->next = p;
        p->data = N-i+1;
    }   
}

int main()
{
    int i,j,k;
    cin>>N>>K;
    int a,b,c;
    init();
    for(i=1; i<=K; i++)
    {
        cin>>a>>b>>c;
        Node *p,*q,*r;
        Node *temp1, *temp2, *temp3;
        
        int cnt = 0;
        for(p=head; cnt<a-1; cnt++,p=p->next);
        temp1 = p;
        
        cnt = 0;
        for(p=head; cnt<b; cnt++,p=p->next);
        temp2 = p;
        
        cnt = 0;
        for(p=head; cnt<c; cnt++,p=p->next);
        temp3 = p;
        
        Node *temp4 = temp2->next;
        temp2->next = temp3->next;
        temp3->next = temp1->next;
        temp1->next = temp4;
    }
    Node *p;
    int cnt = 0;
    for(p=head->next,cnt=0; cnt<10; cnt++,p=p->next)
    {
        cout<<p->data<<endl;
        
    }
    while(1);
    return 0;
}

3.

4.参考华杰做出来的

//置换群问题 
/*
求最小费用时求较小着：用分解后的每个循环里的最小值，或者全局最小值 
*/
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int maxn = 1010;
int N;
int g_min = 1010;//全局置换群最小值，题目上说最大高度是1000 ,每次的全局最小会改变，不能是const 

int hash[maxn],a[maxn],b[maxn];
bool vis[maxn];

int solve()
{
    memset(vis,false,sizeof(vis)); 
    int i,j,k;
    //若分解后的循环里面只有一个元素，则该元素在原来的群里面必定是排好序的
    int len = N;
    int l_min = 1010;//局部最小值 
    int ans = 0;
    while(len>0)
    {
        int i = 0;
        int length = 0;//循环的长度 
        //vis数组标记的是输入的顺序，先找到第一个后,那么经过下面的操作后第一个循环就被全部标记过了 
        while(vis[i])
        {
            i++;
        }
        int begin = i;
        int sum = 0;//每次循环的所有元素和 
        //找循环
        /*
        必须用 do while(至少执行一次)，或者死循环里用break；不可while(i!=begin)这样的话 因为int begin = i则大循环一直执行 
        */
        do
        {
            length++;
            vis[i] = true;//i是个下标值 ,放在i改变之前                
            if(l_min>a[i])
                l_min = a[i]; 
            sum += a[i];
            //hash数组返回的只是一个下标值 
            i = hash[b[i]];//返回的是起点对应的下标所对应元素的下标 ，必须放在sum之后 
        }while(begin!=i);
        
        len -= length;//必须在continue之前 
        if(length==1)//必须有 ,表示循环里只有一个元素，则不花费代价 
            continue;
                  
        //ans1用的是循环内最小值，sum存的是循环内所有的元素和 ，局部最小元素用了 (length-1)次，其他的用了一次，因为在sum
        //里已经加了一次局部最小，所以 length-2)*l_min;
        int ans1 = sum + (length-2)*l_min;
        //全局的先把局部的换出来最后还要在换回来 ,所以答案是两次全局 + 两次局部 + sum里除了局部之外的其他元素和 
        int ans2 = sum + l_min + (length+1)*g_min;
        
        ans += ans1>ans2?ans2:ans1;//是累计,不是直接赋值 
    }
    return ans;    
}

int main()
{
    int i,j,k;
    int T;
    cin>>T;
    while(T--)
    {
        cin>>N;
        memset(hash,0,sizeof(hash));
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
      
        
        for(i=0; i<N; i++)
        {
            cin>>a[i];
            b[i] = a[i];//排好序的数组 
            if(g_min>a[i])
            {
                g_min = a[i];
            }
            hash[a[i]] = i;
        }
        sort(b,b+N);
        int ans = solve();
        cout<<ans<<endl; 
    }
    system("pause");
    return 0;
}