kakaの博客

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

0%

Codeforces Round 750 (Div. 2)

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

比赛链接：https://codeforces.ml/contest/1582

A. Luntik and Concerts

直接找规律，发现答案肯定只有01。

  1. 模上1,2,3的公倍数，然后暴力枚举
  2. (a+c)%2
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
#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 = 3e5 + 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)
#define endl '\n'

void solve() {
    int T; cin >> T; while (T--) {
        int a, b, c; cin >> a >> b >> c;
        cout << (a+c)%2 << 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. Luntik and Subsequences

记0的个数为num0，1的个数为num1

$f=num1*2^{num0}$

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
#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)

void solve() {
    int T; cin >> T; while (T--) {
        int n; cin >> n;
        vector<int> a(n+1);
        ll base = 1, ans = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            if (a[i] == 0) base = base * 2;
        }
        for (int i = 1; i <= n; i++) {
            if (a[i] == 1) ans += base;
        }
        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. Grandma Capa Knits a Scarf

从两端开始枚举，直到第一个不同位置，那么答案一定就是两者之一了，暴力判断一下

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#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)

void solve() {
    int T; cin >> T; while (T--) {
        int n; cin >> n;
        string s; cin >> s;
        char c1, c2;
        int flag = 0;
        for (int i = 0; i < s.size() / 2; i++) {
            if (s[i] != s[n-i-1]) {
                flag = 1;
                c1 = s[i];
                c2 = s[n-i-1];
                break;
            }
        }
        if (!flag) cout << 0 << endl;
        else {
            int l = 0, r = n - 1;
            int num1 = 0;
            int flag1 = 0;
            while (l < r) {
                if (s[l] == s[r]) {
                    l++, r--;
                } else {
                    if (s[l] == c1) {
                        l++;
                        num1++;
                    } else if (s[r] == c1) {
                        r--;
                        num1++;
                    } else {
                        flag1 = 1;
                        break;
                    }
                }
            }
            l = 0, r = n - 1;
            int num2 = 0;
            int flag2 = 0;
            while (l < r) {
                if (s[l] == s[r]) {
                    l++, r--;
                } else {
                    if (s[l] == c2) {
                        l++;
                        num2++;
                    } else if (s[r] == c2) {
                        r--;
                        num2++;
                    } else {
                        flag2 = 1;
                        break;
                    }
                }
            }
            if (flag1 && flag2) cout << -1 << endl;
            else {
                if (flag1 && !flag2) cout << num2 << endl;
                else if (!flag1 && flag2) cout << num1 << endl;
                else cout << min(num1, num2) << 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. Vupsen, Pupsen and 0

思路其实很好想，如果是偶数，直接两两配对。如果是奇数，那么我们选择三个数配对，三个数怎么选呢，如果三个数分别为a,b,c，那么我们给a,b一个系数c，c的系数为-(a+b)。这里还有一个坑，即a+b为0。我先是随机找两个数判，然后t了，后来改成两个同符号的就可以了。

记得两两配对需要除上gcd，不然第二种情况$\sum bi$可能会大于1e9

以下是证明可行性：
奇数时的$\sum bi$最大可构造的数为1e4,1e4-1,1e4,1e4-1…，因此sum<1e9-1e5，那么剩下的a,b,c系数和肯定小于1e5，因此符合要求

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
73
74
75
76
77
78
79
80
81
82
83
84
85
#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];
void solve() {
    int T; cin >> T; while (T--) {
        int n; cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        if (n % 2 == 0) {
            for (int i = 1; i <= n; i += 2) {
                cout << -a[i+1] << ' ' << a[i] << ' ';
            }
            cout << endl;
        } else {
            int x, y;
            vector<int> fu, zhen;
            for (int i = 1; i <= n; i++) {
                if (a[i] > 0) zhen.push_back(i);
                else fu.push_back(i);
            }
            if (fu.size() > 1) x = fu[0], y = fu[1];
            else x = zhen[0], y = zhen[1];
            vector<int> vis(n+1), ans(n+1);
            vis[x] = vis[y] = 1;
            int pre = 0;
            for (int i = 1; i <= n; i ++) {
                if (vis[i]) continue;
                if (pre) {
                    int gcd = __gcd(abs(a[i]), abs(a[pre]));
                    ans[i] = -a[pre]/gcd;
                    ans[pre] = a[i]/gcd;
                    vis[pre] = vis[i] = 1;
                    pre = 0;
                } else {
                    pre = i;
                }
            }
            for (int i = 1; i <= n; i++) {
                if (!vis[i]) {
                    ans[x] = ans[y] = a[i];
                    ans[i] = -(a[x]+a[y]);
                    break;
                }
            }
            for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
            cout << 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;
}

E. Pchelyonok and Segments

考虑dp，因为$\frac{(k+1)*k}{2}<n$，$k<\sqrt{(2n)}$

因此状态可以表示成$dp[i][j]$代表前i个数当前长度为j的最大值

$dp[i][j]=max(dp[i][j],sum[i+j-1]-sum[i-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
63
64
65
66
#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 = 1e5 + 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];
ll dp[N][500], sum[N];
void solve() {
    int T; cin >> T; while (T--) {
        int n; cin >> n;
        for (int i = 0; i <= n+1; i++) {
            for (int j = 0; j <= sqrt(2*n); j++) {
                dp[i][j] = 0;
            }
        }
        for (int i = 1; i <= n; i++) cin >> a[i], sum[i] = sum[i-1] + a[i];
        dp[n+1][0] = inf;
        for (int i = n; i >= 1; i--) {
            for (int j = 0; j <= sqrt(2*n); j++) {
                dp[i][j] = dp[i+1][j];
                if (j && i + j - 1 <= n && sum[i+j-1] - sum[i-1] < dp[i+j][j-1]) {
                    dp[i][j] = max(dp[i][j], sum[i+j-1] - sum[i-1]);
                }
            }
        }
        int ans = 0;
        for (int j = 1; j <= sqrt(2*n); j++) {
            if (dp[1][j]) ans = j;
        }
        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;
}

F1. Korney Korneevich and XOR (easy version)

同样考虑dp

dp的状态还是很巧妙的，设$dp[i]$表示构成i的当前最小值，两层for转移一下就行

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 = 1e9 + 7;

#define fi first
#define se second
#define re register
#define lowbit (-x&x)
#define endl '\n'
int a[N];
int dp[N];
void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= 1024; j++) {
            if (a[i] > dp[j]) {
                dp[j^a[i]] = min(dp[j^a[i]], a[i]);
            }
        }
    }
    vector<int> ans;
    for (int i = 0; i <= 1024; i++) if (dp[i] <= 500) ans.push_back(i);
    cout << ans.size() << endl;
    for (auto it : ans) cout << it << ' ';
    cout << 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;
}

赛后想到更直接的转移，利用线段树。

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#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)
#define endl '\n'
int a[N];
struct Tree {
    int l, r;
    bitset<1024> f;
}t[505<<2];
void push_up(int u) {
    t[u].f = t[u<<1].f | t[u<<1|1].f;
}
void build(int u, int l, int r) {
    t[u].l = l, t[u].r = r;
    if (l == r) {
        if (l == 0) t[u].f[0] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(u<<1, l, mid);
    build(u<<1|1, mid+1, r);
    push_up(u);
}
void modify(int u, int pos, bitset<1024> val) {
    if (t[u].l == t[u].r) {
        t[u].f |= val;
        return;
    }
    int mid = (t[u].l + t[u].r) >> 1;
    if (pos <= mid) modify(u<<1, pos, val);
    else modify(u<<1|1, pos, val);
    push_up(u);
}
bitset<1024> query(int u, int ql, int qr) {
    if (ql <= t[u].l && qr >= t[u].r) return t[u].f;
    int mid = (t[u].l + t[u].r) >> 1;
    bitset<1024> ans;
    if (ql <= mid) ans |= query(u<<1, ql, qr);
    if (qr > mid) ans |= query(u<<1|1, ql, qr);
    return ans;
}
void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 0, 500);
    for (int i = 1; i <= n; i++) {
        if (!a[i]) continue;
        bitset<1024> now = query(1, 0, a[i]-1);
        for (int j = 0; j < 1024; j++) if (now[j]) now[j^a[i]]=1;
        modify(1, a[i], now);
    }
    cout << t[1].f.count() << endl;
    for (int i = 0; i < 1024; i++) if (t[1].f[i]) cout << i << ' ';
    cout << 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;
}
相关文章推荐