首页 Tests

  • 两个数异或最值 →\to Trie 上跑跑

  • 一堆数异或最值 →\to 线性基

都是高二的老狗了，心态能不能像老狗一样平稳一点，tmd 被小朋友交几发暴力就吓炸了？！
想起了省选被隔壁老哥支配的恐惧
还是太重结果了，但这种心态会极大程度影响我的过程
这 TM 是老毛病了吧，中考时考数学做到压轴就一直在想 zhy,zzm 他们一定都切穿了导致我后面做的跟屎一样，好在是做到压轴才开始自闭的，要不可能雅礼都进不了
离 CSP 就两次（?）考试了，一定不能再跟别人比较了

耶耶耶今天是保龄 day~

TMD，T1 不会，T2 不会，T3 不会，T4 不会，我这场在干嘛

T1 遇到沟通困难的时候为什么不重新看一遍题？

T2 构造题你写了个啥？没拍过的乱搞活该保灵好吧

T3 为什么不认真读懂题想一想？线性基写脸上了？

T4 是真的不会。

TMD

# Solutions：

# a

nn 页的日记本，写过的页不能再写，第一天可任意写一页，记昨天写的一页为 tt ，那今天只能写 [1,t][1,t] ，求与给定数组 qq 趋势相同的方案数，支持交换 qq 中两个元素。
要求做到 $$O (n\log n)$$.

cnm，看错题了，看错的题到现在还不会做。

那既然我们今天只能写 [1,t][1,t] 的，记还能写的页码为一个集合，我们一定是写一个递减的东西且以当前集合中最小页码结尾。

然后就是大力推组合数的柿子，由于要与给定 qiq_i 趋势相同，那我们找到每个 qi<qi+1q_i<q_{i+1} 的位置拿出来做一个数组 aia_i 咋计数捏？为了方便处理一些奇怪的情况，我们把 0,n0,n 也放进序列。

每个 aia_i 其实是代表了一个递减段的，做每个递减段时，我们剩余数字集合大小是知道的，而我们是并不关注究竟还剩了什么数字的，毕竟是一个排列，放上去会自动排好序，但此时集合中最小的元素是必须被选的，我们可以得出柿子：

Ans=∏i=2k(n−ai−1−1ai−ai−1−1)Ans=\prod\limits_{i=2}^k\binom{n-a_{i-1}-1}{a_i-a_{i-1}-1}

这里就可以做不带修的情况了，带修咋做，上面这个形式不好维护，我们把组合数拆开，乘一乘，发现好多约掉了。

Ans=(n−a1−1)!×∏k=2n1(ai−ai−1)!×1(n−ai)Ans=(n-a_1-1)!\times \prod\limits_{k=2}^n{1\over (a_i-a_{i-1})!}\times {1\over (n-a_i)}

我们钦定了 a1=0a_1=0 那上面那个东西前面就是 (n−1)!(n-1)! 了

这个显然可以 setset 维护交换。

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
/* ==============================
 *  Author : Odalys 
 *
 *  Blog : Odalys.xyz
 *
 *  Mail : minyuenu@gmail.com
 * =============================== */
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &a){
	T w=1; a=0;
	char ch=getchar();
	for(;ch < '0' || ch > '9';ch=getchar()) if(ch == '-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) a=(a<<3)+(a<<1)+(ch^48);
	a*=w;
}
template <typename T> inline void ckmax(T &a, T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a, T b){a = a < b ? a : b;}
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mii map<int, int> 
#define pii pair<int, int> 
#define ins insert
#define era erase
#define vi vector<int> 
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i) 
#define foR(i,l,r) for (int i = l; i >= r; --i)
const int N = 3e5 + 10;
const int Mod = 1e9 + 7;
inline int Mul (int x, int y) {
	return 1ll * x * y >= Mod ? (1ll * x * y % Mod) : (x * y); 
}
inline int Add (int x, int y) {
	return (x + y >= Mod) ? (x + y - Mod) : x + y; 
}
inline int Sub (int x, int y) {
	return (x - y < 0) ? (x - y + Mod) : (x - y); 
}
int qpow (int a, int b) {
	int ans = 1, base = a;
	while (b) {
		if (b & 1) ans = Mul(ans, base);
		base = Mul(base, base);
		b >>= 1;
	}
	return ans; 
}
int fac[N], ifac[N];
void Init (int M) {
	fac[0] = ifac[0] = 1;
	For (i, 1, M) fac[i] = Mul(fac[i - 1], i);
	ifac[M] = qpow(fac[M], Mod - 2);
	foR (i, M - 1, 1) ifac[i] = Mul(ifac[i + 1], i + 1);
}
int bin (int a, int b) {
	if (a < b || a < 0 || b < 0) return 0;
	return Mul(fac[a], Mul(ifac[a - b], ifac[b])); 
}
int Inv (int s) {
	int a = qpow(s, Mod - 2); 
	return (a ? a : 1);
}
set <int> mck;
int a[N], s[N], tot;
int Ans;
int n, m; 
int eps(int x) { return x ? x : 1; }
inline void Era (int x) {
	auto it1 = mck.lower_bound(x); it1--; int pre = *it1; 
	Ans = Mul(Ans, Mul(eps(n - x), fac[x - pre - 1]));
	auto it2 = mck.upper_bound(x); int nxt = *it2;
	Ans = Mul(Ans, Mul(eps(n - nxt), fac[nxt - x - 1]));
	mck.erase(x); 
	Ans = Mul(Ans, Mul(Inv(n - nxt), ifac[nxt - pre - 1]));
}
inline void Ins (int x) {
	auto it1 = mck.lower_bound(x), it2 = mck.upper_bound(x); 
	it1--;
	int pre = *it1, nxt = *it2;
	Ans = Mul(Ans, Mul(eps(n - nxt), fac[nxt - pre - 1]));
	Ans = Mul(Ans, Mul(Inv(n - x), ifac[x - pre - 1]));
	Ans = Mul(Ans, Mul(Inv(n - nxt), ifac[nxt - x - 1]));
	mck.insert(x); 
}

