题目链接：http://codeforces.com/contest/814/problem/B

题意 : 有一个给出两个含有 n 个数的序列 a 和 b, 这两个序列和(1~n)的其中一个全排列序列 p 只有一个元素不同, 要求你找出任意满足这个条件的序列 p

 

分析 : 全排列有个特点, 就是各个元素各不相同, 只要改变了其中的一个元素(当然改变后还是在1~n内), 那序列当中必有重复的元素, 而且在1~n中必定有一个数不会出现在这个序列中。很显然的一个特点, 如果没有想到的话, 这题可能就比较难看出解法了。实际上a 和 b就是这样改变了一个元素后的序列, 所以只要找出 a 中的两个相同元素所在的位置, 分别轮流替换成未出现的元素和原来的元素, 然后去和b匹配一下是否满足题意, 如果满足则就是第一种组合, 否则就是第二种了。例如 1 2 2 3 , 那就可以变化成 1 2 4 3 和 1 4 2 3去匹配b。

 

瞎搞 : 想来想去想了挺久, 往错的方向想了很久, 最后情况分类实在太多, 自己也晕了, 打出来也就只通过了21个点, 还是弱啊........

 

#include
      
       using namespace std;map
       
         m;int n;int a[1001], b[1001], vis[1001], c[1001];bool Check(){    int diffb = 0;    for(int i=1; i<=n; i++){        if(c[i]!=b[i]) diffb++;    }    if(diffb==1) return true;    return false;}int main(void){    scanf("%d", &n);    int fir, sec;    memset(vis, false, sizeof(vis));    int index1, index2;    for(int i=1; i<=n; i++){        scanf("%d", &a[i]);        vis[a[i]] = true;        if(m.count(a[i])){            index1 = m[a[i]];            index2 = i;            fir = a[i];        }        m[a[i]] = i;    }    for(int i=1; i<=n; i++){        scanf("%d", &b[i]);        if(i!=index1 || i!=index2) c[i] = a[i];    }    for(int i=1; i<=n; i++){        if(!vis[i] && i!=fir){            sec = i;            break;        }    }    c[index1] = fir, c[index2] = sec;    if(Check()){        for(int i=1; i<=n; i++){            printf("%d ", c[i]);        }        puts("");        return 0;    }    c[index1] = sec, c[index2] = fir;    for(int i=1; i<=n; i++){        printf("%d ", c[i]);    }    puts("");    return 0;}