20240708NOIP模拟赛赛后复盘

legendcn / 2024-07-09 / 原文

20240708NOIP模拟赛

总结

策略

7:45~8:15 思考 T1，感觉十分奇妙，输出 Impossible 直接下一题。
8:15~8:47 写出了 T2 一个最朴素的暴力
8:47~9:23 写了一下 T3 的暴力并优化了一下
9:23~10:36 继续思考 T2，感觉可以计算贡献，利用出题人给的小知识化简为子集问题，可以用高维前缀和
10:36~11:10 把 T2 正解写出来了
11:10~11:15 T4 输出样例骗分

得分

T1：0/40，该写的暴力没有写
T2: 100/100
T3: 30/60，map 复杂度太高，暴力写的不好
T4: 10/10
总得分：140/210
挂了 70 分，呜呜呜

题目及题解

红黑树

题目描述

有一颗有根二叉树，每个点都有 $0$，$1$，$2$ 个孩子。假设每个点都有 $2$ 个孩子，对于不足 $2$ 个孩子的节点，给他添一个空节点。
对于满足以下条件的树，我们称之为红黑树

每个非空节点都被染成红色或者黑色
没有一条边的两个端点都是红色的。空节点被认为是黑色的。
每一条从根节点到空节点的简单路径，包含黑节点的数量相等。
询问给定二叉树是否为红黑树。

题解

容易发现，如果一颗树满足条件，那么他的一棵子树也一定满足条件。所以可以树形 DP
设 $f_{u,j,0/1}$ 表示以 $u$ 为根的子树中，从根节点到空节点（不包括这个点）黑点的个数为 $j$，且 $u$ 号为红色或者黑色。
然后使用树形 DP 构造即可。

# include <bits/stdc++.h> 
using namespace std; 
using namespace IOS; 
typedef long long ll; 
//# define int long long 
# define lc u << 1
# define rc u << 1 | 1 
const int N = 505;

int n; 
int fa[N]; 
vector <int> e[N];
bool f[N][N][2]; // f[i][j][0/1]表示以i为根的子树中，经过了j个黑点，其中i涂成0/1
char ans[N]; 
void dfs (int u)
{
    if (!u) return;
    for (int v : e[u]) dfs (v); 
    int ls = e[u][0], rs = e[u][1];
    for (int i = 0; i <= n; i ++ )
    {
        if (i > 0)
        {
            for (int j = 0; j <= 1; j ++ )
            {
                for (int k = 0; k <= 1; k ++ )
                    f[u][i][0] |= (f[ls][i - 1][j] & f[rs][i - 1][k]);
            }
        }
        f[u][i][1] |= (f[ls][i][0] & f[rs][i][0]);
    }
}
void getans (int u, int i, int op)
{
    if (!u) return;
    int ls = e[u][0], rs = e[u][1];
    if (op)
    {
        ans[u] = 'R';
        getans (ls, i, 0), getans (rs, i, 0);
    }
    else
    {
        ans[u] = 'B';
        bool flag = 0;
        for (int j = 0; j <= 1; j ++ )
        {
            for (int k = 0; k <= 1; k ++ )
            {
                if (f[ls][i - 1][j] & f[rs][i - 1][k])
                {
                    flag = 1;
                    getans (ls, i - 1, j);
                    getans (rs, i - 1, k);
                    break; 
                }
            }
            if (flag) break;
        }
    }
}
signed main()
{
    freopen ("rbt.in", "r", stdin);
    freopen ("rbt.out", "w", stdout); 
    read (n); 
    f[0][0][0] = 1; 
    int rt = 0; 
    for (int i = 1; i <= n; i ++ )
    {
        int u; read (u); 
        if (!u) rt = i;
        else e[u].push_back (i);
    }
    for (int i = 1; i <= n; i ++ )
    {
        while ((int)e[i].size() < 2)
            e[i].push_back (0);
    }
    dfs (rt);
    for (int i = 0; i <= n; i ++ )
    {
        if (f[rt][i][0])
        {
            getans (rt, i, 0); 
            for (int j = 1; j <= n; j ++ ) write (ans[j]);
            return 0; 
        }
        if (f[rt][i][1])
        {
            getans (rt, i, 1);
            for (int j = 1; j <= n; j ++ ) write (ans[j]); 
            return 0;
        }
    }
    puts ("Impossible"); 
    return 0;
}

