题目链接:http://codeforces.com/problemset/problem/814/B
题目意思:分别给定一个长度为 n 的不相同序列 a 和 b。这两个序列至少有 i 个位置(1 ≤ i ≤ n ), a[i] != b[i] 。现在需要构造一个长度为 n,每个数只能取值1~n 且只能取值一次的序列 p, 使得恰好存在有一个位置 i(1 ≤ i ≤ n ), ai ≠ pi 。和恰好存在一个位置 j (1 ≤ j ≤ n) , bj ≠ pj ,保证这个序列 p 有n-1个位置是跟序列a和b的数是相同的。如果有多个符合的序列,输出任意一个即可。
【 中文解说起来怎么感觉有点啰哩吧嗦的 = = (大家还是看不明白意思且自问英文还过得去的,建议直接看英文意思)】
题目解析:首先,p序列取值范围1~n(这个我有看到),但只能取值一次,这个貌似真的没有说,看到后台测试样例才发现。这个有点坑。
然后我们不难想到先构造一条保存 a[i] = b[i](p[i]=a[i]), a[j] != b[j] (p[j] = 0,代表未知) 的 p 序列。
接着可以发现题目说, a 和 b 有 i 个位置的数是不相同的。其实,这个 i 只能为 1 (test3)或者 2(这个情况比较多)。
分析 i = 1 这种情况,只可能 a != b, 所以填入一个不等于 a 和 b 的数就可以了(前提要有一个 vis 数组标记,所以没有 vis 过的就是该填的数了)
分析 i = 2 这种情况,假设 a 序列对应 a1、a2, b 序列对应b1、b2, p在这两个位置分别取值p1、p2
(1)a1=a2,b1=b2, a1!=b1 ——》 p1=a1, p2=b1 或者 p1=b1,p2=a2
(2)a1=a2!=b1,b1!=b2 或者 a1!= a2 , b1=b2!=a1
(3)a1 != a2 != b1 != b2
情况(2)、(3),p的取值需要根据当前a1、a2,b1、b2,是否vis过来取。当序列a和b相同位置且值相同,就标记访问过。这样当遇到 (2)(3)情况,取值就取没有 vis 过的。
当然我们还需要进行一次预处理。为啥?
先看 test37这个例子。因为是先处理第三个位置的,但是a[3] 和 b[3] 都都没有vis过, 如果很不幸的取了b[3]=1,而不是 a[3]=3, 之后第四个位置就无值可取了(都vis过)。然后这种思路解题就不适合了。
5
5 4 3 5 2
5 4 1 1 2
所以这个预处理就是保存a[i] = b[i] (1 ≤ i ≤ n )时,vis[a[i]] =1之后,当遇到 a[j] != b[j] 时(1 ≤ j ≤ n),但有可能 a[j] 或者 b[j] 是 vis 过的,此时也要打标记。这个先后出现顺序是没所谓的,大家想想就明白了。
构造题还是挺考思维的,而且想问题得全面点呢~~~
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <algorithm>
6 using namespace std;
7
8 const int maxn = 1000 + 5;
9 int a[maxn], b[maxn];
10 int p[maxn];
11 int vis[maxn];
12 int n;
13
14 void Output()
15 {
16 for (int i = 1; i <= n; i++) {
17 printf("%d%c", p[i], i != n ? ' ': '\n');
18 }
19 }
20
21
22 int main()
23 {
24 #ifndef ONLINE_JUDGE
25 freopen("in1.txt", "r", stdin);
26 #endif // ONLINE_JUDGE
27
28 while (scanf("%d", &n) !=EOF) {
29 for (int i = 1; i <= n; i++) {
30 scanf("%d", &a[i]);
31 p[i] = vis[i] = 0;
32 }
33
34 int cntzero = 0, pos = 0;
35 for (int i = 1; i <= n; i++) {
36 scanf("%d", &b[i]);
37 if (b[i] == a[i]) {
38 p[i] = b[i];
39 vis[b[i]] = 1;
40 }
41 else { //b[i] != a[i]
42 if (vis[b[i]] && !vis[a[i]]) {
43 p[i] = a[i];
44 vis[a[i]] = 1;
45 }
46 else if (!vis[b[i]] && vis[a[i]]) {
47 p[i] = b[i];
48 vis[b[i]] = 1;
49 }
50 cntzero++;
51 pos = i;
52 }
53 }
54
55 if (cntzero == 1 && b[pos] != a[pos]) {
56 for (int j = 1; j <= n; j++) {
57 if (!vis[j]) {
58 p[pos] = j;
59 break;
60 }
61 }
62 }
63 // cntzero = 2
64 else {
65 for (int i = 1; i <= n; i++) {
66 if (p[i] == 0) {
67 if (!vis[a[i]] && vis[b[i]]) {
68 p[i] = a[i];
69 vis[p[i]] = 1;
70 }
71 // vis[a[i]] && !vis[b[i]] 或者 !vis[a[i]] && !vis[b[i]]
72 else {
73 p[i] = b[i];
74 vis[p[i]] = 1;
75 }
76 }
77 }
78 }
79 Output();
80 }
81 return 0;
82 }
转载于:https://www.cnblogs.com/windysai/p/6970660.html