CSP-S2019兴奋不已

Day 1

T1 格雷码

题目大意

  According to the rules of gray code generation $n$ For the arrangement of binary,And the output Numbers for $k$ The arrangement of.

  $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 构成.

  按该算法,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.

分析

  We according to the rules can be found,$n$ For binary gray code number is from $0\sim 2^n-1$,And for the first number $i$ 和编号 $2^n-i$ For two binary stringsIn addition to the highest instead,The rest of the position is the same.

  然后我们又可以发现.If written the subscript $n$ Bit binary number,就像这样：

1. 0(0), 1(1)
2. 00(00), 01(01), 11(10), 10(11)
3. 000(000),001(001),011(010),010(011),110(100),111(101),101(110),100(111)
   $⋮$

  We can find Numbers meet “For the first number $i$ 和编号 $i+2^{n-1}$ For two binary stringsIn addition to the highest instead,The rest of the position is the same” 的规律,So we consider to find a relationship number and find the answer.

  To observe we can find that,Because this is arranged rules first half has $2^n$ 个,In the second part has $2^n$ 个,So if the number $k$ 的某一位是 $1$,Also means that when the answer from the front structure has undergone a reverse.So we consider：

  对于一个 $k$,把它写成 $n$ 位二进制串,每遇到一个 “$1$”,We put back all of the string of reverse again,也就是 $0$ 变成 $1$,$1$ 变成 $0$,Is the exclusive or on a fully $1$ 串.Doing so is equivalent to begin with the string of existing in turn back to the original string back.这就是一个 $O(\log n)$ 的做法了,Apparently can drop this topic,But we can still continue to optimize this algorithm.

  We don't consider meet a $1$ Reverse again,Twenty to each number in a reverse mark.

  We consider the reverse tag have any rule,很明显的,Is divided into four：

1. 当前数为 $0$ 且 $rev\_tag=0$,It means that the current the figures have not been reversed,It also doesn't have to be behind the reversed,So it under a $re{v}_{t}ag$ 也就等于 $0$.
2. 当前数为 $0$ 且 $rev\_tag=1$,It means that the current number is reversed into $1$,同理,He also need not reverse behind（Because of the need to turn twice is equivalent to not）,So it the next digit $rev\_tag=0$.
3. 当前数为 $1$ 且 $rev\_tag=0$,It means that the current meaning has not been reversed,So he is going to be behind $1$ 反转一次,Is it under a $rev\_tag=1$.
4. 当前数为 $1$ 且 $rev\_tag=1$,That means the current number to be reversed into $0$,It means that the back of the number will be reversed once,So he under a $rev\_tag$ 还是 $1$.

  To write out all cases can be found,$rev\_tag$ The value of the just and on a $k$ 的值是一样的,而且 $k$ Direct vision or on $re{v}_{t}ag$ 就是答案,所以答案就是 $k\oplus (k>>1)$.Then find out the answer becomes $O(1)$ 的了 Although the output is still log 的.

代码

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long

int n = 0; int k = 0;

int main(){
    
	cin >> n >> k;
	k ^= k >> 1;
	while(~--n) cout << (k >> n & 1);
	return 0;
}

T2 括号树

题目大意

  题目太长了,To sum up,Put a portal：CSP-S2019 Day1 T2

分析

  Obviously from the root down $dfs$,Each of us to a new point will be added to a character,You now have two things：

1. Add character is left parenthesis,Obviously this will not have any effect on the answer,No matter directly.
2. Add character is right parenthesis,We consider this bracket contribution to answer.First of all, the right parenthesis matching to the left parenthesis is certainly the only,And it has formed a tuo legal list（From the right end to the left somewhere）.We assume that the added right parenthesis matching to the left parenthesis subscript as $i$,So if you want to and the tuo legal strings of string of words on the left side of the new legal legal at the end of the string must be $i-1$,So you can fight together to form a new bunch of.So the new added the right parenthesis produced the answer is $1+nu{m}_{i-1}$,其中 $nu{m}_{i-1}$ 是以 $i-1$ At the end of the string of legal string number.That is a new house in the position of the right parenthesis is $j$,那么 $nu{m}_j=nu{m}_{i-1}+1$.

  So the problem becomes very simple.

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in read()
#define MAXN 500500
#define MAXM MAXN << 2

