Codeforces Round 810 div.1 ABC

A. Color the Picture

观察发现同一个颜色必须呈整行或整列才能满足条件，且至少需要连续两行，计算一下每个颜色最多可以涂几行/列即可，特判奇数行/列时，所有颜色都仅能涂2行/列的情况。

ll n, m, k;
ll a[maxn];
void solve(){
    cin >> n >> m >> k;
    for(ll i=1;i<=k;i++) cin >> a[i];
    ll s = 0;
    bool fg = 0;
    for(ll i=1;i<=k;i++){
        ll d = a[i] / n;
        if(d > 1) s += d;
        if(d > 2) fg = true;
    }
    if((fg || m % 2 == 0) && s >= m){
        cout << "Yes\n";
        return;
    }
    s = 0;
    fg = 0;
    for(ll i=1;i<=k;i++){
        ll d = a[i] / m;
        if(d > 1) s += d;
        if(d > 2) fg = true;
    }
    if((fg || n % 2 == 0) && s >= n){
        cout << "Yes\n";
        return;
    }
    cout << "No\n";
}

B. Rain

首先预处理出每个位置上降水量的总值（离散化差分或数据结构），然后将所有降水按照左端点排序，枚举每个位置 \(x\)，二分找出第一个 删除之后，不能使得 \(x\) 处降水量少于m的位置，显然这个点右侧的全都不合法。

同理再按照右端点排序搞一次，就把所有不合法的点筛去了。

struct node{
    ll x, p;
    ll id;
    ll sum;
}a[maxn], b[maxn];
 
ll n, m;
map<ll, ll> d2;
void solve(){
    cin >> n >> m;
    d2.clear();
    for(ll i=1;i<=n;i++){
        a[i].id = i;
        cin >> a[i].x >> a[i].p;
        d2[a[i].x-a[i].p+1] += 1;
        d2[a[i].x+1] -= 2;
        d2[a[i].x+a[i].p+1] += 1;
    }
    ll sum = 0;
    vector<pair<ll, ll>> d11;
    for(auto [p, c]: d2){
        sum += c;
        d11.emplace_back(p, sum);
    }
    sum = 0;
    sort(a+1, a+n+1, [](node x, node y){
        return x.x < y.x;
    });
    for(ll i=0, j=1;i<d11.size();i++){
        while(j <= n && d11[i].first > a[j].x){
            a[j].sum = sum + d11[i-1].second * (a[j].x - d11[i-1].first);
            j++;
        }
        sum += d11[i].second;
        if(i > 0) sum += d11[i-1].second * (d11[i].first - d11[i-1].first - 1);
        while(j <= n && d11[i].first == a[j].x){
            a[j].sum = sum;
            j++;
        }
    }
 
    sort(a+1, a+n+1, [](node x, node y){
        return x.x - x.p + 1 < y.x - y.p + 1;
    });
    for(ll i=1;i<=n;i++) b[i] = a[i];
    sort(b+1, b+n+1, [](node x, node y){
        return x.x + x.p - 1 < y.x + y.p - 1;
    });
 
    vector<ll> ans(n+1, 1);
    ll midel = 1e9;
    for(ll i=1;i<=n;i++){
        if(a[i].sum <= m) continue;
        ll d = a[i].sum - m;
        ll p = lower_bound(a+1, a+n+1, a[i].x - d + 1, [&](node a, ll pos){
            return a.x - a.p + 1 <= pos;
        }) - a;
        midel = min(midel, p);
    }
    for(ll i=midel;i<=n;i++) ans[a[i].id] = 0;
 
    ll mxdel = 0;
    for(ll i=1;i<=n;i++){
        if(b[i].sum <= m) continue;
        ll d = b[i].sum - m;
        ll p = lower_bound(b+1, b+n+1, b[i].x+d-1, [&](node a, ll pos){
            return a.x + a.p - 1 < pos;
        }) - b;
        mxdel = max(mxdel, p-1);
    }
    for(ll i=1;i<=mxdel;i++) ans[b[i].id] = 0;
    for(ll i=1;i<=n;i++) cout << ans[i];
    cout << '\n';
}

C. XOR Triangle

新的一种bitmask技巧：

设 \(cnt_{i,j,k}\)，定义是这样的：

当 \(a,b,c\) 的第 \(x\) 位分别为 \(i,j,k\) 时，\(cnt_{i,j,k}\) 就在 \(x\) 位上为1，否则为0

例如对于下面的 \(a,b,c\)，有如下 \(cnt\)： \[ \begin{align*} cnt[011]:&\quad 10000001\\ a:&\quad 01010010\\ b:&\quad 10010101\\ c:&\quad 10111001 \end{align*} \] 即仅有 \(abc=011\) 的位置，\(cnt_{011}\) 才为1

有了这种 \(cnt\) 数组，就可以推断出一些东西：

\(a=\sum\sum cnt_{1jk}\)（\(a\) 中所有的 \(1\) 不重复不遗漏的加起来）

\(b=\sum\sum cnt_{i1k}\)

\(a\bigoplus b=\sum cnt_{01k}+\sum cnt_{10k}\)

简单推断可得，题目的条件等价于：\(cnt_{001}+cnt_{110}>0\)，\(cnt_{011}+cnt_{100}>0\)，\(cnt_{010}+cnt_{101}>0\)

设 \(dp[i][j][k]\) 为前 \(i\) 位，上限状态为 \(j\)，\(cnt\) 状态为 \(k\) 的方案数

\(j\) 用三位表示 \(a,b,c\) 三个数是否达到了上限，\(k\) 用三位表示上述三组 \(cnt\) 是否已经大于0，转移复杂度为 \(O(8^3n)\)

vector<int> subset(int x){
    int k = x;
    vector<int> r;
    while(k > 0){
        r.push_back(k);
        k = (k - 1) & x;
    }
    r.push_back(0);
    return r;
}
 
void solve() {
    string s;
    cin >> s;
    vector f(8, vector<ll>(8, 0));
    f[0][0] = 1;
    for(char c: s){
        int curlim = (c == '0' ? 0 : 7);
        vector g(8, vector<ll>(8, 0));
        for(int lim = 0; lim < 8; lim++){
            for(int frm = 0; frm < 8; frm++){
                for(int st: subset(lim | curlim)){
                    int nt = frm;
                    if(st == 1 || st == 6){
                        nt |= 1;
                    }
                    if(st == 2 || st == 5){
                        nt |= 2;
                    }
                    if(st == 3 || st == 4){
                        nt |= 4;
                    }
                    (g[lim | (st ^ curlim)][nt] += f[lim][frm]) %= mode;
                }
            }
        }
        f = g;
    }
    ll ans = 0;
    for(int i = 0; i < 8; i++) (ans += f[i][7]) %= mode;
    cout << ans << '\n';
}