ABC 451 全题解
2026-03-28 22:34:49
发布于：云南
722阅读
0回复
0点赞
ABC 450 差 1s AK，气急败坏的我顺手 AK ABC 451。
| 题号 | 个人难度 | tag（个人做法） | AC time |
|---|---|---|---|
| A | 红 | 字符串 | 2'19'' |
| B | 红 | STL | 4'24'' |
| C | 橙 | STL | 10'23'' |
| D | 黄 | 枚举、BFS | 22'33'' |
| E | 绿 | MST、BFS | 34'07'' |
| F | 蓝 | 带权 DSU | 50'54'' |
| G | 紫 | 01 Trie、线性基 | 85'19'' |
A. illegal
使用 string 类的 size() 函数或者 length() 函数判断是否为 的倍数即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
string s; cin >> s;
if(s.size() % 5 == 0) cout << "Yes";
else cout << "No";
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T = 1;
while(T--) solve();
return 0;
}
B. Personnel Change
用一个桶记录两个学期每个社团的人数，然后相减即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
map<int,int> mp1,mp2;
void solve(){
int n,m; cin >> n >> m;
for(int i = 1;i <= n;i++){
int a,b; cin >> a >> b;
mp1[a]++;
mp2[b]++;
}
for(int i = 1;i <= m;i++) cout << mp2[i] - mp1[i] << "\n";
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T = 1;
while(T--) solve();
return 0;
}
C. Understory
看到操作容易想到 multiset，它不会自动去重，而且自动排序，因此每次删除操作时只需要使用 upper_bound() 找大于 的第一个数，erase() 区间删除即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
multiset<int> se;
void solve(){
int q; cin >> q;
while(q--){
int op,h; cin >> op >> h;
if(op == 1) se.insert(h);
else{
auto it = se.upper_bound(h);
se.erase(se.begin(),it);
}
cout << se.size() << "\n";
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T = 1;
while(T--) solve();
return 0;
}
D. Concat Power of 2
由于 ，所以可以从每个 的幂出发，使用 BFS 暴力生成所有拼接数，用 set 去重，最后将集合中的数排序即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int> pw;
int d[35],mul[35];
set<int> se;
queue<int> q;
int fp(int a,int b){
int ans = 1;
while(b){
if(b & 1) ans = ans * a;
a = a * a;
b >>= 1;
}
return ans;
}
void solve(){
int n; cin >> n;
int k = 1;
while(k <= 1000000000){
pw.push_back(k);
k *= 2;
}
for(int i = 0;i < pw.size();i++){
d[i + 1] = to_string(pw[i]).size();
mul[i + 1] = fp(10LL,(int)d[i + 1]);
}
for(auto i : pw){
if(se.find(i) == se.end()){
se.insert(i);
q.push(i);
}
}
while(!q.empty()){
int u = q.front();
q.pop();
for(int i = 0;i < pw.size();i++){
int t = u * mul[i + 1] + pw[i];
if(t <= 1000000000 && se.find(t) == se.end()) {
se.insert(t);
q.push(t);
}
}
}
vector<int> t(se.begin(),se.end());
sort(t.begin(),t.end());
cout << t[n - 1];
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T = 1;
while(T--) solve();
return 0;
}
E. Tree Distance
由于是稠密图，所以我们使用 Prim。以 为边权构建最小生成树。在 MST 上跑所有点对的最短路，与输入矩阵比较即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
int a[3005][3005],minn[3005],fa[3005],d[3005];
bool vis[3005];
vector<pair<int,int>> ve[3005];
void solve(){
int n; cin >> n;
fill(minn,minn + 3001,INF);
fill(fa,fa + 3001,-1);
for(int i = 1;i <= n;i++){
for(int j = i + 1;j <= n;j++){
cin >> a[i][j];
a[j][i] = a[i][j];
}
}
minn[1] = 0;
for(int i = 1;i <= n;i++){
int v = -1;
for(int j = 1;j <= n;j++){
if(!vis[j] && (v == -1 || minn[j] < minn[v])) v = j;
}
vis[v] = 1;
if(fa[v] != -1){
ve[fa[v]].push_back(make_pair(v,minn[v]));
ve[v].push_back(make_pair(fa[v],minn[v]));
}
for(int u = 1;u <= n;u++){
if(!vis[u] && a[v][u] < minn[u]){
minn[u] = a[v][u];
fa[u] = v;
}
}
}
for(int rt = 1;rt <= n;rt++){
queue<int> q;
fill(d,d + 3001,-1);
d[rt] = 0;
q.push(rt);
while(!q.empty()){
int u = q.front();
q.pop();
for(auto [v,w] : ve[u]){
if(d[v] == -1){
d[v] = d[u] + w;
q.push(v);
}
}
}
for(int i = 1;i <= n;i++){
if(d[i] != a[rt][i]){
cout << "No";
return;
}
}
}
cout << "Yes";
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T = 1;
while(T--) solve();
return 0;
}
F. Make Bipartite 3
用带权 DSU 维护每个连通分量内的颜色关系。每个分量根节点维护 和 分别表示与根同色和异色的顶点数。当加边时：
- 若 已在同一分量，检查边是否异色，若为 则出现奇环，不可行。
- 否则合并两个分量，根据 的颜色关系计算需要翻转其中一个分量的颜色，更新合并后的计数和最小黑点数。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int fa[200005],d[200005],cnt[200005][2],tot,fl;
int get(int x,int &k){
if(fa[x] == x){
k = 0;
return x;
}
int rt = get(fa[x],k);
k ^= d[x];
fa[x] = rt;
d[x] = k;
return rt;
}
int add(int u,int v){
if(!fl) return -1;
int cu,cv,uu = get(u,cu),vv = get(v,cv);
if(uu == vv){
if((cu ^ cv) == 0){
fl = 0;
return -1;
}
return tot;
}else{
int k = cu ^ cv ^ 1;
int ou = min(cnt[uu][0],cnt[uu][1]),ov = min(cnt[vv][0],cnt[vv][1]);
fa[vv] = uu;
d[vv] = k;
if(k == 1) swap(cnt[vv][0],cnt[vv][1]);
cnt[uu][0] += cnt[vv][0];
cnt[uu][1] += cnt[vv][1];
tot = tot - ou - ov + min(cnt[uu][0],cnt[uu][1]);
return tot;
}
}
void solve(){
int n,q; cin >> n >> q;
fl = 1;
for(int i = 1;i <= n;i++){
fa[i] = i;
cnt[i][0] = 1;
cnt[i][1] = 0;
}
while(q--){
int u,v; cin >> u >> v;
cout << add(u,v) << "\n";
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T = 1;
while(T--) solve();
return 0;
}
G. Minimum XOR Walk
油 奠 以 死
完成了 异或粽子 和 线性基 以后，你就会发现他其实就是这俩玩意的结合。没做过先别着急做，看我操作。
这种典题有一些经典步骤：
- 固定一棵生成树，任意两点间的异或 walk 最小值为 与所有环的线性基组合得到的最小值。
- 所有环的异或值构成一个线性基 ，则任意两点间的最小异或值等于 ，即 在子空间 中的最小表示。
- 通过线性基可以将所有 base 向量化简为代表元，使得之间两两的异或值就是原图两点间的最小异或值。
容易将问题转化为：有多少对 满足 。那就经典了：
- 建一棵 位 01 Trie，插入时统计。
- 对每个代表元，在 Trie 中查询与它异或值 的数的个数（这一步貌似是经典数位 DP 查询）。
- 注意去重，可以在插入前先查询，再插入当前数。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[200005],base[200005],bb[35],fa[200005];
bool vis[200005];
int ch[6000005][2],cnt[6000005],tot;
void init(){
tot = 1;
ch[0][0] = ch[0][1] = -1;
cnt[0] = 0;
}
void insert(int x){
int cur = 0;
for(int msk = 29;msk >= 0;msk--){
int now = (x >> msk) & 1;
if(ch[cur][now] == -1){
ch[cur][now] = tot;
ch[tot][0] = ch[tot][1] = -1;
cnt[tot] = 0;
tot++;
}
cur = ch[cur][now];
cnt[cur]++;
}
}
int query(int x,int k){
int cur = 0,ans = 0;
for(int msk = 29;msk >= 0;msk--){
if(cur == -1) break;
int now = (x >> msk) & 1;
if((k >> msk) & 1 == 1){
if(ch[cur][now] != -1) ans += cnt[ch[cur][now]];
cur = ch[cur][1 - now];
}else cur = ch[cur][now];
}
if(cur != -1) ans += cnt[cur];
return ans;
}
tuple<int,int,int> eg[200005];
vector<pair<int,int>> ve[200005];
stack<int> st;
void solve(){
int n,m,k; cin >> n >> m >> k;
for(int i = 1;i <= n;i++) ve[i].clear();
for(int i = 1;i <= m;i++){
int u,v,w; cin >> u >> v >> w;
eg[i] = {u,v,w};
ve[u].emplace_back(v,i);
ve[v].emplace_back(u,i);
}
memset(vis,0,sizeof vis);
memset(bb,0,sizeof bb);
fill(fa + 1,fa + n + 1,-1);
base[1] = 0;
vis[1] = 1;
st.push(1);
while(!st.empty()){
int u = st.top();
st.pop();
for(auto [v,id] : ve[u]){
if(!vis[v]){
vis[v] = 1;
fa[v] = id;
auto [_,_,w] = eg[id];
base[v] = base[u] ^ w;
st.push(v);
}
}
}
for(int i = 1;i <= m;i++){
auto [u,v,w] = eg[i];
if(fa[u] == i || fa[v] == i) continue;
int x = base[u] ^ base[v] ^ w;
for(int msk = 29;msk >= 0;msk--){
if((x >> msk) & 1){
if(bb[msk]) x ^= bb[msk];
else{
bb[msk] = x;
break;
}
}
}
}
for(int i = 1;i <= n;i++){
int t = base[i];
for(int msk = 29;msk >= 0;msk--){
if(((t >> msk) & 1) && bb[msk]) t ^= bb[msk];
}
a[i] = t;
}
init();
int ans = 0;
for(int i = 1;i <= n;i++){
ans += query(a[i],k);
insert(a[i]);
}
cout << ans << "\n";
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T; cin >> T;
while(T--) solve();
return 0;
}
有帮助，赞一个