即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

Codeforces Round #418 (Div. 2) B. An express train to reveries

编程语言 Rewriter_huanying 8℃ 0评论

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

题意:给出a、b两个数字序列和长度n,求一个序列,要求1到n每个数字都出现一次且与a、b序列分别有且仅有一处数字不同,若有多解,输出任意一个答案。

思路:读题读的我好辛苦Orz。。。


可以看出,a、b两序列相同的部分就是答案序列,不同的部分可能有两种情况:


(1)只有一个位置不同


统计相同的那部分1到n有哪个数字没出现过,直接填上即可。


(2)有两个位置不同


那同时也就有两个数字没用过,反正一共两种情况,放进去看看满不满足条件判断下就好。

代码:c++

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int maxn = 2000;

int a[maxn], b[maxn];
int ans[maxn];
vector<int> pos;

int main()
{
    int n;
    cin >> n;
    for(int i=0; iscanf("%d", &a[i]);
    }
    for(int i=0; iscanf("%d", &b[i]);
    }
    set<int> all;
    for(int i=1; i<=n; i++)
    {
        all.insert(i);
    }
    for(int i=0; iif(a[i]==b[i])
        {
            ans[i] = a[i];
            all.erase(a[i]);
        }
        else
        {
            pos.push_back(i);
        }
    }
    set<int>::iterator iter = all.begin();
    if(pos.size()==1)
    {
        ans[pos[0]] = *iter;
    }
    else
    {
        int t1 = *iter;
        iter++;
        int t2 = *iter;
        int p1 = pos[0];
        int p2 = pos[1];
        int differa = 0, differb = 0;
        if(t1!=a[p1])
        {
            differa++;
        }
        if(t2!=a[p2])
        {
            differa++;
        }
        if(t1!=b[p1])
        {
            differb++;
        }
        if(t2!=b[p2])
        {
            differb++;
        }
        if(differa==1&&differb==1)
        {
            ans[p1] = t1;
            ans[p2] = t2;
        }
        else
        {
            ans[p1] = t2;
            ans[p2] = t1;
        }
    }
    for(int i=0; iif(i!=0)
        {
            putchar(' ');
        }
        printf("%d", ans[i]);
    }
    return 0;
}

转载请注明:CodingBlog » Codeforces Round #418 (Div. 2) B. An express train to reveries

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情