Codeforces Round 929 (Div. 3)
A
思路
将所有的负数放到一起，再一起变成相反数。即将所有数的绝对值加在一起即可。
Code
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
int n;
cin >> n;
int ans = 0;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
ans += abs(x);
}
cout << ans << '\n';
}
int main()
{
cin.tie(0)->ios::sync_with_stdio(false);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}B
思路
判断所有数的和对 \(3\) 取余的结果： - 余 \(0\) ：说明已经是三的倍数，直接输出 \(0\) - 余 \(1\) ：如果存在一个数对 \(3\) 取余为 \(1\) ，则删除这个数即可，需要 \(1\) 步。若不存在，则可以让一个数 \(+2\) ，需要 \(2\) 步。 - 余 \(2\) ：直接让一个数 \(+1\) 即可，需要 \(1\) 步
Code
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
int n;
cin >> n;
vector<int> a(n);
for (int &x : a)
cin >> x;
int sum = 0;
for (int x : a)
sum += x;
int t = sum % 3;
if (t == 0)
{
cout << t << '\n';
return;
}
else if (t == 1)
{
for (auto x : a)
{
if (x % 3 == 1)
{
cout << 1 << '\n';
return;
}
}
cout << 2 << '\n';
}
else
cout << 1 << '\n';
}
int main()
{
cin.tie(0)->ios::sync_with_stdio(false);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}C
思路
因为 \(l\) 的大小不超过 \(1e6\) ，所以 \(x\) 和 \(y\) 的大小不超过 \(20\ (2^{20} = 1048576 \gt 1e6)\)
所以我们遍历所有可能用 \(set\) 对答案去重即可。（用 \(pow\) 不会超时但是不建议）
Code
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qpow(ll a, ll b, ll mod = 1e9 + 7)
{
ll res = 1;
for (; b; b >>= 1)
{
if (b & 1)
res = 1LL * res * a % mod;
a = 1LL * a * a % mod;
}
return res;
}
void solve()
{
ll a, b, l;
cin >> a >> b >> l;
set<ll> ans;
for (int x = 0; x <= 20; x++)
{
if (qpow(a, x) > l)
break;
for (int y = 0; y <= 20; y++)
{
if (qpow(b, y) > l)
break;
ll z = qpow(a, x) * qpow(b, y);
if (l % z == 0)
ans.insert(l / z);
}
}
cout << ans.size() << '\n';
}
int main()
{
cin.tie(0)->ios::sync_with_stdio(false);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}D
思路
已知，如果 \(a \lt b\)，则 \(a\%b = a\)。故我们可以将数组按升序排序。
如果最小值只有一个数，则从它开始往后取余最后的结果一定是他本身。
如果最小值不止一个，则遍历所有的数，对最小值取余。取余后的结果一定小于最小值。如果存在不为 \(0\) 的余数，则输出 \(YES\)。
Code
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++)
cin >> v[i];
sort(v.begin(), v.end());
if (v[0] != v[1])
{
cout << "YES\n";
return;
}
for (auto x : v)
{
if (x % v[0] != 0)
{
cout << "YES\n";
return;
}
}
cout << "NO\n";
}
int main()
{
cin.tie(0)->ios::sync_with_stdio(false);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}E
思路
能力提高的值是一个首项为 \(u\)，公差为 \(-1\)，的等差数列的前 \(n\) 项和，可知当 \(n = u\) 或者 \(n = u + 1\) 时取最大值。
通过前缀和的预处理加上二分搜索，我们可以快速找到最大值是在哪个赛道。由于懒得证明，采用遍历周围几个判断是否有别的情况。
Code
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll get(ll a1, ll d, ll n)
{
return n * a1 + n * (n - 1) / 2 * d;
}
void solve()
{
int n;
cin >> n;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
partial_sum(a.begin(), a.end(), a.begin());
int q;
cin >> q;
while (q--)
{
int l, u;
cin >> l >> u;
if (a[l - 1] + u >= a[n])
{
cout << n << ' ';
continue;
}
int r = lower_bound(a.begin(), a.end(), a[l - 1] + u) - a.begin();
int ans = 0;
ll ma = -0x3f3f3f3f3f3f3f3f;
for (int p = max(l, r - 2); p <= min(r + 2, n); p++)
{
if (!ans || get(u, -1, a[p] - a[l - 1]) > ma)
{
ans = p;
ma = get(u, -1, a[p] - a[l - 1]);
}
}
cout << ans << ' ';
}
cout << '\n';
}
int main()
{
cin.tie(0)->ios::sync_with_stdio(false);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}F
思路
我们可以将石头看作是不动的，那么对于机器人每次有两种行动，向下走两步和向右下角走一步（还有原地不动，对移动没有贡献故不计）。终点每次会向下移动走一步。
通过 \(BFS\) 可以求出机器人到达最后一列的步数，此时答案即为步数加上机器人和终点当前位置的距离。
Code
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
int x, y, cnt;
};
char mp[2010][2010];
int px, py;
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> mp[i][j];
px = n - 1, py = m - 1;
queue<node> q;
q.push({0, 0, 0});
vector<vector<bool>> vis(n, vector<bool>(m, false));
vis[0][0] = true;
int ans = 0x3f3f3f3f;
while (!q.empty())
{
auto [x, y, cnt] = q.front();
q.pop();
if (y == py)
{
px = (px + cnt) % n;
cout << min(n - abs(px - x), abs(px - x)) + cnt << '\n';
return;
}
if (mp[(x + 1) % n][y] == '0' && mp[(x + 2) % n][y] == '0' && !vis[(x + 2) % n][y])
{
vis[(x + 2) % n][y] = true;
q.push({(x + 2) % n, y, cnt + 1});
}
if (mp[(x + 1) % n][y + 1] == '0' && !vis[(x + 1) % n][y + 1])
{
vis[(x + 1) % n][y + 1] = true;
q.push({(x + 1) % n, y + 1, cnt + 1});
}
}
cout << -1 << '\n';
}
int main()
{
cin.tie(0)->ios::sync_with_stdio(false);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}Codeforces Round 929 (Div. 3)
http://xiaowhang.github.io/archives/4210095459/