int del[N];

int main() {
	Init(N - 10);
	read(n); read(m);
	For (i, 1, n) read(a[i]);
	s[++tot] = 0; mck.ins(0);
	For (i, 1, n - 1) if (a[i] < a[i + 1]) s[++tot] = i, mck.ins(i);
	s[++tot] = n; mck.ins(n); 
	Ans = 1;
	For (i, 2, tot) Ans = Mul(Ans, Mul(Inv(n - s[i]), ifac[s[i] - s[i - 1] - 1]));
	printf ("%d\n", Mul(Ans, fac[n - 1])); 
	For (i, 1, m) {
		int x, y; read(x); read(y);

		if (y < n && !del[y]) if (a[y] < a[y + 1]) Era(y), del[y] = 1;
		if (y > 1 && !del[y - 1]) if (a[y - 1] < a[y]) Era(y - 1), del[y - 1] = 1; 
		if (x < n && !del[x]) if (a[x] < a[x + 1]) Era(x), del[x] = 1;
		if (x > 1 && !del[x - 1]) if (a[x - 1] < a[x]) Era(x - 1), del[x - 1] = 1; 
		swap(a[x], a[y]);
		del[x] = del[y] = del[x - 1] = del[y - 1] = 0; 
		if (y < n && !del[y]) if (a[y] < a[y + 1]) Ins(y), del[y] = 1;
		if (y > 1 && !del[y - 1]) if (a[y - 1] < a[y]) Ins(y - 1), del[y - 1] = 1; 
		if (x < n && !del[x]) if (a[x] < a[x + 1]) Ins(x), del[x] = 1;
		if (x > 1 && !del[x - 1]) if (a[x - 1] < a[x]) Ins(x - 1), del[x - 1] = 1; 
		printf ("%d\n", Mul(Ans, fac[n - 1]));
		del[x] = del[y] = del[x - 1] = del[y - 1] = 0; 	
	}
}

# b

一张无向图，可能重边，每条路可黑白染色，构造方案使得每座城市连出的黑白差绝对值最大为 11

每个点度数为偶数的包暗示我们欧拉路

那对于一张所有点度数为偶数的图，拉一条欧拉路，路上点黑白染色，那不难发现起点是唯一可能破戒的，因为其他点度数为偶数，进来一次出去一次差为 00 ，而若欧拉路上有奇数条边，那我们起点就 GG 了，这种不能构造

