Codeforces Round 918 (Div. 4)
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
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int a, b, c;
cin >> a >> b >> c;
if (a == b)
cout << c << '\n';
else if (a == c)
cout << b << '\n';
else
cout << a << '\n';
}
int main()
{
cin.tie(0)->ios::sync_with_stdio(false);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}B
思路
输出出现次数为 \(2\) 的字符
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
#include <bits/stdc++.h>
using namespace std;
void solve()
{
map<char, int> mp;
for (int i = 0; i < 9; i++)
{
char ch;
cin >> ch;
mp[ch]++;
}
for (auto &x : mp)
{
if (x.second == 2)
cout << x.first << endl;
}
}
int main()
{
cin.tie(0)->ios::sync_with_stdio(false);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}C
思路
累加所有的方块数，通过二分判断是不是平方数
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
int n;
cin >> n;
ll sum = 0;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
sum += x;
}
ll l = 1, r = 1e9, ans = 0;
while (l <= r)
{
ll mid = (l + r) >> 1;
if (mid * mid >= sum)
ans = mid, r = mid - 1;
else
l = mid + 1;
}
if (ans * ans == sum)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
int main()
{
cin.tie(0)->ios::sync_with_stdio(false);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}D
思路
在除了第一个的每一个 a 或者 e 的前一个字符之前加个 . ，直接判断下两个字符是不是 a 或者 e 是就加点即可
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
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
string s;
cin >> n >> s;
for (int i = 0; i < n - 2; i++)
{
cout << s[i];
if (s[i + 2] == 'a' || s[i + 2] == 'e')
cout << '.';
}
cout << s[n - 2] << s[n - 1] << endl;
}
int main()
{
cin.tie(0)->ios::sync_with_stdio(false);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}E
思路
将奇偶不同的玻璃杯容量异号，易知如果这个区间满足条件，则区间和为 \(0\) 。通过前缀和即可判断。
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
int n;
cin >> n;
vector<ll> a(n);
for (int i = 0; i < n; i++)
{
cin >> a[i];
if (i & 1)
a[i] = -a[i];
}
partial_sum(a.begin(), a.end(), a.begin());
set<ll> st;
for (int i = 0; i < n; i++)
{
if (st.count(a[i]) || a[i] == 0)
{
cout << "YES" << endl;
return;
}
st.insert(a[i]);
}
cout << "NO" << endl;
}
int main()
{
cin.tie(0)->ios::sync_with_stdio(false);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}F
思路
易知，如果两个人会打招呼则一个人行走的区间一定被另一个人包含。
将右端点排序，然后从左端点最小的区间开始遍历，二分查找到右端点在数组的下标即有多少区间的右端点更小，然后删除这个右端点，使数组内的区间都是左端点大于当前的左端点的。
累加查找到的下标即为答案
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
int n;
cin >> n;
map<int, int> mp;
vector<int> v;
for (int i = 0; i < n; i++)
{
int a, b;
cin >> a >> b;
mp[a] = b;
v.push_back(b);
}
ll ans = 0;
sort(v.begin(), v.end());
for (auto it : mp)
{
auto pos = lower_bound(v.begin(), v.end(), it.second);
ans += (pos - v.begin());
v.erase(pos);
}
cout << ans << endl;
}
int main()
{
cin.tie(0)->ios::sync_with_stdio(false);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}G
思路
优先队列优化的 \(Dijkstra\) 。
dis[u][t] 表示从 \(1\) 到 \(u\) 使用 \(t\) 城市的自行车的所花费的时间。
每次到新的城市，如果这里的自行车更优则更新自行车。d + 1LL * s[t] * w 表示到达 \(j\) 的所花费的时间。
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
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
ll d;
int u, t;
friend bool operator<(const node &a, const node &b)
{
return a.d > b.d;
}
};
void solve()
{
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> g(n + 1);
for (int i = 0; i < m; i++)
{
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
vector<int> s(n + 1);
for (int i = 1; i <= n; i++)
cin >> s[i];
vector<vector<ll>> dis(n + 1, vector<ll>(n + 1, -1));
priority_queue<node> q;
q.push({0, 1, 1});
while (q.size())
{
auto [d, u, t] = q.top();
q.pop();
if (dis[u][t] != -1)
continue;
dis[u][t] = d;
if (u == n)
{
cout << d << '\n';
return;
}
for (auto [j, w] : g[u])
{
int b = (s[j] < s[t] ? j : t);
if (dis[j][b] == -1)
q.push({d + 1LL * s[t] * w, j, b});
}
}
}
int main()
{
cin.tie(0)->ios::sync_with_stdio(false);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}Codeforces Round 918 (Div. 4)
http://xiaowhang.github.io/archives/3281088155/