2025-11-21 XQQ NOIP Round 1 hetao1733837的record

A.tree

提交链接：树

题面

题目描述

给定一棵 $n$ 个点的树和一个长度为 $n$ 的数组 $score[0],...,score[n-1]$。

你觉得这棵树不是很好看，所以你准备修一修这棵树，具体的说，你可以执行若干次以下操作:

• 选择任意一条边并删除，在产生的两个连通块保留一个并删除一个。

定义最后剩下的连通块 $S$ 的价值为 ${\sum }_{u\in S}score[de{g}_u]$ 其中 $de{g}_u$ 表示点 $u$ 的度数，你想要最大化这个价值，输出这个值。

输入格式

第一行一个正整数 $n$，表示节点个数。

第二行 $n$ 个整数 $score[0],score[1],...,score[n-1]$。

接下来 $n-1$ 行每行两个正整数 $x,y$，表示树上的一条无向边。

输出格式

一行一个整数表示答案。

4
10 1 2 3
1 2
1 3
2 4

10

5
0 1 5 1 1
1 2
1 3
1 4
1 5

7

5
-5 -1 1 1 1
1 2
1 3
3 4
3 5

0

数据范围

• 对于 20% 的数据 $n\le 20$.
• 对于 40% 的数据 $n\le 3000$.
• 对于 另外 20% 的数据, 树的形态是一条链.
• 对于 100% 的数据, $2\le n\le 200000$, $|score[i]|\le 10^9$

分析

显然，我们在场上注意到了一颗树（包含子树），删去一条边，会变成一颗子树+啊吧啊吧状物。由于多次修改，无法贪心 ，考虑树上$DP$。

设$f_i$表示$i$选择$i$这个子树里的一些点，同时钦定选$i$以及$i$与父亲节点连边的最大的分，则每次转移时一定会选择所有儿子中最大的几个$f_u$。

于是对于一个点$i$直接将他所有的儿子的$f_v$从大到小排序，然后更新$f_i$即可。
$$f_i=\max (sum{f}_k+scor{e}_{k+1})$$

正解

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200005;
int n, score[N], f[N];
vector<int> e[N];
int ans = 0xc0c0c0c0c0c0c0c0;
void dfs(int u, int fa){
	f[u] = 0xc0c0c0c0c0c0c0c0;
	deque<int> son;
	for (auto v : e[u]){
		if (v == fa)
			continue;
		dfs(v, u);
		son.push_back(f[v]);
	}
	sort(son.begin(), son.end(), greater<int>());
	for (int i = 1; i < son.size(); i++)
		son[i] += son[i - 1];
	son.push_front(0);
	for (int i = 0; i < son.size(); i++){
		ans = max(ans, son[i] + score[i]);
	}
	if (fa){
		for (int i = 0; i < son.size(); i++){
			f[u] = max(f[u], son[i] + score[i + 1]);
		}
	}
}
signed main(){
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> score[i];
	}
	for (int i = 1; i < n; i++){
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1, 0);
	cout << ans;
}

B.card

提交链接：牌

题面

题目描述

有 $n$ 张牌，第 $i$ 张牌正面写着 $a_i$，反面写着 $b_i$。从这 $n$ 张牌中选出若干张，使得他们正面的数的异或和乘以反面的数的异或和的结果最大。牌不能翻面。

输入格式

第一行一个正整数 $T$, 表示测试数据组数。

每组测试数据第一行一个正整数 $n$。

第二行 $n$ 个正整数 $a_i$。

第三行 $n$ 个正整数 $b_i$。

输出格式

每组数据输出一行一个整数, 表示答案。

1
6
1 1 4 5 1 4
19 1 9 8 1 0

130

2
2
1 2
2 1
5
1 2 3 4 5
5 4 5 3 5

9
42

数据范围

• 对于 15% 的数据 $n\le 20$
• 对于 30% 的数据 $n\le 2000,a_i,b_i<2^{10}$
• 对于 60% 的数据, $a_i,b_i<2^{10}$
• 对于另外 10% 的数据 $a_i<2$.
• 对于 100% 的数据, $1\le n\le 10^5,0\le a_i,b_i<2^{20},T\le 5$

分析

难道贪心的选择使得每一个二进制位都有奇数次重合？一看线性基，小蛐蛐，我***！好的，我们拿一下部分分——爆搜！

