Codeforces Round 948 (Div. 2) B - C

总结：

做了A，B，然后开局A看错题wa了一发，B出的又很慢，所以掉大分。总的来说还是c没开出来。

B. Binary Colouring

1.题目大意：
给你一个int范围内的数x，要求构造一个二进制串，能有-1、1、0，二进制串的值不能出现两个连续的地方不为0，二进制串的值要等于x。

2.思路分析：
我们可以发现，对于x的原本的二进制串来说，只有碰到连续的1才会要进行变化，我们希望的是其中一个地方的1变成0。记这两位1中高位为b1，低位为b2。那么只要b1进位，那么b1就会变成0，所以可以让b1 + 1，然后相当于多了一个b2，于是就让b2变成-1，然后就可以了。最后最高位要处理一下进位。

3.代码如下：

void solve() {
    ll x; cin >> x;
    vi ans;
    while(x) {
        ans.push_back(x % 2);
        x /= 2;
    }
    for(int i = 0; i < ans.size() - 1; i++) {
        if(ans[i] == 2) {
            ans[i] = 0;
            ans[i + 1] += 1;
        }
        if(ans[i] == 1 && ans[i + 1] == 1) {
            ans[i] = -1;
            ans[i + 1] += 1;
        }
    }
    if(ans.back() == 2) {
        ans.pop_back();
        ans.push_back(0), ans.push_back(1);
    }
    cout << ans.size() << "\n";
    for(auto i : ans) cout << i << " ";
    cout << "\n";
}

C. Nikita and LCM

1.题目大意：
定义一个数组A的子数组是特殊的，那么这个子数组的lcm不在A中。给你一个数组A，问你数组A的最长的特殊子数组的长度是多少。

2.思路分析：
记整个数组的最大值为maxn

• 如果A中存在不是maxn的因子的数，那么整个数组都是一个特殊数组，因为算出来的lcm一定会比maxn大
• 否则，剩下的除了maxn以外的数一定都是maxn的因子，所以剩下的数字组成的子数组的lcm也是maxn的因子，所以我们可以去枚举maxn的这些因子并且判断这个因子是不是不在数组A中，只有不在的时候才去验证。记每次枚举的因子为x，然后我们遍历一遍数组，碰到的 \(a_{i}\) 只要是x的因子就可以选，最后判断选的所有数的lcm是不是x就可以了。然后在所有情况中选一个最大值。
  

3.代码如下：

void solve() {
    int n;cin >> n;
    int ans = 0;
    vi a(n + 1);
    set<int> st;
    for(int i = 1; i <= n; i++) cin >> a[i], st.insert(a[i]);
    sort(a.begin() + 1, a.begin() + 1 + n);
    int maxn = a[n];
    int flag = 0;
    for(int i = 1; i <= n; i++) {
        flag |= (maxn % a[i]);
    }
    if(flag) {
        cout << n << "\n";
        return;
    }
    auto check = [&](int x) {
        if(st.count(x)) return 0LL;
        int g = 1, cnt = 0;
        for(int i = 1; i <= n; i++) {
            int ng = std::lcm(g, a[i]);
            if(x % ng) continue;
            cnt += 1;
            g = ng;
        }
        if(g == x) return cnt;
        return 0LL;
    };
    for(int i = 1; i * i <= maxn; i++) {
        if(maxn % i) continue;
        ans = max(ans, check(i));
        ans = max(ans, check(maxn / i));
    }
    cout << ans << "\n";
}