526互联

安徽农业大学第二场选拔赛题解

发布时间 2023-04-05 17:45:34作者: Leocsse

A

枚举所有情况

#include <bits/stdc++.h>
using namespace std;

#define INF 1e18
#define endl '\n'
#define LL long long
#define ph push_back
#define inf 0x3f3f3f3f
#define PII pair<int,int>

const int N = 10;

int a[N], b[N];

int main() {
    ios::sync_with_stdio(false);        
    cin.tie(nullptr), cout.tie(nullptr);
    
    int T; cin >> T;
    while (T --) {
        for (int i = 1; i <= 6; i ++) cin >> a[i];
        for (int i = 1; i <= 6; i ++) cin >> b[i];

        int cnt1 = 0, cnt2 = 0;
        for (int i = 1; i <= 6; i ++)
            for (int j = 1; j <= 6; j ++)
                if (a[i] > b[j]) cnt1 ++;
                else if (a[i] < b[j]) cnt2 ++;

        if (cnt1 > cnt2) cout << "Alice" << endl;
        else if (cnt1 < cnt2) cout << "Bob" << endl;
        else cout << "Tie" << endl;
    }
    return 0;
}
View Code

B

n 高达 1e8，时间复杂度控制在 O(n) 以内

考虑对于一个数 x，那么看它有几个倍数在 n 以内，显然答案是 n / x 下取整个

#include <bits/stdc++.h>
using namespace std;

#define INF 1e18
#define endl '\n'
#define LL long long
#define ph push_back
#define inf 0x3f3f3f3f
#define PII pair<int,int>

int n;
LL ans;

int main() {
    ios::sync_with_stdio(false);        
    cin.tie(nullptr), cout.tie(nullptr);
    
    cin >> n;
    for (int i = 1; i <= n; i ++) ans += n / i;
    cout << ans << endl;
    return 0;
}
View Code

C

模拟

#include <bits/stdc++.h>
using namespace std;

#define INF 1e18
#define endl '\n'
#define LL long long
#define ph push_back
#define inf 0x3f3f3f3f
#define PII pair<int,int>

int n;
string str;

int main() {
    ios::sync_with_stdio(false);        
    cin.tie(nullptr), cout.tie(nullptr);
    
    for (int i = 1; i <= 1000; i ++) str += to_string(i);

    cin >> n;

    cout << str[n - 1] << endl;
    return 0;
}
View Code

D

并查集，答案为连通块的个数 - 1

#include <bits/stdc++.h>
using namespace std;

#define INF 1e18
#define endl '\n'
#define LL long long
#define ph push_back
#define inf 0x3f3f3f3f
#define PII pair<int,int>

const int N = 1e5 + 5;

int n, m;
int p[N];

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

int main() {
    ios::sync_with_stdio(false);        
    cin.tie(nullptr), cout.tie(nullptr);
    
    cin >> n >> m;

    for (int i = 1; i <= n; i ++) p[i] = i;

    while (m --) {
        int u, v; cin >> u >> v;
        u = find(u), v = find(v);
        p[u] = v;
    }

    int cnt = 0;
    for (int i = 1; i <= n; i ++)
        if (p[i] == i)
            cnt ++;
    
    cout << cnt - 1 << endl;
    return 0;
}
View Code

E

考虑单个数，若这个数在原本序列的位置为 pos，那么它删除的位置可以在 1 ~ pos,所以若这个数为正那么在 1 删除，否则在 pos 删除

#include <bits/stdc++.h>
using namespace std;

#define INF 1e18
#define endl '\n'
#define LL long long
#define ph push_back
#define inf 0x3f3f3f3f
#define PII pair<int,int>

int n;

int main() {
    ios::sync_with_stdio(false);        
    cin.tie(nullptr), cout.tie(nullptr);
    
    cin >> n;

    LL ans = 0;
    for (int i = 1; i <= n; i ++) {
        int x; cin >> x;
        if (x > 0) ans += x;
        else ans += i * x;
    }
    cout << ans << endl;
    
    return 0;
}
View Code

F

考虑数据范围,但是题目没给模数，不要看到没给模数不敢做了，自己是可以加个模数的，一般模数可以是1e9 + 7或者998244353

然后预处理阶乘，就可以 ac 了

#include <bits/stdc++.h>
using namespace std;

#define INF 1e18
#define endl '\n'
#define LL long long
#define ph push_back
#define inf 0x3f3f3f3f
#define PII pair<int,int>

const int N = 1e5 + 5, mod = 998244353;

int n, m;
LL fact[N];

void init() {
    fact[0] = 1;
    for (int i = 1; i < N; i ++) fact[i] = fact[i - 1] * i % mod;
}

bool solve() {
    cin >> n >> m;

    LL ans1 = 1, ans2 = 1;
    for (int i = 1; i <= n; i ++) {
        int x; cin >> x;
        ans1 = ans1 * fact[x] % mod;
    }
    for (int i = 1; i <= m; i ++) {
        int x; cin >> x;
        ans2 = ans2 * fact[x] % mod;
    }

    return ans1 == ans2;
}

