2025.1.18——1300

---

A 1300

There are $n$ cities located on the number line, the $i$-th city is in the point $a_i$. The coordinates of the cities are given in ascending order, so $a_1<a_2<\cdots <a_n$.

The distance between two cities $x$ and $y$ is equal to $|a_x-a_y|$.

For each city $i$, let’s define the closest city $j$ as the city such that the distance between $i$ and $j$ is not greater than the distance between $i$ and each other city $k$. For example, if the cities are located in points $[0,8,12,15,20]$, then:

• the closest city to the city $1$ is the city $2$;
• the closest city to the city $2$ is the city $3$;
• the closest city to the city $3$ is the city $4$;
• the closest city to the city $4$ is the city $3$;
• the closest city to the city $5$ is the city $4$.

The cities are located in such a way that for every city, the closest city is unique. For example, it is impossible for the cities to be situated in points $[1,2,3]$, since this would mean that the city $2$ has two closest cities ($1$ and $3$, both having distance $1$).

You can travel between cities. Suppose you are currently in the city $x$. Then you can perform one of the following actions:

• travel to any other city $y$, paying $|a_x-a_y|$ coins;
• travel to the city which is the closest to $x$, paying $1$ coin.

You are given $m$ queries. In each query, you will be given two cities, and you have to calculate the minimum number of coins you have to spend to travel from one city to the other city.
Input

The first line contains one integer $t$ ($1\le t\le 10^4$) — the number of test cases.

Each test case is given in the following format:

• the first line contains one integer $n$ ($2\le n\le 10^5$);
• the second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($0\le a_1<a_2<\cdots <a_n\le 10^9$);
• the third line contains one integer $m$ ($1\le m\le 10^5$);
• then $m$ lines follow; the $i$-th of them contains two integers $x_i$ and $y_i$ ($1\le x_i,y_i\le n$; $x_i\ne y_i$), denoting that in the $i$-th query, you have to calculate the minimum number of coins you have to spend to travel from the city $x_i$ to the city $y_i$.

Additional constraints on the input:

• in every test case, for each city, the closest city is determined uniquely;
• the sum of $n$ over all test cases does not exceed $10^5$;
• the sum of $m$ over all test cases does not exceed $10^5$.

---

B 1300

In this problem, you are initially given an empty multiset. You have to process two types of queries:

1. ADD $x$ — add an element equal to $2^x$ to the multiset;
2. GET $w$ — say whether it is possible to take the sum of some subset of the current multiset and get a value equal to $w$.
   Input

The first line contains one integer $m$ ($1\le m\le 10^5$) — the number of queries.

Then $m$ lines follow, each of which contains two integers $t_i$, $v_i$, denoting the $i$-th query. If $t_i=1$, then the $i$-th query is ADD $v_i$ ($0\le v_i\le 29$). If $t_i=2$, then the $i$-th query is GET $v_i$ ($0\le v_i\le 10^9$).

---

C 1300

You are given an integer array $a_1,a_2,\dots ,a_n$, all its elements are distinct.

First, you are asked to insert one more integer $a_{n+1}$ into this array. $a_{n+1}$ should not be equal to any of $a_1,a_2,\dots ,a_n$.

Then, you will have to make all elements of the array equal. At the start, you choose a positive integer $x$ ($x>0$). In one operation, you add $x$ to exactly one element of the array. Note that $x$ is the same for all operations.

What’s the smallest number of operations it can take you to make all elements equal, after you choose $a_{n+1}$ and $x$?
Input

The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($1\le n\le 2\cdot 10^5$).

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($-10^9\le a_i\le 10^9$). All $a_i$ are distinct.

The sum of $n$ over all testcases doesn’t exceed $2\cdot 10^5$.

---

D 1300

Vlad found an array $a$ of $n$ integers and decided to sort it in non-decreasing order.

To do this, Vlad can apply the following operation any number of times:

• Extract the first element of the array and insert it at the end;
• Swap that element with the previous one until it becomes the first or until it becomes strictly greater than the previous one.

Note that both actions are part of the operation, and for one operation, you must apply both actions.

For example, if you apply the operation to the array [$4,3,1,2,6,4$], it will change as follows:

• [$4,3,1,2,6,4$];
• [$3,1,2,6,4,4$];
• [$3,1,2,6,4,4$];
• [$3,1,2,4,6,4$].

Vlad doesn’t have time to perform all the operations, so he asks you to determine the minimum number of operations required to sort the array or report that it is impossible.

---

E 1300

Yarik has already chosen $n$ notes that he wants to use in his new melody. However, since their integers can be very large, he has written them down as an array $a$ of length $n$, then the note $i$ is $b_i=2^{a_i}$. The integers in array $a$ can be repeated.

The melody will consist of several combinations of two notes. Yarik was wondering how many pairs of notes $b_i,b_j$ $(i<j)$ exist such that the combination $(b_i,b_j)$ is equal to the combination $(b_j,b_i)$. In other words, he wants to count the number of pairs $(i,j)$ $(i<j)$ such that $b_i^{b_j}=b_j^{b_i}$. Help him find the number of such pairs.
Input

The first line of the input contains one integer $t$ ($1\le t\le 10^4$) — the number of test cases.

The first line of each test case contains one integer $n$ ($1\le n\le 2\cdot 10^5$) — the length of the arrays.

The next line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$) — array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

---

------------------------思考------------------------

• 前缀维护信息+二进制/充分性+数学+发现结论+配对优化

---

A

1. 前缀维护信息，区间询问。
2. 思考点是如何计算前缀。

---

B