# 异或

题目描述

有一颗 $n$ 个点的树，节点从 $0$ 开始编号，根节点为 $0$ 号节点。每个点都有一个点权，初始时为 $X_i^{(0)}$
第 $d$ 天，一个人会从根节点开始进行下面的操作：

对于节点 $u$，计算其子树中的每个节点 $v$ 在前一天的权值 $X_u^{(d-1)}$ 的异或和，并几位 $u$ 在这一天的权值。
对于 $u$ 的每个儿子，递归进行上面的计算。给定 $Q$ 个日期 $p$，请求出 $X_0^p$。

题解

考虑每个点经过 $t$ 的时间后会异或几次，发现这个数只跟深度有关。设根节点的深度为 $0$，那么深度为 $d$ 的点在时刻 $t$ 的异或次数为 $\binom{d+t}{t}$。
根据出题人给的小知识（也就是 Lucas 定理），$\binom{n}{m} \equiv 1 \mod 2 \Leftrightarrow m \subseteq n$，所以 $d\cap t=\emptyset$。然后 $\text{sosdp}$ 即可。

# include <bits/stdc++.h>
using namespace std;
using namespace IOS;
typedef long long ll;
# define int long long
# define lc u << 1
# define rc u << 1 | 1
const int N = 2000005; 

int n, q; 
int a[N]; 
vector <int> e[N]; 
int dep[N]; 
int f[N]; 
void dfs (int u, int fat)
{
	dep[u] = dep[fat] + 1; 
	f[dep[u]] ^= a[u]; 
	for (int v : e[u])
	{
		if (v == fat) continue; 
		dfs (v, u); 
	}
}
signed main ()
{
	freopen ("xor.in", "r", stdin); 
	freopen ("xor.out", "w", stdout);  
	read (n, q); 
	for (int i = 1; i < n; i ++ )
	{
		int u, v; read (u, v); 
		e[u].push_back (v), e[v].push_back (u); 
	}
	for (int i = 0; i < n; i ++ ) read (a[i]); 
	dep[n + 1] = -1; 
	dfs (0, n + 1); 
	for (int i = 0; i <= 18; i ++ )
	{
		for (int j = 0; j < N; j ++ )
		{
			if (j >> i & 1)
				f[j] ^= f[j ^ (1ll << i)]; 
		}
	}
	while (q -- )
	{
		int d; read (d); d -- ; 
		int s = 0; 
		for (int i = 0; i <= 18; i ++ )
		{
			if (!(d >> i & 1))
				s += (1ll << i); 
		}
		write (f[s], '\n');  
	}
	return 0;
}

临别赠礼

题目描述

$n$ 个数从左到右标号为 $1\cdots n$，每个数有一个标号。
定义标号为 $x$ 的数在某个区间的呵呵值为 $x$ 在这个区间上第一次出现的位置与最后一次出现的位置的差值。
定义一个区间的呵呵值为每个在这个区间出现过的标号的呵呵值之和。
呵呵给你 $m$ 次操作 op a b。如果 $\text{op}$ 为 $1$，即将 $x_a$ 修改为 $b$；如果 $\text{op}$ 为 $2$，即需要你回答 $[a,b]$ 区间的呵呵值之和。

题解

记录一个上一个和 $a_i$ 相同的位置 $las_i$，对于每次询问，其实就是询问 $\sum_{i=l}{r}(i-las_i)[las_i\ge l]$。
因为有修改，所以可以直接转化为三维偏序，用 CDQ 分治。

# include <bits/stdc++.h>
using namespace std; 
using namespace IOS; 
using namespace std; 
typedef long long ll; 
//# define int long long 
# define lc u << 1
# define rc u << 1 | 1 
const int N = 100005; 

