GYOI Beginning Contest #1 Div.3

Welcome to GBC Round 1。

题目顺序按难度排序。

Problem Contents

来自 XU 的评价：

T1 需要思考一下

T2 有点水

T3 直接暴力

T4 ？

Problem Hint List

T1 Hint

到底要怎样才需要交换呢？

T2 Hint

我们设 $g(i, j)$ 表示结点 $i$ 到他的第 $2^j$ 个父亲的 $\gcd$。

T3 Hint

需要用什么算法来求路径的数量？

T4 Hint

T1 Treap

让 $0$ 在前 $1$ 在后的方案，即当 $1$ 在 $0$ 前时则必须使用一次交换，其余 $0$ 或 $1$ 可以跟着这次交换来交换。所以答案就是 10 出现的次数。

当然也可以求除了开头的 0 连通块个数。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N];
int n;
int main(){
	cin>>n;
	for(int i = 1;i <= n;i++){
		cin>>a[i];
	}
	int ans = 0;
	for(int i = 1;i < n;i++){
		if(a[i] == 1 && a[i+1] == 0)	ans++;
	}
	cout<<ans<<"\n";
	return 0;
}

T2 Search

倍增建树

最大公因数会随着数的增加，非严格减小。所以要使 $l \to r$ 最短。

这题实在有点简单，只是代码量高。由题意的移动可以自然联想到完全二叉树，于是就可以建树。

我们现在要求的是 $u \to v$ 的 $\gcd$，还要路径最短，就可以使用 lca 处理。$\gcd(u \to v) = \gcd((u \to \text{lca}),(\text{lca} \to v))$

$g(i, j)$ 表示结点 $i$ 到他的第 $2^j$ 个父亲的 $\gcd$，所以 $g(i,j)=\gcd(g(i,j-1),g(f(i,j-1),j-1))$，即 $2^{j-1}$ 个父亲的 $\gcd$ 与第 $2^{j-1}$ 个父亲到他的第 $2^{j-1}$ 个父亲的 $\gcd$，就是 $u$ 到他的第 $2^j$ 个父亲的 $\gcd$ 了。

所以答案就是 $\gcd(g(l, \text{lca}), g(v, \text{lca}))$。

简单做法

适用于不想建树的朋友。

我们发现 $l \to 1$ 需要经过的结点就是 $l$ 一直 $/2$ 所经过的节点，要求这个只需要 $\log l$ 的时间复杂度，自然可以通过本题。最后基于 $\text{lca}$ 的父亲也一定是 $l, r$ 的父亲，所以只需要从根 $1$ 一直往下搜索知道出现分支，那上一个就是 $\text{lca}$。

最后在路径上取 $\gcd$ 即可

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
ll a[N], n, q; 
int stk1[N], stk2[N], tot1, tot2;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>q;
	assert(1 <= n && 1 <= q && n <= 100000 && q <= 100000);
	for(int i = 1;i <= n;i++)	cin>>a[i];
	while(q--){
		int l, r;
		cin>>l>>r;
		assert(1 <= l && 1 <= r && l <= n && r <= n);
		tot1 = tot2 = 0;
		while(l){
			stk1[++tot1] = l;
			l /= 2;
		}
		while(r){
			stk2[++tot2] = r;
			r /= 2;
		}
		int p = 1;
		while(stk1[p] == stk2[p]){
			if(p == min(tot1, tot2))	break;
			p++;
		}
		ll ans = a[ stk1[p-1] ];
		for(int i = p;i <= tot1;i++){
			ans = __gcd(ans, a[ stk1[i] ]);
		}
		for(int i = p;i <= tot2;i++){
			ans = __gcd(ans, a[ stk2[i] ]);
		}
		cout<<ans<<"\n";
	}


	return 0;
}

T3 DIJ

一道比较明显的 dfs，若不给样例 2，则这题难度在黄。

由样例 2 可得，若图自环，则有无数解。

若有 $d(u)$ 表示 $u \to n$ 的方案数，就可以记忆化搜索，即 $d(u) = \sum d(deg(u))$，即出边的 $d$ 和。若有自环却不能联通 $n$，则输出 $0$，所以要特判。

答案记得开 long long。

时间复杂度 $O(n + m)$。

#include <bits/stdc++.h>
#define int long long 
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
const ll MOD = 702649740970;

int n, m;
ll d[N], vis[N];
vector<int> g[N];
bool iszh = 0;

ll dfs(int u){// 返回到n的方案数 
	ll sum = 0;
	bool f = 0;
	for(auto v : g[u]){
		if(d[v] != -1){
			sum += d[v] % MOD;
			sum %= MOD;
			continue;
		}
		if(vis[v]){
			f = 1;
			continue;// 有自环 
		}
		vis[v] = 1;
		sum += dfs(v) % MOD;
		sum %= MOD;
	}
	d[u] = sum % MOD;
	if(f && sum)	iszh = 1;
	return sum;
}

signed main(){
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>n>>m;
	for(int i = 1;i <= m;i++){
		int u, v;
		cin>>u>>v;
		g[u].push_back(v);
	}
	memset(d, -1, sizeof d);
	d[n] = 1;
	vis[1] = 1;
	dfs(1);
	if(iszh)	cout<<-1;
	else cout<<d[1];
	return 0;
}

