A. 来！选！队！长
签到题。
由于队长的战力要乘以二，因此‘我’的队伍最大战力为 \(r1=a_1 \times 2+a_2+a_3+a_4+a_5\)，好友队伍的最小战力为 \(r2=b_1+b_2+b_3+b_4+b_5 \times 2\)。
题目问是否有可能使得‘我’的队伍战力大于好友队伍战力，因此只需判断 \(r1 > r2\) 这个条件是否成立即可。
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
| #include <bits/stdc++.h>
#define x first
#define y second
#define endl '\n'
using namespace std;
using ll = long long;
using PII = pair<int, int>;
int read(){int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-') f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
void print(int x){if (x < 0){putchar('-');x = -x;}if (x > 9) print(x / 10);putchar(x % 10 + '0');}
void solve()
{
int r1 = 0, r2 = 0;
for (int i = 0; i < 5; i++)
{
int x;
cin >> x;
r1 += x;
if (!i) r1 += x;
}
for (int i = 0; i < 5; i++)
{
int x;
cin >> x;
r2 += x;
if (i == 4) r2 += x;
}
if (r1 > r2) cout << "YES" << endl;
else cout << "NO" << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
while (T--)
{
solve();
}
return 0;
}
|
B. 抽我选的效率曲
分类讨论。
分别统计代号为 \(k\) 的歌曲数以及总歌曲数，设为 \(c1\) 和 \(c2\)。
- \(c1=0,c2 = 0\)，代表没有人选歌，输出 \(1/1000\)。
- \(c1 = 0,c2 \neq 0\)，代表有人选歌，但是没有人选代号为 \(k\) 的歌，输出 \(0/1\)。
- \(c1 \neq 0,c2 \neq 0\)，代表有人选歌，并且也有人选代号为 \(k\) 的歌，输出 \(c1/c2\)，需要注意的是，当 \(c1=2，c2=4\) 时，需要约分成 \(1/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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <bits/stdc++.h>
#define x first
#define y second
#define endl '\n'
using namespace std;
using ll = long long;
using PII = pair<int, int>;
int read(){int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-') f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
void print(int x){if (x < 0){putchar('-');x = -x;}if (x > 9) print(x / 10);putchar(x % 10 + '0');}
void solve()
{
vector<int> a(5);
for (int i = 0; i < 5; i++) cin >> a[i];
int k;
cin >> k;
int c1 = 0, c2 = 0;
for (int i = 0; i < 5; i++)
{
if (a[i] == k) c1++;
if (a[i]) c2++;
}
if (!c2) cout << "1/1000" << endl;
else if (!c1) cout << "0/1" << endl;
else
{
int g = gcd(c1, c2);
c1 /= g, c2 /= g;
cout << c1 << '/' << c2 << endl;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
|
C. 睡前床边看LIVE
可以确定的是，对于相同的颜色，对应的豆腐人的回答都是相同的。因此，颜色的种类数至少是豆腐人回答的种类数。
接下来可以豆腐人回答的种类数进行分类讨论。
- 种类数为 \(1\)，所有人回答都是一样的。若 \(\lfloor\frac{a_0}{n}\rfloor>1\)，则可以每 \(a_0\) 个为一种颜色，例如 \(2,2,2,2,2\)，颜色可以分为 \(A,A,B,B,C\)。若 \(a_0+1=n\)，则所有人都为一样的颜色即可合理分配。剩下的其他情况都为 \(Lie\)。
- 种类数为 \(2\)。首先把数组排序，此时\(a_0\) 为第一种回答，\(a_{n-1}\) 为第二种回答，设\(c_0\) 为回答是 \(a_0\) 的个数，\(c_{n-1}\) 为回答是 \(a_{n-1}\) 的个数。则当且仅当 \(c0=a_{n-1}\) 并且 \(a_0+1=a_{n-1}\) 时，才能输出 \(Other\)，其他情况全都输出 \(Lie\)。分配方案为 \(c_0\) 个回答 \(a_0\) 全部一个颜色，\(c_{n-1}\) 个回答 \(a_{n-1}\) 染成其他颜色，并且互不相同
- 种类数大于等于 \(3\)。可以发现，无法找到合法的颜色分配方案，统一输出 \(Lie\)。
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
| #include <bits/stdc++.h>
#define x first
#define y second
#define endl '\n'
using namespace std;
using ll = long long;
using PII = pair<int, int>;
int read(){int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-') f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
void print(int x){if (x < 0){putchar('-');x = -x;}if (x > 9) print(x / 10);putchar(x % 10 + '0');}
void solve()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
sort(a.begin(), a.end());
map<int, int> p;
for (int i = 0; i < n; i++) p[a[i]]++;
if (p.size() > 2) cout << "Lie" << endl;
else if (p.size() == 2)
{
int c1 = p[a[0]], c2 = p[a[n - 1]];
if (c1 == a[n - 1] && a[0] + 1 == a[n - 1]) cout << "Other" << endl;
else cout << "Lie" << endl;
}
else
{
if (n / a[0] > 1 || n - 1 == a[0]) cout << "Other" << endl;
else cout << "Lie" << endl;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
|
D. 世界树上找米库
转化题意，\(Sekai\) 是叶子节点，对于每个节点，它的权值为这个节点到最近叶子节点的距离，要求我们找到权值最大的节点，并从小到大输出节点编号。
标准的多源 \(bfs\) 问题，设 \(f_i\) 为节点 \(i\) 到最近叶子节点的距离，以每个叶子节点为起点跑一遍 \(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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| #include <bits/stdc++.h>
#define x first
#define y second
#define endl '\n'
using namespace std;
using ll = long long;
using PII = pair<int, int>;
int read(){int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-') f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
void print(int x){if (x < 0){putchar('-');x = -x;}if (x > 9) print(x / 10);putchar(x % 10 + '0');}
void solve()
{
int n;
cin >> n;
vector<vector<int>> h(n + 1);
for (int i = 0; i < n - 1; i++)
{
int u, v;
cin >> u >> v;
h[u].push_back(v), h[v].push_back(u);
}
vector<int> f(n + 1, 1e9);
auto bfs = [&](int st)
{
f[st] = 0;
queue<int> q;
q.push(st);
while (q.size())
{
int u = q.front();
q.pop();
for (auto v: h[u])
{
if (f[v] <= f[u] + 1) continue;
f[v] = f[u] + 1;
q.push(v);
}
}
};
for (int i = 1; i <= n; i++)
if (h[i].size() == 1)
bfs(i);
int maxv = 0;
vector<int> s;
for (int i = 1; i <= n; i++)
{
if (f[i] >= maxv)
{
if (f[i] > maxv) s.clear();
maxv = f[i];
s.push_back(i);
}
}
sort(s.begin(), s.end());
cout << s.size() << endl;
for (auto x: s) cout << x << ' ';
cout << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
|
E. 森友会里打音游
\(dp\)，设 \(f_i\) 为遍历到 \(i\)，并保留第 \(i\) 个物品，所需删除的最小物品数。
在进行思考前，我们需要知道枚举 \(a_i\) 的因数，所需的时间复杂度是 \(O(\sqrt{a_i})\)，而题目中 \(a_i\) 的上界为 \(n\)，因此整体复杂度应该往 \(O(n \sqrt{n})\) 去靠拢。
对于 \(a_i\)，设它的因数为 \(c_1,c_2,c_3,...,c_j\)，要分别考虑要把 \(a_i\) 的左边变成它的因数还是倍数。 * 变成因数。设左边离 \(i\) 最近因数的下标分别为 \(p_1,p_2,p_3...p_j\)，则有 \(f_i= min\{f_i,f_{p_1}+i-p_1-1,f_{p_2}+i-p_2-1,f_{p_3}+i-p_3-1,...,f_{p_j}+i-p_j-1\}\)。 * 变成倍数。由于倍数的枚举没有因数那么方便，因此，当我们处理完一个 \(f_i\) 时，可以考虑对它右边的因数进行转移。设右边离 \(i\) 最近因数的下标分别为 \(p_1,p_2,p_3,...,p_j\)，则有 \(f_{p_j}=min(f_{p_j},f_i+p_j-i-1)\)。也就是说，当我们遍历到 第 \(i\) 个物品的时候，对于把它左边的数变成它的倍数的情况，已经提前处理完成了。
最终答案为 \(\max_{1 \le i \le n} (n-(f_i + n - i))\)。
时间复杂度 \(O(n \sqrt{n})\)。
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
73
| #include <bits/stdc++.h>
#define x first
#define y second
#define endl '\n'
using namespace std;
using ll = long long;
using PII = pair<int, int>;
int read(){int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-') f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
void print(int x){if (x < 0){putchar('-');x = -x;}if (x > 9) print(x / 10);putchar(x % 10 + '0');}
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
vector<vector<int>> st(n + 1);
for (int i = n; i >= 1; i--) st[a[i]].push_back(i);
vector<int> pos(n + 1, 0), f(n + 1, n);
for (int i = 1; i <= n; i++)
{
f[i] = min(f[i], i - 1);
for (int j = 1; j <= a[i] / j; j++)
{
if (a[i] % j) continue;
f[i] = min(f[i], f[pos[j]] + i - pos[j] - 1);
f[i] = min(f[i], f[pos[a[i] / j]] + i - pos[a[i] / j] - 1);
}
st[a[i]].pop_back();
for (int j = 1; j <= a[i] / j; j++)
{
if (a[i] % j) continue;
if (st[j].size())
{
int p = st[j].back();
f[p] = min(f[p], f[i] + p - i - 1);
}
if (st[a[i] / j].size())
{
int p = st[a[i] / j].back();
f[p] = min(f[p], f[i] + p - i - 1);
}
}
pos[a[i]] = i;
}
int res = 0;
for (int i = 1; i <= n; i++) res = max(res, -f[i] + i);
cout << res << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
|
F. 这招太狠了烤学妹
首先可以注意到，如果要对一段长度为 \(x\) 的 \(o\) 序列修改 \(c\) 次，一定是均等的分成 \(c+1\) 段对分数的贡献最小，设这个切分后分数计算函数为 \(calc(x,c)\)(具体实现见代码)。
我们可以考虑先把所有 \(o\) 序列全部处理出来，然后用优先队列来进行维护，优先选择 \(calc(x,c)-calc(x,c+1)\) 最大的段。
时间复杂度 \(O(nlogn)\)。
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
73
74
75
76
77
78
79
80
81
| #include <bits/stdc++.h>
#define x first
#define y second
#define endl '\n'
using namespace std;
using ll = long long;
using PII = pair<int, int>;
int read(){int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-') f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
void print(int x){if (x < 0){putchar('-');x = -x;}if (x > 9) print(x / 10);putchar(x % 10 + '0');}
ll calc(ll x, ll c)
{
x -= c;
return (1 + x / (c + 1)) * (x / (c + 1)) / 2 * (c + 1) + x % (c + 1) * (x / (c + 1) + 1);
}
struct Node
{
ll x, c;
bool operator< (const Node &B) const
{
return calc(x, c) - calc(x, c + 1) < calc(B.x, B.c) - calc(B.x, B.c + 1);
}
};
void solve()
{
int n, k;
string s;
cin >> n >> k >> s;
priority_queue<Node> q;
int l = 0, r = 0;
while (r < n)
{
if (s[l] != s[r])
{
if (s[l] == 'o') q.push({r - l, 0});
l = r;
}
r++;
}
if (s[l] == 'o') q.push({r - l, 0});
while (k-- && q.size())
{
auto [x, c] = q.top();
q.pop();
if (c + 1 < x) q.push({x, c + 1});
}
ll res = 0;
while (q.size())
{
auto [x, c] = q.top();
q.pop();
res += calc(x, c);
}
cout << res << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
|