15pts

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100005;
int a[N], b[N], n;
int ans = 0xc0c0c0c0;
void dfs(int p, int z, int f){
    if (p > n){
        ans = max(ans, z * f);
        return ;
    }
    dfs(p + 1, z, f);
    dfs(p + 1, z ^ a[p], f ^ b[p]);
}
signed main(){
    freopen("card.in", "r", stdin);
    freopen("card.out", "w", stdout);
    int T;
    cin >> T;
    while (T--){
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        for (int i = 1; i <= n; i++)
            cin >> b[i];
        ans = 0;
        dfs(0, 0, 0);
        cout << ans << '\n';
    }
}

看看满分做法能不能看懂吧……

呃……线性基是个……呃……通俗来说，就是用基底表示$n$维空间的东西……mhh认为应该是对的。

这题有异或相关，所以，自然而然地想到线性基（线性基用于维护异或相关……）。

好的，那么，我编不下去了，直接把题解拿下来。

发现值域不大，我们对于所有$a_i$建立一个线性基，在建立的时候，如果一个$a_i$成功被插入到了这个线性基中，我们记录此时对应的$b_i$。否则，如果$a_i$可以通过线性基里已有的若干个数异或起来表示，同时，也满足$a_i$与这些数异或起来等于$0$，把此时$b_i$还剩下的值$b^{\prime }$（在$a_i$插入过程中，$a_i$会在线性基中疯狂异或，同时$b_i$也会疯狂异或记录的$b$，最后会剩下一个$b^{\prime }$）插入到另一个线性基中。

插入完成，我们枚举选出若干个牌之后正面的异或值$X$，然后判断 $X$是否能被 若干个$a_i$合并，若能，此时会有一个对应的反面的异或和$Y$，是一组合法的特解。但是$Y$不一定是最大的，枚举第二个线性基 ，查询$Y$异或上若干个$b^{\prime }$的最大值。

复杂度$O((n+V)logV)$

正解

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100005, D = 40;
int n, a[N], b[N];
int T;
struct _bas1{
	int p[D], q[D];
	int insert(int u, int v){
		for (int i = 20; i >= 0; i--){
			if ((u >> i) & 1){
				if (p[i]){
					u ^= p[i];
					v ^= q[i];
				}
				else{
					p[i] = u;
					q[i] = v;
					return 0;
				}
			}
		}
		return v;
	}
	int query(int x){
		int res = 0;
		for (int i = 20; i >= 0; i--){
			if ((x >> i) & 1){
				if (!p[i])
					return -1;
				x ^= p[i];
				res ^= q[i];
			}
		}
		return res;
	}
	void clear(){
		fill(p, p + D, 0ll);
		fill(q, q + D, 0ll);
	}
}b1;
struct _bas2{
	int p[D];
	void insert(int x){
		for (int i = 20; i >= 0; i--){
			if ((x >> i) & 1){
				if (p[i]){
					x ^= p[i];
				}
				else{
					return p[i] = x, void();
				}
			}
			if (!x)
				return ;
		}
	}
	int querymx(int x){
		for (int i = 20; i >= 0; i--){
			if ((x ^ p[i]) >= x){
				x ^= p[i];
			}
		}
		return x;
	}
	void clear(){
		fill(p, p + D, 0ll);
	}
}b2;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	freopen("card.in", "r", stdin);
	freopen("card.out", "w", stdout);
	cin >> T;
	while (T--){
		b1.clear();
		b2.clear();
		cin >> n;
		for (int i = 1; i <= n; i++)
			cin >> a[i];
		for (int i = 1; i <= n; i++)
			cin >> b[i];
		for (int i = 1; i <= n; i++){
			int res = b1.insert(a[i], b[i]);
			if (res)
				b2.insert(res);
		}
		int ans = 0;
		for (int i = 0; i < (1ll << 20); i++){
			int res = b1.query(i);
			if (res == -1)
				continue;
			ans = max(ans, b2.querymx(res) * i);
		}
		cout << ans << '\n';
	}
}

C.coin

提交链接：币

题面

题目描述

小 D 非常无聊，所以他开始记录自己掷硬币的结果。

如果硬币的正面朝上就在纸上写下一个 $1$，反面朝上就写下一个 $0$，将写下的数看成一个字符串，如果这个 $01$ 字符串的末尾 $n$ 个字符组成的子串正好是 $S_1$，那么小 $D$ 就会停下。

我们认为掷硬币的结果是一个独立的随机事件，正面朝上和反面朝上概率均为 $1/2$。

现在小 $D$ 已经投掷了 $m$ 次硬币，并以字符串的形式给出了这 $m$ 次投掷的结果 $S_2$，你想要知道，他期望再投掷多少次会停下。

为了避免精度误差，你只需要输出答案对 $10^9+7$ 取模的结果。

注意，如果在前 $m$ 次投掷的某次末尾的 $n$ 个字符已经组成 $S_1$，那么你应该输出 $0$。

