
壁纸链接
题目链接:https://atcoder.jp/contests/abc478/tasks
A - Grapes
每完成一轮长度为的分配,所有位置都会得到个。将写为,其中、,则完整的轮使每个位置都得到个,剩余个依次分配给前个位置。因此编号不超过时输出,其余位置输出即可。时间复杂度为。
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
第项的成本为,收益为,需要选择恰好三个不同下标,使成本之和不超过且收益之和最大。由于,可以直接枚举所有,检查,并用更新答案。严格递增的下标既保证三项互不相同,也保证每种组合只枚举一次。时间复杂度为。
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
先将原数组复制并排序,得到目标数组。设所有满足的位置中,最左和最右的下标分别为和。一次操作只能改变所选区间内部的元素,因此该区间必须包含所有错位位置,必要条件为。
这个条件也是充分的。因为之外的元素已经与相同,而整体包含相同的元素及出现次数,所以区间内部的元素也恰好对应的同一区间。将其排序即可恢复目标顺序。若区间长度小于,可以在数组范围内向两侧扩展到长度恰好为;扩展部分原本就与相同,排序后仍会得到目标数组。
若没有错位位置,则数组已经有序,对任意长度为的子数组排序都不会改变结果,仍然输出Yes。排序的时间复杂度为。
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
集合中同一个值只会计数一次,因此不能直接将每次操作都视为区间加。对于固定的值,它对第个集合的贡献为,当且仅当被至少一个插入的区间覆盖。于是可以先按分组,分别求每组区间的并集。
将同组区间按左端点排序,依次合并重叠或相邻的区间。若当前区间左端点不超过上一个合并区间右端点加,就更新右端点;否则建立新的区间。合并后,同一个值对应的各段互不重叠,每个位置对该值最多计数一次。
对所有合并后的区间执行差分:令加,当时令减。最后求差分数组的前缀和,即可得到每个集合中不同元素的数量。所有分组排序的总时间复杂度为。
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
由于为整数,两类约束可以统一写为:对应不严格递增,对应至少增加。为每条约束建立有向边,边权为,问题就转化为在有向图上构造满足所有边约束的整数值。
一条有向路径上的约束累加后,路径终点的值不会小于起点的值。因此同一个强连通分量中的任意两个顶点互相可达,它们的值必须相等。若某条权值为的边位于同一强连通分量内,就会要求两个相等的值严格递增,产生矛盾;否则分量内部全部为权值的边,可以统一赋值。
代码使用Kosaraju算法求强连通分量:先在原图上DFS并记录退出顺序,再按退出顺序的逆序遍历反图,确定每个顶点所属的分量。将每个分量缩成一个点后,得到DAG,分量之间保留原约束的边权。
令表示分量的取值,初始全部设为。按拓扑序遍历缩点图,对于边、权值,执行 。 当被处理时,所有前驱的约束都已经传递到它,因此最终每条边都满足要求。这个过程等价于求以任意分量为起点、初值为的DAG最长路。
设分量数为,DAG中的路径最多包含条边,且每条边权至多为,所以,也满足题目对数值范围的要求。最后令即可。求强连通分量、缩点和拓扑转移的总时间复杂度为,空间复杂度为。
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 998244353typedef 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;}