T4 Plus

性质

1. 总是可以在 $b$ 的左、右端 $+1$，如 $123 \to 124$ 或 $123 \to 321 \to 322 \to 223$
2. 可以不花代价给左、右端增加数字 $0$，如 $123 \to 0123$ 或 $123 \to 321 \to 0321 \to 1230$
3. 无论如何，我们不能单独修改 $b$ 内部的元素，只能通过进位。如要使 $123 \to 133$，只能 $+10$。

思路

在性质二下，使用性质一，可以让 $b$ 的左端点增加任意数，所以除了 $b$ 以外的数，要使其它元素分别等于 $a$ 中的数，代价就是 $\sum_{j=1}^{n}a_j, ~ j \notin {b \text{所在的下标}}$。而 $b$ 内部的代价基本就是 $a$ 所对应的序列与 $b$ 的差。

再考虑 $b$ 内部的数，其必然匹配 $a$ 长度为 $m$ 的子序列。设 $a$ 中，下标为 $i \sim j$ 的子序列所组成数的为 $[a_i, a_j]$。若 $b$ 匹配 $[a_i, a_{i+m}]$，则：

要使 $b \to [a_i, a_{i+m}]$，还需要几个特性：

4. 当 $b_1 + 1$ 时，应当往右边进位而不是往左。
5. $10^i > \sum_{j = 0}^{i-1} (10^j \times 9)$，即在贪心最小的时候，要尽量往位数小的做。

考虑到只有两边能动，所以答案要使得 $b$ 从两端出发的子序列分别与 $a$ 所对应的子序列形成的差最小，自然要让两个子序列位数分别最少，即以中位数为中间，把左右两边分成两个序列，每个序列与 $a$ 所对应的序列的差就是代价的最小值。

于是代价就是左半子序列的倒序 $+$ 右半子序列。其中子序列指差值的子序列形成的数。

当然，这种情况仅限于 $a$ 的左半子序列的倒序 $\ge$ $b$ 的左半子序列的倒序，$a$ 的右半子序列 $\ge$ $b$ 的右半子序列。

分类

再考虑借位。我们发现，若有两个整数 $x, y$，其数位都为 $s$，则 $x-y$ 的借位最多为 $(x-y + 10^{s}) \bmod 10^{s} < 10^{s+1}$，所以无论借位与否，中位数永远是最优答案。

很明显，这题推到这就成了一个大分类的题目。

设 $a$ 的左半子序列的倒序 $[a_i, a_{i + \frac{m}{2}}]$ 为 $a_l$，$a$ 的右半子序列的正序 $[a_{i + \frac{m}{2} + 1}, a_{i+m}]$ 为 $a_r$。$b$ 同理，将 $i$ 替换成 $1$。

若 $a_l \ge b_l, a_r \ge b_r$，则答案就是 $a_l - b_l + a_r - b_r$，前面已经提到过了。

若 $a_l \ge b_l, a_r < b_r$，则发现，右边的需要通过借位实现减法，而左边不用，所以我们需要使 $b_l$ 的首项 $+1$，于是又有了判断

若 $a_l \ge b_l$ 则左边仍然能够被减，所以答案就是 $a_l - b_l + a_r - b_r$

否则，这个方式无解。

若 $a_l < b_l, a_r \ge b_r$ 则发现，左边的需要通过借位实现操作，所以需要 $b_r$ 的首项 $+1$，

若 $a_r \ge b_r$，则左边仍然能够被相减，所以答案就是 $a_r - b_r + a_l - b_l$

否则，这个方式无解。

若 $a_r < b_r, a_l < b_l$，则这个中间值无解。

现在，我们做完了中间值的大分类，但答案肯定不止一个中间值。我们将 $a_l, a_r$ 定义为以 $\text{mid}$ 为中间值的左半子序列和右半子序列。$b_l, b_r$ 同理，中间值为 $\text{mid} - i$，但为方便理解，统一写作 $\text{mid}$。

维护最小中间值

到了这里，我们要满足答案的 $\text{mid}$ 离 $i + \frac{m}{2}$ 最短，还要让 $\text{mid}$ 有解，需要在 $O(\log)$ 算出。

在以往的思路内，我们常用 $b \to a_{str}$，不妨换个思路，让 $a_{str} \to b$。自然要使得其中的最高位有解，于是可以预处理 $a$ 中每个 $\text{mid}$ 的左右最高值，将其排序，可以二分找到最优解。

实际上，现在还有一点不明确的地方，那就是大小判断。当左边要进位，$b$ 左边的最高位可能和 $a$ 左边的最高位相等，就不能 $\theta(1)$ 求出大小了。既然数据保证了每一位互不相同，那就有它们的下一位互不相同，自然可以解出 $a_l,b_l$ 的大小关系。

在很多情况下，答案总是会无法通过合法的中间值算出答案，所以这时要重新让 $b \to a_{str}$，并计算最差进位下的答案最小值。需要注意，此时不能无脑取模取最小：因为模数的存在，又要使答案最小，只能通过性质 5 来贪心。而模数的处理只需要从答案的左右段分别取 $10^9$ 个数位形成的数再取模。