kakaの博客

你所热爱的，就是你的生活

0%

Codeforces Round 410 (Div.2)

发表于 更新于 分类于 ， 阅读次数： Valine：
本文字数： 5.4k 阅读时长 ≈ 5 分钟

比赛链接点这里

A. Mike and palindrome

必须改变一个字母，使得字符串变成回文串。

直接暴力枚举每个字符然后判断就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
const ll inf = 1e18;
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const double eps = 1e-8;
const int mod = 998244353;

#define fi first
#define se second
#define re register
#define lowbit (-x&x)
bool check(string s) {
    for (int i = 0; i < s.size(); i++) {
        if (s[s.size()-i-1] != s[i]) return false;
    }
    return true;
}
void solve() {
    string s; cin >> s;
    int f = 0;
    for (int i = 0; i < s.size(); i++) {
        char tmp = s[i];
        for (int j = 0; j < 26; j++) {
            s[i] = 'a' + j;
            if (s[i] == tmp) continue;
            if (check(s)) f = 1;
        }
        s[i] = tmp;
    }
    if (f) cout << "YES" << endl;
    else cout << "NO" << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifdef ACM_LOCAL
    freopen("input", "r", stdin);
    freopen("output", "w", stdout);
#endif

#ifdef ACM_LOCAL
    auto start = clock();
#endif
    int t = 1;
//    cin >> t;
    while (t--)
        solve();
#ifdef ACM_LOCAL
    auto end = clock();
    cerr << "Run Time: " << double(end - start) / CLOCKS_PER_SEC << "s" << endl;
#endif
    return 0;
}

B. Mike and strings

也是暴力。

直接枚举最后全部变成第i个字符串，然后取min就可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
const ll inf = 1e18;
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const double eps = 1e-8;
const int mod = 998244353;

#define fi first
#define se second
#define re register
#define lowbit (-x&x)
string s[N];
void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> s[i];
    int f = 0;
    int ans = 1e9;
    int len = s[1].size();
    for (int i = 1; i <= n; i++) {
        string tmp = s[i];
        int sum = 0;
        for (int j = 1; j <= n; j++) {
            int ff = 0;
            string back = s[j];
            for (int t = 1; t <= len; t++) {
                if (tmp == s[j]) {
                    ff = 1;
                    break;
                }
                s[j].push_back(*s[j].begin());
                s[j].erase(s[j].begin());
                sum++;
            }
            if (!ff) {
                f = 1;
                break;
            }
            s[j] = back;
        }
        ans = min(ans, sum);
    }
    if (f) cout << -1 << endl;
    else cout << ans << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifdef ACM_LOCAL
    freopen("input", "r", stdin);
    freopen("output", "w", stdout);
#endif

#ifdef ACM_LOCAL
    auto start = clock();
#endif
    int t = 1;
//    cin >> t;
    while (t--)
        solve();
#ifdef ACM_LOCAL
    auto end = clock();
    cerr << "Run Time: " << double(end - start) / CLOCKS_PER_SEC << "s" << endl;
#endif
    return 0;
}

C. Mike and gcd problem

最开始直接判定gcd是否>1,如果大于1，直接输出结果。

接着扫一遍，将所有都变成偶数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
const ll inf = 1e18;
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const double eps = 1e-8;
const int mod = 998244353;

#define fi first
#define se second
#define re register
#define lowbit (-x&x)
ll a[N], b[N];
void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    ll gcd = 0;
    for (int i = 1; i <= n; i++) gcd = __gcd(gcd, a[i]);
    if (gcd > 1) {
        cout << "YES" << endl;
        cout << 0 << endl;
    } else {
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            while (a[i] % 2) {
                int t1 = abs(a[i+1] - a[i]), t2 = a[i+1] + a[i];
                a[i] = t1;
                a[i+1] = t2;
                ans++;
            }
        }
        cout << "YES" << endl;
        cout << ans << endl;
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifdef ACM_LOCAL
    freopen("input", "r", stdin);
    freopen("output", "w", stdout);
#endif

#ifdef ACM_LOCAL
    auto start = clock();
#endif
    int t = 1;
//    cin >> t;
    while (t--)
        solve();
#ifdef ACM_LOCAL
    auto end = clock();
    cerr << "Run Time: " << double(end - start) / CLOCKS_PER_SEC << "s" << endl;
#endif
    return 0;
}

D. Mike and distribution

直接用rand做的，貌似可以过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
const ll inf = 1e18;
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const double eps = 1e-8;
const int mod = 1e9 + 7;

#define fi first
#define se second
#define re register
#define lowbit (-x&x)

int a[N], b[N], c[N];
void solve() {
    int n, m; cin >> n;
    ll sum1 = 0, sum2 = 0;
    for (int i = 1; i <= n; i++) cin >> a[i], sum1 += a[i];
    for (int i = 1; i <= n; i++) cin >> b[i], sum2 += b[i];
    for (int i = 1; i <= n; i++) c[i] = i;
    srand(time(0));
    while (1) {
        random_shuffle(c+1, c+n+1);
        ll ans1 = 0, ans2 = 0;
        for (int i = 1; i <= n/2+1; i++) {
            ans1 += a[c[i]];
            ans2 += b[c[i]];
        }
        if (ans1 * 2 > sum1 && ans2 * 2 > sum2) {
            cout << n / 2 + 1 << endl;
            for (int i = 1; i <= n/2+1; i++) cout << c[i] << ' ';
            cout << endl;
            break;
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifdef ACM_LOCAL
    freopen("input", "r", stdin);
    freopen("output", "w", stdout);
#endif

#ifdef ACM_LOCAL
    auto start = clock();
#endif
    int t = 1;
//    cin >> t;
    while (t--)
        solve();
#ifdef ACM_LOCAL
    auto end = clock();
    cerr << "Run Time: " << double(end - start) / CLOCKS_PER_SEC << "s" << endl;
#endif
    return 0;
}
相关文章推荐