kakaの博客

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

0%

AtCoder Beginner Contest 223

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

比赛链接：点这里

A. Exact Price

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

int main() {
    int n; cin >> n;
    if (n % 100 == 0 && n / 100 >= 1) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B. String Shifting

直接暴力找出所有字符串排序

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 = 1e9;
const int N = 1e6 + 10;
const int M = 1e6 + 10;
const double eps = 1e-8;
const int mod = 1e9+7;
vector<string> ve;
void solve() {
    string s; cin >> s;
    ve.push_back(s);
    for (int i = 0; i < s.size(); i++) {
        s = s.back() + s;
        s.pop_back();
        ve.push_back(s);
    }
    sort(ve.begin(), ve.end());
    cout << ve[0] << endl;
    cout << ve[ve.size()-1] << 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. Doukasen

找到一半的时间点，然后暴力找一遍

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 = 5e6 + 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)
int a[N], b[N];
double t[N];
void solve() {
    int n; cin >> n;
    double sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        t[i] = a[i] * 1.0 / b[i];
        sum += t[i];
    }
    sum /= 2;
    double ans = 0;
    for (int i = 1; i <= n; i++) {
        if (sum - t[i] >= eps) {
            ans += a[i];
            sum -= t[i];
        } else {
            ans += a[i] * (sum / t[i]);
            break;
        }
    }
    printf("%.6lf\n", ans);
}

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. Restricted Permutation

根据优先级拓扑建边，然后用优先队列贪心最小的下标

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
#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 = 5e6 + 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)
int in[N], n;
vector<int> g[N], order;
void tupo() {
    priority_queue<int, vector<int>, greater<int>> q;
    for (int i = 1; i <= n; i++) {
        if (!in[i]) q.push(i);
    }
    while (q.size()) {
        int now = q.top();
        q.pop();
        order.push_back(now);
        for (auto v : g[now]) {
            --in[v];
            if (!in[v]) q.push(v);
        }
    }
}
void solve() {
    int m; cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        in[v]++;
    }
    tupo();
    if (order.size() != n) {
        cout << -1 << endl;
        return;
    }
    for (auto it : order) cout << it << ' ';
}

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;
}

F. Parenthesis Checking

线段树维护前缀和，一个区间是合法的当且仅当区间和为0，且区间和恒不小于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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#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)
struct Tree {
    int l, r;
    int mi, tag;
}t[N<<2];
int sum[N];
char s[N];
void push_up(int u) {
    t[u].mi = min(t[u<<1].mi, t[u<<1|1].mi);
}
void push_down(int u) {
    if (t[u].tag) {
        t[u<<1].mi += t[u].tag;
        t[u<<1|1].mi += t[u].tag;
        t[u<<1].tag += t[u].tag;
        t[u<<1|1].tag += t[u].tag;
        t[u].tag = 0;
    }
}
void build(int u, int l, int r) {
    t[u].l = l, t[u].r = r;
    t[u].mi = 1e9;
    if (l == r) {
        t[u].mi = sum[l];
        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 ql, int qr, int val) {
    if (ql <= t[u].l && qr >= t[u].r) {
        t[u].mi += val;
        t[u].tag += val;
        return;
    }
    push_down(u);
    int mid = (t[u].l + t[u].r) >> 1;
    if (ql <= mid) modify(u<<1, ql, qr, val);
    if (qr > mid) modify(u<<1|1, ql, qr, val);
    push_up(u);
}
int query(int u, int ql, int qr) {
    if (ql <= t[u].l && qr >= t[u].r) return t[u].mi;
    push_down(u);
    int mid = (t[u].l + t[u].r) >> 1;
    int mi = 1e9;
    if (ql <= mid) mi = min(mi, query(u<<1, ql, qr));
    if (qr > mid) mi = min(mi, query(u<<1|1, ql, qr));
    return mi;
}
void solve() {
    int n, m; cin >> n >> m;
    cin >> (s + 1);
    for (int i = 1; i <= n; i++) {
        if (s[i] == '(') sum[i] = sum[i-1] + 1;
        else sum[i] = sum[i-1] - 1;
    }
    build(1, 0, n);
    for (int i = 1; i <= m; i++) {
        int opt, l, r; cin >> opt >> l >> r;
        if (opt == 1) {
            if (s[l] == '(' && s[r] == ')') {
                s[l] = ')';
                s[r] = '(';
                modify(1, l, n, -2);
                modify(1, r, n, 2);
            } else if (s[l] == ')' && s[r] == '(') {
                s[l] = '(';
                s[r] = ')';
                modify(1, l, n, 2);
                modify(1, r, n, -2);
            }
        } else {
            int pre = query(1, l - 1, l - 1);
            int lst = query(1, r, r);
            if (lst != pre || query(1, l, r) < pre) printf("No\n");
            else printf("Yes\n");
        }
    }
}

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;
}

G. Vertex Deletion

待补

H. Xor Query

待补

相关文章推荐
-------------本文结束感谢您的阅读-------------