输入格式

第一行一个正整数 $T$，表示测试数据组数。

每组测试数据包含两行，第一行一个整数 $n$ 和一个字符串 $S_1^{\prime }$。

第二行一个整数 $m$ 和一个字符串 $S_2^{\prime }$

原始的 $S_1$ 和 $S_2$ 需要从 $S_1^{\prime }$ 和 $S_2^{\prime }$ 解出。

加密串包含 ‘a’-‘z’(分别代表 0 - 25)，和 ‘A’-‘F’(分别代表 26 - 31)，将加密串的每个字符替换成对应数组的五位二进制数，比如 “An” 替换之后为 “1101001101”。替换之后取前 $n$ ($m$)个字符作为原始的 $S_1$ ($S_2$).

输出格式

对于每组数据，输出一行一个整数，表示答案。

3
1 a
0 a
3 a
2 a
8 An
3 B

2
8
254

3
10 rayisgay
13 gayisray
20 asdfjissjs
13 difisjfsdd
12 fdddddfdf
13 ddodododo

1020
1048512
4102

数据范围与提示

• 对于 20% 的数据 $n\le 3$
• 对于 30% 的数据, $n\le 10$
• 对于 50% 的数据, $n\le 100$
• 对于 70% 的数据, $n\le 2000$
• 对于 90% 的数据, $n\le 10^5$
• 对于 100% 的数据, $T\le 10,1\le |S_1^{\prime }|,|S_2^{\prime }|\le 200000,1\le n\le 5\times |S_1^{\prime }|,0\le m\le 5\times |S_2^{\prime }|,1\le \sum |S_1^{\prime }|,\sum |S_2^{\prime }|\le 10^6$

分析

法一

猜到的$KMP$。艹，你们AC自动机考爽了？还在出？尝试一下。匹配完成了$j$个字符，要匹配第$j+1$个字符时有两种情况：

$s_{j+1}=t_i$，状态从$j\to j+1$转移

$s_{j+1}\ne t_i$，状态从$j\to fai{l}_j$

这个题上，我们每次概率生成$0$或$1$，然后：

如果这次生成的和之前生成的一样，那么状态从$i\to i+1$，否则，状态$i\to fai{l}_i$

设$f_i$表示要走到$i+1$得到期望步数 ，有：
$$f_i=1+\frac{1}{2}\sum _{j=fai{l}_i}^i{f}_j$$
将 右侧的$f_i$移到左侧 ，前缀和优化转移即可。

正解

#include <bits/stdc++.h>
#define int long long
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
using namespace std;
const int N = 1000005, mod = 1e9 + 7, inv2 = (mod + 1) / 2;
int fplus(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }
void Fplus(int &x, int y) { x = fplus(x, y); }
int fminus(int x, int y) { return x - y < 0 ? x + mod - y : x - y; }
void Fminus(int &x, int y) { x = fminus(x, y); }
int n, m, s[N], t[N], nxt[N], tr[N][2], f[N];
char ch[N];
void input(int *a) {
    scanf("%s", ch);
    int len = strlen(ch);
    rep(i, 0, len - 1) {
        int c = ch[i] >= 'a' && ch[i] <= 'z' ? ch[i] - 'a' : ch[i] - 'A' + 26;
        rep(j, 1, 5) a[i * 5 + j] = c >> (5 - j) & 1;
    }
}
bool Med;
int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar();
    }
    return x * f;
}
signed main() {
    freopen("coin.in", "r", stdin);
    freopen("coin.out", "w", stdout);
    fprintf(stderr, "%3lfMb\n", (&Med - &Med) / 1024. / 1024.);
    for (int T = read(); T--;) {
        n = read(), input(s);
        m = read(), input(t);
        for (int i = 2, j = 0; i <= n; i++) {
            while (j && s[j + 1] != s[i])
                j = nxt[j];
            nxt[i] = j += s[j + 1] == s[i];
        }
        rep(i, 0, n - 1) {
            rep(j, 0, 1) {
                if (s[i + 1] == j)
                    tr[i][j] = i + 1;
                else
                    tr[i][j] = i ? tr[nxt[i]][j] : 0;
            }
        }
        int cur = 0;
        rep(i, 1, m) {
            cur = tr[cur][t[i]];
            if (cur == n)
                break;
        }
        if (cur == n) {
            printf("0\n");
            continue;
        }
        f[0] = 2;
        rep(i, 1, n - 1) {
            int j = tr[i][0] ^ tr[i][1] ^ (i + 1);
            f[i] = fplus(2, fminus(f[i - 1], j ? f[j - 1] : 0));
            Fplus(f[i], f[i - 1]);
        }
        printf("%d\n", fminus(f[n - 1], cur ? f[cur - 1] : 0));
    }
    return 0;
}