inline int read(){
    
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
    
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int n = 0; int tot = 0;
int first[MAXN] = {
     0 };
int   nxt[MAXM] = {
     0 };
int    to[MAXM] = {
     0 };
int value[MAXN] = {
     0 };
inline void add(int x, int y){
    
	nxt[++tot] = first[x];
	first[x] = tot; to[tot] = y;
}

int top = 0, temp = 0, ans = 0;
int stk[MAXN] = {
     0 };
int num[MAXN] = {
     0 };
int lst[MAXN] = {
     0 };                                                // On a right parenthesis can match to the
void dfs(int x){
    
	stk[++top] = value[x];
	if(value[x] == 0){
    
		int p = top - 1;
		if(lst[p] != -1) p = lst[p] - 1;                              // 如果 p 不是左括号
		if(p != 0 and stk[p] == 1){
                                       // Alive and are left parenthesis(能匹配上)
			num[top] = 1;
			if(p != 1 and lst[p - 1] != -1)                           // Not the first and one is not left parenthesis before
				lst[top] = lst[p - 1],
				num[top] += num[p - 1];
			else lst[top] = p;                                        // 否则就是第一个
			temp += num[top];
		}
		else lst[top] = -1, num[top] = 0;                             // 是左括号
	}
	else lst[top] = -1, num[top] = 0;
	ans = ans ^ (x * temp);
	for(int e = first[x]; e; e = nxt[e])
		dfs(to[e]);
	temp -= num[top], top--;
}

signed main(){
    
	n = in; char c;
	for(int i = 1; i <= n; i++){
    
		c = getchar();
		while(c != '(' and c != ')') c = getchar();
		if(c == '(') value[i] = 1;
		else value[i] = 0;
	}
	for(int i = 1; i < n; i++){
    
		int y = in;
		add(y, i + 1);
	} dfs(1);
	cout << ans << '\n';
	return 0;
}

T3 树上的数

  The first black offering qwq.

题目大意

  To a $n$ 个节点的树,Each node has two values,一个编号,一个数字.And the number and the Numbers are belong to $[1,n]$ And each number only appear once.

  现在有 $n-1$ 个操作,The edge of every time delete a tree,同时,This side connecting the two points to exchange Numbers.After all the operation,把所有节点取出来,And then sorted by digital,Form a node sequence.Then put the serial number of all points out to form an array.

  Now order minimum requirements by changing the sequence of operation to find the dictionary array,并输出.

分析

  Because to make the dictionary minimum order,So we consider the greedy.First, let digital $1$ As far as possible to a small number,Digital again $2$ To meet the Numbers $1$ On the premise of minimum on the minimum number of,以此类推.

  We now consider the delete order will give the answer on the side of the impact.我们考虑一个点 $x$,It even to other many other points $y_i$,Made by $y_i$ The collection of as $Y$.We now if you delete an edge $e=(x,y_i),y_i\in Y$,Then the point in the middle of the $x$ 就会和 $y_i$ 交换,此时,其他的点 $y_j\in Y$ They could no longer get $x$ 这个点了.

  还有一种特殊情况,We considered the last delete the edge $e=(x,y_i),y_i\in Y$,那么最终 $x$,Original position will become $y_i$,Other points can't be $x$ The position of the original.

  In addition of natural is neither the first nor the last delete the edge.

  So we consider the boundary is divided into three kinds of：

1. The first delete called out while,Effect will be sent out $x$.
2. Delete the last of side to accept the side,Effect is to accept $y_i$.
3. The middle edge become transshipment will delete,Effect is transfer $a$.

  Which in the process of transshipment may delete sequence has a certain requirement on the side of,If we're going to chain to connect three points $x,y,z$ 中的一个端点 $x$ Send to another endpoint $z$ .Then it must be first delete $e_1=(x,y)$,And then immediately delete $e_2=(y,z)$.We call this deleted $e_1$ We will delete $e_2$ The constraint conditions with symbol $e_1\to e_2$ 表示.

  We want to consider a greedy（尝试把 $x$ 移动到 $y$）,We will put the path into three process：

1. 把 $x$ 送出去
2. 中转
3. $y$ 接收 $x$

  We now consider this three parts request to.

  首先是把 $x$ 送出去,In front of the description of what we already know,If you want to send $x$ You must see to it that $Path(x\to y)$ 上的与 $x$ Connect the edge $e_1$ Is the first to be deleted（It is be out side）.同理,$Path(x\to y)$ 中与 $y$ 相连的边 $e_2$ Must be accept the edge,To the last delete,Transshipment en route and some $e_i\to e_j$ 的条件.

  So we consider a partial order maintenance chain（Maintain a point delete edge order）To maintain these constraints.

  So we just need to know from $x\to y$ Can successfully to meet the following conditions are not set up.

1. 送出：
   a. The first position has been occupied.
   b. $e_1$ Have been unable to put into the first place.
   c. 放完 $e_1$ Formed after the end of the chain of partial order,And there are side didn't put it in.
2. 接收：
   a. The last position has been occupied.
   b. $e_2$ Have been unable to put in the last place.
   c. 放完 $e_2$ Formed after the end of the chain of partial order,And there are side didn't put it in.
3. 中转：
   a. 条件 $e_i\to e_j$ With previous partial order chain appears contradiction.
   c. 放完 $e_i$ Formed after the end of the chain of partial order,There is still a side and put it in.

  这样一来,We since the childhood enumeration number $x$,Since the enumeration number $i$,判断能否将 $x$ The node to $i$ 的节点.So according to our above methods to judge,Then the complexity of the judgment is $O(n)$ 的了,So the overall complexity is $O(n^3)$.

  But we can optimize the practice,Because join two judgment whether to point $nod{e}_1$ 和 $nod{e}_2$ 满足 $dep[lca(nod{e}_1,nod{e}_2)]<dep[x]$,Then illustrate two go path has repeated.And that a repeat clearly only judge a good.

  所以我们考虑,Every time we from digital $x$ 开始,直接 $dfs$ 一遍,在 $dfs$ Each point is determined by the way, when will be the receiver（Including this can become a transit point between two points）.And then find the smallest can reach.For each number, we will only use $O(n)$ 了,总的复杂度就是 $O(n^2)$了.

代码

#include<bits/stdc++.h>
using namespace std;
#define in read()
#define MAXN 2020
#define MAXM MAXN << 2

inline int read(){
    
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
    
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int T = 0;
int n = 0; int tot = 0;
int first[MAXN] = {
     0 };
int   nxt[MAXM] = {
     0 };
int    to[MAXM] = {
     0 };
inline void add(int x, int y){
    
	nxt[++tot] = first[x];
	first[x] = tot; to[tot] = y;
}

int p[MAXN] = {
     0 };                                         // p[idx] = val
int d[MAXN] = {
     0 };                                         // i There are many side didn't walk
int d1[MAXN] = {
     0 };                                        // i Article on how much the edge is a number came in only one
int d2[MAXN] = {
     0 };                                        // i Article on how much the edge is only a number to come out again
int fa[MAXN] = {
     0 };                                        // i 的父亲
int from[MAXN] = {
     0 };                                      // i Where the points on the shipped
int ttoo[MAXN] = {
     0 };                                      // i Was moved to the point where
int st[MAXN][MAXN] = {
     0 };                                  // 对于节点 i 来说 (i, j) As at the beginning of the current partial order chain node
int en[MAXN][MAXN] = {
     0 };                                  // 对于节点 i 来说 (i, j) For the current partial order at the end of the chain node
int edge[MAXN][MAXN] = {
     0 };                                // -1 : (i, j) Not been through; i : (i, j) There is only one number from i 到 j 经过了一次; j : There is only one number from j 到 i 经过一次; 0 : 其他情况
int flag[MAXN] = {
     0 };                                      // 是否可行

inline void init(){
    
	tot = 0;
	for(int i = 1; i <= n; i++)
		d[i] = d1[i] = d2[i] = 0,
		first[i] = from[i] = ttoo[i] = 0;
}

void dfs(int x, int root){
    
	for(int e = first[x]; e; e = nxt[e]){
    
		int y = to[e];
		if(y == fa[x]) continue;
		fa[y] = x, flag[y] = 1;
		if(x != root){
    
			if(edge[fa[x]][x] == fa[x] or edge[x][y] == x) flag[y] = 0;
			if(edge[fa[x]][x] == 0 or edge[x][y] == 0) flag[y] = 0;
			if(en[x][y] == from[x] and st[x][fa[x]] == ttoo[x] and d2[x] + d1[x] + d[x] * 2 - 2 > 0) flag[y] = 0;
			if(en[x][y] == fa[x]) flag[y] = 0;
		}
		else{
    
			if(edge[x][y] == x) flag[y] = 0;
			if(edge[x][y] == 0) flag[y] = 0;
			if(flag[x])
				if(en[x][y] == from[x] and d[x] + d1[x] + d2[x] - 1 != 0) flag[y] = 0;
		}
		flag[y] &= flag[x];
		dfs(y, root);
	}
	if(x == root) flag[x] = 0;
	else{
    
		if(from[x]) flag[x] = 0;
		if(ttoo[x])
			if(en[x][ttoo[x]] == fa[x] and d[x] + d1[x] + d2[x] - 1 != 0) flag[x] = 0;
	}
}

int main(){
    
	freopen("a.in", "r", stdin);
	T = in;
	while(T--){
    
		n = in; init();
		for(int i = 1; i <= n; i++) p[i] = in;
		for(int i = 1; i < n; i++){
    
			int x = in, y = in;
			add(x, y), add(y, x);
			d[x]++, d[y]++;
			edge[x][y] = edge[y][x] = -1;
			st[x][y] = en[x][y] = y;
			st[y][x] = en[y][x] = x;
		}
		for(int i = 1; i <= n; i++){
    
			for(int j = 1; j <= n; j++) fa[j] = 0;
			flag[p[i]] = 1;
			dfs(p[i], p[i]);
			int res = 0;
			for(int j = 1; j <= n; j++)
				if(flag[j]) {
     res = j; break; }
			cout << res << ' ';
			from[res] = fa[res];
			while(fa[res] != p[i]){
    
				if(edge[fa[res]][res] == -1){
    
					edge[fa[res]][res] = edge[res][fa[res]] = fa[res];
					d[res]--, d2[res]++;
					d[fa[res]]--, d1[fa[res]]++;
				}
				else{
    
					edge[fa[res]][res] = edge[res][fa[res]] = 0;
					d1[res]--, d2[fa[res]]--;
				}
				int t = res;
				res = fa[res];
				st[res][en[res][t]] = st[res][fa[res]];
				en[res][st[res][fa[res]]] = en[res][t];
			}
			if(edge[fa[res]][res] == -1){
    
				edge[fa[res]][res] = edge[res][fa[res]] = fa[res];
				d[res]--, d2[res]++;
				d[p[i]]--, d1[p[i]]++;
			}
			else{
    
				edge[fa[res]][res] = edge[res][fa[res]] = 0;
				d1[res]--, d2[p[i]]--;
			}
			ttoo[p[i]] = res;
		}
		puts("");
	}
	return 0;
}

  完结撒花！！！