1. 充分性：判断是否可以组成时，枚举每一位进行判断。
2. 思考点是判断某位是否可以被组成。

---

C

1. 将一数组元素任意加某一确定数，致所有数相同。加的数为所有数 $gcd$ 操作次数最少。
2. 之前做过类似的题，但想不到为什么这样思考。自己数学推一下就想明白了。
3. 至于 $a[i+1]$ ，一开始出了假思路 $a[n]+g/a[n]-g$ 。实际最大值减某个倍数的最大公约数才是最优解。

---

D

1. 模拟一下，观察发现结论即可。

---

E

1. 除了相同的情况，二进制数中仅有2⁴==4²，统计对数，维护信息扫一遍即可。

---

------------------------代码------------------------

A

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // attention: interactive/debug
#define el cout << endl
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
#define bugv(VEC, ST)                     \for (int i = ST; i < VEC.size(); i++) \cout << VEC[i] << ' ';            \el;void _();
signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cout << fixed << setprecision(10);int T = 1;cin >> T;while (T--)_();return 0;
}void _()
{int n;cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i++)cin >> a[i];vector<int> pre(n + 1), suf(n + 2);auto closest = [&](int u, int r, int l){return abs(a[u] - a[r]) <= abs(a[u] - a[l]);};for (int i = 2; i <= n; i++){pre[i] = a[i] - a[i - 1];if (i == 2 || closest(i - 1, i, i - 2))pre[i] = 1;pre[i] += pre[i - 1];}for (int i = n - 1; i; i--){suf[i] = a[i + 1] - a[i];if (i == n - 1 || closest(i + 1, i, i + 2))suf[i] = 1;suf[i] += suf[i + 1];}// bugv(pre, 1);int q;cin >> q;while (q--){int st, ed;cin >> st >> ed;int res = pre[ed] - pre[st];if (st > ed)res = suf[ed] - suf[st];cout << res << endl;}
}

---

B

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // attention: interactive/debug
#define el cout << endl
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
#define bugv(VEC, ST)                     \for (int i = ST; i < VEC.size(); i++) \cout << VEC[i] << ' ';            \el;void _();
signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cout << fixed << setprecision(10);int T = 1;// cin >> T;while (T--)_();return 0;
}void _()
{int q;cin >> q;vector<int> x(32);while (q--){int op, v;cin >> op >> v;if (op == 1)x[v]++;else{auto t = x;bool f = 1;for (int i = 0; v >> i; i++)if (v >> i & 1){int ned = 1, j = i;for (int j = i; ned && j >= 0; j--, ned <<= 1){int has = min(t[j], ned);t[j] -= has, ned -= has;}if (ned)f = 0;}cout << (f ? "YES" : "NO") << endl;}}
}

---

C

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // attention: interactive/debug
#define el cout << endl
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
#define bugv(VEC, ST)                     \for (int i = ST; i < VEC.size(); i++) \cout << VEC[i] << ' ';            \el;void _();
signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cout << fixed << setprecision(10);int T = 1;cin >> T;while (T--)_();return 0;
}void _()
{int n;cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i++)cin >> a[i], a[i] += 1e9;sort(a.begin() + 1, a.end());int g = 0;for (int i = 2; i <= n; i++)g = __gcd(g, a[i] - a[i - 1]);if (!g)g = 1;map<int, bool> has;for (int i = 1; i <= n; i++)has[a[i]] = 1;for (int st = a[n] - g;; st -= g)if (!has[st]){a[0] = st;break;}int res = 0;for (auto v : a)res += (a[n] - v) / g;cout << res << endl;
}
// void _()
// {
//     int n;
//     cin >> n;
//     vector<int> a(n + 1);
//     for (int i = 1; i <= n; i++)
//         cin >> a[i], a[i] += 1e9;
//     sort(a.begin() + 1, a.end());
//     int g = 0;
//     for (int i = 2; i <= n; i++)
//         g = __gcd(g, a[i] - a[i - 1]);
//     if (!g)
//         g = 1;
//     bool f = 1;
//     for (int i = 1; i <= n; i++)
//         if (a[i] == a[n] - g)
//             f = 0;
//     a[0] = f ? a[n] - g : a[n] + g;
//     int mx = max(a[0], a[n]);
//     int res = 0;
//     for (auto v : a)
//         res += (mx - v) / g;
//     cout << res << endl;
// }

---

D

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // attention: interactive/debug
#define el cout << endl
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
#define bugv(VEC, ST)                     \for (int i = ST; i < VEC.size(); i++) \cout << VEC[i] << ' ';            \el;void _();
signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cout << fixed << setprecision(10);int T = 1;cin >> T;while (T--)_();return 0;
}void _()
{int n;cin >> n;vector<int> a(n);int mn = 1e10, id = -1;for (int i = 0; i < n; i++){int &x = a[i];cin >> x;if (x < mn)mn = x, id = i;}bool f = 1;for (int i = id + 1; i < n; i++)if (a[i] < a[i - 1])f = 0;cout << (f ? id : -1) << endl;
}

---

E

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // attention: interactive/debug
#define el cout << endl
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
#define bugv(VEC, ST)                     \for (int i = ST; i < VEC.size(); i++) \cout << VEC[i] << ' ';            \el;void _();
signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cout << fixed << setprecision(10);int T = 1;cin >> T;while (T--)_();return 0;
}void _()
{int n;cin >> n;int res = 0;map<int, int> cnt;while (n--){int x;cin >> x;res += cnt[x];if (x == 1)res += cnt[2];if (x == 2)res += cnt[1];cnt[x]++;}cout << res << endl;
}

---