何意味啊，我们看法二。

法二

期望是$\sum _{i\in border(S)}{2}^i$。设$f_i$表示生成前$i$个字符所需要的期望次数，有：
$$f_i=\sum _{j\in border(S)}{2}^j=f_{fail(i)}+2^i$$
由于期望线性性，最终答案$f_n-f_{ex}$，$ex$是$s2$最长后缀满足是$s1$的前缀。

代码

#include <bits/stdc++.h>
using namespace std;

// Options Start

// #define NETWORK_FLOW
// #define SEGMENT_TREE
#define FILE_IO
#define MULTI_TESTS

// Options End
#ifdef LOCAL_TEST
bool __mem_begin;
#endif
#define int long long
#define mid ((l + r) >> 1)
#ifndef LOCAL_TEST
#define endl '\n'
#endif
#ifdef SEGMENT_TREE
#define lson (p << 1)
#define rson (p << 1 | 1)
#endif
#ifdef NETWORK_FLOW
#define rev(p) (p ^ 1)
#endif

const int mod = 1e9 + 7;

int quickpow(int a, int b) {
	int ret = 1;
	while (b) {
		if (b & 1) ret = ret * a % mod;
		a = a * a % mod; b >>= 1;
	}
	return ret;
}



void work() {
	string s1, s2;
	int n, m;
	cin >> n >> s1;
	cin >> m >> s2;
	vector<int> a, b;
	a.push_back(-1);
	for (int i = 0; i < (int)s1.size(); ++i) {
		int x = 0;
		if (islower(s1[i])) x = s1[i] - 'a';
		else x = s1[i] - 'A' + 26;
		for (int j = 4; j >= 0; --j) {
			if (x >> j & 1) a.push_back(1);
			else a.push_back(0);
		}
	}
	a.erase(a.begin() + n + 1, a.end());
	b.push_back(-1);
	for (int i = 0; i < (int)s2.size(); ++i) {
		int x = 0;
		if (islower(s2[i])) x = s2[i] - 'a';
		else x = s2[i] - 'A' + 26;
		for (int j = 4; j >= 0; --j) {
			if (x >> j & 1) b.push_back(1);
			else b.push_back(0);
		}
	}
	b.erase(b.begin() + m + 1, b.end());

	// cout << "a=" << a.size() << endl;
	// for (auto x:a)
	// 	cout << x << ' ';
	// cout << endl;
	// cout << "b=" << b.size() << endl;
	// for (auto x:b)
	// 	cout << x << ' ';
	// cout << endl;

	vector<int> fail(n + 1), f(n + 1);
	int j = 0;
	for (int i = 2; i <= n; ++i) {
		while (j && a[j + 1] != a[i]) j = fail[j];
		if (a[j + 1] == a[i]) j++;
		fail[i] = j;
	}
	j = 0;
	for (int i = 1; i <= m; ++i) {
		while (j && a[j + 1] != b[i]) j = fail[j];
		if (a[j + 1] == b[i]) ++j;
		if (j >= n) return cout << 0 << endl, void();
	}
	// cout << "f=" << endl;
	for (int i = 1; i <= n; ++i) {
		f[i] = (f[fail[i]] + quickpow(2, i)) % mod;
		// cout << f[i] << ' ';
	}
	// cout << endl;
	vector<int> c, failc;
	c.push_back(-1);
	c.insert(c.end(), a.begin() + 1, a.end());
	c.push_back('#');
	c.insert(c.end(), b.begin() + 1, b.end());
	failc.resize(c.size());
	j = 0;
	for (int i = 2; i < (int)c.size(); ++i) {
		while (j && c[j + 1] != c[i]) j = failc[j];
		if (c[j + 1] == c[i]) j++;
		failc[i] = j;
	}
	int ex = failc.back();
	ex = min(ex, n);
	// cout << "ex=" << ex << endl;
	cout << (f[n] - f[ex] + mod) % mod << endl;
}

#ifdef LOCAL_TEST
bool __mem_end;
#endif

signed main(void) {
#ifdef FILE_IO
#ifndef LOCAL_TEST
	freopen("coin.in", "r", stdin);
	freopen("coin.out", "w", stdout);
#endif
#endif
	ios::sync_with_stdio(false); cin.tie(NULL);
	srand(time(nullptr));
#ifdef MULTI_TESTS
	int T = 1; cin >> T; T--;
	while (T--) work();
#endif
	work();
	return 0;
}

D.hole

原题链接：洞

分析