Codeforces 1243 #Codeforces

1243A.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

void redirect_input(){freopen("./input.txt","r",stdin);}
void redirect_output(){freopen("./output.txt","w",stdout);}

int val[1200];

void solve(){
    int n;
    cin >> n;
    for(int i=0; i<n; i++) cin >> val[i];
    sort(val, val+n);
    int ans = 0;
    for(int i=0; i<n; i++){
        int edge = min(n - i, val[i]);
        ans = max(ans, edge);
    }
    cout << ans << '\n';
}

signed main(){
    Android;
    int q;
    cin >> q;
    while(q--)
        solve();
}

1243B1.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

void redirect_input(){freopen("./input.txt","r",stdin);}
void redirect_output(){freopen("./output.txt","w",stdout);}

const int maxn = 1e4 + 1000;
char s1[maxn], s2[maxn];

void solve(){
    int n;
    cin >> n >> s1 >> s2;
    vector<int> diff;
    for(int i=0; i<n; i++){
        if(s1[i] != s2[i]){
            diff.push_back(i);
        }
    }
    if(diff.size()==2 && s1[diff[0]] == s1[diff[1]] && s2[diff[0]] == s2[diff[1]]){
        cout << "YES\n";
    }else if(diff.size() == 0){
        cout << "YES\n";
    }else{
        cout << "NO\n";
    }
}

signed main(){
    Android;
    redirect_input();
    int q;
    cin >> q;
    while(q--)
        solve();
}

1243B2.cpp

 #include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

void redirect_input(){freopen("./input.txt","r",stdin);}
void redirect_output(){freopen("./output.txt","w",stdout);}

const int maxn = 70;
char s1[maxn], s2[maxn];
int cnt[26];

void solve(){
    memset(cnt, 0, sizeof cnt);
    int n;
    cin >> n >> s1 >> s2;
    for(int i=0; i<n; i++) {
        cnt[s1[i]-'a']++;
        cnt[s2[i]-'a']++;
    }
    for(int i=0; i<26; i++){
        if(cnt[i] % 2){
            cout << "NO\n";
            return;
        }
    }
    
    vector<pair<int, int> > ans;
    for(int i=0; i<n; i++){
        if(s1[i] == s2[i]) continue;
        int next_c = -1;
        for(int j=i+1; j<n && next_c==-1; j++) 
            if(s1[i] == s1[j]) next_c = j;

        if(next_c != -1){
            ans.push_back({next_c, i});
            swap(s1[next_c], s2[i]);
        }else{
            for(int j=i+1; j<n && next_c==-1; j++)
                if(s2[j] == s1[i]) next_c = j;
            swap(s1[n-1], s2[next_c]);
            ans.push_back({n-1, next_c});
            swap(s1[n-1], s2[i]);
            ans.push_back({n-1, i});
        }
    }
    
    cout << "YES\n" << ((int)ans.size()) << "\n";
    for(pair<int, int> pii:ans){
        cout << pii.first + 1 << " " << pii.second + 1 << "\n";
    }

}

signed main(){
    Android;
    int q;
    cin >> q;
    while(q--)
        solve();
}

1243C.cpp

 #include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

void redirect_input(){freopen("./input.txt","r",stdin);}
void redirect_output(){freopen("./output.txt","w",stdout);}

ll judge(ll val){
    ll cnt = 0, v;
    for(int i=2; i<=sqrt(val) + 1 && cnt < 2; i++){
        if(val % i == 0){
            cnt++;
            while(val % i == 0) val /= i;
            v = i;
        }
    }
    if(val != 1){
        cnt++;
        v = val;
    }
    return cnt==1?v:1;
}

void solve(){
    ll val;
    cin >> val;
    cout << judge(val) << endl;
}

signed main(){
    Android;
    solve();
}

1243D_1.cpp

/*
    耗时264ms
*/

#include <bits/stdc++.h>
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const int maxn = 1e5 + 100;

bitset<maxn> b;
set<int> edge[maxn];

// 使用bitset
void dfs(int u){
    b[u] = 0;
    for(int i=b._Find_first(); i<b.size(); i=b._Find_next(i)){
        if(edge[u].find(i) == edge[u].end()) dfs(i);
    }
}

void solve(){
    int n, m, u, v, ans = 0;
    cin >> n >> m;
    for(int i=0; i<m; i++){
        cin >> u >> v;
        edge[u].insert(v);
        edge[v].insert(u);
    }
    for(int i=1; i<=n; i++) b[i] = 1;
    for(int i=1; i<=n; i++){
        if(b[i]) dfs(i), ans++;
    }
    cout << ans-1 << endl;
}

signed main(){
    Android;
    solve();
}

1243D_2.cpp

/*
    耗时155ms
*/
#include <bits/stdc++.h>
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const int maxn = 1e5 + 100;

set<int> comp;
set<int> edge[maxn];
int n, m;

void bfs(set<int>::iterator k){
    queue<int> que;
    que.push(*k);
    comp.erase(k);
    while(!que.empty()){
        int u = que.front();
        que.pop();
        for(auto it=comp.begin(); it!=comp.end(); ){
            if(edge[u].find(*it) == edge[u].end()){
                que.push(*it);
                it = comp.erase(it);
            }else{
                it++;
            }
        }
    }
}

void solve(){
    int u, v, ans = 0;
    cin >> n >> m;
    for(int i=0; i<m; i++){
        cin >> u >> v;
        edge[v].insert(u);
        edge[u].insert(v);
    }
    for(int i=1; i<=n; i++) comp.insert(i);
    while(!comp.empty()){
        bfs(comp.begin());
        ans++;
    }
    
    cout << ans-1 << endl;
}

signed main(){
    Android;
    solve();
}