【视频题解】

---

A

- 30%

暴力搜索

- 100pts

考虑到当往左或往右走一步时，$x=x′$，所以 $c_y$ 和 $c_y′$的奇偶性要相同。同样的当往上或往下走一步时，$y=y′$，所以 $r_x$ 和 $r_x′$的奇偶性要相同。所以保证有 $r_{s_x},r_{s_x+1}...r_{t_x}$ 奇偶性相同，$c_{s_y},c_{s_y+1}...c_{t_y}$ 奇偶性相同即可。

多次询问提前预处理即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int n,q,r[N],c[N],a[N],b[N],x1,x2,y1,y2;
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>r[i],r[i]%=2;
    for(int i=1;i<=n;i++) cin>>c[i],c[i]%=2;
    for(int i=2;i<=n;i++){
        a[i]=(r[i]==r[i-1]? a[i-1]:i);
        b[i]=(c[i]==c[i-1]? b[i-1]:i);
    }
    while(q--){
        cin>>x1>>y1>>x2>>y2;
        if(a[x1]==a[x2]&&b[y1]==b[y2]) cout<<"YES\n";
        else cout<<"NO\n";
    }
}

B

- 30pts

进行枚举尝试即可

- 100pts

位运算的题目往往也要逐位开始分析。对于数组 $A$ 中的数字，若其在第 $i$ 位都相同，则无论 $x$ 在该位为多少，最后该位按位或的结果均相同。所以必须要选择某位 $i$，使得 $A$ 中数字该位不同，然后 $x$ 的第 $i$ 位为 $0$，才能保证按位或后该位依旧有不同的结果。

枚举满足上述要求的位 $i$ 填 $0$，再从高向低枚举，能填 $1$ 则填 $1$。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N];
int main() {
	// your code goes here
	int t = 1;
	while(t--) {
        int n, x; cin >> n >> x;
        for(int i = 1; i <= n; i++) cin >> a[i];
	    int ans = 0;
	    for(int i = 29; i >= 0; i--) {
	        int cnt = 0, cur = 0;
	        for(int j = 1; j <= n; j++) 
	            if((a[j] >> i) & 1) cnt++;
	        if(0 < cnt && cnt < n) {
        	    for(int k = 29; k >= 0; k--) {
        	        if(k != i)
        	            if(cur + (1 << k) <= x)
        	                cur |= 1 << k;
        	    }
	            ans = max(ans, cur);
	        }
	    }
	    cout << ans << endl;
	}
}

C

注意到 $k$ 的范围是很小的，$k=1$ 时可以拿一些部分分。

$k=2$ 时尝试搜索所有满足条件的数字，然后按大小排好序，再使用二分查找确定 $\ge x$ 的答案。

具体搜索方法是枚举要使用的 $2$ 个数位 $p,q$，然后逐位进行数字的拼接，每次从两数中选一个拼到末尾即可。

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
ll k1[1505], k2[5000005];
int q1, q2;
void dfs1(int p, ll now)
{
	if (now > 1111111111)
	{
		return;
	}
	k1[++q1] = now;
	dfs1(p, now * 10 + p);
}
void dfs2(int p, int q, ll now)
{
	if (now > 1000000000)
	{
		return;
	}
	k2[++q2] = now;
	dfs2(p, q, now * 10 + p);
	dfs2(p, q, now * 10 + q);
}
void Sol1(ll s)
{
	ll l = 1, r = q1;
	while (l <= r)
	{
		ll mid = (l + r) >> 1;
		if (k1[mid] == s)
		{
			cout << k1[mid] << endl;
			return;
		}
		if (k1[mid] > s)
		{
			r = mid - 1;
		}
		else if (k1[mid] < s)
		{
			l = mid + 1;
		}
	}
	cout << k1[l] << endl;
}
void Sol2(ll s)
{
	ll l = 1, r = q2;
	while (l <= r)
	{
		ll mid = (l + r) >> 1;
		if (k2[mid] == s)
		{
			cout << k2[mid] << endl;
			return;
		}
		if (k2[mid] > s)
		{
			r = mid - 1;
		}
		else if (k2[mid] < s)
		{
			l = mid + 1;
		}
	}
	cout << k2[l] << endl;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	for (int i = 1; i <= 9; i++)
	{
		dfs1(i, i), dfs2(i, 0, i);
	}
	for (int i = 1; i <= 9; i++)
	{
		for (int j = 1; j < i; j++)
		{
			dfs2(i, j, i);
			dfs2(i, j, j);
		}
	}
	sort(k1 + 1, k1 + q1 + 1);
	sort(k2 + 1, k2 + q2 + 1);
	int T;
	cin >> T;
	while (T--)
	{
		ll n, k;
		cin >> n >> k;
		if (k == 1)
		{
			Sol1(n);
		}
		else
		{
			Sol2(n);
		}
	}
}

