最近的场好像风格奇怪了起来，感觉大部分都挺trivial的~
这个E1跟E2也不难，其实看着挺显然的，就是考验代码调试能力。
D刚好当天上午学了根号分治，晚上就考到了，我不好说，总之这把虽然很唐但是回蓝啦。
B
题目大意：给定一个长度为 $n$ 的排列 $p$ 和长度为 $n$ 的数组 $a$ ，可以对 $p$ 进行任意次以下操作： $p_i=p_{i+1}$ 或者 $p_{i+1}=p_i$ ，是否能把 $p$ 转变为 $a$ ？
数据范围： $2 \leq n \leq 2 \cdot 10^5,1 \leq p_i \leq n,1 \leq a_i \leq n$ 。
思路：手玩样例，不难发现如果能转变需要两个条件，一是需要 $a$ 中每个数的出现都要连续，二是相对 $p$ 中原来元素的出现顺序， $a$ 中的出现不能交错，也就是 $a$ 去重后是 $p$ 的子序列。
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
|
void solve() {
int n;
cin >> n;
vi p(n);
vi a(n);
rep(i, 0, n - 1) cin >> p[i];
rep(i, 0, n - 1) cin >> a[i];
vector<pair<int, int>> pos(n + 1, {INT_MAX, INT_MIN});
vi cnt(n + 1);
map<int, int> ma;
rep(i, 0, n - 1) {
pos[a[i]].first = min(pos[a[i]].first, i);
pos[a[i]].second = max(pos[a[i]].second, i);
cnt[a[i]]++;
ma[p[i]] = i;
}
rep(i, 1, n) {
if (pos[i] == make_pair(INT_MAX, INT_MIN)) continue;
if (pos[i].second - pos[i].first + 1 != cnt[i]) {
cout << "No" << endl;
return;
}
}
int l = 0;
int r = 0;
auto a2 = a;
a2.erase(unique(all(a2)), a2.end());
int m = sz(a2);
rep(i, 0, m - 1) {
if (ma[a2[i]] < l) {
cout << "No" << endl;
return;
}
l = max(l, ma[a2[i]]);
}
cout << "Yes" << endl;
return;
}
|
C
题目大意：Alice和Bob在玩游戏，一开始给定两个数 $p$ 和 $q$ ，每次当 $p>0$ 可以将 $p$ 减一，当 $q>1$ 可以将 $q$ 减一。当 $p=0$ 且 $q=1$ 时，游戏结束。如果在任意时候 $\frac{p}{q}=\frac{2}{3}$ ，则Bob获胜，反之Alice获胜，请求出胜者。
数据范围： $1 \leq p,q \leq 10^18$
思路：手玩样例，发现当 $p-2x=q-3x$ 时，Bob可以操纵获得胜利，反之Alice获得胜利。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void solve() {
ll p, q;
cin >> p >> q;
ll tot = p * 3;
ll tot2 = p + q - 1LL;
ll x = q - p;
if ((tot % 2 == 0 && tot / 2 == q) || (x > 0 && 1LL * 3 * x < q && 1LL * 2 * x < p)) {
cout << "Bob" << endl;
return;
}
cout << "Alice" << endl;
return;
}
|
D
题目大意：给定数组 $a$ ，请求出 $a_i \cdot a_j=j-i$ 的下标对 $(i,j)$ 数量。
数据范围：$2 \leq n \leq 2 \cdot 10^5, 1 \leq a_i \leq 10^9$ 。
思路：这道题，由于左边的乘法式子并没有什么好的性质，因此考虑如何降低复杂度。
我的第一思路是，通过式子进行放缩然后求解，发现会被 $1,n,\ldots,1\ldots,1$ 卡掉。
然后，就开始瞪，发现可以用调和级数来枚举，但是还是被 $1,\ldots,1$ 卡掉。
刚好早上刚学过根号分治，于是就往这方面想了，这也是启发一个思路，就是根号复杂度是一个很好的复杂度（这句话不能给伊人看到，毕竟我还是黑子）。
可以看出当 $a_i$ 较大的时候，使用调和级数枚举右维护左，一次操作的复杂度为 $O(\frac{n}{a_i})$ 。
然后，当 $a_i$ 较小的时候，完全可以直接枚举一遍，操作复杂度为 $O(n)$ 。
设分界点为 $B$ ，有总操作复杂度为 $O(nB+(n-B) \cdot \frac{n}{B})$ 显然当 $B=\sqrt{n}$ 的时候取得最优。
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
|
void solve() {
int n;
cin >> n;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
ll ans = 0;
int B = sqrt(n);
rep(i, 1, B - 1) {
rep(j, 0, n - 1) {
ll tem = 1LL * j + 1LL * i * a[j];
if (tem < 0 || tem >= n) continue;
if (a[tem] == i) ans++;
}
}
rep(i, 0, n - 1) {
ll tem = a[i];
if (a[i] < B) continue;
while (tem <= i) {
ll tem2 = 1LL * i - tem;
if (tem2 < 0) break;
if (a[tem2] == tem / (1LL * a[i])) ans++;
tem += 1LL * a[i];
}
}
cout << ans << endl;
return;
}
|
E1
题目大意：交互题，给定一个有向无环图，有 $n$ 个顶点和 $m$ 条边（这里 $m$ 是未知数），每次通过查询 $x$ 来找出按字典序排序的所有路径中的第 $x$ 条路径，请在 $32 \cdot (n+m)$ 次查询内找出这个图中所有的边。
数据范围： $n \leq 15$ 。
思路：首先考虑有向无环图的性质，根据前置知识知道它可以被拓扑排序，且拓扑序就是按照DFS/BFS进行的排序，因此按照字典序排序，就是a/a->b/a->b->c/b这样排的。
看到32其实会很自然地想到二分，这里可以直接按照路径的前两个点（一条新边）进行二分查找。
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
|
void solve() {
int n;
cin >> n;
vector<pii> res;
rep(i, 0, n - 1) {
int las = -1;
while (true) {
int l = 1, r = (1 << 30), mid;
int ans = r;
while (l <= r) {
mid = (l + r) / 2;
vi tem = ask(mid);
if (tem.empty())
r = mid - 1;
else if (sz(tem) == 1 && tem[0] > i + 1)
r = mid - 1;
else if (sz(tem) == 1 && tem[0] <= i + 1)
l = mid + 1;
else if (sz(tem) >= 2) {
if (tem[0] < i + 1)
l = mid + 1;
else if (tem[0] > i + 1)
r = mid - 1;
else if (tem[0] == i + 1) {
if (tem[1] > las) {
r = mid - 1;
ans = mid;
} else
l = mid + 1;
}
}
}
vi tem = ask(ans);
if (sz(tem) <= 1) break;
res.emplace_back(tem[0], tem[1]);
las = tem[1];
}
}
report(res);
return;
}
|
E2
题目大意：跟上题一样，查询次数变为 $n+m$ 次，且 $n \leq 30$ 。
数据范围： $n \leq 30$ 。
思路：这里的查询次数变少了，因此肯定需要新的性质来做。
回想起，有向无环图可以在拓扑序上做DP，同时列举一下这里的字典序顺序可以发现，有很多需要跳过的部分，也就是遇到某个已经访问过点时需要跳过它的子树部分。
并且观察到，字典序相邻的两条路径，要么前者是后者的前缀（刚好增加一个顶点），要么删除一个顶点后缀，添加一个新的顶点后缀。
还没完，如果每次访问到一个已经访问的节点（指路径的最后一个顶点），直接跳过它的子树部分，那么每次访问，要么拓展一条新的边，要么跳到一个单顶点的路径，因此一共 $n+m$ 次，这里代码保证每次一定跳到单顶点路径，因此调的比较久。
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
|
void solve() {
int n;
cin >> n;
vector<pii> res;
vector<bool> pd(n, false);
vl dp(n, 1);
vi tem;
ll cnt = 1;
rep(i, 0, n - 1) {
cnt += 1LL * dp[i];
pd[i] = true;
while (true) {
tem = ask(cnt);
if (sz(tem) <= 1) {
break;
}
rep(j, 0, sz(tem) - 2) dp[tem[j] - 1] += dp[tem.back() - 1];
res.emplace_back(tem[sz(tem) - 2], tem[sz(tem) - 1]);
if (pd[tem.back() - 1]) {
cnt += dp[tem.back() - 1];
continue;
}
pd[tem.back() - 1] = true;
cnt++;
}
}
report(res);
return;
}
|