int main() {
    ios::sync_with_stdio(false);        
    cin.tie(nullptr), cout.tie(nullptr);
    
    init();

    int T; cin >> T;
    while (T --) {
        if (solve()) cout << "equal" << endl;
        else cout << "unequal" << endl;
    }
    return 0;
}
View Code

G

不能纯暴力，不然会T，可以发现幸运值最大为9

给你一个数 x，是可以发现无论 x 为多少， x ~ x + 100 之间必定会出现幸运值是 9 的

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define LL long long
#define ph push_back    
#define INF 0x3f3f3f3f
#define PII pair<int,int>

void solve() {
    int l, r; cin >> l >> r;

    int ans = -1, num = 0;
    while (l <= r) {
        string str = to_string(l);

        int maxv = 0, minv = 10;
        for (int i = 0; i < str.size(); i ++) {
            int t = str[i] - '0';
            minv = min(minv, t);
            maxv = max(maxv, t);
        }

        if (maxv - minv > ans) {
            ans = maxv - minv;
            num = l;
        }
        if (ans == 9) break;

        l ++;
    }

    cout << num << endl;
}

int main() {    
    ios::sync_with_stdio(false);        
    cin.tie(nullptr), cout.tie(nullptr);
    
    int T; cin >> T;
    while (T --) solve();
    return 0;
}
View Code

H

#include <bits/stdc++.h>
using namespace std;

#define INF 1e18
#define endl '\n'
#define LL long long
#define ph push_back
#define inf 0x3f3f3f3f
#define PII pair<int,int>

int cnt[10];

int main() {
    ios::sync_with_stdio(false);        
    cin.tie(nullptr), cout.tie(nullptr);
    
    for (int i = 1; i <= 6; i ++) {
        int x; cin >> x;
        cnt[x] ++;
    }

    sort(cnt + 1, cnt + 11, greater<int>());

    if (cnt[1] == 6) cout << "Elephant" << endl;
    else if (cnt[1] == 5) cout << "Bear" << endl;
    else if (cnt[1] == 4) {
        if (cnt[2] == 2) cout << "Elephant" << endl;
        else cout << "Bear" << endl;
    }
    else cout << "Hernia" << endl;
    return 0;
}
View Code

I

要了解异或的性质， x ^ x = 0, 偶数个 x 异或等于 0， 奇数个 x 异或等于 x

#include <bits/stdc++.h>
using namespace std;

#define INF 1e18
#define endl '\n'
#define LL long long
#define ph push_back
#define inf 0x3f3f3f3f
#define PII pair<int,int>

const int N = 1e3 + 5;

int n;
int a[N];

void solve() {
    cin >> n;

    int ans = 0;
    for (int i = 1; i <= n; i ++) cin >> a[i], ans ^= a[i];

    if (n % 2 == 0) {
        if (ans == 0) cout << 0 << endl;
        else cout << -1 << endl;
    }
    else cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);        
    cin.tie(nullptr), cout.tie(nullptr);

    int T; cin >> T;
    while (T --) solve();
    return 0;
}
View Code

J

记录每个字母变的是 0 还是 1

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define LL long long
#define ph push_back    
#define INF 0x3f3f3f3f
#define PII pair<int,int>

int n;
string str;

bool solve() {
    cin >> n >> str;

    map<char, int> mp;
    mp[str[0]] = 0;

    for (int i = 1; i < n; i ++) {
        if (mp.count(str[i])) {
            if (mp[str[i]] == mp[str[i - 1]]) return false;
        }
        else {
            if (mp[str[i - 1]] == 0) mp[str[i]] = 1;
            else mp[str[i]] = 0;
        }
    }

    return true;
}

int main() {    
    ios::sync_with_stdio(false);        
    cin.tie(nullptr), cout.tie(nullptr);

    int T; cin >> T;
    while (T --) {
        if (solve()) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}
View Code

K

手动模拟一下

#include <bits/stdc++.h>
using namespace std;

#define INF 1e18
#define endl '\n'
#define LL long long
#define ph push_back
#define inf 0x3f3f3f3f
#define PII pair<int,int>

const int N = 1e6 + 5;

int n, m;
string str;
int a[N];

int main() {
    ios::sync_with_stdio(false);        
    cin.tie(nullptr), cout.tie(nullptr);
    
    cin >> n >> m >> str;

    int tot = 0;
    for (int i = 0; i < n; i ++) {
        if (i - m >= 0) tot ^= a[i - m];

        a[i] = tot ^ (str[i] - '0');
        tot ^= a[i];
    }

    for (int i = 0; i < n; i ++) cout << a[i];
    return 0;
}
View Code

L

枚举各种情况

#include <bits/stdc++.h>
using namespace std;

#define INF 1e18
#define endl '\n'
#define LL long long
#define ph push_back
#define inf 0x3f3f3f3f
#define PII pair<int,int>

int a, b, c;
int ans;

int main() {
    ios::sync_with_stdio(false);        
    cin.tie(nullptr), cout.tie(nullptr);
    
    cin >> a >> b >> c;

    ans = max(a + b + c, a * b * c);
    ans = max({ans, (a + b) * c, a * (b + c), a + b * c, a * b + c});
    cout << ans << endl;
    return 0;
}
View Code