A

LYF & WD 树、构造

可以发现一个性质：只要某个子树中有2，就可以把这个2放在子树根节点

证明：考虑相邻两棵子树之差和2的位置，有三种情况

相邻两个子树和相同；
相邻两棵子树和差1，且2在较大的那棵子树
相邻两棵子树和差2，且2在较小的那棵子树

前两种情况比较显然，第三种情况可以把这个2和较大子树中任意一个1交换，变为第二种情况

有了这个性质之后可以得到一个填充策略：如果子树中还要填2，那么可以直接把这个2填在子树根上，可以保证是最优解之一，也就是优先填2，2填完了或者总和=1的情况才填1。

当知道了子树之和以及子树根节点的值以后，根节点的左右子树之和也分别可以确定了，对于左右子树，采取同样的策略

从根结点开始bfs，bfs过程中如果发现没东西能填了（1不够了）就直接输出-1

C

D

状压dp

披着博弈皮的状压dp，可以发现第一行的胜负情况是由最后八行的胜负情况可以确定的，用$dp[i][j]$表示考虑前$i$行，后八行胜负状态为$j$时，第一行的胜负情况

而$dp[i][j]$的求解是可以由$dp[i-1]$推导出的，$j$已知的情况下，唯一要确定的是第$i-8$行的胜负情况，而第$i-8$行又可以由$j$导出，得到上一层状态$prev$，所以$dp[i][j]=dp[i-1][prev]$

可以发现总状态数$2^8O(n)$，转移为$O(1)$，可以用记忆化搜索的方式剪枝。

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define mem(x, y) memset(x, y, sizeof(x))
#define debug(x) cerr << #x << " = " << x << ' '
#define debugl(x) cerr << #x << " = " << x << '\n'

using namespace std;
typedef long long ll;

const int N = 3e5 + 5, M = (1 << 8) - 1;

int n, status[N], path[N][10];

int dp[N][M + 5];

char s[10];

int bitcount(int x) {
    int res = 0;
    while(x) {
        res += x & 1;
        x >>= 1;
    }
    return res;
}

int dfs(int x, int st) {
    if (dp[x][st] != -1) return dp[x][st];
    int &res = dp[x][st];
    if (x <= 8) return res = (st >> (x - 1)) & 1;
    int prev = x - 8, pst = st >> 1;
    for (int i = 1; i <= 8; i++) {
        if (path[prev][i] && !((st >> (8 - i)) & 1)) {
            pst |= (1 << 7);
            break;
        }
    }
    return res = dfs(x - 1, pst);
}

int main() {
    scanf("%d\n", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        int temp = 0;
        for (int j = 0; j <= 7; j++) {
            temp = temp * 2 + (s[j] == 'W' ? 0 : 1);
        }
        status[i] = temp;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 8; j++) {
            if (8 - bitcount(status[i] ^ status[i + j]) >= j) path[i][j] = 1;
        }
    }
    mem(dp, -1);
    int now = 0;
    for (int i = 1; i <= n; i++) {
        int now = 0;
        for (int j = 1; j <= 7; j++) {
            int target = i - j;
            for (int k = 1; k <= j; k++) {
                if (path[target][k] && !((now >> (j - k)) & 1)) {
                    now |= (1 << j);
                    break;
                }
            }
        }
        printf("%d", 2 - dfs(i, now));
    }
    printf("\n");
    return 0;
}

E

K

LYF 签到

L

树

思路是可以发现把所有会继续往下递归的点连起来，一定是最左和最右两个点的LCA加上根节点到这个LCA的路径，问题就是怎么找出这左右两个端点。这两个端点肯定和区间$[L,R]$的L和R有关，以左端为例，直接直接找出两个点，{比L小的最大的点}和{大于等于L的最小的点}，求两点LCA，可以求出左端点，右端点同理（？），这个结论找不到反例但是也证不清楚。

不补了，浪费太多时间了，可能是特例没讨论干净，题解也说的不太清楚

M

ZRC