Codeforces Round #740(Div. 2)部分题解_codeforces round 740

A

点击此处查看对应的题目.
本题模拟
本题要求最后迭代完成的数组必须递增，那么，首先检验是否符合这个条件，如果不符合就反复迭代。

按题意来说，迭代的过程需要按奇数和偶数进行枚举，不符合条件则与后一个数交换。反复迭代后记录其次数便是答案。

时间复杂度 $O(n^3)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1010,INF = 1e9 + 5;
int a[N];
int n;

bool exam()//检验
{
    for(int i = 1;i <= n - 1;i ++)
        if(a[i] > a[i + 1])
            return false;
    return true;
}
void solve()
{
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i];

    int cnt = 0;
    while(!exam()){
        cnt ++;
        if(cnt % 2){
            for(int i = 1;i <= n - 1;i += 2)
                if(a[i] > a[i + 1])
                    swap(a[i],a[i + 1]);
        }else{
            for(int i = 2;i <= n - 1;i += 2)
                if(a[i] > a[i + 1])
                    swap(a[i],a[i + 1]);
        }
    }
    if(cnt) cout <<cnt<<'\n';
    else puts("0");
}
int main()
{
    int t;
    cin >> t;
    while(t -- ){
        solve();
    }
    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
43
44
45

---

B

点击此处查看对应的题目.
本题思维题
本题乍一看还是挺懵的，不过经过分析我们可以知道，假设Alice先发球，Alice总的发球次数就是$p=\lceil \frac{a+b}{2}\rceil$次，Borys的罚球次数就是$q=\lfloor \frac{a+b}{2}\rfloor$次。Borys破发的次数可以达到x次（$0<=x<=p$）,Alice的破发次数可以达到y次（$0<=y<=q$）。

在这种情况下，Alice最多可以胜利a = (p - x) + y次，Borys最多可以胜利b = (q - y) + x次。分析到这说明（a与b）是与（x与y)有线性的关系的，而我们要求的就是 x + y 的可能值，那不正好，即x + y <= a + b

但其实以上的分析也可以靠感觉想出来出来QwQ
所以x + y 就可以从一个最小可能性 d 出发循环至最大可能性，但要注意a+b要分奇偶讨论，确定破发次数的上升规律。

最小可能性分析：两者的一攻一守，轮流交替，则出现破发的最小可能那便是a-b/2.

让最小破发可能性$d=\lfloor \frac{|a-b|}{2}\rfloor ,$
(这里之所以向下取整是因为我们求的是最小可能性.)

如果$a+b$是偶数，破发的所有可能值是$d,d+2,d+4，\dots ，a+b-d$。
如果$a+b$是奇数，破发的所有可能值是$d,d+1,d+2，\dots ，a+b-d$。

$\lfloor \rfloor$表示其中的值向下取整,$\lceil \rceil$表示向上取整。

时间复杂度$O(n)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;

void solve()
{
    int a,b;
    cin >> a >> b;
    int d = abs(a - b) >> 1;

    if((a + b) % 2){
        cout << a + b - 2 * d + 1 << '\n';
        for(int i = 0;d + i <= a + b - d;i ++)
            cout << d + i << " ";
    }else{
        cout << (a + b - 2 * d) / 2 + 1<< '\n';
        for(int i = 0;d + i <= a + b - d;i += 2)
            cout << d + i << " ";
    }
    puts("");
}
int main()
{
    int t;
    cin >> t;
    while(t -- ){
        solve();
    }
    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

---

C

点击此处查看对应的题目.
本题涉及算法：二分答案 + 排序 + 贪心
本题是一个武士如何用最小的初始力量值打怪的一个问题。

我们要做的主要是一件事，我们要确定武士访问山洞的顺序，然后把答案确定出来。这里求访问山洞的顺序需要根据武士进入每个山洞需要的力量的最大瓶颈值排序，然后按排好的访问山洞的顺序进行二分答案找到所需的初始力量值即可。

时间复杂度 $O(nlogn)$

#include<bits/stdc++.h>
using namespace std;
const int N = 100010,INF = 1e9 + 5;
int n,k;
vector<int> a;
struct Node
{
    vector<int> hp;//存山洞怪物血量的数组
    int st;//记录访问山洞每个山洞怪物的力量瓶颈值
    bool operator < (const Node &N)const{
        return st < N.st;
    }

}cave[N];

bool check(int x)
{
    for(int i = 0;i < a.size();i ++)
        if(i + x <= a[i])
            return false;
    return true;
}
void solve()
{
    cin >> n;
    a.clear();
    for(int i = 0;i < n;i ++){
        cin >> k;
        cave[i].hp.clear();
        cave[i].st = -INF;
        for(int j = 0;j < k;j ++){
            int x;
            cin >> x;
            cave[i].hp.push_back(x);
            cave[i].st = max(x - j,cave[i].st);//得到进入每个山洞需要的初始力量的最大瓶颈值
        }
    }

    sort(cave,cave + n);//确定要访问山洞的顺序
    for(int i = 0;i < n;i ++)
        for(auto it : cave[i].hp)
            a.push_back(it);//将所有怪加入新数组以便查找
    //二分答案
    int l = 0,r = INF;
    while(l + 1 < r){
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid;
    }
    if(check(l)) cout << l << '\n';
    else cout << r << '\n';
}
int main()
{
    int t;
    cin >> t;
    while(t -- ){
        solve();
    }
    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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62