Codeforces Round #599 (Div. 2)

Codeforces Round #599 (Div. 2)

A. Maximum Square

• 思路：水题

• AC代码

---

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

const int N = 1010;

int k, n;
int a[N];

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> k;
    while (k -- ){
        cin >> n;
        int cnt = 0;
        for (int i = 1; i <= n; i ++ )
            cin >> a[i];
        sort(a + 1, a + n + 1);
        for (int i = n; i >= 1; i -- ){
            if (cnt >= a[i])
                break;
            cnt ++ ;
        }
        cout << cnt << "\n";
    }
    return 0;
}

B. Character Swap

• 思路：当a[i] != a[i]时 遍历是否存在a[j] == a[i] 若存在则交换a[j]和b[i] 否则判断是否存在a[i] == b[j] 若存在则交换a[j]和b[j] a[j]和b[i]

• AC代码

---

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

int k, n;
bool flag;
string a, b;
vector<pair<int, int> > ans;

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> k;
    while (k -- ){
        flag = true;
        ans.clear();
        vector<int> cnt(26);
        cin >> n >> a >> b;
        a.insert(0, " "), b.insert(0, " ");
        for (int i = 1; i <= n; i ++ ){
            cnt[a[i] - 'a'] ++ ;
            cnt[b[i] - 'a'] ++ ;
        }
        for (auto x: cnt){
            if (x & 1){
                flag = false;
                break;
            }
        }
        if (!flag){
            cout << "No\n";
            continue;
        }
        cout << "Yes\n";
        for (int i = 1; i <= n; i ++ ){
            if (a[i] != b[i]){
                flag = false;
                for (int j = i + 1; j <= n; j ++ ){
                    if (a[i] == a[j]){
                        flag = true;
                        ans.emplace_back(j, i);
                        swap(a[j], b[i]);
                        break;
                    }
                }
                if (!flag){
                    for (int j = i + 1; j <= n; j ++ ){
                        if (a[i] == b[j]){
                            flag = true;
                            ans.emplace_back(j, j);
                            ans.emplace_back(j, i);
                            swap(a[j], b[j]);
                            swap(a[j], b[i]);
                            break;
                        }
                    }
                }
            }
        }
        cout << ans.size() << "\n";
        for (auto x: ans)
            cout << x.first << " " << x.second << "\n";
    }
    return 0;
}

C. Tile Painting

• 思路：唯一分解定理后 对每一个p求个gcd即可

• AC代码

---

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

const int N = 1e6 + 10;

ll n, ans;
vector<ll> p;

void divide(ll x){
    ll i;
    for (i = 2; i * i < x; i ++ ){
        if (x % i == 0){
            p.push_back(i);
            p.push_back(x / i);
        }
    }
    if (i * i == x)
        p.push_back(i);
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    divide(n);
    p.push_back(n);
    ans = p[0];
    for (int i = 0; i < p.size(); i ++ )
        ans = gcd(ans, p[i]);
    cout << ans << "\n";
    return 0;
}

D. 0-1 MST

• 思路：参考其他博客的思路 bfs暴力 求出连通块的个数 答案就是连通块的个数 - 1

• AC代码

---

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

const int N = 1e5 + 10;
int n, m, ans;
int vis[N];
set<int> st, G[N];

void bfs(int x){
    queue<int> q;
    q.push(x);
    st.erase(x);
    while (!q.empty()){
        int y = q.front();
        q.pop();
        if (vis[y])
            continue;
        vis[y] = 1;
        for (auto it = st.begin(); it != st.end(); ){
            int v = *it;
            ++ it;
            if (G[y].find(v) == G[y].end()){
                q.push(v);
                st.erase(v);
            }
        }
    }
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        st.insert(i);
    for (int i = 1; i <= m; i ++ ){
        int x, y;
        cin >> x >> y;
        G[x].insert(y);
        G[y].insert(x);
    }
    for (int i = 1; i <= n; i ++ ){
        if (!vis[i]){
            bfs(i);
            ans ++ ;
        }
    }
    cout << ans - 1 << "\n";
    return 0;
}