牛客小白月赛127
约 1663 字大约 6 分钟
2026-01-17
比赛链接:https://ac.nowcoder.com/acm/contest/126634
A. Flower_Rainbow_and_You
根据题意,比较 a,b,c,d,e,f,g 的大小,输出最大所对应的值。
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s[7] = {"Red", "Orange", "Yellow", "Green", "Blue", "Indigo", "Violet"};
int st[7];
for (int i = 0; i < 7; i++)
{
cin >> st[i];
}
int lst = 0;
int v = st[0];
for (int i = 1; i < 7; i++)
{
if (st[i] > v)
{
lst = i;
v = st[i];
}
}
cout << s[lst];
return 0;
}B. Flower_Rainbow_and_Rhythm
对于每一个 ai 判断对 k 求余是否为整数,可以使用 map<int,int> 存取。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
vector<int> vi(n);
for (int i = 0; i < n; i++)
{
cin >> vi[i];
}
map<int, int> mpii;
for (int i = 0; i < n; i++)
{
mpii[vi[i] % k]++;
}
for (auto j : mpii)
{
if (j.second % 2 != 0)
{
cout << "No";
return 0;
}
}
cout << "Yes";
return 0;
}C. Flower_Rainbow_and_Wave
注意到对于长度不是 1 的奇数来说,若长度为 n,其可以得到 k=(n+1)/2 的序列 [1,2,3,⋯,k−1,k,k−1,c⋯,3,2,1];而 奇数加奇数等于偶数,所以除了 2=1+1,4=1+3 唯一成立且包含 1 长度的波形来说,不存在,其余的偶数直接使用 [1,2,3]+n 进行分解即可。
#include <bits/stdc++.h>
using namespace std;
void sol()
{
int n;
cin >> n;
if (n == 1)
{
cout << -1;
}
else if (n % 2 != 0)
{
int k = (n + 1) / 2;
for (int i = 1; i <= k; i++)
{
cout << i << " ";
}
for (int i = k - 1; i >= 1; i--)
{
cout << i << " ";
}
}
else if (n == 2 || n == 4)
{
cout << -1;
}
else
{
cout << "1 2 1 ";
int k = (n - 3 + 1) / 2;
for (int i = 1; i <= k; i++)
{
cout << i << " ";
}
for (int i = k - 1; i >= 1; i--)
{
cout << i << " ";
}
}
}
int main()
{
int t;
cin >> t;
while (t--)
{
sol();
cout << "\n";
}
return 0;
}D. Flower_Rainbow_and_Balloon
对于区间 [ℓ,r] 可以获取的最大愉悦值是 s=max(R×2+Y,Y×2+R)+2×min(W,m),其中
- R 表示红色气球个数
- Y 表示黄色气球个数
- W 表示白色气球个数
注意到 s 随着右端点右移,R/Y/W 都只增不减;左端点右移时只减不增,所以 s 单调;考虑滑动窗口队列,复杂度为 O(n):
- 左指针 l=0,右指针 r 从 0 扫到 n−1;
- 动态维护窗口内的 R、Y、W
- 每次右扩后,检查当前窗口是否满足:
max(R×2+Y,Y×2+R)+2×min(W,m)⩾k
- 如果满足,就尝试移动左指针缩小窗口,同时更新答案
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void sol()
{
int n, m;
ll k;
cin >> n >> m >> k;
string s;
cin >> s;
ll R = 0, Y = 0, W = 0;
int l = 0;
int ans = INT_MAX;
for (int r = 0; r < n; ++r)
{
if (s[r] == 'r')
R++;
else if (s[r] == 'y')
Y++;
else
W++;
while (l <= r)
{
ll base0 = 2 * R + Y;
ll base1 = 2 * Y + R;
ll base = max(base0, base1);
ll extra = 2 * min(W, (ll)m);
ll score = base + extra;
if (score >= k)
{
ans = min(ans, r - l + 1);
if (s[l] == 'r')
R--;
else if (s[l] == 'y')
Y--;
else
W--;
l++;
}
else
{
break;
}
}
}
if (ans == INT_MAX)
cout << -1 << "\n";
else
cout << ans << "\n";
}
int main()
{
int T;
cin >> T;
while (T--)
{
sol();
}
return 0;
}E. Flower_Rainbow_and_Game
由于直接求面对 2×105 的数据,枚举两个点的距离复杂度 O(n2) 肯定超时。
设节点个数为 n 对于每相邻的两个节点 u,v 构成的边,如果没有瞬移规则,所有点对的距离和在树上是经典结论:对每一条边 e,设去掉它后两边的点数是 s 和 n−s,那么这条边对总距离的贡献是 s⋅(n−s)。
把所有边的 s(n−s) 加起来,就是
SumDist=u<v∑dist(u,v).
这个用一次 DFS 求子树大小就能算出来。
其次当 a 是 b 的祖先时,原本距离是
dist(a,b)=depth[b]−depth[a],
但现在 rf(a,b)=1,也就是说,这一对要从总和里减掉
(depth[b]−depth[a])−1.
于是我们需要计算
Reduction=a∈Anc(b), a=b∑(depth[b]−depth[a]−1).
固定一个点 b,设它有 k=depth[b]个祖先(根深度记为 0),这些祖先的深度之和为∑depth[a]。那么对这个 b 的贡献是
k⋅(depth[b]−1)−∑depth[a].
在 DFS 从根往下走时,维护两样东西:
- 当前节点的深度
dep - 从根到当前节点所有祖先深度的和
sumDepAnc
到达节点 b 时:
- k=dep
- ∑depth[a]=sumDepAnc
于是累加
dep⋅(dep−1)−sumDepAnc.
总的流程为
- 建树,根设为 1。
- DFS 一次:
- 算每个节点的子树大小
sz[u],并用边贡献法累加SumDist。
- 算每个节点的子树大小
- DFS 再一次(或在第一次里顺带):
- 维护
dep和sumDepAnc,累加Reduction。
- 维护
- 输出 (SumDist−Reduction)mod998244353。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static const ll MOD = 998244353;
int n;
vector<vector<int>> adj;
vector<int> sz;
ll sd, reduc;
void dfs1(int u, int p)
{
sz[u] = 1;
for (int v : adj[u])
{
if (v == p)
continue;
dfs1(v, u);
sz[u] += sz[v];
ll s = sz[v];
sd = (sd + s * (n - s)) % MOD;
}
}
void dfs2(int u, int p, int dep, ll sumDepAnc)
{
ll c = 1LL * dep * (dep - 1) - sumDepAnc;
reduc = (reduc + c) % MOD;
for (int v : adj[u])
{
if (v == p)
continue;
dfs2(v, u, dep + 1, sumDepAnc + dep);
}
}
void sol()
{
cin >> n;
adj.assign(n + 1, {});
sz.assign(n + 1, 0);
for (int i = 0; i < n - 1; i++)
{
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
sd = 0;
reduc = 0;
dfs1(1, 0);
dfs2(1, 0, 0, 0);
ll ans = (sd - reduc) % MOD;
if (ans < 0)
ans += MOD;
cout << ans << "\n";
}
int main()
{
int T;
cin >> T;
while (T--)
{
sol();
}
return 0;
}F. Flower_Rainbow_and_Forever
赛时没做出来,但是想出来了,不过有点难构造的,这里仅提出思路:
考虑对所有数字分为 3 类:
- A 表示权值是 4 的倍数;
- B 表示权值是 uB%4=2;
- C 表示权值是奇数。
贪心地将 B 类连成一条链,剩下 A,C 两类,发现对于有 n 个 A 类节点最多可以连接 nC=(k−1)×nA 个。
std:
#include <bits/stdc++.h>
void RainbowDash()
{
int n, k;
std ::cin >> n >> k;
std ::queue<int> A, B, C;
for (int i = 1; i <= n; i++)
{
int x;
std ::cin >> x;
if (x % 4 == 0)
A.push(i);
else if (x % 2 == 0)
B.push(i);
else
C.push(i);
}
if (n == 1)
{
std ::cout << "1\n";
return;
}
int root, pre;
auto print_link = [&]() -> void
{
while (A.size())
{
std ::cout << pre << ' ' << A.front() << '\n';
pre = A.front();
A.pop();
}
while (B.size())
{
std ::cout << pre << ' ' << B.front() << '\n';
pre = B.front();
B.pop();
}
return;
};
if (C.empty())
{
if (!A.empty())
{
root = pre = A.front();
A.pop();
}
else
{
root = pre = B.front();
B.pop();
}
std ::cout << root << '\n';
print_link();
return;
}
root = pre = C.front();
C.pop();
if (A.empty())
{
std ::cout << "-1\n";
return;
}
std ::vector<std ::array<int, 2>> ok;
bool use = true;
while (!C.empty())
{
if (!C.empty() && A.empty())
{
std ::cout << "-1\n";
return;
}
ok.push_back({pre, A.front()});
pre = A.front();
A.pop();
int t;
use = true;
for (int i = 1; i <= k; i++)
{
if (C.empty())
{
use = false;
break;
}
t = C.front();
ok.push_back({pre, t});
C.pop();
}
if (use)
pre = t;
}
if (use && A.empty() && !B.empty())
{
std ::cout << "-1\n";
return;
}
std ::cout << root << '\n';
for (std ::array<int, 2> &p : ok)
std ::cout << p[0] << ' ' << p[1] << '\n';
print_link();
return;
}
signed main()
{
std ::ios ::sync_with_stdio(0);
std ::cin.tie(0);
std ::cout.tie(0);
int T = 1;
std ::cin >> T;
while (T--)
RainbowDash();
return 0;
}