# BZOJ4567 [Scoi2016]背单词
## 题目描述
凤老师告诉 Lweb ，我知道你要学习的单词总共有 n 个，现在我们从上往下完成计划表，对于一个序号为 x 的单词（序号 1...x-1 都已经被填入）：
1) 如果存在一个单词是它的后缀，并且当前没有被填入表内，那他需要吃 n×n 颗泡椒才能学会；
2) 当它的所有后缀都被填入表内的情况下，如果在 1...x-1 的位置上的单词都不是它的后缀，那么你吃 x 颗泡椒就能记住它；
3) 当它的所有后缀都被填入表内的情况下，如果 1...x-1的位置上存在是它后缀的单词，所有是它后缀的单词中，序号最大为 y ，那么你只要吃 x-y 颗泡椒就能把它记住。
Lweb 是一个吃到辣辣的东西会暴走的奇怪小朋友，所以请你帮助 Lweb ，寻找一种最优的填写单词方案，使得他记住这 n 个单词的情况下，吃最少的泡椒。

## 解题报告
显然，对于任意一个单词，只有当其在它所有后缀都填满后去填才可以达到最优方案。
如何找到后缀呢？考虑建一棵字典树，依次把每一个单词逆序插入。之后可以将问题转化为给树上的点标号，且每个点的标号大于其父亲的标号。每个点的代价为它的标号与它的父亲标号的差，求最小化代价。
首先，子树之间两两独立，不难证明依次标号每一棵子树一定可以达到最优解。其次，显然先标号较小的子树更优。之后就可以在字典树上 DFS 了。贪心，先走较小的子树进行标号即可。
```cpp:n
#include <bits/stdc++.h>
using namespace std;

#define N 100005

int n, head[N], size[N];
long long ans;
char str[N];
vector<int> son[N];

struct node
{
	node *son[26];
	int tag;
	node() : tag(0) { memset(son, 0, sizeof son); }
} *root;

void insert(int x, char str[])
{
	int len = strlen(str);
	node *p = root;
	for (int i = len - 1; i >= 0; --i)
	{
		if (!p->son[str[i] - 'a'])
			p->son[str[i] - 'a'] = new node();
		p = p->son[str[i] - 'a'];
	}
	p->tag = x;
}

void build(node *p, int fa)
{
	if (p->tag) son[fa].push_back(p->tag), fa = p->tag;
	for (int i = 0; i < 26; ++i)
		if (p->son[i]) build(p->son[i], fa);
}

int cmp(int x, int y)
{
	return size[x] < size[y];
}

void dfs(int x)
{
	size[x] = 1;
	for (int i = 0; i < (int)son[x].size(); ++i)
		dfs(son[x][i]), size[x] += size[son[x][i]];
}

void getans(int x, int fa)
{
	static int tot = 0;
	int id = ++tot; ans += tot - fa;
	sort(son[x].begin(), son[x].end(), cmp);
	for (int i = 0; i < (int)son[x].size(); ++i)
		getans(son[x][i], id);
}

int main()
{
	cin >> n;
	root = new node();
	for (int i = 1; i <= n; ++i)
		scanf("%s", str), insert(i, str);
	build(root, 0);
	dfs(0);
	getans(0, 1);
	cout << ans << endl;
	return 0;
}
```
# BZOJ4568 [Scoi2016]幸运数字
## 题目描述
A 国共有 n 座城市，这些城市由 n-1 条道路相连，使得任意两座城市可以互达，且路径唯一。每座城市都有一个幸运数字，以纪念碑的形式矗立在这座城市的正中心，作为城市的象征。一些旅行者希望游览 A 国。旅行者计划乘飞机降落在 x 号城市，沿着 x 号城市到 y 号城市之间那条唯一的路径游览，最终从 y 城市起飞离开 A 国。在经过每一座城市时，游览者就会有机会与这座城市的幸运数字拍照，从而将这份幸运保存到自己身上。然而，幸运是不能简单叠加的，这一点游览者也十分清楚。他们迷信着幸运数字是以异或的方式保留在自己身上的。例如，游览者拍了 3 张照片，幸运值分别是 5，7，11，那么最终保留在自己身上的幸运值就是 9（5 xor 7 xor 11）。
有些聪明的游览者发现，只要选择性地进行拍照，便能获得更大的幸运值。例如在上述三个幸运值中，只选择 5 和 11 ，可以保留的幸运值为 14 。现在，一些游览者找到了聪明的你，希望你帮他们计算出在他们的行程安排中可以保留的最大幸运值是多少。

