【CSP-S2019】D1T1 格雷码 D1T2 括号树 题解

CSP-S2019 D1T1 格雷码

题目

题目描述

通常，人们习惯将所有 $n$ 位二进制串按照字典序排列，例如所有 $2$ 位二进制串按字典序从小到大排列为：$00$，$01$，$11$，$10$。

格雷码（Gray Code）是一种特殊的 $n$ 位二进制串排列法，它要求相邻的两个二进制串间恰好有一位不同，特别地，第一个串与最后一个串也算作相邻。

所有 2 位二进制串按格雷码排列的一个例子为：$00$，$01$，$11$，$10$。

$n$ 位格雷码不止一种，下面给出其中一种格雷码的生成算法：

1. 1 位格雷码由两个 $1$ 位二进制串组成，顺序为：$0$，$1$。
2. $n+1$ 位格雷码的前 $2^n$ 个二进制串，可以由依此算法生成的 $n$ 位格雷码（总共 $2^n$ 个 $n$ 位二进制串）按顺序排列，再在每个串前加一个前缀 $0$ 构成。
3. $n+1$ 位格雷码的后 $2^n$ 个二进制串，可以由依此算法生成的 $n$ 位格雷码（总共 $2^n$ 个 $n$ 位二进制串）按逆序排列，再在每个串前加一个前缀 $1$ 构成。

综上，$n+1$ 位格雷码，由 nnn 位格雷码的 $2^n$ 个二进制串按顺序排列再加前缀 $0$，和按逆序排列再加前缀 $1$ 构成，共 $2^{n+1}$ 个二进制串。另外，对于 $n$ 位格雷码中的 $2^n$ 个 二进制串，我们按上述算法得到的排列顺序将它们从 $0?2^n?1$ 编号。

按该算法，$2$ 位格雷码可以这样推出：

1. 已知 1 位格雷码为 $0$，$1$。
2. 前两个格雷码为 $00$，$01$。后两个格雷码为 $11$，$10$。合并得到 $00$，$01$，$11$，$10$，编号依次为 $0?3$。

同理，$3$ 位格雷码可以这样推出：

1. 已知 $2$ 位格雷码为：$00$，$01$，$11$，$10$。
2. 前四个格雷码为：$000$，$001$，$011$，$010$。后四个格雷码为：$110$，$111$，$101$，$100$。合并得到：$000$，$001$，$011$，$010$，$110$，$111$，$101$，$100$，编号依次为 $0?7$。

现在给出 $n$，$k$，请你求出按上述算法生成的 $n$ 位格雷码中的 $k$ 号二进制串。

分析

简单列出 $n\le 4$ 的情况就可以发现，对于第 $k$ 个串，去掉它的最后一位就和 $n?1$ 的第 $?\frac{k}{2}?$ 位上的串一样了，且不难发现最后一位成 $0$ ， $1$ ， $1$ ， $0$ 循环，于是直接递归处理。

注意题目数据要求开 unsigned long long。

参考代码

#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;typedef unsigned long long ull;int N;
ull K;
string s;void DFS(int t, ull k) {
    if(t == 0) return;DFS(t - 1, k / 2);if(k % 4 == 2 || k % 4 == 1) s += '1';else s += '0';
}int main() {
    
// freopen("code.in", "r", stdin);
// freopen("code.out", "w", stdout);cin >> N >> K;DFS(N, K);cout << s << endl;return 0;
}

D1T2 括号树

题目

题目描述

小 Q 是一个充满好奇心的小朋友，有一天他在上学的路上碰见了一个大小为 $n$ 的树，树上结点从 $1?n$ 编号，$1$ 号结点为树的根。除 $1$ 号结点外，每个结点有一个父亲结点，$u$（$2\le u\le n$）号结点的父亲为 $f_u$?（$1\le f_u<u$）号结点。

小 Q 发现这个树的每个结点上恰有一个括号，可能是( 或)。小 Q 定义 $s_i$? 为：将根结点到 $i$ 号结点的简单路径上的括号，按结点经过顺序依次排列组成的字符串。

显然 $s_i$? 是个括号串，但不一定是合法括号串，因此现在小 Q 想对所有的 $i$（$1\le i\le n$）求出，$s_i$? 中有多少个互不相同的子串是合法括号串。

这个问题难倒了小 Q，他只好向你求助。设 $s_i$? 共有 $k_i$? 个不同子串是合法括号串， 你只需要告诉小 Q 所有 $i\times k_i$? 的异或和，即：

$$(1\times k_1)?(2\times k_2)?(3\times k_3)???(n\times k_n)$$

其中 $?$ 是位异或运算。

分析

就不讲我考场上怎么做的吧，要看的话直接去我的爆炸记里面看就可以了。。。

令 $g_u$ 为从节点 $1$ 到节点 $f{a}_u$ 的路径上的括号序列中，加入 $u$ 的括号后新增加的合法匹配的括号序列的数量。

则节点 $u$ 的答案为从根到 $u$ 的路径上的 $g$ 之和。

考虑怎么转移这个东西。

我们用一个栈来记录左括号的位置。

则对于一个节点，我们分两种情况来讨论：

• 若当前节点是左括号：将这个节点塞进栈里，显然没有新增合法括号匹配，令 $g_u=0$ 即可；
• 若当前节点是右括号，我们再分两种情况讨论：
  • 若当前栈是空的，则这个节点上也没有新增合法括号匹配，令 $g_u=0$ 即可；
  • 否则取出栈顶 $t$，不难发现节点 $u$ 可以和 $t$ 匹配增加一个合法的括号匹配，此时我们应令 $g_u=g_t+1$ 。

注意在向下递归完后要恢复现场。 不要学我开 $N$ 个栈。。。

参考代码

#include <stack>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;typedef long long ll;
const int Maxn = 5e5;int N;
char s[Maxn + 5];
vector<int> G[Maxn + 5];
void addedge(int u, int v) {
    G[u].push_back(v), G[v].push_back(u);
}stack<int> stk;
ll f[Maxn + 5], g[Maxn + 5];
int fa[Maxn + 5];
void DFS(int u, int pre) {
    int tp = -1;if(s[u] == '(') stk.push(u);else {
    if(!stk.empty()) {
    tp = stk.top();g[u] = g[fa[tp]] + 1;stk.pop();}}f[u] = f[fa[u]] + g[u];for(int i = 0; i < (int)G[u].size(); i++) {
    int v = G[u][i];if(v == pre) continue;DFS(v, u);}if(tp != -1) stk.push(tp);else if(!stk.empty()) stk.pop();
}int main() {
    
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifscanf("%d", &N);scanf("%s", s + 1);for(int i = 2; i <= N; i++) {
    scanf("%d", &fa[i]);addedge(fa[i], i);}DFS(1, 0);ll ans = 0;for(int i = 1; i <= N; i++)ans ^= (1LL * i * f[i]);printf("%lld\n", ans);return 0;
}