A - Fibonacci Equations

由于 $\left| \dfrac{1 - \sqrt{5}}{2} \right| < 1$ ，当 $n \to +\infty$ 时， $\left( \dfrac{1 - \sqrt{5}}{2} \right)^n \to 0$ ，此时 $\dfrac{\left( \dfrac{1 + \sqrt{5}}{2} \right)^n - \left( \dfrac{1 - \sqrt{5}}{2} \right)^n}{\sqrt{5}} \to \dfrac{\left( \dfrac{1 + \sqrt{5}}{2} \right)^n}{\sqrt{5}}$，于是方程可以近似写成（显然 $R \ne \dfrac{\sqrt{5} - 1}{2}$ ）:

$$\begin{cases}\displaystyle\sum _{i = 1} ^{2n} \dfrac{\left( \dfrac{1 + \sqrt{5}}{2} \right)^i}{\sqrt{5}} R^{i - 1} = 0 \\ R \ne \dfrac{\sqrt{5} - 1}{2}\end{cases}$$$$\begin{cases}\displaystyle\sum _{i = 0} ^{2n - 1} \left( \dfrac{1 + \sqrt{5}}{2} \right)^i R^i = 0 \\ R \ne \dfrac{\sqrt{5} - 1}{2}\end{cases}$$$$\begin{cases}\dfrac{1 - \left( \dfrac{1 + \sqrt{5}}{2} R \right)^{2n}}{1 - \left( \dfrac{1 + \sqrt{5}}{2} \right) R} = 0 \\ R \ne \dfrac{\sqrt{5} - 1}{2}\end{cases}$$$$\begin{cases}\left( \dfrac{1 + \sqrt{5}}{2} R \right)^{2n} = 1 \\ R \ne \dfrac{\sqrt{5} - 1}{2}\end{cases}$$

\dfrac{1 + \sqrt{5}}{2} R = -1

R = \dfrac{1 - \sqrt{5}}{2}

-0.6180339887

B - Super Laser Gun

考虑依次选取以下 $7$ 个「关键营地」（需要指出的是，这 $7$ 个「关键营地」不一定都存在）：

$0$ 号「关键营地」为输入的第一个营地。
$1$ 号「关键营地」为输入的第一个与 $0$ 号「关键营地」 $x$ 坐标相同， $y$ 坐标不同的营地。
$2$ 号「关键营地」为输入的第一个与 $0$ 号「关键营地」 $x$ 坐标不同， $y$ 坐标相同的营地。
$3$ 号「关键营地」为输入的第一个与 $0$ 号「关键营地」 $x$ 坐标不同， $y$ 坐标不同的营地。
$4$ 号「关键营地」为输入的第一个与 $0$ 号「关键营地」 $x$ 坐标不同， $y$ 坐标不同，与 $3$ 号「关键营地」 $x$ 坐标相同， $y$ 坐标不同的营地。
$5$ 号「关键营地」为输入的第一个与 $0$ 号「关键营地」 $x$ 坐标不同， $y$ 坐标不同，与 $3$ 号「关键营地」 $x$ 坐标不同， $y$ 坐标相同的营地。
$6$ 号「关键营地」为输入的第一个与 $0$ 号「关键营地」 $x$ 坐标不同， $y$ 坐标不同，与 $3$ 号「关键营地」 $x$ 坐标不同， $y$ 坐标不同的营地。

可以证明，如果某个询问有解，则这 $7$ 个「关键营地」中必有一个是该询问的合法解，证明此处从略。