## 解题报告
显然异或和最大问题可以使用线性基解决。
使用倍增 lca 做法，对于每一个点保存其上 2 的整数幂步的线性基，空间复杂度和查询复杂度均为 O(60*NlogN)。
也可以使用树分治，每次求出重心后，求出重心到每个点路径上的数的线性基。查询复杂度可降至为 O(60^2)。
```cpp:n
#include <bits/stdc++.h>
using namespace std;

#define N 20005

int n, q, head[N], fa[N][16], deep[N];
long long w[N];

inline long long read()
{
	long long x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}

struct graph
{
	int next, to;
	graph() {}
	graph(int _next, int _to)
	: next(_next), to(_to) {}
} edge[N * 2];

inline void add(int x, int y)
{
	static int cnt = 1;
	edge[++cnt] = graph(head[x], y);
	head[x] = cnt;
}

struct lin_base
{
	long long a[61];
	lin_base() { memset(a, 0, sizeof a); }
	void insert(long long x)
	{
		for (int i = 60; i >= 0; --i)
			if (x & (1ll << i))
			{
				if (a[i]) x ^= a[i];
				else { a[i] = x; break; }
			}
	}
} base[N][16];

lin_base merge(lin_base a, lin_base b)
{
	lin_base re = a;
	for (int i = 60; i >= 0; --i)
		if (b.a[i]) re.insert(b.a[i]);
	return re;
}

void dfs(int x)
{
	deep[x] = deep[fa[x][0]] + 1;
	for (int i = head[x]; i; i = edge[i].next)
		if (edge[i].to != fa[x][0])
			fa[edge[i].to][0] = x, dfs(edge[i].to);
}

lin_base lca(int x, int y)
{
	lin_base re;
	if (deep[x] < deep[y]) swap(x, y);
	for (int i = 15; i >= 0; --i)
		if (deep[fa[x][i]] >= deep[y])
			re = merge(re, base[x][i]), x = fa[x][i];
	if (x == y) { re.insert(w[x]); return re; }
	for (int i = 15; i >= 0; --i)
		if (fa[x][i] != fa[y][i])
			re = merge(re, base[x][i]), re = merge(re, base[y][i]),
			x = fa[x][i], y = fa[y][i];
	re = merge(re, base[x][0]); re = merge(re, base[y][0]);
	re.insert(w[fa[x][0]]);
	return re;
}

long long query(int x, int y)
{
	lin_base t = lca(x, y);
	long long re = 0;
	for (int i = 60; i >= 0; --i)
		if ((re ^ t.a[i]) > re) re ^= t.a[i];
	return re;
}

int main()
{
	cin >> n >> q;
	for (int i = 1; i <= n; ++i)
		w[i] = read();
	for (int x, y, i = 1; i < n; ++i)
		x = read(), y = read(), add(x, y), add(y, x);
	dfs(1);
	for (int i = 1; i <= n; ++i)
		base[i][0].insert(w[i]);
	for (int j = 1; j <= 15; ++j)
		for (int i = 1; i <= n; ++i)
			if (fa[i][j - 1])
				fa[i][j] = fa[fa[i][j - 1]][j - 1],
				base[i][j] = merge(base[i][j - 1], base[fa[i][j - 1]][j - 1]);
	for (int x, y, i = 1; i <= q; ++i)
		x = read(), y = read(), printf("%lld\n", query(x, y));
	return 0;
}
```

# BZOJ4569 [Scoi2016]萌萌哒
## 题目描述
一个长度为n的大数，用S1S2S3...Sn表示，其中Si表示数的第i位,S1是数的最高位，告诉你一些限制条件，每个条件表示为四个数，l1，r1，l2，r2，即两个长度相同的区间，表示子串Sl1Sl1+1Sl1+2...Sr1与Sl2Sl2+1Sl2+2...Sr2完全相同。比如n=6时，某限制条件l1=1，r1=3，l2=4，r2=6，那么123123，351351均满足条件，但是12012，131141不满足条件，前者数的长度不为6，后者第二位与第五位不同。问满足以上所有条件的数有多少个。

