又是状态极菜的一场哈哈哈我不活啦😁
上一场眼瞎不判断s[ 0 ],这一场不开 LL我服了。。怎么老是犯低级错误
还发现一个不知道为啥的东西,关流之后再用快读就有出BUG,以后还是字符串多的时候关流,数字多的时候用快读把。。不可兼得。。
另,Sublime颜值居然这么高!真香了
D. 0-1 MST
题意:n个点,任意两点之间都有边相连,给的m条边是边权为1的边,其余边边权为0,求最小生成树
对于每个点,他能通过边权为0的边到达的点都“属于”这个点(连通分量???生成树中添加这个点就相当于把一堆点加进去了,白嫖)
如果忽略权值为1的边,原图就分离出多个连通分量,最小生成树的权值就是此时连通分量个数-1.
int n,m; set<int>g[MAXN],s; void bfs(int x) { queue<int>q; q.push(x); s.erase(x); while(q.size()) { x=q.front();q.pop(); std::vector<int> to_erease; for(int i:s) if(g[x].count(i)==0) to_erease.push_back(i); for(int i:to_erease) s.erase(i),q.push(i); } } int main() { rd(n),rd(m); for (int i = 0; i < m; ++i) { int x,y; rd(x),rd(y);--x,--y; g[x].insert(y); g[y].insert(x); } int ans=0; for (int i = 0; i < n ; ++i) s.insert(i); for (int i = 0; i < n ; ++i) if(s.count(i)) ++ans,bfs(i); cout<<ans-1<<endll; //stop; return 0; }
B2. Character Swap (Hard Version)
#include <bits/stdc++.h> using namespace std; #define endll '\n' #define C getchar() using ll=long long; #define pi acos(-1.0) #define INF 0x3f3f3f3f #define mod 1000000007 #define pii pair<int,int> const int MAXN = 1e6 + 10; #define stop system("pause") #define lowbit(x) ((x) & (-x)) #define Temp template <typename T> #define mem(a, b) memset(a, b, sizeof(a)) #define rep(i, a, b) for (int i = a; i <= b; i++) #define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) Temp inline void rd(T &s) { s = 0;T t = 1, k = C; for (; k < '0' || k > '9'; k = C)if (k == '-') t = -1; for (; k >= '0' && k <= '9'; k = C) s = (s << 1) + (s << 3) + (k ^ 48); s *= t; } int n; string s,t; std::vector<pii > v; bool slove() { cin>>n>>s>>t; v.clear(); for (int i = 0; i < n; ++i) { if(s[i]==t[i]) continue; for (int j = i+1; j < n; ++j) { if(s[i]==s[j]) { v.push_back({j+1,i+1}); swap(s[j],t[i]); break; } if(s[i]==t[j]) { swap(s[j],t[j]); v.push_back({j+1,j+1}); swap(s[j],t[i]); v.push_back({j+1,i+1}); break; } } } return s==t; } int main() { fast; int q;cin>>q; while(q--) { if(slove()) { cout<<"Yes\n"<<(int)v.size()<<endll; for(auto i:v) cout<<i.first<<" "<<i.second<<endll; } else cout<<"No\n"; } return 0; }