最终的时间复杂度为 $O(n + q)$ ，空间复杂度为 $O(1)$ 。

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
	int x = 0;
	char c = getchar_unlocked();
	while (c < '0') c = getchar_unlocked();
	while (c >= '0')
	{
		x = x * 10 + c - '0';
		c = getchar_unlocked();
	}
	return x;
}
void write(int x)
{
	if (x <= 9)
	{
		putchar_unlocked(x + '0');
		return;
	}
	write(x / 10);
	putchar_unlocked(x % 10 + '0');
}
inline void write_solution(int x)
{
	write(x);
	putchar_unlocked('\n');
}
inline void write_no_solution()
{
	putchar_unlocked('-');
	putchar_unlocked('1');
	putchar_unlocked('\n');
}
struct Point
{
	int x, y, i;
};
Point p[7];
int main()
{
	freopen("laser.in", "r", stdin);
	freopen("laser.out", "w", stdout);
	int n = read(), q = read();
	p[0] = (Point) {read(), read(), 1};
	for (int i = 2; i <= n; i++)
	{
		int x = read(), y = read();
		if (x == p[0].x && y != p[0].y) p[1] = (Point) {x, y, i};
		if (x != p[0].x && y == p[0].y) p[2] = (Point) {x, y, i};
		if (x != p[0].x && y != p[0].y)
		{
			if (!p[3].i)
			{
				p[3] = (Point) {x, y, i};
				continue;
			}
			if (x == p[3].x && y != p[3].y) p[4] = (Point) {x, y, i};
			if (x != p[3].x && y == p[3].y) p[5] = (Point) {x, y, i};
			if (x != p[3].x && y != p[3].y) p[6] = (Point) {x, y, i};
		}
			
	}
	while (q--)
	{
		int x = read(), y = read();
		for (int i = 0; i <= 7; i++)
		{
			if (i == 7)
			{
				write_no_solution();
				break;
			}
			if (x != p[i].x && y != p[i].y && p[i].i)
			{
				write_solution(p[i].i);
				break;
			}
		}
	}
	return 0;
}

C - Balanced Trees

对于一棵 $n + 1$ 个结点的「平衡树」，枚举其根结点的子树个数 $d$ 和子树大小 $s$ 。

首先要将 $2, 3, \ldots, n + 1$ 这 $n$ 个编号无序地分给 $d$ 个互不区分的（稍后会根据每个子树中的最小结点编号加以区分），大小均为 $s$ 的子树，方案数为 $\dfrac{n!}{d! \cdot (s!)^k}$ 。
接下来，每棵（互相区分的）子树均有 $a_s$ 种不同的结构（ $a_s$ 为大小等于 $s$ 的本质不同的「平衡树」的数量），方案数为 $a_s^k$ 。

因此我们得到了递推式：

$$a_{n + 1} = \sum _{d \cdot s = n} \dfrac{n!}{d! \cdot (s!)^k} \cdot a_s^k$$

根据初始状态 $a_1 = 1$ ，枚举 $s = 1, 2, \ldots, n - 1$ 和 $d = 1, 2, \ldots, \left\lfloor\dfrac{n - 1}{s}\right\rfloor$ 逐个更新答案即可。