int n, m; 
int a[N]; 
set <int> s[N]; 
struct node { int pre, pos, tim, val, op; } p[N * 10]; int tot; 
bool cmp (node x, node y) { return x.pre != y.pre ? x.pre > y.pre : x.pos < y.pos; }
int c[N]; 
int lowbit(int x) { return x & (-x); }
void add (int x, int w) { for (; x <= n; x += lowbit (x)) c[x] += w; }
int query (int x) { int s = 0; for (; x; x -= lowbit (x)) s += c[x]; return s; }
void cdq (int l, int r)
{
	if (l == r) return; 
	int mid = l + r >> 1; 
	cdq (l, mid), cdq (mid + 1, r); 
	sort (p + l, p + 1 + mid, cmp); 
	sort (p + 1 + mid, p + 1 + r, cmp); 
	int i = mid + 1, j = l; 
	while (i <= r)
	{
		while (j <= mid && p[j].pre >= p[i].pre)
		{
			if (p[j].op == 1) add (p[j].pos, p[j].val); 
			j ++ ; 
		}
		if (p[i].op == 2) p[i].val += query (p[i].pos);
		i ++ ;
	}
	for (int i = l; i < j; i ++ )
	{
		if (p[i].op == 1)
			add (p[i].pos, -p[i].val); 
	}
}
signed main ()
{
	freopen ("goodbye.in", "r", stdin); freopen ("goodbye.out", "w", stdout); 
	read (n, m); 
	for (int i = 1; i <= n; i ++ )
	{
		read (a[i]); 
		s[a[i]].insert (i); 
		auto it = s[a[i]].lower_bound (i); 
		if (it != s[a[i]].begin ())
		{
			it -- ; 
			int x = (*it); 
			p[ ++ tot] = {x, i, tot, i - x, 1}; 
		}
	}
	for (int i = 1; i <= m; i ++ )
	{
		int op, x, y; read(op, x, y); 
		if (op == 1)
		{
			if (a[x] == y) continue;
			auto it = s[a[x]].lower_bound (x);
			int pre = 0, nxt = 0;  
			if (it != s[a[x]].begin ())
			{
				auto preit = it; preit -- ; 
				pre = (*preit); 
			}
			auto nxtit = it; nxtit ++ ; 
			if (nxtit != s[a[x]].end ()) nxt = (*nxtit);
			if (pre) p[ ++ tot] = {pre, x, n + i, pre - x, 1}; 
			if (nxt) p[ ++ tot] = {x, nxt, n + i, x - nxt, 1};
			if (pre && nxt) p[ ++ tot] = {pre, nxt, n + i, nxt - pre, 1};
			s[a[x]].erase (it);
			s[y].insert (x);
			a[x] = y; 

			it = s[a[x]].lower_bound (x);
			pre = 0, nxt = 0; 
			if (it != s[a[x]].begin ())
			{
				auto preit = it; preit -- ; 
				pre = (*preit); 
			}
			nxtit = it; nxtit ++ ; 
			if (nxtit != s[a[x]].end ()) nxt = (*nxtit);
			if (pre) p[ ++ tot] = {pre, x, n + i, x - pre, 1}; 
			if (nxt) p[ ++ tot] = {x, nxt, n + i, nxt - x, 1};
			if (pre && nxt) p[ ++ tot] = {pre, nxt, n + i, pre - nxt, 1};
		}
		else p[ ++ tot] = {x, y, n + i, 0, 2}; 
	}
	sort (p + 1, p + 1 + tot, [&](node x, node y) 
	{
		return x.tim != y.tim ? x.tim < y.tim : 
			(x.pre != y.pre ? x.pre > y.pre : x.pos < y.pos); 
	}); 
	cdq (1, tot); 
	sort (p + 1, p + 1 + tot, [&](node x, node y) 
	{
		return x.tim != y.tim ? x.tim < y.tim : 
			(x.pre != y.pre ? x.pre > y.pre : x.pos < y.pos); 
	}); 
	for (int i = 1; i <= tot; i ++ )
	{
		if (p[i].op == 2)
			write (p[i].val, '\n'); 
	}
	return 0; 
}