若有奇数度数的点，新建虚点连上去，一样做就好，推荐一种好写的写法，使用了类似当前弧一样的东西。

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
/* ==============================
 *  Author : Odalys 
 *
 *  Blog : Odalys.xyz
 *
 *  Mail : minyuenu@gmail.com
 * =============================== */
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &a){
	T w=1; a=0;
	char ch=getchar();
	for(;ch < '0' || ch > '9';ch=getchar()) if(ch == '-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) a=(a<<3)+(a<<1)+(ch^48);
	a*=w;
}
template <typename T> inline void ckmax(T &a, T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a, T b){a = a < b ? a : b;}
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mii map<int, int> 
#define pii pair<int, int> 
#define vi vector<int> 
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i) 
#define foR(i,l,r) for (int i = l; i >= r; --i)
const int N = 4e6 + 10;
struct edge {
	int to, nxt, id;
} e[N << 1];
int head[N], cnt = 1;
inline void add (int u, int v, int Id) {
	e[++cnt].to = v; e[cnt].nxt = head[u]; e[cnt].id = Id; head[u] = cnt;
}
int du[N];
int n, m;
int Ans[N << 1], vis[N << 1], edges;
void dfs (int u) {
	for (int &i = head[u]; i; i = e[i].nxt) { // !
		int v = e[i].to, j = i / 2;
		if (vis[j]) continue;
		vis[j] = 1; dfs(v); Ans[j]= (++edges) & 1;
	}
}
int main() {
	read(n); read(m);
	For (i, 1, m) {
		int u, v; read(u); read(v); add(u, v, i), add(v, u, i); 
		du[u]++, du[v]++;
	}
	int id = m;
	For (i, 1, n) if (du[i] & 1) add(0, i, ++id), add(i, 0, id);
	For (u, 0, n) {
		edges = 0;
		dfs(u); 
		if ( (edges & 1) && u ) return puts("-1"), 0;
	}
	For (u, 1, m) printf ("%d ", Ans[u]); 
}



# c

一棵树，每个点带权，求每个点不在他到父亲的链上以及他子树内的所以点异或和最大值。

本场考试最简单的题了把，看懂就能切。

两个数异或最值 →\to Trie 上跑跑

一堆数异或最值 →\to 线性基

然后树上 dfsdfs ，跑到一个点时的线性基就是一边的答案，跑完一个点子树再将这个点加入线性基，正反都跑一遍即可。

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
/* ==============================
 *  Author : Odalys 
 *
 *  Blog : Odalys.xyz
 *
 *  Mail : minyuenu@gmail.com
 * =============================== */
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &a){
	T w=1; a=0;
	char ch=getchar();
	for(;ch < '0' || ch > '9';ch=getchar()) if(ch == '-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) a=(a<<3)+(a<<1)+(ch^48);
	a*=w;
}
#define int long long
template <typename T> inline void ckmax(T &a, T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a, T b){a = a < b ? a : b;}
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mii map<int, int> 
#define pii pair<int, int> 
#define vi vector<int> 
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i) 
#define foR(i,l,r) for (int i = l; i >= r; --i)
#define ll long long
const int N = 4e5 + 10;
const int L = 62;
vi to[N];
struct Linear_Basic {
	ll a[L | 1];
	inline void clear () {
		memset (a, 0, sizeof a); 
	}
	bool ins (ll t) {
		foR (i, L, 0) {
			if (t & (1ll << i)) {
				if (a[i]) {t ^= a[i];  continue;}
				For (j, 0, i - 1) if (t & (1ll << j) ) t ^= a[j];
				For (j, i + 1, L) if ( a[j] & (1ll << j) ) a[j] ^= t;
				a[i] = t;
				return true;
			} 
		}
		return false; 
	}
} cur, l[100], r[100];
int ltot, rtot;
int n, qy, v[N];
ll Ans[100][100];
int idl[N], idr[N];
void dfs (int u, int fa) {
	idl[u] = ltot;
	int sz = to[u].size(); 
	For (i, 0, sz - 1) {
		int v = to[u][i];
		if (v == fa) continue;
		dfs(v, u);
	}
	if (cur.ins(v[u])) l[++ltot] = cur;
}


void sfd (int u, int fa) {
	idr[u] = rtot;
	int sz = to[u].size(); 
	foR (i, sz - 1, 0) {
		int v = to[u][i];
		if (v == fa) continue;
		sfd(v, u);
	}
	if (cur.ins(v[u])) r[++rtot] = cur;
}

signed main() {
	read(n); For (i, 1, n) read(qy);
	For (i, 1, n) read(v[i]);
	For (i, 1, n - 1) {
		int u, v; read(u); read(v);
		to[u].pb(v), to[v].pb(u); 
	}
	dfs(1, 0);
	cur.clear();	
	sfd(1, 0);
	For (i, 0, ltot) For (j, 0, rtot) {
		cur.clear();
		For (k, 0, L) cur.ins(l[i].a[k]), cur.ins(r[j].a[k]);
		foR (k, L, 0) {
			ll val = Ans[i][j] ^ cur.a[k];
			ckmax(Ans[i][j], val); 
		}
	}
	For (i, 1, n) printf ("%lld\n", Ans[idl[i]][idr[i]]);
}

# D

会了