最终的时间复杂度为 $O(n \log n)$ ，空间复杂度为 $O(n)$ 。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 12;
const int P = 1e9 + 7;
long long a[N], fc[N], ffc[N];
int divs(int a, int b = 1, int p = P)
{
	if (b % a == 0) return b / a;
	int x = divs(p % a, a - b % a, a);
	return (1ll * x * p + b) / a;
}
int main()
{
	freopen("trees.in", "r", stdin);
	freopen("trees.out", "w", stdout);
	int n;
	cin >> n;
	fc[0] = 1;
	for (int i = 1; i <= n; i++)
		fc[i] = fc[i - 1] * i % P;
	ffc[n] = divs(fc[n]);
	for (int i = n - 1; i >= 0; i--)
		ffc[i] = ffc[i + 1] * (i + 1) % P;
	a[1] = 1;
	for (int y = 1; y <= n; y++)
	{
		a[y] = a[y] * ffc[y] % P;
		long long cur = 1;
		for (int x = y, z = 1; x <= n; x += y, z++)
		{
			cur = cur * a[y] % P;
			long long val = fc[x] * ffc[z] % P;
			a[x + 1] += cur * val % P;
			if (a[x + 1] >= P) a[x + 1] -= P;
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		ans += a[i] * fc[i] % P;
		if (ans >= P) ans -= P;
	}
	cout << ans << endl;
	return 0;
}

D - Sorrowful Substrings

注意到子串的权值在其中一个端点固定时随着另一个端点向外扩展而单调递增，可以使用双指针统计答案。

将原序列反转，改为匹配子序列 $\{\texttt 2, \texttt 3, \texttt 3, \texttt 3\}$ ，分别维护子序列 $\{\texttt 2\}, \{\texttt 2, \texttt 3\}, \{\texttt 2, \texttt 3, \texttt 3\}, \{\texttt 2, \texttt 3, \texttt 3, \texttt 3\}$ 的出现次数即可实现双指针移动时对权值的实时计算。

最终的时间复杂度为 $O(n)$ ，空间复杂度为 $O(1)$ ，其中输入的字符串 $S$ 不计入空间复杂度。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 12;
inline __int128 read()
{
	__int128 x = 0;
	char c = getchar_unlocked();
	while (c < '0') c = getchar_unlocked();
	while (c >= '0')
	{
		x = x * 10 + c - '0';
		c = getchar_unlocked();
	}
	return x;
}
inline std::string readline()
{
	std::string x = "";
	char c = getchar_unlocked();
	while (c < '0') c = getchar_unlocked();
	while (c >= '0')
	{
		x += c;
		c = getchar_unlocked();
	}
	return x;
}
void write(__int128 x)
{
	if (x <= 9)
	{
		putchar_unlocked(x + '0');
		return;
	}
	write(x / 10);
	putchar_unlocked(x % 10 + '0');
}
inline void writeline(__int128 x)
{
	write(x);
	putchar_unlocked('\n');
}
int main()
{
	freopen("sorrow.in", "r", stdin);
	freopen("sorrow.out", "w", stdout);
	__int128 n = read(), k = read();
	string s = readline();
	reverse(s.begin(), s.end());
	s = ' ' + s;
	__int128 r = 0, ans = n * (n + 1) / 2;
	__int128 c3 = 0, c2 = 0, c23 = 0, c233 = 0, c2333 = 0;
	for (int i = 1; i <= n; i++)
	{
		while (c2333 < k && r <= n)
		{
			r++;
			if (s[r] == '2') c2++;
			if (s[r] == '3')
			{
				c3++;
				c2333 += c233;
				c233 += c23;
				c23 += c2;
			}
		}
		ans -= (r - i);
		if (s[i] == '3') c3--;
		if (s[i] == '2')
		{
			c2--;
			c2333 -= c3 * (c3 - 1) * (c3 - 2) / 6;
			c233 -= c3 * (c3 - 1) / 2;
			c23 -= c3;
		}
	}
	writeline(ans);
	return 0;
}

E - Extraordinary TSP Problem

忽略编号小于 $7$ 的结点（将求得的答案加上 $6$ 即可），设不大于 $n$ 的最大质数为 $p$ ：

对于编号大于 $p$ 的结点，向 $p$ 号结点连边最优。
对与编号小于 $p$ 的非质数结点，将它们连向最近的质数结点最优。
对于质数结点，将它们从小到大连成一条链最优，此时相邻两个质数间可以免费串联一个非直属结点 —— 将相邻两个质数的平均数串联上去最优。

用欧拉筛筛出不大于 $n$ 的所有质数后根据上述结论直接计算即可，过程中需要结合双指针快速找出最近的质数。

最终的时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ 。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e8 + 12, M = 6e6 + 12;
int pp = 0, ps[M];
bitset <N> pt;
int main()
{
	freopen("tsp.in", "r", stdin);
	freopen("tsp.out", "w", stdout);
	int n, pp = 0, ans = 6, pi = 4;
	cin >> n;
	if (n <= 8)
	{
		cout << n - 1 << endl;
		return 0;
	}
	for (int i = 2; i <= n; i++)
	{
		if (!pt[i])
		{
			pp++;
			ps[pp] = i;
		}
		for (int j = 1; j <= pp; j++)
		{
			int h = ps[j] * i;
			if (h > n) break;
			pt[h] = true;
			if (i % ps[j] == 0) break;
		}
	}
	ps[pp + 1] = 2 * N;
	for (int i = 8; i <= n; i++)
	{
		if (pi < pp && ps[pi + 1] == i)
		{
			ans += ps[pi + 1] - ps[pi];
			pi++;
			continue;
		}
		if (ps[pi + 1] - i == i - ps[pi]) continue;
		ans += min(ps[pi + 1] - i, i - ps[pi]);
	}
	cout << ans << endl;
	return 0;
}

F - Trivial Array Queries

考虑使用颜色段均摊技巧维护序列，然后对每个权值利用一棵动态开点权值线段树维护该权值在序列中的出现位置。对于查询操作，贪心地尽量靠左匹配原序列，维护当前匹配到的位置，对给定的每个段在对应的动态开点权值线段树上二分得到匹配完成时的位置即可。

最终的时间复杂度为 $O(n \log n + m \log n + q \log n)$ ，空间复杂度为 $O(n \log n + q \log n)$ 。

（用平衡树存储每个权值对应的颜色段来代替动态开点权值线段树，可以将空间复杂度优化到 $O(n + q)$ ，但可能会影响程序运行性能并增加代码编写难度。）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 12;
const int D = 17;
const int E = 1 << D;
const int F = 5 * D * N;
struct I
{
	int l;
	int r;
};
bool operator<(I x, I y)
{
	if (x.l != y.l) return x.l < y.l;
	return x.r < y.r;
}
map <I, int> segs;
struct J
{
	int a;
	int b;
	int l;
	int r;
};
struct K
{
	J v[F];
	int c;
	int add(int l, int r, int ll, int rr, int k, int b)
	{
		if (!b)
		{
			c++;
			b = c;
		}
		v[b].b += (r - l + 1) * k;
		if (l == ll && r == rr)
		{
			v[b].a += k;
			return b;
		}
		int lmid = (ll + rr) >> 1, rmid = lmid + 1;
		if (r <= lmid)
		{
			v[b].l = add(l, r, ll, lmid, k, v[b].l);
			return b;
		}
		if (l >= rmid)
		{
			v[b].r = add(l, r, rmid, rr, k, v[b].r);
			return b;
		}
		v[b].l = add(l, lmid, ll, lmid, k, v[b].l);
		v[b].r = add(rmid, r, rmid, rr, k, v[b].r);
		return b;
	}
	int get(int r, int acc, int ll, int rr, int b)
	{
		if (!r) return 0;
		if (!b) return (r - ll + 1) * acc;
		if (r == rr) return v[b].b + (rr - ll + 1) * acc;
		int lmid = (ll + rr) >> 1, rmid = lmid + 1;
		if (r <= lmid) return get(r, acc + v[b].a, ll, lmid, v[b].l);
		return get(lmid, acc + v[b].a, ll, lmid, v[b].l) + get(r, acc + v[b].a, rmid, rr, v[b].r);
	}
	int search(int k, int acc, int ll, int rr, int b)
	{
		int cur = get(rr, acc, ll, rr, b);
		if (cur < k) return cur - k;
		if (ll == rr) return rr;
		int lmid = (ll + rr) >> 1, rmid = lmid + 1, ans = search(k, acc + v[b].a, ll, lmid, v[b].l);
		if (ans < 0) ans = search(-ans, acc + v[b].a, rmid, rr, v[b].r);
		return ans;
	}
};
K w;
int main()
{
	freopen("array.in", "r", stdin);
	freopen("array.out", "w", stdout);
	ios::sync_with_stdio(0);
	int n, q;
	cin >> n >> q;
	w.c = n;
	for (int i = 1; i <= n; i++)
	{
		int x;
		cin >> x;
		w.add(i, i, 1, E, 1, x);
		segs[(I) {i, i}] = x;
	}
	while (q--)
	{
		int z, l, r, v, m, x, y;
		cin >> z;
		if (z == 1)
		{
			map <I, int> temp;
			cin >> l >> r >> v;
			map<I, int>:: iterator seg = segs.lower_bound((I) {l, 0});
			if (seg == segs.end()) seg--;
			if ((*seg).first.l > l) seg--;
			temp[(*seg).first] = (*seg).second;
			w.add((*seg).first.l, (*seg).first.r, 1, E, -1, (*seg).second);
			segs.erase(seg);
			while (1)
			{
				if (segs.empty()) break;
				map<I, int>:: iterator seg = segs.lower_bound((I) {l, 0});
				if (seg == segs.end()) break;
				if ((*seg).first.l > r) break;
				temp[(*seg).first] = (*seg).second;
				w.add((*seg).first.l, (*seg).first.r, 1, E, -1, (*seg).second);
				segs.erase(seg);
			}
			pair<I, int> t1 = (*(temp.begin()));
			if (t1.first.l < l)
			{
				segs[(I) {t1.first.l, l - 1}] = t1.second;
				w.add(t1.first.l, l - 1, 1, E, 1, t1.second);
			}
			pair<I, int> t2 = (*(temp.rbegin()));
			if (t2.first.r > r)
			{
				segs[(I) {r + 1, t2.first.r}] = t2.second;
				w.add(r + 1, t2.first.r, 1, E, 1, t2.second);
			}
			segs[(I) {l, r}] = v;
			w.add(l, r, 1, E, 1, v);
		}
		if (z == 2)
		{
			cin >> m;
			int cur = 1;
			for (int i = 1; i <= m; i++)
			{
				cin >> x >> y;
				if (cur == n + 2) continue;
				cur = w.search(w.get(cur - 1, 0, 1, E, x) + y, 0, 1, E, x) + 1;
				if (cur <= 0) cur = n + 2;
			}
			if (cur == n + 2)
			{
				puts("No");
				continue;
			}
			puts("Yes");
		}
	}
	return 0;
}

G - Returning Brooms

Hall 定理：对于一个左部点个数不多于右部点个数的二分图 $G$ ，设 $N(S)$ 代表 $G$ 中与左部点集合 $S$ 中至少一个点有连边的右部点的集合，则 $G$ 存在完美匹配的充分必要条件是，对于任意的非空左部点集合 $S$ ，总有 $|N(S)| \ge |S|$ 。

考虑对于一个给定的权值 $t$ 求解最小权值能够不小于它的最小 $k$ 值。

则对于任意的非空左部点集合 $S$ ，无论哪 $m - k$ 个右部点被删去，最终的二分图都要有 $|E_S| \ge |S|$ ，因此原图中 $|E_S| \ge |S| + m - k$ ，即 $k \ge |S| - |E_S| + m$ 。

根据 Hall 定理，对所有 $2^n - 1$ 个集合 $S$ 分别计算 $|S| - |E_S| + m$ ，取其中的最大值即可得到确保能够完成归还工作的最小 $k$ 值。

考虑倒序枚举 $t = nm, nm - 1, \ldots, 1$ ，每次会有若干个 $|E_S|$ 的值减少 $1$ （ $nm$ 轮中一共会有 $(2^n - 1) \cdot m$ 次减少操作）。由于 $|S| - |E_S| + m$ 的值总是不大于 $n + m$ 且随枚举过程单调递增，结合双指针开桶统计 $|S| + |E_S| - m$ 的分布情况即可实现 $O(1)$ 单点修改和 $O(1)$ 查询最大值。

最终的时间复杂度为 $O(2^n \cdot m)$ ，空间复杂度为 $O(nm + 2^n)$ 。

（std 中对 $d_{i, j}$ 使用了 std::sort，导致实际的时间复杂度为 $O(2^n \cdot m + nm \log nm)$ 。由于题目保证了矩阵 $\{d_{n, m}\}$ 中的所有元素构成一个 $\{1, 2, \ldots, nm\}$ 的排列，这一点可以使用桶排序来规避。）

#include <bits/stdc++.h>
using namespace std;
const int N = 10 + 2;
const int M = 1e5 + 12;
const int D = 1 << N;
const int S = N + M;
const int T = N * M;
int b[D], e[M], t[S];
struct I
{
	int i;
	int j;
	int v;
};
I d[T];
bool cmp(I x, I y)
{
	return x.v < y.v;
}
inline int lowbit(int x)
{
	return x & (-x);
}
inline int popcount(int x)
{
	int c = 0;
	while (x)
	{
		c++;
		x -= lowbit(x);
	}
	return c;
}
int main()
{
	freopen("brooms.in", "r", stdin);
	freopen("brooms.out", "w", stdout); 
	int n, m, p, l = 0;
	scanf("%d %d", &n, &m);
	p = m - 1;
	for (int i = 1; i < (1 << n); i++)
		b[i] = m + n - popcount(i);
	for (int i = 1; i < (1 << n); i++)
		t[b[i]]++;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			l++;
			scanf("%d", &d[l].v);
			d[l].i = i - 1;
			d[l].j = j;
		}
	sort(d + 1, d + l + 1, cmp);
	for (int i = l; i >= 1; i--)
	{
		int s = d[i].j, j = e[s];
		do
		{
			int o = (1 << d[i].i) | j;
			t[b[o]]--;
			b[o]--;
			t[b[o]]++;
			j = (j - 1) & e[s];
		}
		while (j != e[s]);
		e[s] |= 1 << d[i].i;
		while (t[p])
		{
			printf("%d", d[i].v);
			if (p == n - 1)
			{
				puts("");
				return 0;
			}
			putchar(' ');
			p--;
		}
	}
	return 0;
}

Sleeping Cup #8 Editorials

A - Fibonacci Equations

B - Super Laser Gun

C - Balanced Trees

D - Sorrowful Substrings

E - Extraordinary TSP Problem

F - Trivial Array Queries

G - Returning Brooms

状态

开发

支持

关于

Sleeping Cup #8 Editorials

A - Fibonacci Equations

B - Super Laser Gun

C - Balanced Trees

D - Sorrowful Substrings

E - Extraordinary TSP Problem

F - Trivial Array Queries

G - Returning Brooms

状态

开发

支持

关于

还没有账户？

登录