## 解题报告
好厉害的想法……用倍增简化并查集操作。
参见 ST 表的思路，每一个合并操作可以转化为两段长度为 2 的整数次幂的区间的合并。建立 logN 个并查集，分别记录每种长度之间合并的情况。
最后，从高层向低层下传合并情况，统计最底层联通块个数，就可以计算答案了。
```cpp:n
#include <bits/stdc++.h>
using namespace std;

#define N 100005

int n, m, log_2[N], fa[20][N];

int find(int s, int x)
{
	if (x == fa[s][x]) return x;
	return fa[s][x] = find(s, fa[s][x]);
}

void merge(int s, int x, int y)
{
	int fx = find(s, x), fy = find(s, y);
	if (fx != fy) fa[s][fx] = fy;
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> n >> m;
	if (n == 1) { cout << 10 << endl; return 0; }
	for (int i = 2; i <= n; ++i)
		log_2[i] = log_2[i >> 1] + 1;
	for (int i = 0; i <= log_2[n]; ++i)
		for (int j = 1; j <= n; ++j)
			fa[i][j] = j;
	for (int l1, r1, l2, r2, i = 1; i <= m; ++i)
	{
		cin >> l1 >> r1 >> l2 >> r2;
		int s = log_2[r1 - l1];
		merge(s, l1, l2);
		merge(s, r1 - (1 << s) + 1, r2 - (1 << s) + 1);
	}
	for (int i = log_2[n]; i >= 1; --i)
		for (int j = 1; j + (1 << i) - 1 <= n; ++j)
			merge(i - 1, find(i, j), j),
			merge(i - 1, find(i, j) + (1 << (i - 1)), j + (1 << (i - 1)));
	int cnt = 0;
	for (int i = 1; i <= n; ++i)
		if (find(0, i) == i) ++cnt;
	int ans = 9;
	for (int i = 1; i < cnt; ++i)
		ans = 1ll * ans * 10 % 1000000007;
	cout << ans << endl;
	return 0;
}
```
# BZOJ4602 [Sdoi2016]齿轮
## 题目描述
现有一个传动系统，包含了N个组合齿轮和M个链条。每一个链条连接了两个组合齿轮u和v，并提供了一个传动比x : y。即如果只考虑这两个组合齿轮，编号为u的齿轮转动x圈，编号为v的齿轮会转动y圈。传动比为正表示若编号为u的齿轮顺时针转动，则编号为v的齿轮也顺时针转动。传动比为负表示若编号为u的齿轮顺时针转动，则编号为v的齿轮会逆时针转动。若不同链条的传动比不相容，则有些齿轮无法转动。我们希望知道，系统中的这Ｎ个组合齿轮能否同时转动。

## 解题报告
和 IPSC 练习赛题目如出一辙。随便找一个起点开始搜索，记录每一个齿轮的方向以及转速，判断是否存在矛盾即可。
不同的是，这道题卡精度。听说 long double 可以通过，听说取对数也可以通过。然而，通过对一个素数取模的方法虽可能造成冲突，但可以避免精度。
```cpp:n
#include <bits/stdc++.h>
using namespace std;

#define P 5462617
#define N 1005
#define M 20005

int T, n, m, inv[P], v[N], head[N], cnt, vis[N], flag;

struct graph
{
	int next, to, val;
	graph() {}
	graph(int _next, int _to, int _val)
	: next(_next), to(_to), val(_val) {}
} edge[M];

inline void add(int x, int y, int z)
{
	edge[++cnt] = graph(head[x], y, z);
	head[x] = cnt;
}

void dfs(int x)
{
	vis[x] = true;
	for (int i = head[x]; i; i = edge[i].next)
		if (!vis[edge[i].to])
			v[edge[i].to] = 1ll * v[x] * edge[i].val % P, dfs(edge[i].to);
		else if (v[edge[i].to] != 1ll * v[x] * edge[i].val % P)
			flag = true;
}

int main()
{
	inv[1] = 1;
	for (int i = 2; i < P; ++i)
		inv[i] = 1ll * inv[P % i] * (P - P / i) % P;
	cin >> T;
	for (int test = 1; test <= T; ++test)
	{
		memset(head, 0, sizeof head); cnt = 1;
		memset(vis, 0, sizeof vis); flag = false;
		cin >> n >> m;
		for (int x, y, s, t, i = 1; i <= m; ++i)
			cin >> x >> y >> s >> t,
			add(x, y, (t * inv[s] % P + P) % P),
			add(y, x, (s * inv[(t + P) % P]) % P);
		for (int i = 1; i <= n; ++i)
			if (!vis[i] && !flag)
				v[i] = 1, dfs(i);
		cout << "Case #" << test << ": " << (flag ? "No" : "Yes") << endl;
	}
	return 0;
}
```

# BZOJ4571 [Scoi2016]美味
## 题目描述
一家餐厅有 n 道菜，编号 1...n ，大家对第 i 道菜的评价值为 ai(1≤i≤n)。有 m 位顾客，第 i 位顾客的期望值为 bi，而他的偏好值为 xi 。因此，第 i 位顾客认为第 j 道菜的美味度为 bi XOR (aj+xi)，XOR 表示异或运算。第 i 位顾客希望从这些菜中挑出他认为最美味的菜，即美味值最大的菜，但由于价值等因素，他只能从第 li 道到第 ri 道中选择。请你帮助他们找出最美味的菜。

