1177 字
3 分钟
Atcoder_Beginner_Contest_478(A~E题)
2026-10-10
浏览量 109 · 访客 13

壁纸链接
题目链接:https://atcoder.jp/contests/abc478/tasks

A - Grapes#

每完成一轮长度为NN的分配,所有位置都会得到11个。将MM写为M=Nq+rM=Nq+r,其中q=⌊M/N⌋q=\lfloor M/N\rfloor、r=M mod Nr=M\bmod N,则完整的qq轮使每个位置都得到qq个,剩余rr个依次分配给前rr个位置。因此编号不超过rr时输出q+1q+1,其余位置输出qq即可。时间复杂度为O(N)O(N)。

void solved(){
int m, n; cin >> n >> m;
int rest = m % n;
for(int i = 1; i <= n;i++){
if(rest >= i){
cout << m / n + 1 << '\n';
}
else cout << m / n << '\n';
}
}

B - Topping#

第ii项的成本为ii,收益为AiA_i,需要选择恰好三个不同下标,使成本之和不超过VV且收益之和最大。由于N≤100N\leq100,可以直接枚举所有i<j<ki<j<k,检查i+j+k≤Vi+j+k\leq V,并用Ai+Aj+AkA_i+A_j+A_k更新答案。严格递增的下标既保证三项互不相同,也保证每种组合只枚举一次。时间复杂度为O(N3)O(N^3)。

void solved(){
int n, v; cin >> n >> v;
vector<int> a(n + 1);
for(int i = 1; i <= n;i++){
cin >> a[i];
}
int ans = 0;
for(int i = 1; i <= n;i++){
for(int j = i + 1; j <= n;j++){
for(int k = j + 1; k <= n;k++){
if(i + j + k <= v){
ans = max(ans, a[i] + a[j] + a[k]);
}
}
}
}
cout << ans << '\n';
}

C - Sort Subarray#

先将原数组复制并排序,得到目标数组BB。设所有满足Ai≠BiA_i\neq B_i的位置中,最左和最右的下标分别为leftleft和rightright。一次操作只能改变所选区间内部的元素,因此该区间必须包含所有错位位置,必要条件为right−left+1≤Kright-left+1\leq K。

这个条件也是充分的。因为[left,right][left,right]之外的元素已经与BB相同,而A,BA,B整体包含相同的元素及出现次数,所以区间内部的元素也恰好对应BB的同一区间。将其排序即可恢复目标顺序。若区间长度小于KK,可以在数组范围内向两侧扩展到长度恰好为KK;扩展部分原本就与BB相同,排序后仍会得到目标数组。

若没有错位位置,则数组已经有序,对任意长度为KK的子数组排序都不会改变结果,仍然输出Yes。排序的时间复杂度为O(Nlog⁡N)O(N\log N)。

void solved(){
int n, k; cin >> n >> k;
vector<int> a(n + 1);
for(int i = 1; i <= n;i++){
cin >> a[i];
}
vector<int> b = a;
sort(b.begin(), b.end());
int left = -1, right = -1;
for(int i = 1; i <= n; i++){
if(a[i] != b[i]){
if(left == -1) left = i;
right = i;
}
}
if(left == -1) cout << "Yes" << '\n';
else {
if(right - left + 1 <= k) cout << "Yes" << '\n';
else cout << "No" << '\n';
}
}

D - Range Set Insertion Query#

集合中同一个值只会计数一次,因此不能直接将每次操作都视为区间加11。对于固定的值XX,它对第ii个集合的贡献为11,当且仅当ii被至少一个插入XX的区间覆盖。于是可以先按XX分组,分别求每组区间的并集。

将同组区间按左端点排序,依次合并重叠或相邻的区间。若当前区间左端点ll不超过上一个合并区间右端点加11,就更新右端点;否则建立新的区间。合并后,同一个值对应的各段互不重叠,每个位置对该值最多计数一次。

对所有合并后的区间[l,r][l,r]执行差分:令diffldiff_l加11,当r<Nr<N时令diffr+1diff_{r+1}减11。最后求差分数组的前缀和,即可得到每个集合中不同元素的数量。所有分组排序的总时间复杂度为O(Qlog⁡Q)O(Q\log Q)。

void solved(){
int n, q;
cin >> n >> q;
vector<vector<pii>> a(q);
for(int i = 0; i < q;i++){
int l, r, x;
cin >> l >> r >> x;
x--;
a[x].push_back({l, r});
}
vector<int> diff(n + 1);
vector<pii> merged;
for(int i = 0;i < q;i++){
if(a[i].empty()) continue;
sort(a[i].begin(), a[i].end());
merged.clear();
for(auto [l, r] : a[i]){
if(merged.empty() || l > merged.back().second + 1)
merged.push_back({l, r});
else merged.back().second = max(merged.back().second, r);
}
for(auto [l, r] : merged){
if(r + 1 <= n) diff[r + 1]--;
diff[l]++;
}
}
for(int i = 1; i <= n;i++){
diff[i] += diff[i - 1];
cout << diff[i] << " ";
}
cout << '\n';
}

E - lt and le#

由于AiA_i为整数,两类约束可以统一写为Av≥Au+tA_v\geq A_u+t:t=0t=0对应不严格递增,t=1t=1对应至少增加11。为每条约束建立有向边u→vu\to v,边权为tt,问题就转化为在有向图上构造满足所有边约束的整数值。

