Bridging the Gap 2

题目大意

有$n$个步行者，第$i$个步行者对应一个体力值$h_i$，如果这个步行者坐上船，那么这个步行者的体力值会减$1$，体力值为$0$的步行者不能上船。起初所有步行者都在左岸，船在左岸，船上只能容纳$[L,R]$区间的人数，问这$n$个步行者能否全部到右岸。

解题思路

贪心。

基本思路即船从左岸到右岸载的人应尽量的多，因为会消耗每次船从右岸开回左岸的体力值，所以船从左岸到右岸一定选择$min(左岸剩余人数，R)$。同理，船从右岸开回左岸的人数一定越少越好，因为最终的目的是将所有人运到右边，这样一定不优，选择$L$人从右岸开回左岸最好。

以上确定了两种情况选多少人，接下来思考选怎么样的人（选最大的若干个?）。

我们右岸的人划到左岸的目的是送船，让左边的人可以回来。从左岸划到右岸的选人的根本目的是在这些方案中，船划到右岸后(左岸此时还有人)，右岸还能有$L$个人还能再划回左岸并且这$L$人能有体力再回来。

而这里，左岸划到右岸的所有方案一定要保证右岸划到左岸的选择一定是当前局面体力最大的$L$个人，否则可能回出现小体力和小体力组队从右往左划船，剩下大体力没有组队划船的。

因此一种直观且最优的想法就是每次选择左岸最大的$R$个，右岸最大的$L$个划船。

赛时思路以为左岸应该是最大的$L$个带着最小的$R-L$个最优，其实并无区别，根本目的是从右向左划船的需要是当前局面最大的$L$个。

想到这，我们就可以这样思考，求出船从右岸到左岸需要多少趟，总共$n$个人，去掉刚开始往右岸走的$R$个人，还剩下$n-R$人留在左岸，此时船在右岸，每次相当于右岸的$L$个人去左岸接$R-L$个人，等同于每次左岸少掉$R-L$个人，因此船从右岸到左岸需要的趟数$S=\lceil \frac{n-R}{R-l}\rceil$，而对于每个人，他到达右岸后能去左岸接人的趟数$a_i=\frac{h_i-1}2$，若右岸每次选$L$个能到左岸$S$趟就说明可以把左岸所有人运到右岸。

考虑如何计算右岸每次选$L$个能到左岸的趟数$V$，这里考虑每个人的对趟数的贡献，每次船上要有$L$个人。考虑第$i$ 个人可以走$a_i$趟，如果趟数大于$S$多余的部分显然无效，因为总共只有$S$趟，我最多参与$S$趟。

这里记$T=\sum_{i=1}^n min(a_i, S)$，证明若$T\ge L\times S$则说明可以把左岸所有人运到右岸。把$L\times S$想象成一块二维矩形，内部每一个纵向矩形表示每一趟船有哪些人，如果这$n$个人的贡献能把这个二维矩形填满即可。想象纵坐标是$L$，横坐标是$S$，每个人的贡献想象成宽为$1$，长为$a_i$的矩形，第一个人的贡献从左下角填起，如果一行填不下将矩形拆到下一行的开头填，因为矩形长$a_i$已经和$S$取最小，因此这样操作纵向一定不会出现同一个人。这样填满则证明这$S$趟从右岸到左岸的船都有不同的人可以上船，证毕。

时间复杂度$O(n)$

参考代码

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
typedef long long LL;
const int INF = 0x3f3f3f3f3f3f3f3f;

bool multi = 0;

void solve(){
    int n, L, R;
    cin >> n >> L >> R;
    vector<int> h(n);
    for (int i = 0; i < n; i++) cin >> h[i];
    sort(h.begin(), h.end());
    if(n >= L && n <= R) {
        cout << "Yes\n";
        return;
    }
    int S = (n - R) / (R - L);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += min(S, (h[i] - 1) / 2);
    }
    cout << (sum >= L * S ? "Yes\n" : "No\n");
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T = 1;
    if(multi) cin >> T;
    while(T--) {
        solve();
    }

    return 0;
}

Rigged Games

题目大意

给定只包含’0’或‘1’的长度为$n$的字符串，‘0’和‘1’分别表示队伍A和队伍B获胜，给定$a,b$表示两个队伍有一个队伍小分先赢$a$场，大分加$1$，大分先赢$b$场的队伍获胜。

解题思路

为方便表述，这里定义小局得分为小分，大局得分为大分，队伍0为队伍A，队伍1为队伍B。