## 解题报告
如果不存在加法操作，这就是一道可持久化 Trie 的裸题。
既然有加法操作，那么换成可持久化线段树查询一下就可以了。
```cpp:n
#include <bits/stdc++.h>
using namespace std;

#define N 200005

int n, m;

inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}

struct node
{
	node *son[2]; int size;
	node() { size = 0; }
} *root[N];

void insert(node *&pos, node *pre, int l, int r, int x)
{
	pos = new node(); *pos = *pre; ++pos->size;
	if (l == r) return;
	int mid = (l + r) >> 1;
	if (x <= mid) insert(pos->son[0], pre->son[0], l, mid, x);
	else insert(pos->son[1], pre->son[1], mid + 1, r, x);
}

int query(node *pos, node *pre, int l, int r, int x, int y)
{
	if (x <= l && r <= y) return pos->size - pre->size;
	int mid = (l + r) >> 1, re = 0;
	if (x <= mid) re += query(pos->son[0], pre->son[0], l, mid, x, y);
	if (y > mid) re += query(pos->son[1], pre->son[1], mid + 1, r, x, y);
	return re;
}

int main()
{
	cin >> n >> m;
	root[0] = new node();
	root[0]->son[0] = root[0]->son[1] = root[0];
	for (int i = 1; i <= n; ++i)
		insert(root[i], root[i - 1], 0, 100000, read());
	for (int b, x, l, r, i = 1; i <= m; ++i)
	{
		b = read(), x = read(), l = read(), r = read();
		int ans = 0, s, t;
		for (int j = 18; j >= 0; --j)
		{
			if ((b >> j) & 1)  s = ans, t = ans + (1 << j) - 1;
			else s = ans + (1 << j), t = ans + (1 << (j + 1)) - 1;
			s = max(s - x, 0), t = min(t - x, 100000);
			if (s <= t && query(root[l - 1], root[r], 0, 100000, s, t))
				ans += (1 << j) * (((b >> j) & 1) ^ 1);
			else ans += (1 << j) * ((b >> j) & 1);
		}
		printf("%d\n", ans ^ b);
	}
	return 0;
}
```
# BZOJ4590 [Shoi2015]自动刷题机
## 题目描述
曾经发明了信号增幅仪的发明家SHTSC又公开了他的新发明：自动刷题机--一种可以自动AC题目的神秘装置。自动刷题机刷题的方式非常简单：首先会瞬间得出题目的正确做法，然后开始写程序，每秒，自动刷题机的代码生成模块会有两种可能的结果：
A.写了x行代码。
B.心情不好，删掉了之前写的y行代码。（如果y大于当前代码长度则相当于全部删除。）
对于每个OJ所有题目，存在某个固定的长度n>0。一旦自动刷题机在某秒结束时积累了大于等于n行的代码，它就会自动提交并AC此题，然后新建一个文件开始写下一题。SHTSC在某个OJ上跑了一天的自动刷题机，得到了很多条关于写代码的日志信息。他突然发现自己没有记录这个OJ的n究竟是多少。所幸他通过自己在OJ上的Rank知道了机一共切了k道题。希望你计算n可能的最小值和最大值。

## 解题报告
可以发现，题目满足二分性质。于是直接二分答案，得到答案的左右端点就好了。
```cpp:n
#include <bits/stdc++.h>
using namespace std;

#define N 100005

int n, k, a[N];
long long ans1, ans2;

int calc(long long x)
{
	long long sum = 0;
	int re = 0;
	for (int i = 1; i <= n; ++i)
	{
		sum = max(sum + a[i], 0ll);
		if (sum >= x) ++re, sum = 0;
	}
	return re;
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> n >> k;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	long long l = 1, r = 1e15;
	while (l <= r)
	{
		long long mid = (l + r) >> 1;
		if (calc(mid) > k) ans1 = mid, l = mid + 1;
		else r = mid - 1;
	}
	l = 1, r = 1e15;
	while (l <= r)
	{
		long long mid = (l + r) >> 1;
		if (calc(mid) < k) ans2 = mid, r = mid - 1;
		else l = mid + 1;
	}
	++ans1, --ans2;
	if (calc(ans1) != k) cout << -1 << endl;
	else cout << ans1 << ' ' << ans2 << endl;
	return 0;
}
```