比赛链接
B - Magical Subsequence
题意：给一个长度为 \(n\) 的数列 \(A_i\)，选取其中 \(m\) 项 \(A_{b_1},
A_{b_2},\cdots, A_{b_m}\) 且满足：
- 要求 \(m\) 为偶数；
- 要求 \(A_{b_1}+A_{b_2}=A_{b_3}+A_{b_4}=\cdots=A_{b_{m-1}}+A_{b_m}\)。
求最大的 \(m\)。
数据范围：\(n\le 10^5, 1\le A_i\le
100\)。
展开题解
注意到 \(1\le A_i\le
100\)，我们可以枚举 \(A_{b_1}+A_{b_2}=v\) 的值。对于一个 \(A_i\)，如果我们把它作为 \(A_{b_x}+A_{b_{x+1}}\) 的前一项，那么后一项
\(A_{b_{x+1}}\) 需满足：值等于 \(v-A_i\) 且 \(b_{x+1}>i\)。贪心地，我们选择 \(b_{x+1}\)
尽量小的那个。我们对每个值维护一个
vector，那么二分编号即可。于是我们得到了若干条线段，问题转化为选取最多条线段，互不相交，这是一个经典的贪心问题。
时间复杂度 \(O(Vn\log n)\)，其中
\(V\) 为值域上界。
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
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
constexpr int MAXN = 1e5 + 5;
constexpr int MAXV = 101;
int n, A[MAXN], minv, maxv;
vector<int> V[MAXV];
struct Seg {
int l, r;
};
bool operator < (Seg a, Seg b) {
return a.r < b.r;
}
int check(int v) {
vector<Seg> seg;
for(int i = 1; i <= n; i++) {
int op = v - A[i];
if(op < minv || op > maxv)
continue;
vector<int>::iterator it = upper_bound(V[op].begin(), V[op].end(), i);
if(it != V[op].end()) {
seg.push_back({i, *it});
}
}
if(seg.empty())
return 0;
sort(seg.begin(), seg.end());
int lst = 0, ans = 0;
for(auto v : seg) {
if(v.l > lst) {
++ans;
lst = v.r;
}
}
return 2 * ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
minv = 200;
for(int i = 1; i <= n; i++) {
cin >> A[i];
V[A[i]].push_back(i);
minv = min(minv, A[i]);
maxv = max(maxv, A[i]);
}
int ans = 0;
for(int v = 2 * minv; v <= 2 * maxv; v++)
ans = max(ans, check(v));
cout << ans << endl;
return 0;
}
|
D - Math master
题意：给出一个分数 \(\dfrac{p}{q}\)，要求在十进制下，划去 \(p\) 和 \(q\)
中相同种类、个数的数字，并保持分数值不变。求最小表示（使得 \(p\) 尽量小）。
例如，\(\dfrac{163}{326}\) 同时划去
\(\lbrace 3,6\rbrace\) 可以得到 \(\dfrac{1}{2}\) 为最简。
数据范围：\(0<p,q<2^{63}\)。
展开题解
在十进制下， \(p\) 至多有 \(\lg p\) 位。枚举删去哪些位，至多有 \(2^{\lg p}\) 种。代入 \(p<2^{63}\) 计算，至多有 \(511683\) 种情况。所以直接枚举删去哪些位，将
\(p\) 删成 \(x\)；再根据 \(p/q=x/y\) 直接计算得到 \(y\)，然后判断即可。
时间复杂度 \(O(2^{\lg p}\cdot poly(\lg
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| #include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
constexpr int MAX = 19;
ll P, Q, p10[MAX];
int delp[MAX], nump[MAX], _p, U;
int delq[MAX], numq[MAX], _q, more0;
ll ansx, ansy;
void initdel() {
for(int i = 0; i <= 9; i++)
delp[i] = delq[i] = 0;
more0 = 0;
}
bool equaldel() {
for(int i = 1; i <= 9; i++)
if(delp[i] != delq[i])
return 0;
return delq[0] <= delp[0] && delp[0] <= delq[0] + more0;
}
void work() {
cin >> P >> Q;
ll tmpP = P, tmpQ = Q;
_p = _q = 0;
while(tmpP) {
nump[_p++] = tmpP % 10;
tmpP /= 10;
}
while(tmpQ) {
numq[_q++] = tmpQ % 10;
tmpQ /= 10;
}
ansx = P, ansy = Q;
U = 1 << _p;
for(int S = 0; S < U; S++) {
initdel();
ll x = 0;
int cnt = 0;
for(int i = 0; i < _p; i++)
if((S >> i) & 1) {
x += p10[cnt] * nump[i];
++cnt;
} else {
delp[nump[i]]++;
}
if(x == 0)
continue;
__int128 M = (__int128)x * Q;
if(M % P != 0)
continue;
ll y = (ll)(M / P), tmpy = y;
int tot = 0;
while(tmpy && tot < _q) {
int y0 = tmpy % 10;
while(tot < _q && numq[tot] != y0) {
delq[numq[tot]]++;
tot++;
}
if(tot >= _q)
break;
tmpy /= 10;
tot++;
}
if(tmpy)
continue;
while(tot < _q) {
if(numq[tot] != 0)
delq[numq[tot]]++;
else more0++;
tot++;
}
if(equaldel()) {
if(x < ansx)
ansx = x, ansy = y;
}
}
cout << ansx << ' ' << ansy << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
p10[0] = 1;
for(int i = 1; i < MAX; i++)
p10[i] = p10[i-1] * 10;
int n;
cin >> n;
while(n--)
work();
return 0;
}
|
E - Power and Modulo
题意：给一个长度为 \(n\) 的数列 \(A_i\)，问是否存在唯一的 \(M\ge 1\) 满足 \(\forall i\in\lbrace 1, 2, \cdots, n\rbrace ,
A_i=2^{i-1}\bmod M\)。
数据范围：\(1\le n\le 10^5\)，\(0\le A_i\le 10^9\)。
题解1（愚蠢的原思路）
我们看，\(A_i=2^{i-1}\bmod M\)
是什么意思。一方面，由于 \(2^{i-1}\bmod
M\in[0, M-1]\)，我们知道 \(0\le A_i\le
M-1\)，故有 \(M> \max
A_i\)。
另一方面，我们知道 \(M\mid
(A_i-2^{i-1})\)，故 \(M\mid
\gcd(A_i-2^{i-1})\)。我们先求出 \(\gcd(A_i-2^{i-1})\) 即可。在 \(n\) 较小时，\(A_i-2^{i-1}\) 可能全为 \(0\)，这时任意大于 \(A_i\)
最大值的数都可以。否则，我们找到第一个 \(A_i-2^{i-1}\) 非零的数（因为 \(A_i\le 10^9\) 而 \(2^{i-1}\)
增长很快，这个数注定不会太大），把它作为 \(M_0\)；然后考虑它和下一个数的 \(\gcd\)，如为 \(\gcd(M_0, 2^{j-1}-A_j)\)。根据 \(\gcd\) 的性质，我们只需计算 \(\gcd(M_0, (2^{j-1}-A_j)\bmod
M)\)，快速幂计算第二项，再欧几里得即可。最后得到的 \(M\) 就是最大的可能的 \(M\) 了，其余可能的 \(M\) 都是它的因子。再判断是否满足 \(M>\max A_i\) 即可。
那么怎么判断 \(M\)
是否唯一呢，只要让 \(M\) 除去 \(M\) 最小的非 1 因子即可。再判断这个数 \(M'\) 是否大于 \(\max A_i\) 即可。时间复杂度 \(O(n\log 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
constexpr int MAXN = 1e5 + 5;
ll qpow(ll a, ll n, ll M) {
ll ret = 1;
for(; n; a = a * a % M, n >>= 1)
if(n & 1)
ret = ret * a % M;
return ret % M;
}
ll gcd(ll a, ll b) {
return !b ? a : gcd(b, a % b);
}
int n;
ll A[MAXN], g, mxv;
void work() {
cin >> n;
g = mxv = 0;
for(int i = 1; i <= n; i++)
cin >> A[i], mxv = max(mxv, A[i]);
for(int i = 1; i <= n; i++)
if(g == 0) {
g = abs((1ll << (i-1)) - A[i]);
} else {
g = gcd(g, (qpow(2, i-1, g) - A[i]) % g + g);
}
if(g <= mxv) {
cout << -1 << '\n';
return ;
}
if(g == 1) {
cout << g << '\n';
return ;
}
ll g2 = 0;
for(ll i = 2; i * i <= g; i++)
if(g % i == 0) {
g2 = g / i;
break;
}
if(!g2)
g2 = 1;
if(g2 <= mxv) {
cout << g << '\n';
} else {
cout << -1 << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T--)
work();
return 0;
}
|
题解2（一个比较好的做法）
分 \(A_1\) 三种情况讨论：
- 如果 \(A_1=0\)，那么 \(1\bmod M=0\)，故 \(M=1\)，检测其它的 \(A_i(i\le 2)\) 是否全为 \(0\) 即可。
- 如果 \(A_1\le 2\)，那么 \(1\bmod M=A_1\le 2\)，无解。
- 如果 \(A_1=1\)，我们寻找不满足
\(A_{i+1}=2A_i\) 的最小的 \(i\)，那么我们知道：\(A_{i+1}=2A_i\bmod
M\)。因为根据递推式，\(A_i=2^{i-1}=2^{i-1}\bmod M\)，故 \(M>A_i\)，于是 \(2A_i\bmod M\) 要么等于 \(2A_i\) 要么等于 \(2A_i-M\)。由于 \(A_{i+1}\ne 2A_i\)，故 \(A_{i+1}=2A_i-M\)，即确定了 \(M=2A_i-A_{i+1}\)。
再从头判断一遍即可。
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include <algorithm>
#include <iostream>
using namespace std;
constexpr int MAXN = 1e5 + 5;
int n, A[MAXN];
void work() {
cin >> n;
for(int i = 1; i <= n; i++)
cin >> A[i];
if(A[1] == 0) {
bool fl = 1;
for(int i = 1; i <= n; i++)
if(A[i] != 0) {
fl = 0;
break;
}
if(fl)
cout << 1 << '\n';
else
cout << -1 << '\n';
return ;
} else if(A[1] >= 2) {
cout << -1 << '\n';
return ;
} else {
int M = -1;
for(int i = 1; i < n; i++) {
if(2 * A[i] != A[i+1]) {
M = 2 * A[i] - A[i+1];
break;
}
}
if(M == -1) {
cout << -1 << '\n';
return ;
}
int fl = 1;
for(int i = 1; i < n; i++)
if(2 * A[i] % M != A[i+1]) {
fl = 0;
break;
}
if(fl)
cout << M << '\n';
else
cout << -1 << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T--)
work();
return 0;
}
|
J - Local Minimum
签到水题，不写题意和题解了，给个代码。
展开代码
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
| #include <algorithm>
#include <iostream>
using namespace std;
constexpr int MAXN = 1e3 + 5;
constexpr int INF = 0x3f3f3f3f;
int n, m, A[MAXN][MAXN], row[MAXN], col[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for(int i = 1; i <= max(n, m); i++)
row[i] = col[i] = INF;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) {
cin >> A[i][j];
row[i] = min(row[i], A[i][j]);
col[j] = min(col[j], A[i][j]);
}
int ans = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(A[i][j] == row[i] && A[i][j] == col[j])
ans++;
cout << ans << endl;
return 0;
}
|