令$val[i][j][k]$表示队伍$i$从$j$开始进行$2^k$场大局赢的局数，$nev[i][j][k]$表示队伍$i$从$j$开始进行$2^k$场大局会到哪个位置。

这样通过$nev[i][j][k]=nev[i][nev[i][j][k-1]][k-1],val[i][j][k]=val[i][j][k-1]+val[i][nev[i][j][k-1]][k-1]$就可以倍增出这两个数组。

我们需要的信息是$nev[i][j][0],val[i][j][0]$，即考虑进行一场大局会到哪个位置以及能赢多少局。这个问题可以通过双指针或前缀和+二分或题解做法再用一次倍增得到。我这里用的是前缀和+二分，需要$O(nlogn)$时间复杂度。做法就是把所有前缀和对应的下标放在前缀和数组中，对于每一个位置$j$二分队伍$i$最早赢得$presum[i][j-1]+a$场($presum[i][j]$表示从队伍$i$从第$0$场打到第$i$场赢了多少小局)第一个大于等于$i$的下标取最小，注意这里有一个坑点就是它所到的位置应该是这个点的下一个位置。

看最终谁获胜只需要进行$2\times b-1$轮大局哪个队伍赢得小局多，直接通过$nev,val$这两个倍增数组求得。

参考代码

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
typedef long long LL;
const int INF = 0x3f3f3f3f3f3f3f3f;

bool multi = 0;

int n, a, b;
string s;

void solve(){
    cin >> n >> a >> b;
    cin >> s;
    while (s.size() < (int)3e5) {
        s += s;
    }
    while((int)s.size() > (int)3e5 + 5) {
        s.pop_back();
    }
    vector<vector<int>> pre(2, vector<int>(s.size()));
    vector<vector<vector<int>>> pos(2, vector<vector<int>>(3e5 + 10, vector<int>()));
    for (int i = 0; i < s.size(); i++) {
        for(int j = 0; j < 2; j++) {
            pre[j][i] = (i - 1 >= 0 ? pre[j][i - 1] : 0) + ((s[i] - '0') == j);
            pos[j][pre[j][i]].push_back(i);
        }
    }
    vector<vector<vector<int>>> val(2, vector<vector<int>>(n, vector<int>(30, -1)));
    vector<vector<vector<int>>> nev(2, vector<vector<int>>(n, vector<int>(30, -1)));
    for(int i = 0; i < n; i++) {
        bool who = 0;
        int mn = INF;
        for(int j = 0; j < 2; j++) {
            int presum = (i - 1 >= 0 ? pre[j][i - 1] : 0) + a;
            auto it = lower_bound(pos[j][presum].begin(), pos[j][presum].end(), i);
            if(it == pos[j][presum].end()) {
                continue;
            }
            int p = *it;
            if(mn > p) {
                mn = p;
                who = j;
            }
        }
        assert(mn != INF);
        nev[!who][i][0] = (mn + 1) % n;
        nev[who][i][0] = (mn + 1) % n;
        val[who][i][0] = 1;
        val[!who][i][0] = 0;
    }


    for(int k = 1; k < 30; k++) {
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                if(nev[i][j][k - 1] != -1 && nev[i][nev[i][j][k - 1]][k - 1] != -1) nev[i][j][k] = nev[i][nev[i][j][k - 1]][k - 1];
            }
        }
    }
    for (int k = 1; k < 30; k++) {
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                if(nev[i][j][k - 1] != -1 && val[i][j][k - 1] != -1 && val[i][nev[i][j][k - 1]][k - 1] != -1) val[i][j][k] = val[i][j][k - 1] + val[i][nev[i][j][k - 1]][k - 1];
            }
        }
    }
    for (int i = 0; i < n; i++) {
        int mx = -1;
        bool ans = 0;
        for(int j = 0; j < 2; j++) {
            int tb = b * 2 - 1;
            int cur = 0;
            int now = i;
            for (int k = 29; k >= 0; k--) {
                if(tb >= (1LL << k)) {
                    tb -= (1LL << k);
                    if(val[j][now][k] == -1) {
                        cur = -1;
                        break;
                    }
                    cur += val[j][now][k];
                    now = nev[j][now][k];
                }
            }
            if(mx < cur) {
                mx = cur;
                ans = j;
            }
        }
        cout << ans;
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T = 1;
    if(multi) cin >> T;
    while(T--) {
        solve();
    }

    return 0;
}