Codeforces Round #603 (Div. 2)

A. Sweet Problem

思路：水题当时有点降智贡献一发wa
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 t;
ll a, b, c, max_, min_, sum, 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 >> t;
    while (t -- ){
        cin >> a >> b >> c;
        max_ = max(a, max(b, c));
        min_ = min(a, min(b, c));
        sum = a + b + c;
        ans = sum - max_ - min_;
        if (min_ + ans > max_)
            cout << max_ + (min_ + ans - max_) / 2 << "
";
        else
            cout << min_ + ans << "
";
    }
    return 0;
}

B. PIN Codes

思路：由于每次最多只有十个数故只用管最后一位从0到9整就行了
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 = 20;

int t, n, tot;
string p[N], ans[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 >> t;
    while (t -- ){
        tot = 0;
        cin >> n;
        for (int i = 1; i <= n; i ++ )
            cin >> p[i];
        for (int i = 1; i <= n; i ++ ){
            for (int j = 1; j <= n; j ++ ){
                if (i == j)
                    continue;
                if (p[i] == p[j]){
                    while (true){
                        bool flag = false;
                        if (p[i][3] != '9')
                            p[i][3] = char((int)p[i][3] + 1);
                        else
                            p[i][3] = '0';
                        for (int k = 1; k <= n; k ++ ){
                            if (i == k)
                                continue;
                            if (p[i] == p[k]){
                                flag = true;
                                break;
                            }
                        }
                        if (!flag)
                            break;
                    }
                    tot ++ ;
                    break;
                }
            }
        }
        cout << tot << "
";
        for (int i = 1; i <= n; i ++ )
            cout << p[i] << "
";
    }
    return 0;
}

C. Everyone is a Winner!

思路：分块
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 = 1e7 + 10;

int t, n, tot, res, cnt, tmp;
int ans[N];
bool flag;

int primes[N];
bool vis[N];

void Init(){
    for (int i = 2; i < N; i ++ ){
        if (!vis[i])
            primes[tot ++ ] = i;
        for (int j = 0; j < tot && i * primes[j] <= n; j ++ ){
            vis[i * primes[j]] = true;
            if (!(i % primes[j]))
                break;
        }
    }
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Init();
    cin >> t;
    while (t -- ){
        tmp = -1, cnt = 1, res = 0;
        flag = false;
        cin >> n;
        ans[0] = n;
        for (int i = 0; i <= tot - 1; i ++ ){
            if (primes[i - 1] > n)
                break;
            if (tmp == n / primes[i]){
                flag = true;
                break;
            }
            else{
                ans[cnt ++ ] = n / primes[i];
                tmp = n / primes[i];
            }
        }
        if (flag)
            res += tmp;
        res += cnt;
        cout << res << "
";
        if (flag)
            for (int i = 0; i <= tmp - 1; i ++ )
                cout << i << " ";
        for (int i = cnt - 1; i > 0; i -- )
            cout << ans[i] << " ";
        cout << ans[0] << "
";
    }
    return 0;
}

D. Secret Passwords

思路：并查集维护即可
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 = 50;

int n, res, ans, tmp;
int fa[N], flag1[N], flag2[N];
string s;

int find(int x){
    if (fa[x] == x)
        return x;
    return fa[x] = find(fa[x]);
}

void Init(){
    for (int i = 1; i < N; i ++ )
        fa[i] = i;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Init();
    cin >> n;
    for (int i = 1; i <= n; i ++ ){
        cin >> s;
        tmp = s[0] - 'a' + 1;
        flag1[tmp] = true;
        res = find(tmp);
        for (int j = 1; j < s.length(); j ++ ){
            tmp = s[j] - 'a' + 1;
            fa[tmp] = res;
            flag1[tmp] = true;
        }
    }
    for (int i = 1; i <= 26; i ++ ){
        fa[i] = find(fa[i]);
        if (!flag2[fa[i]] && flag1[i]){
            flag2[fa[i]] = true;
            ans ++ ;
        }
    }
    cout << ans << "
";
    return 0;
}