一条有向路径上的约束累加后,路径终点的值不会小于起点的值。因此同一个强连通分量中的任意两个顶点互相可达,它们的值必须相等。若某条权值为11的边位于同一强连通分量内,就会要求两个相等的值严格递增,产生矛盾;否则分量内部全部为权值00的边,可以统一赋值。

代码使用Kosaraju算法求强连通分量:先在原图上DFS并记录退出顺序,再按退出顺序的逆序遍历反图,确定每个顶点所属的分量。将每个分量缩成一个点后,得到DAG,分量之间保留原约束的边权。

令dpcdp_c表示分量cc的取值,初始全部设为11。按拓扑序遍历缩点图,对于边u→vu\to v、权值tt,执行 dpv=max⁡(dpv,dpu+t)dp_v=\max(dp_v,dp_u+t)。 当vv被处理时,所有前驱的约束都已经传递到它,因此最终每条边都满足要求。这个过程等价于求以任意分量为起点、初值为11的DAG最长路。

设分量数为CC,DAG中的路径最多包含C−1C-1条边,且每条边权至多为11,所以1≤dpc≤C≤N1\leq dp_c\leq C\leq N,也满足题目对数值范围的要求。最后令Ai=dpbelongiA_i=dp_{belong_i}即可。求强连通分量、缩点和拓扑转移的总时间复杂度为O(N+Q)O(N+Q),空间复杂度为O(N+Q)O(N+Q)。

void solve(){
int n, q; cin >> n >> q;
vector<vector<int>> g(n + 1), rg(n + 1);
vector<tuple<int, int, int>> edges;
for(int i = 1; i <= q;i++){
int t, u, v; cin >> t >> u >> v;
g[u].push_back(v);
rg[v].push_back(u);
edges.push_back({t, u, v});
}
//第一次dfs:求退出顺序
vector<int> vis(n + 1, 0);
vector<int> order;
auto dfs1 = [&](auto&& self, int u) -> void {
vis[u] = 1;
for(auto v : g[u])
if(!vis[v]) self(self, v);
order.push_back(u);
};
for(int i = 1; i <= n;i++)
if(!vis[i]) dfs1(dfs1, i);
reverse(order.begin(), order.end());
//第二遍DFS:反图求 SCC
vector<int> belong(n + 1, 0);
int sccCnt = 0;
auto dfs2 = [&](auto&& self, int u, int id) -> void {
belong[u] = id;
for(auto v : rg[u])
if(!belong[v]) self(self, v, id);
};
for(auto u : order){
if(belong[u]) continue;
sccCnt++;
dfs2(dfs2, u, sccCnt);
}
//缩点建DAG
vector<vector<pii>> dag(sccCnt + 1);
vector<int> indeg(sccCnt + 1, 0);
for(auto [t, u, v] : edges){
int x = belong[u];
int y = belong[v];
if(x == y){
if(t == 1){
cout << "No" << '\n';
return;
}
continue;
}
dag[x].push_back({y, t});
indeg[y]++;
}
//拓扑排序 + DAG 最长路
queue<int> que;
vector<int> dp(sccCnt + 1, 1);
for(int i = 1; i <= sccCnt;i++){
if(indeg[i] == 0) que.push(i);
}
while(!que.empty()){
int u = que.front();
que.pop();
for(auto [v, w] : dag[u]){
dp[v] = max(dp[v], dp[u] + w);
indeg[v]--;
if(indeg[v] == 0) que.push(v);
}
}
cout << "Yes" << '\n';
for(int i = 1; i <= n;i++){
cout << dp[belong[i]] << (i == n ? '\n' : ' ');
}
}

个人模板:

#include <bits/stdc++.h>
#include <exception>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define mod 998244353
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll fast_pow(ll a, ll b, ll MOD){
ll ans = 1;
while(b){
if(b & 1) ans = (ans * a) % MOD;
b >>= 1;
a = (a * a) % MOD;
}
return ans;
}
vector<ll> get_inverse(ll n, ll MOD){
vector<ll> inverse(n + 1, 0);
inverse[1] = 1;
for(int i = 2; i <= n;i++){
inverse[i] = MOD - (MOD / i) * inverse[MOD % i] % MOD;
}
return inverse;
}
struct DSU{
vector<int> fa, sz;
DSU(int n){
fa.resize(n + 1);
sz.resize(n + 1, 1);
for(int i = 1; i <= n;i++){
fa[i] = i;
}
}
int find(int x){
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
bool merge(int x, int y){
x = find(x);
y = find(y);
if(x == y) return false;
if(sz[x] > sz[y]) swap(x, y);
fa[y] = x;
sz[x] += sz[y];
return true;
}
};
void solve(){
}
signed main(){
ios::sync_with_stdio(false),
cin.tie(nullptr), cout.tie(nullptr);
signed _ = 1;
//cin >> _;
while(_--){
solve();
}
return 0;
}
分享

如果这篇文章对你有帮助,欢迎分享给更多人!

Atcoder_Beginner_Contest_478(A~E题)
https://mkrari.cn/posts/abc_478/
作者
Mkrari
发布于
2026-10-10
许可协议
CC BY-NC-SA 4.0