A.Bridging the Gap 2

题目大意 ：有n个人要划船过河（只有一艘船），每个人有\(h_i\)的体力，每次划船最少要L人，最多R人，划船要消耗船上所有人1的体力，问存不存在一种方案可以让所有人过河。
思路 ：首先除了最后一次，前面的都需要有L人把船开回来，所以要有L人体力大于三，即可以算出一共需要\(t=\lceil \frac {n-R}{r-L} \rceil\)趟可以运完所有人。每个人可以划的趟数为\(a_i=\lfloor \frac {h_i-1}{2} \rfloor\)，满足\(\sum_1^n min(a_i,t)\geq t*l\)即可

#include<bits/stdc++.h>

using namespace std;
#define int long long
const int N = 5e5 + 10;

int h[N];

void solve() {
    int n,l,r;
    cin >> n>>l>>r;
    int t=(n-r)/(r-l)+((n-r)%(r-l)!=0);
    int sum=0;
    for(int i=0;i<n;i++){
        cin >> h[i];
        sum+=min((h[i]-1)/2,t);
    }
    if(sum>=t*l) cout <<"Yes";
    else cout <<"No";
}


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

D.Dominoes!

题目大意 给出n块多米诺骨牌，每块上有两个数字，给出一种排列顺序使相邻多米诺骨牌上头尾数字不同，如(a,b)(c,d)(e,f)，若\(b\neq c,d\neq e\)即合法。
思路 ：若一块多米诺骨牌上两个数字不相同则通过翻转一定可以放在末尾，所以处理数字相同的多米诺骨牌即可。

#include<bits/stdc++.h>

using namespace std;
#define int long long
const int N = 5e5 + 10;
#define debug(x) cerr<<"! x="<<x<<'\n'
map<int, int> num2;
map<int, int> same;
vector<pair<int, int> > k;
vector<pair<int, int>> ans;

void solve() {
    int n;
    cin >> n;
    int f = 0;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        if (a == b) {
            same[a]++;
        } else k.emplace_back(a, b);
        num2[a]++;
        num2[b]++;
        if (num2[a] > n + 1 || num2[b] > n + 1) f = 1;
    }
    int len=k.size();
    if (f) {
        cout << "No";
        return;
    }
    cout << "Yes" << '\n';
    priority_queue<pair<int, int> > d;
    for (auto i: same) {
        d.emplace(i.second, i.first);
    }
    while (d.size() >= 2) {
        auto [sa, na] = d.top();
        d.pop();
        auto [sb, nb] = d.top();
        d.pop();
        ans.emplace_back(na, na);
        ans.emplace_back(nb, nb);
        if (sa > 1) d.emplace(sa - 1, na);
        if (sb > 1) d.emplace(sb - 1, nb);
    }
    if (d.size() == 1) {
        auto [cnt, val] = d.top();
        if(ans.empty()||ans.back().second!=val){
            ans.emplace_back(val,val);
            cnt--;
        }
        while(cnt){
            for(int i=0;i<len;i++){
                int a=k[i].first;
                int b=k[i].second;
                if(a==0) continue;
                if(a!=val&&b!=val){
                    cnt--;
                    ans.emplace_back(a,b);
                    ans.emplace_back(val,val);
                    k[i]={0,0};
                }
                if(cnt==0) break;
            }
        }
    }
    int p = -1;
    if(ans.size()) p = ans.back().second;
    for (auto i: k) {
        if (i.first == 0) continue;
        if (i.first == p) {
            ans.emplace_back(i.second, i.first);
        } else {
            ans.emplace_back(i.first, i.second);
            p = i.second;
        }
    }
    for (auto i: ans) {
        cout << i.first << ' ' << i.second << "\n";
    }
}


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

J.Rigged Games

题目大意 ：给出一串01串表示接下来比赛中A队的输赢情况，此01串无限循环直至比赛结束，给出a,b表示赢a场小比赛算作赢一场大比赛，赢b场大比赛即算作赢下比赛，输出从给出01串的第i个字符开始比赛时第胜负情况。
思路 ：用双指针遍历01串记录从i开始第一场大比赛结束时的结果和结束的位置，然后用倍增求出比赛结果

#include<bits/stdc++.h>

using namespace std;
#define int long long
const int N = 5e5 + 10;

vector<int> w(N);
vector<vector<vector<int> > > go(N, vector<vector<int> >(30, vector<int>(3)));

void solve() {
    int n, a, b;
    cin >> n >> a >> b;
    for (int i = 0; i < n; i++) {
        char num;
        cin >> num;
        w[i] = num - '0';
    }
    int j = 0;
    int ya = 0;
    int yb = 0;
    for (int i = 0; i < n; i++) {
        while (!(ya == a || yb == a)) {
            if (w[j] == 1) ya++;
            else yb++;
            j++;
            j %= n;
        }
        if (ya == a) go[i][0] = {j, 1, 0};
        else go[i][0] = {j, 0, 1};
        if (w[i] == 1) ya--;
        else yb--;
    }
//    for (int i = 0; i < n; i++)
//        //cout << i << ' ' << go[i][0][0] << ' ' << go[i][0][1] << ' ' << go[i][0][2] << ' ' << '\n';
    for (int i = 1; i <= 20; i++) {
        for (j = 0; j < n; j++) {
            if (go[j][i - 1][1] + go[go[j][i - 1][0]][i - 1][1] > b ||
                go[j][i - 1][2] + go[go[j][i - 1][0]][i - 1][2] > b ||
                go[j][i - 1][1] == 0 && go[j][i - 1][2] == 0 ||
                go[go[j][i - 1][0]][i - 1][1] == 0 && go[go[j][i - 1][0]][i - 1][2] == 0 ||
                go[j][i - 1][1] == b || go[go[j][i - 1][0]][i - 1][1] == b ||
                go[j][i - 1][2] == b || go[go[j][i - 1][0]][i - 1][2] == b)
                continue;
            go[j][i][0] = go[go[j][i - 1][0]][i - 1][0];
            go[j][i][1] = go[j][i - 1][1] + go[go[j][i - 1][0]][i - 1][1];
            go[j][i][2] = go[j][i - 1][2] + go[go[j][i - 1][0]][i - 1][2];
            //cout << j << ' ' << i << ' ' << go[j][i][0] << " " << go[j][i][1] << " " << go[j][i][2] << "\n";
        }
    }
    for (int i = 0; i < n; i++) {
        int idx = i;
        ya = 0;
        yb = 0;
        for (int k = 20; k >= 0; k--) {
            //cout << idx << ' '<<k <<'\n';
            if (go[idx][k][1] + go[idx][k][2] == 0) continue;
            int aa = ya + go[idx][k][1];
            int bb = yb + go[idx][k][2];
            //cout << aa <<'|'<< bb<<"|";
            if (aa > b || bb > b||aa>=b&&bb>=b) continue;
            if (aa == b || bb == b ) {
                if (aa == b) cout << 1;
                else cout << 0;
                break;
            }
            ya = aa;
            yb = bb;
            idx = go[idx][k][0];
        }
    }
}


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