4/10上午考试

4/10上午考试

四月 10, 2022
T1

来源：不知道

题意：

　　两个人玩 ♂ 游戏，对于第 $i$ 次会在以 $i$ 为根的子树内两人分别选择一个点（不可重复）设为 $x , y$ ，得分为 $w_x \oplus w_y​$。A 要求最小化得分，B 要求最大化得分，在两人都秃头绝顶聪明的情况下，求出每次游戏的得分。

题解：

　　如果只算一颗子树，考虑异或的性质，高位肯定比低位优，可以把用一颗 Trie 树表示出这棵子树内的所有数字并在 Trie 上进行 DP，对于 Trie 上一个点 ，如果它的子树里面总共只表示了一个数字（重复算两个）则答案为 -1 。

如果它的左子树或者右子树中只有一个数字，那么只要A走进这个只有一个数字的子树 B 就必须走另一个，这时的对答案的贡献最大，否则这个点的答案就是左右子树的答案中较大的，因为如果 A 选择走进答案较大的子树 B 就要跟进去。
如果要计算多个子树的答案，只需要从下向上进行 Trie 树合并，合并的同时根据上面的方法维护答案即可。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/* Written by Rikka__  */
/* 手持两把锟斤拷，口中疾呼烫烫烫   */
#include<bits/stdc++.h>
using namespace std;
#define _ =read()
#define int long long
inline int read(){
	int r = 0 , w = 1;
	char ch = getchar();
	while(ch > '9' || ch < '0') {if(ch == '-') w = -1; ch = getchar();} 
	while(ch >='0' && ch <='9') {r = r * 10 + ch -'0'; ch = getchar();}
	return r * w;
}
namespace FileIO{
	string InFile;
	string OutFile;
	void File(string s){
		InFile = s + ".in";
		OutFile = s + ".out";
		freopen(InFile.data() , "r" , stdin);
		freopen(OutFile.data() , "w" , stdout);
	}
}
const int Maxn = 201010;
int n;
struct Vollerei{
	int to;
	int nxt;
};
Vollerei *ed[Maxn << 1];
int ecnt;
int head[Maxn];
void add(int x , int y){
	ed[++ecnt] = new Vollerei;
	ed[ecnt]->to = y;	
	ed[ecnt]->nxt = head[x];
	head[x] = ecnt;
}
namespace Trie{
	struct node{
		int siz;
		int val;
		node *l;
		node *r;
	};
	node tr[2000010];
	node *cnt = tr;
	node *rt[Maxn];
	node* Newnode(int x , int dep = 17){
		node *cur = cnt++;
        cur->siz = 1;
		if(dep == 0) return cur;
		int num = (x >> dep - 1 & 1);
		if(num == 0) cur->l = Newnode(x , dep - 1);
		else cur->r = Newnode(x , dep - 1);
		return cur;
	}
	inline int find(node *x , node *y , int dep){
		int s = 0;
		for( ; dep ; dep--){
			int num = !(x->l);
			if(num == 0) x = x->l;
			else x = x->r;
			if(num == 0){
				if(y->l) y = y->l;
				else s |= 1 << dep - 1 , y = y->r;
			}
            else{
                if(y->r) y = y->r;
                else s |= 1 << dep - 1 , y = y->l;
            }
        }
    	return s;
    }
    node* merge(node *x , node *y , int dep = 17){
        if(x == nullptr) return y;
        if(y == nullptr) return x;
        x->siz += y->siz;
        if(dep == 0) return x;
        x->l = merge(x->l , y->l , dep - 1);
        x->r = merge(x->r , y->r , dep - 1);
        if(x->l == nullptr) x->val = x->r->val;
        else if(x->r == nullptr) x->val = x->l->val;
        else if(x->l->siz == 1) x->val = 1 << dep - 1 | find(x->l , x->r , dep - 1);
        else if(x->r->siz == 1) x->val = 1 << dep - 1 | find(x->r , x->l , dep - 1);
        else x->val = max(x->l->val , x->r->val);
        return x;
    }
};
using namespace Trie;
int ans[Maxn];
void dfs(int x , int fa){
    for(int i = head[x] ; i ; i = ed[i]->nxt){
        int to = ed[i]->to;
        if(to == fa) continue;
        dfs(to , x);
        rt[x] = merge(rt[x] , rt[to]);
    }
    if(rt[x]->siz < 2) ans[x] = -1;
    else ans[x] = rt[x]->val;
}
signed main(){
    //FileIO::File("game");
    n _;
    for(int i = 1 ; i <= n ; i++){
        int x _;
        rt[i] = Newnode(x);
    }
    for(int i = 1 ; i < n ; i++){
        int x _ , y _;
        add(x , y) , add(y , x);
    }
    dfs(1 , 0);
    for(int i = 1 ; i <= n ; i++) cout << ans[i] << "\n";
    getchar();
    return 0;
}

T2

来源：不知道

题意：

　　给定若干 $n$ 元一次同余方程求出一组解满足尽量多的方程。

题解：

　　观察数据：

　　　　1.只有一个未知数而且模数相同，直接枚举。

　　　　2.未知数和方程都是 50 个，发现模数都是质数的幂的形式而且互质，直接大力 CRT合并就行。

　　　　3.未知数和方程有 300 个，但是模数相同而且为 $10^9+7$ 直接大力高斯消元。

　　　　4.发现对于每个未知数只有两种选择，而且得到 10 分的标准要恰好满足其中之一，直接 $2^n$ 枚举检验就行。

　　　　5.模数相同，且模数为若干质数的乘积（$2\times3\times5\times7\times11\times13\times17\times19\times23 =223092870$ ，直接对于每个因子高斯消元最后 CRT 合并就行了。

　　　　6.模数不同，但是模数的质因子最大只有 200，对于 200 以下的质数分别进行高斯消元然后CRT合并。

　　　　7.模数相同而且比较小，上面的方程的权重比较大，所以优先满足上面的，下面的方程对于每个数有三种取值，直接 dp 就行。

　　　　8.和 6 一样。

　　　　9.送分的，求个众数就行。

　　　　10.比较玄学，题解上是暴力搜索 64 个比较好搜的，对于剩下 26 个使用状压 dp 求解。