Codeforces Round #599 (Div. 2)
久违的写篇博客吧
A. Maximum Square
题目链接：https://codeforces.com/contest/1243/problem/A
题意：
给定n个栅栏，对这n个栅栏进行任意排序，问可形成的最大正方形面积是多少
分析：
水题。
先排个序 ， 然后暴力枚举正方形边长就可以了
#include<bits/stdc++.h> #define ios std::ios::sync_with_stdio(false) #define sd(n) scanf("%d",&n) #define sdd(n,m) scanf("%d%d",&n,&m) #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) #define pd(n) printf("%d\n", (n)) #define pdd(n,m) printf("%d %d\n", n, m) #define pld(n) printf("%lld\n", n) #define pldd(n,m) printf("%lld %lld\n", n, m) #define sld(n) scanf("%lld",&n) #define sldd(n,m) scanf("%lld%lld",&n,&m) #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) #define sf(n) scanf("%lf",&n) #define sff(n,m) scanf("%lf%lf",&n,&m) #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--) #define mm(a,n) memset(a, n, sizeof(a)) #define pb push_back #define all(x) (x).begin(),(x).end() #define fi first #define se second #define ll long long #define MOD 1000000007 #define pi 3.14159265358979323 #define lrt rt<<1 #define rrt rt<<1|1 #define lson l, m, lrt #define rson m+1, r, rrt #define debug(x) cout << #x << ": " << x << endl #define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl; #define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl; #define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl; using namespace std; const ll INF (0x3f3f3f3f3f3f3f3fll); const int inf (0x3f3f3f3f); template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);} template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');} ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a*b/gcd(a,b);} ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;} ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;} ll mult(ll a,ll b,ll p){a%=p;b%=p;ll r=0,v=a;while(b){if(b&1){r+=v;if(r>p)r-=p;}v<<=1;if(v>p)v-=p;b>>=1;}return r;} ll quick_pow(ll a,ll b,ll p){ll r=1,v=a%p;while(b){if(b&1)r=mult(r,v,p);v=mult(v,v,p);b>>=1;}return r;} bool CH(ll a,ll n,ll x,ll t) {ll r=quick_pow(a,x,n);ll z=r;for(ll i=1;i<=t;i++){r=mult(r,r,n);if(r==1&&z!=1&&z!=n-1)return true;z=r;}return r!=1;} bool Miller_Rabin(ll n) {if(n<2)return false;if(n==2)return true;if(!(n&1))return false;ll x=n-1,t=0;while(!(x&1)){x>>=1;t++;}srand(time(NULL)); ll o=8;for(ll i=0;i<o;i++){ll a=rand()%(n-1)+1;if(CH(a,n,x,t))return false;}return true;} int prime[30000010],minprime[30000010]; void euler(int n) {int c=0,i,j;for(i=2;i<=n;i++){if(!minprime[i])prime[++c]=i,minprime[i]=i;for(j=1;j<=c&&i*prime[j]<=n;j++) {minprime[i*prime[j]]=prime[j];if(i%prime[j]==0)break;}}} const int N = 1e3 + 10; int a[N]; int main(){ ios; int t; cin >> t; while(t -- ) { int n; cin >> n; int a[N]; rep(i , 0 , n - 1) { cin >> a[i]; } sort(a,a+n); int len = 0; per(i , n - 1 , 0) { if(a[i] > len){ len ++; } else { break; } } cout << len << '\n'; } return 0; }
B1. Character Swap (Easy Version)
题目链接：https://codeforces.com/contest/1243/problem/B1
题意：
给你两个长度为 n 的字符串 S 和 T ，每次操作你可以交换 S 、T上任意两个位置的字符。问是否能只进行一次操作使 S 串 等于 T串。能输出 "Yes" ， 不能输出 "No"
分析：
遍历字符串，当 S[i] != T[i] 时，判断从i + 1 到 n是否有s[j] == s[i] && t[j] != s[j]，若不存在则说明无法进行一次操作使得两个字符串相等;
若存在则标记cot为0，继续遍历，倘若又一次出现s[i] != t[i]，则输出"No".
#include<bits/stdc++.h> #define ios std::ios::sync_with_stdio(false) #define sd(n) scanf("%d",&n) #define sdd(n,m) scanf("%d%d",&n,&m) #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) #define pd(n) printf("%d\n", (n)) #define pdd(n,m) printf("%d %d\n", n, m) #define pld(n) printf("%lld\n", n) #define pldd(n,m) printf("%lld %lld\n", n, m) #define sld(n) scanf("%lld",&n) #define sldd(n,m) scanf("%lld%lld",&n,&m) #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) #define sf(n) scanf("%lf",&n) #define sff(n,m) scanf("%lf%lf",&n,&m) #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--) #define mm(a,n) memset(a, n, sizeof(a)) #define pb push_back #define all(x) (x).begin(),(x).end() #define fi first #define se second #define ll long long #define MOD 1000000007 #define pi 3.14159265358979323 #define lrt rt<<1 #define rrt rt<<1|1 #define lson l, m, lrt #define rson m+1, r, rrt #define debug(x) cout << #x << ": " << x << endl #define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl; #define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl; #define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl; using namespace std; const ll INF (0x3f3f3f3f3f3f3f3fll); const int inf (0x3f3f3f3f); template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);} template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');} ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a*b/gcd(a,b);} ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;} ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;} ll mult(ll a,ll b,ll p){a%=p;b%=p;ll r=0,v=a;while(b){if(b&1){r+=v;if(r>p)r-=p;}v<<=1;if(v>p)v-=p;b>>=1;}return r;} ll quick_pow(ll a,ll b,ll p){ll r=1,v=a%p;while(b){if(b&1)r=mult(r,v,p);v=mult(v,v,p);b>>=1;}return r;} bool CH(ll a,ll n,ll x,ll t) {ll r=quick_pow(a,x,n);ll z=r;for(ll i=1;i<=t;i++){r=mult(r,r,n);if(r==1&&z!=1&&z!=n-1)return true;z=r;}return r!=1;} bool Miller_Rabin(ll n) {if(n<2)return false;if(n==2)return true;if(!(n&1))return false;ll x=n-1,t=0;while(!(x&1)){x>>=1;t++;}srand(time(NULL)); ll o=8;for(ll i=0;i<o;i++){ll a=rand()%(n-1)+1;if(CH(a,n,x,t))return false;}return true;} int prime[30000010],minprime[30000010]; void euler(int n) {int c=0,i,j;for(i=2;i<=n;i++){if(!minprime[i])prime[++c]=i,minprime[i]=i;for(j=1;j<=c&&i*prime[j]<=n;j++) {minprime[i*prime[j]]=prime[j];if(i%prime[j]==0)break;}}} const int N = 2e5 + 10; char s[N] , t[N]; int main() { ios; int q; cin >> q; while(q --) { int n ; cin >> n; cin >> s + 1 >> t + 1 ; int flag = 1 , cot = 1; rep(i , 1 , n) { if(!flag) break; if(s[i] == t[i]) continue; else { if(cot == 0) { cout << "No\n"; flag = 0; break; } int have = 0; rep(j , i + 1 , n) { if(s[j] == s[i] && t[j] != s[j]) { swap(t[i] , s[j]); cot = 0; have = 1; } } if(!have) { cout << "No\n"; flag = 0; } } } if(flag) cout <<"Yes\n"; } return 0; }
B2. Character Swap (Hard Version)
题目链接：https://codeforces.com/contest/1243/problem/B2
题意：
给你两个长度为 n 的字符串 S 和 T ，每次操作你可以交换 S 、T上任意两个位置的字符。
问在 2n 操作次数内能否是 S 等于 T，若可以则输出"Yes"并打印交换方法，若不可以则输出"No"
分析：
其实仔细观察我们会发现只要能够使S串变为T串，那么它的操作次数一定是在2n以内。
然而我们还是要优先选择优质的交换方法。
当 S[i] != T[i] 从后遍历判断是否存在S[j] == S[i] , 若存在则交换 T[i] 和 S[j] , 否则判断是否存在T[j] == S[i] ，若存在则可以先交换S[i] 和 T[i] ，再交换S[i] = T[j]，若不存在则输出"No"
#include<bits/stdc++.h> #define ios std::ios::sync_with_stdio(false) #define sd(n) scanf("%d",&n) #define sdd(n,m) scanf("%d%d",&n,&m) #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) #define pd(n) printf("%d\n", (n)) #define pdd(n,m) printf("%d %d\n", n, m) #define pld(n) printf("%lld\n", n) #define pldd(n,m) printf("%lld %lld\n", n, m) #define sld(n) scanf("%lld",&n) #define sldd(n,m) scanf("%lld%lld",&n,&m) #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) #define sf(n) scanf("%lf",&n) #define sff(n,m) scanf("%lf%lf",&n,&m) #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--) #define mm(a,n) memset(a, n, sizeof(a)) #define pb push_back #define all(x) (x).begin(),(x).end() #define fi first #define se second #define ll long long #define MOD 1000000007 #define pi 3.14159265358979323 #define lrt rt<<1 #define rrt rt<<1|1 #define lson l, m, lrt #define rson m+1, r, rrt #define debug(x) cout << #x << ": " << x << endl #define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl; #define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl; #define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl; using namespace std; const ll INF (0x3f3f3f3f3f3f3f3fll); const int inf (0x3f3f3f3f); template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);} template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');} ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a*b/gcd(a,b);} ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;} ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;} ll mult(ll a,ll b,ll p){a%=p;b%=p;ll r=0,v=a;while(b){if(b&1){r+=v;if(r>p)r-=p;}v<<=1;if(v>p)v-=p;b>>=1;}return r;} ll quick_pow(ll a,ll b,ll p){ll r=1,v=a%p;while(b){if(b&1)r=mult(r,v,p);v=mult(v,v,p);b>>=1;}return r;} bool CH(ll a,ll n,ll x,ll t) {ll r=quick_pow(a,x,n);ll z=r;for(ll i=1;i<=t;i++){r=mult(r,r,n);if(r==1&&z!=1&&z!=n-1)return true;z=r;}return r!=1;} bool Miller_Rabin(ll n) {if(n<2)return false;if(n==2)return true;if(!(n&1))return false;ll x=n-1,t=0;while(!(x&1)){x>>=1;t++;}srand(time(NULL)); ll o=8;for(ll i=0;i<o;i++){ll a=rand()%(n-1)+1;if(CH(a,n,x,t))return false;}return true;} int prime[30000010],minprime[30000010]; void euler(int n) {int c=0,i,j;for(i=2;i<=n;i++){if(!minprime[i])prime[++c]=i,minprime[i]=i;for(j=1;j<=c&&i*prime[j]<=n;j++) {minprime[i*prime[j]]=prime[j];if(i%prime[j]==0)break;}}} const int N = 2e5 + 10; char s[N] , t[N]; pair<int , int>hehe; vector<pair<int , int>>vec; map<char ,int >haha; int main() { ios; int T; cin >> T; while(T -- ) { haha.clear(); vec.clear(); int n; cin >> n; cin >> s + 1 >> t + 1 ; rep(i , 1 , n) haha[s[i]] ++ , haha[t[i]] ++ ; int flag = 0; rep(i , 0 , 25) { if(haha[i + 'a'] & 1) { flag = 1; break; } } if(flag) { cout << "No" << '\n'; continue; } rep(i , 1 , n) { if(s[i] == t[i]) continue; else { int falg = 0; rep(j , i + 1 , n) { if(s[i] == s[j]) { hehe.first = j , hehe.second = i; vec.pb(hehe); swap(s[j] , t[i]); falg = 1; break; } } if(!falg) { rep(j , i + 1 , n) { if(s[i] == t[j]) { swap(s[i] , t[i]); hehe.fi = i , hehe.se = i; vec.pb(hehe); swap(s[i] , t[j]); hehe.fi = i , hehe.se = j; vec.pb(hehe); break; } } } } } int len = vec.size(); if(len >= 2 * n) { cout << "No" << '\n'; continue; } cout << "Yes" << '\n'; cout << vec.size() << '\n'; rep(i , 0 , vec.size() - 1) cout << vec[i].fi << " " << vec[i].se << '\n'; } return 0; }
C. Tile Painting
题目链接：https://codeforces.com/contest/1243/problem/C
题意：
给你 n 个方格 ， 第 i 个位置的倍数的颜色需要和 第 i 个位置的颜色相同，问你最多可以用多少种颜色来填充
分析：
找找规律我们会发现它是有循环节的，而循环节就是n / lcm = 所有因子的gcd
#include<bits/stdc++.h> #define ios std::ios::sync_with_stdio(false) #define sd(n) scanf("%d",&n) #define sdd(n,m) scanf("%d%d",&n,&m) #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) #define pd(n) printf("%d\n", (n)) #define pdd(n,m) printf("%d %d\n", n, m) #define pld(n) printf("%lld\n", n) #define pldd(n,m) printf("%lld %lld\n", n, m) #define sld(n) scanf("%lld",&n) #define sldd(n,m) scanf("%lld%lld",&n,&m) #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) #define sf(n) scanf("%lf",&n) #define sff(n,m) scanf("%lf%lf",&n,&m) #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--) #define mm(a,n) memset(a, n, sizeof(a)) #define pb push_back #define all(x) (x).begin(),(x).end() #define fi first #define se second #define ll long long #define MOD 1000000007 #define pi 3.14159265358979323 #define lrt rt<<1 #define rrt rt<<1|1 #define lson l, m, lrt #define rson m+1, r, rrt #define debug(x) cout << #x << ": " << x << endl #define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl; #define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl; #define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl; using namespace std; const ll INF (0x3f3f3f3f3f3f3f3fll); const int inf (0x3f3f3f3f); template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);} template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');} ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a*b/gcd(a,b);} ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;} ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;} ll mult(ll a,ll b,ll p){a%=p;b%=p;ll r=0,v=a;while(b){if(b&1){r+=v;if(r>p)r-=p;}v<<=1;if(v>p)v-=p;b>>=1;}return r;} ll quick_pow(ll a,ll b,ll p){ll r=1,v=a%p;while(b){if(b&1)r=mult(r,v,p);v=mult(v,v,p);b>>=1;}return r;} bool CH(ll a,ll n,ll x,ll t) {ll r=quick_pow(a,x,n);ll z=r;for(ll i=1;i<=t;i++){r=mult(r,r,n);if(r==1&&z!=1&&z!=n-1)return true;z=r;}return r!=1;} bool Miller_Rabin(ll n) {if(n<2)return false;if(n==2)return true;if(!(n&1))return false;ll x=n-1,t=0;while(!(x&1)){x>>=1;t++;}srand(time(NULL)); ll o=8;for(ll i=0;i<o;i++){ll a=rand()%(n-1)+1;if(CH(a,n,x,t))return false;}return true;} int prime[30000010],minprime[30000010]; void euler(int n) {int c=0,i,j;for(i=2;i<=n;i++){if(!minprime[i])prime[++c]=i,minprime[i]=i;for(j=1;j<=c&&i*prime[j]<=n;j++) {minprime[i*prime[j]]=prime[j];if(i%prime[j]==0)break;}}} const int N = 2e5 + 10; vector<ll>haha; void init(ll n) { ll i ; for(i = 2 ; i * i < n ; i ++) { if(n % i == 0) haha.pb(i) , haha.pb(n / i); } if(i * i == n) haha.pb(i); } int main() { ios; haha.clear(); ll n; cin >> n; init(n); haha.pb(n); ll ans = haha[0]; rep(i , 0 , haha.size() - 1) ans = gcd(ans , haha[i]); cout << ans << '\n'; return 0; }
D. 0-1 MST
题目链接：https://codeforces.com/contest/1243/problem/D
题意：
给你一张包含 n 个点的完全图，其中有m条边的权值为1，其它的为0。现要求你求出最小生成树的权值
分析：
先将 n 个点存入 set<int> S（表示该点还未在任何连通块里），并用vis进行标记
再对每个点开个set<int>G用来存图
遍历每个点 ， 若 vis[i] = 1 则将 i 从集合S中删除并以 i 为起点进行 bfs 寻找连通块 ， 同时连通块个数 cnt ++。
bfs 过程中遍历S , 若 G[i].count(*it) == 1 ， 则说明两点没有连通 ， 若为 0 则说明两点有连通。若连通则将其从S中erase、vis标记为1，并加入队列进行下一轮bfs
最后输出 cnt - 1即可
#include<bits/stdc++.h> #define ios std::ios::sync_with_stdio(false) #define sd(n) scanf("%d",&n) #define sdd(n,m) scanf("%d%d",&n,&m) #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) #define pd(n) printf("%d\n", (n)) #define pdd(n,m) printf("%d %d\n", n, m) #define pld(n) printf("%lld\n", n) #define pldd(n,m) printf("%lld %lld\n", n, m) #define sld(n) scanf("%lld",&n) #define sldd(n,m) scanf("%lld%lld",&n,&m) #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) #define sf(n) scanf("%lf",&n) #define sff(n,m) scanf("%lf%lf",&n,&m) #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--) #define mm(a,n) memset(a, n, sizeof(a)) #define pb push_back #define all(x) (x).begin(),(x).end() #define fi first #define se second #define ll long long #define MOD 1000000007 #define pi 3.14159265358979323 #define lrt rt<<1 #define rrt rt<<1|1 #define lson l, m, lrt #define rson m+1, r, rrt #define debug(x) cout << #x << ": " << x << endl #define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl; #define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl; #define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl; using namespace std; const ll INF (0x3f3f3f3f3f3f3f3fll); const int inf (0x3f3f3f3f); template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);} template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');} ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a*b/gcd(a,b);} ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;} ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;} ll mult(ll a,ll b,ll p){a%=p;b%=p;ll r=0,v=a;while(b){if(b&1){r+=v;if(r>p)r-=p;}v<<=1;if(v>p)v-=p;b>>=1;}return r;} ll quick_pow(ll a,ll b,ll p){ll r=1,v=a%p;while(b){if(b&1)r=mult(r,v,p);v=mult(v,v,p);b>>=1;}return r;} bool CH(ll a,ll n,ll x,ll t) {ll r=quick_pow(a,x,n);ll z=r;for(ll i=1;i<=t;i++){r=mult(r,r,n);if(r==1&&z!=1&&z!=n-1)return true;z=r;}return r!=1;} bool Miller_Rabin(ll n) {if(n<2)return false;if(n==2)return true;if(!(n&1))return false;ll x=n-1,t=0;while(!(x&1)){x>>=1;t++;}srand(time(NULL)); ll o=8;for(ll i=0;i<o;i++){ll a=rand()%(n-1)+1;if(CH(a,n,x,t))return false;}return true;} int prime[30000010],minprime[30000010]; void euler(int n) {int c=0,i,j;for(i=2;i<=n;i++){if(!minprime[i])prime[++c]=i,minprime[i]=i;for(j=1;j<=c&&i*prime[j]<=n;j++) {minprime[i*prime[j]]=prime[j];if(i%prime[j]==0)break;}}} const int N = 2e5 + 10; set<int>G[N]; set<int>s; set<int>::iterator it; int n , m; int vis[N]; void bfs(int x) { queue<int>q; q.push(x); s.erase(x); vis[x] = 1; while(!q.empty()) { int k = q.front(); q.pop(); for(it = s.begin() ; it != s.end() ;) { int ha = *it ++; if(G[k].count(ha) == 0) { vis[ha] = 1; q.push(ha); s.erase(ha); } } } } int main() { ios; cin >> n >> m; rep(i , 1 , n) s.insert(i); rep(i , 1 , m) { int x , y; cin >> x >> y; G[x].insert(y); G[y].insert(x); } int ans = 0; rep(i , 1 , n) { if(!vis[i]) { ans ++; bfs(i); } } cout << ans - 1 << '\n'; return 0; }
查看7道真题和解析