Codeforces Round #704 (Div. 2)-E-暴力，思维_codeforces round #704 (div. 2)e

2023大厂真题提交网址(含题解):

www.CodeFun2000.com（http://101.43.147.120/）

最近我们一直在将收集到的机试真题制作数据并搬运到自己的OJ上，供大家免费练习,体会真题难度。现在OJ已录入50+道2023年最新大厂真题，同时在不断的更新。同时，可以关注"塔子哥学算法"公众号获得每道题的题解。

题目大意:

给你$n$个长度为$m$的序列。问你是否能够构造出一个序列，使得其与这$n$个序列的差别最多两处.

$n\ast m\le 250000$

题目思路:

由于我们要满足对于每个序列的差别都最多两处。所以自然想到就拿第一个序列当作答案序列，在其基础上作修改。

先看其他序列与第一个序列的差别的最大值$d$:

1.$d\ge 5$时，无解。
2.$d\le 2$时，合法。

对于1.因为差别在五个了，那么意味着我们至少得修改第一个序列(答案序列)的三个地方，才能满足它与这个序列的差别缩小到2.但是这个时候答案序列和第一个序列的差别又等于3了。所以这种情况肯定无解了。

对于2.是显然，题目也就是这么要求的。

接下来重点讨论:

3.$d=4$时，假设这个序列是第$i$个(可能不止一个，随便选一个而已),我们知道我们必须得修改 至少且最多 (那就是恰好)第一个序列中的4个不同位置中的两个位置成第$i$个序列的那两个。那么有6种方法。修改完后，我们第二次循环直接$check$ 是不是$d$全部在$2$以内。因为第二层的时候，我们已经用光了两次修改的机会了。所以我们无法再去修改第一个序列了。

4.$d=3$时，假设这个序列是第$i$个，我们可以从3个里面选择任一个位置修改完后，再在第二次check的时候以同样的方式找$d\le 3$的。因为当我们已经修改完一次之后，如果还碰到有$d\ge 4$的。我们已经修改不了了，因为只剩一次可以修改的机会了。然后递归进行。

所以我们可以将$3,4$给统一起来。利用递归来求解这个问题。

bool dfs(step) 代表的是我现在还剩下$step$步修改机会，是否能够找到一种合法的修改方案.答案就是$dfs(2)$

时间复杂度分析:$O(n\ast m)$

为什么不是指数级别？

由于每个序列的差别都最多两处的限制。当我们遍历$[2,n]$内序列时。如果遇到了$d=3||4$的序列时，我们就必须修改第一个序列来满足它，这是无法逃避掉的。然后我们最多又只允许修改两处地方(不能多，可以少。多了就会让答案序列和第一个序列的差值$>2$.而且我们这两次修改不能在同一个地方进行。如果将第一次修改的位置又修改回去了，就又会导致第一次找到的那个序列差值又再次$>$ 2)。所以这三层递归，递归前两层做的事情就是找到第一个$d=3||4$的地方(当然，找不到那也是直接返回Yes),然后枚举要修改的这几个不同的位置，递归第三层做的事情才是$check是否d\le 2$

心得

由于每个序列的差别都最多两处的限制,这个题目的解法本质上就是暴力。但是是一个非常思维的暴力。你必须得把这个过程想的很清楚。我是想了好久才差不多明白为啥可以这么做。不过我解释的可能也不太行。如果有更好更简洁的解释或者方法还请大佬们指出来，嘿嘿.

代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int a[maxn] , d[maxn] , n , m;
int f(int x , int y){ return (x - 1) * m + y;}
bool dfs (int step)
{
    for (int i = 2; i <= n ; i++){
        int d = 0;
        vector<pair<int,int>> c;
        for (int j = 1 ; j <= m ; j++)
            if (a[f(1,j)] != a[f(i,j)])
                d++ , c.push_back(make_pair(j , a[f(i,j)]));
        if (d >= 5) return false;
        if (d <= 2) continue;
        if (step <= (d == 4)) return false;
        for (auto g : c){
            int tmp = a[f(1,g.first)];
            a[f(1,g.first)] = g.second;
            if (dfs(step - 1)) return true;
            a[f(1,g.first)] = tmp;
        }
        return false;
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i++) for (int j = 1 ; j <= m ; j++) cin >> a[f(i,j)];
    bool ok = dfs(2);
    if (!ok){
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;
    for (int i = 1 ; i <= m ; i++) cout << a[f(1 , i)] << ' ';
    cout << endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42