数图

题目描述

给定一个无向图，呵呵希望图上能有 $n$ 个点，$m$ 条边，并且任意两个站点能够互相到达。
特别的，如果一个点的度数只有 $2$，说明这个点是一个呵呵点。呵呵希望标号最小的 $t$ 个点都是呵呵点。问这样的无向连通图个数。

题解

$t = 0$
设 $e_n$ 为 $n$ 个点的完全图的边数 $\frac{n(n+1)}{2}$，$f_{i,j}$ 为 $i$ 个点 $j$ 条边的连通图个数。考虑容斥，枚举 $1$ 号点所在的连通块对应的点数 $a$ 和边数 $b$，可得 $f_{i,j}=\binom{e_i}{j}-\sum_a \sum_b f_{a,b}\binom{i-1}{a-1}\binom{e_{i-a}}{j-b}$
$t=1$
可以看作在 $n-1$ 个点的连通图中选一条边 $(u,v)$，将其替换为 $(1,u)$，$(1,v)$；或者直接加上两条边。所以 $f_{i,j}=f_{n-1,m-1}(m-1)+f_{n-1,m-2}(m-2)$
$t=2$
加边，加边：$f_{n-2,m-4}(m-4)^2$
换边，换边：$f_{n-2,m-2}(m-2)(m-3+2)$ <=因为第一个换边会多 $2$ 条边
加边，换边：$f_{n-2,m-3}(m-3)(m-1)$
换边，加边：$f_{n-2,m-3}(m-3)(m-4)$
在 $n-2$ 个点的连通图上选一个点 $x$，连 $(x,1),(x,2),(1,2)$：$f_{n-2,m-3}(n-2)$

# include <bits/stdc++.h> 
using namespace std; 
using namespace IOS; 
using namespace std; 
typedef long long ll; 
# define int long long 
# define lc u << 1
# define rc u << 1 | 1 
const int N = 55, M = N * N, mod = 1e9 + 7; 

int n, m, K; 
int f[N][N]; 
int c[M][M]; 
void initC ()
{
	for (int i = 0; i < M; i ++ )
	{
		for (int j = 0; j <= i; j ++ )
		{
			if (!j) c[i][j] = 1; 
			else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod; 
		}
	}
}
int getndnum (int x) { return x * (x - 1) >> 1; }
signed main ()
{
	freopen ("count.in", "r", stdin); freopen ("count.out", "w", stdout); 
	read (n, m, K); 
	initC (); 
	for (int i = 1; i <= n; i ++ )
	{
		for (int j = 0; j <= K; j ++ )
		{
			f[i][j] = c[getndnum (i)][j]; 
			for (int k = 1; k < i; k ++ )
			{
				for (int l = 0; l <= j; l ++ )
					f[i][j] = (f[i][j] + mod - c[i - 1][k - 1] * f[k][l] % mod * c[getndnum (i - k)][j - l]) % mod;
			}
		}
	}
	if (!m) write (f[n][K], '\n'); 
	else if (m == 1)
	{
		int ans = 0; 
		// change one to two
		if (K >= 1) ans = (ans + f[n - 1][K - 1] * (K - 1) % mod) % mod;
		// add two 
		if (K >= 2) ans = (ans + f[n - 1][K - 2] * (K - 2) % mod) % mod;
		write (ans, '\n'); 
	}
	else if (m == 2)
	{
		int ans = 0; 
		// add add
		if (K >= 4) ans = (ans + f[n - 2][K - 4] * (K - 4) % mod * (K - 4)) % mod;
		// change change
		if (K >= 2) ans = (ans + f[n - 2][K - 2] * (K - 2) % mod * (K - 3 + 2)) % mod; 
		if (K >= 3) ans = (ans + f[n - 2][K - 3] * (K - 3) % mod * (K - 4 + K - 3 + 2)) % mod; 
		// chose x, connect (1,x), (2,x), (1,2)
		if (K >= 3) ans = (ans + f[n - 2][K - 3] * (n - 2) % mod) % mod;
		write (ans, '\n'); 
	}
	return 0;
}