2024牛客暑期多校训练营3（补题）

· · 个人记录

Bridging the Gap 2

思路：思维题，想的是正确的，求解的方法过于复杂了，只过了80%左右，换个思路简单很多，我们可以知道总共需要往返的次数是确定的 x=(n-r +(r-l-1))/(r-l),即x=(n-l-1)/(r-l),每次需要l个不同的车夫那么我们可以得出，需要当作车夫的次数是y=x*l，因为每次的车夫都不同，那么一个人可以当车夫的次数是min((a[i]-1)/2,x)，那么我们直接求和是否>=y即可

diamond：

#include <bits/stdc++.h>
#define int long long
#define mod 1000000007
#define PII pair<int,int>
#define PIII pair<PII,int>
#define double long double
#define endl '\n'
#pragma GCC optimize(3,"Ofast","inline")

using namespace std;

const int N = 5e5 + 4, SZ = N << 2;

vector<PII>g[N];
int a[N];
int n, k, m;
int ans = 0;
void solve() {
    int l, r;
    cin >> n >> l >> r;
    int cs=(n-l-1)/(r-l);
    int sum=cs*l;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] = (a[i] - 1) >> 1;
        sum-=min(a[i],cs);
    }
    if(sum>0){
        cout<<"No\n";
    }
    else{
        cout<<"Yes\n";
    }
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
//  cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

Rigged Games

思路：首先考虑，大局套小局，我们先处理a小局，我们可以得出从每个点出发，一局后的情况，为（0的个数，1的个数，下一个位置idx），设为g[i][0][0~~3]，那么我们通过倍增得到g[i][1]=g[i][0]+g[g[i][0][2]][0],走两步，就等于走一步的0的个数和1的个数加上从走到的那个位置开始，走一步的0的个数和1的个数，这样就可以预处理出来以每一个位置开始，走1，2，4，8……步的0和1的个数，以及下一步是哪儿，然后我们反向倍增求一下，第一个0和1的个数到达a的地方在哪儿，就是看走几步，先走多的，如果可以，就走，如果不可以，就走小的步数，通过二进制凑出即可,这样就处理出来了大局的f[i][0][0~3]，比如小局中，从i开始，走了9步到达了j，1的个数到了a，那么f[i][0]={0,1,nxt[j]}，这样就预处理出来了，大局中，从i开始走j步的状态了，再次倍增求解即可

diamond：

#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define endl '\n'
const int N=1e5+5;

int ans[N];
array<int, 3> operator+(const array<int, 3> &a, const array<int, 3> &b)
{
    return {a[0] + b[0], a[1] + b[1], b[2]};
}
void  solve() {
    int n, a, b;
    cin >> n >> a >> b;
    vector<vector<array<int, 3>>> f(n + 3, vector<array<int, 3>>(26));
    vector<vector<array<int, 3>>> g(n + 3, vector<array<int, 3>>(26));
    int a1 = 0, b1 = 0, now = 0;
    string c;
    cin >> c;
    c=" "+c;
    for (int i = 1; i <= n; i++) {
        int fen=(c[i]=='1');
        int nx=i%n+1;
        if(fen==0){
            g[i][0]={1,0,nx};
        }
        else g[i][0]={0,1,nx};
    }
    for (int i = 1; i <= 18; i++) {
        for (int j = 1; j <= n; j++) {
            g[j][i] = g[j][i - 1] + g[g[j][i - 1][2]][i - 1];
        }
    }
    for (int i = 1; i <= n; ++i) {
        int now = i;
        int sum0 = 0, sum1 = 0;
        for (int j = 18; j >= 0; --j) {
            if (sum0 + g[now][j][0] >= a or sum1 + g[now][j][1] >= a) {
                continue;
            }
            sum0 += g[now][j][0];
            sum1 += g[now][j][1];
            now = g[now][j][2];
        }
        sum0 += g[now][0][0];
        sum1 += g[now][0][1];
        int nx=g[now][0][2];
        if (sum0 == a) {
            f[i][0]={1,0,nx};
        } else f[i][0]={0,1,nx};
    }
    for (int i = 1; i <= 18; i++) {
        for (int j = 1; j <= n; j++) {
            f[j][i] = f[j][i - 1] + f[f[j][i - 1][2]][i - 1];
        }
    }
    for (int i = 1; i <= n; ++i) {
        int now = i;
        int sum0 = 0, sum1 = 0;
        for (int j = 18; j >= 0; --j) {
            if (sum0 + f[now][j][0] >= b or sum1 + f[now][j][1] >= b) {
                continue;
            }
            sum0 += f[now][j][0];
            sum1 += f[now][j][1];
            now = f[now][j][2];
        }
        sum0 += f[now][0][0];
        sum1 += f[now][0][1];
        if (sum0 == b) {
            cout << 0;
        } else cout << 1;
    }
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int t=1;
    //   cin>>t;
    while (t--){
        solve();
    }
}