D

可以发现是否能有相差为 $1$ 的涂色方法与子树大小息息相关。记 $dp[u][0/1]$ 为以 $u$ 为根的子树，两色相差为 $0/1$ 的方案数。所求即为 $dp[1][0]+2\times dp[1][1]$，因为相差为 $1$ 有红多、黑多两种情况。

考虑转移，有 $u\rightarrow v$，即 $v$ 为 $u$ 的儿子，若 $siz[v]$ 为偶数，则 $v$ 子树内一定红黑树量相同，因为所有子树都必须两色数量相差不超过 $1$。所以 $siz$ 为偶数的 $v$ 不影响 $u$ 的情况，因此记录 $siz$ 为奇数的 $v$ 数量 $cnt$，因为 $siz[v]$ 为奇数，所以此子树内两色差一定为 $1$。若 $cnt$ 为偶数，则可两色差再次抵消，使得 $dp[u][0]$ 可行；若 $cnt$ 为奇数，则只能 $dp[u][1]$ 可行。乘法原理再乘上组合数。即有：

cnt 为 $u$ 奇数儿子个数

$dp[u][0] = \prod_{siz[v_i]为偶数} dp[v_i][0]\times \prod_{siz[v_j]为奇数}dp[v_j][1]\times C_{cnt}^{\frac{cnt}2}(cnt为偶)$

$dp[u][1] = \prod_{siz[v_i]为偶数} dp[v_i][0]\times \prod_{siz[v_j]为奇数}dp[v_j][1]\times C_{cnt}^{\lfloor \frac{cnt}2 \rfloor}(cnt为奇)$

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e6 + 5;
int n, fac[N], inv[N], mod = 1e9 + 7, dp[N][2], siz[N];
vector<int> g[N];

int qpow(int base, int k) {
	int res = 1;
	base %= mod;
	while(k) {
		if(k&1) res=(res*base)%mod;
		base=(base*base)%mod;
		k>>=1;
	}
	return res;
}

void init() {
    fac[0] = inv[0] = 1;
    for(int i = 1; i <= 300000; i++) fac[i] = fac[i-1] * i % mod;
    inv[300000] = qpow(fac[300000], mod - 2);
    for(int i = 300000; i >= 1; i--) inv[i-1] = inv[i] * i % mod;
}

int C(int n,int m) { 
    return fac[n] * inv[m] % mod * inv[n-m] % mod; 
}

void dfs(int u,int fa) {
    siz[u]=1, dp[u][0] = dp[u][1] = 0;
    int cnt=1;
    for(int v:g[u]) if(v!=fa) dfs(v,u),siz[u]+=siz[v],cnt+=siz[v]%2;
    if(siz[u]%2==0) {
        dp[u][0]=C(cnt,cnt/2);
        for(int v:g[u]) if(v!=fa) {
            if(siz[v]%2==0) (dp[u][0]*=dp[v][0]) %=mod;
            else (dp[u][0]*=dp[v][1]) %= mod;
        }
    }
    else {
        dp[u][1]=C(cnt,(cnt-1)/2);
        for(int v:g[u]) if(v!=fa) {
            if(siz[v]%2==0) (dp[u][1]*=dp[v][0]) %= mod;
            else (dp[u][1]*=dp[v][1]) %= mod;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    init();
	cin >> n;
	for(int i = 1; i < n; i++) {
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
        }
	dfs(1, 0);
	cout << (dp[1][0] + 2 * dp[1][1]) % mod << endl;
}