3.21 CF

List

Test Generator

I heve to say till now i think that i dont tolly understand this problem.

Fitst we should note that so we can abstrct a array . And from this we can perform the following operation for i>0:

we can substract one from and then add two to .

So if the exits one on the binary representatuion of s and dont exits in m, we can substract one and move back.

The problem becaume we should find the max number in all .

And with the dandiao, we can use binary search here.

cpp

bool get(int x, int a, int lim){
    int f = 0;
    for (int i = 59; i >= 0; i--){
        f <<= 1;
        if (((x >> i) & 1) == 1){
            f++;
        }
        if (((a >> i) & 1) == 1){
            f -= min(lim, f);
        }
    }
    return (f == 0);
}

void solve(){
    int x, a;
    cin >> x >> a;

    if (!get(x, a, 1ll << 60)){
        cout << -1 << '\n';
        return;
    }

    int l = 0, r = (1ll << 60);
    while(l <= r){
        int m = l + (r - l) / 2;
        if (get(x, a, m)){
            r = m - 1;
        }
        else{
            l = m + 1;
        }
    }

    cout << l << '\n';
}

Find B

Since we should query the set. So we should use presum to achive the query in O(n).

And note that if we have a 1 during our query, we must set it to 2, and other number can be every one. So there exits a lower bound.

Moving Chips

With attention, the answer is the number of zeros between two block of 1.

Simons and Posting Blogs

Actuall what matters here is the last ocurrence of each element, so we determine the order by working backwords.

With the reverse, we iterate through its element. If an element is already contained in Q, ignore it and otherwise we append it to the end of Q. So we need a array to store the elements that have visited.

Thus, at each step we choose the array with the smallest lexicographically among the remain ones.

cpp

         #include <bits/stdc++.h>
#define rep1(i, l, r) for (int i = l; i <= int(r); ++i)
using namespace std;
const int MAXN = 1e6 + 10, inf = ~0U >> 2;
int n, vis[MAXN], chg[8010]; vector <int> a[8010];

void init(vector <int> &now) {
    for (auto &v : now) cin >> v, vis[v] = 0;
    reverse(begin(now), end(now));
    vector <int> nw;
    for (auto v : now) if (!vis[v]) nw.emplace_back(v), vis[v] = 1;
    for (auto v : nw) vis[v] = 0;
    now = nw;
}

void change(vector <int> &now) {
    if (now.size() == 1 && now[0] == inf) return;
    vector <int> nw;
    for (auto v : now) if (!vis[v]) nw.emplace_back(v);
    now = nw;
}

void solve() {
    cin >> n;
    rep1(i, 1, n) {
    int _;
    cin >> _;
        a[i].resize(_); init(a[i]); chg[i] = 0;
    }
    rep1(i, 1, n) {
        int id = 1;
        rep1(j, 1, n) if (!chg[j] && a[j] < a[id]) id = j;
        auto &now = a[id];
        for (auto v : now) printf("%d ", v), vis[v] = 1;
        now = vector <int> {inf}; chg[id] = 1;
        rep1(j, 1, n) if (!chg[j]) change(a[j]);
    } puts("");
}

int main() {
    int T;
    cin >> T;
    for (; T--; ) solve();
    return 0;
}

Array

Attention is all you need. Same for Flip Chips.

Ghostfires

The structure ABAC is the best.

3.21 CF ​

List ​

Test Generator ​

Find B ​

Moving Chips ​

Simons and Posting Blogs ​

Array ​

Ghostfires ​