Codeforces Round #1082(Div.2)

B

题目大意：

数据范围：

思路：

 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


void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    string t;
    if (n % 2 == 1) {
        if (s[0] == 'b') {
            cout << "NO" << endl;
            return;
        }
        for (int i = 2; i <= n - 1; i += 2) {
            if (s[i] == 'a' && s[i - 1] == 'a' || s[i] == 'b' && s[i - 1] == 'b') {
                cout << "NO" << endl;
                return;
            }
        }
    } else {
        for (int i = 1; i <= n - 1; i += 2) {
            if (s[i] == 'a' && s[i - 1] == 'a' || s[i] == 'b' && s[i - 1] == 'b') {
                cout << "NO" << endl;
                return;
            }
        }
    }
    cout << "YES" << endl;
    return;
}

C1

题目大意：

数据范围：

思路：

 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


void solve() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    int las = -1;
    int ans = 0;
    int i = 0;
    while (i <= n - 1) {
        int j = i + 1;
        map<int, int> ma;
        ma[a[i]]++;
        while (j <= n - 1) {
            if (a[j] <= a[j - 1] + 1 && a[j] > a[i]) {
                j++;
            } 
            else {
                break;
            }
        }
        ans++;
        i = j;
    }
    cout << ans << endl;
    return;
}

C2

题目大意：

数据范围：

思路：

 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


void solve() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll ans = 1LL * n * (n + 1) / 2;
    ll tem = 0;
    vi l(n, -1);
    stack<int> s;
    rep(i, 0, n - 1) {
        while (!s.empty() && a[s.top()] >= a[i]) s.pop();
        if (!s.empty()) l[i] = s.top();
        s.push(i);
    }
    int las = 0;
    vi l2(n, 0);
    rep(i, 1, n - 1) {
        if (a[i] > a[i - 1] + 1) {
            las = i;
        }
        l2[i] = las;
    }
    rep(i, 1, n - 1) {
        int tem = (l2[i] > l[i]) ? i : (i - l[i] - 1);
        ans += 1LL * tem * (n - i);
    }
    cout << ans << endl;
    return;
}

D

题目大意：

数据范围：

思路：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


void solve() {
    int n, k;
    cin >> n >> k;
    if (k > 2 * n - 1 || k < n) {
        cout << "NO" << endl;
        return;
    }
    cout << "YES" << endl;
    if (k == n) {
        rep(i, 1, n) cout << i << ' ' << i << ' ';
        cout << endl;
        return;
    }
    int tem = k - n;
    int res = k + 1 - n;
    cout << "1 2 ";
    rep(i, 3, res) cout << i << ' ' << i - 2 << ' ';
    cout << res - 1 << ' ' << res << ' ';
    rep(i, res + 1, n) cout << i << ' ' << i << ' ';
    cout << endl;
    return;
}

E

题目大意：

数据范围：

思路：

 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


const int MOD = 998244353;
const int MX = 3e5 + 1;
int cnt[MX];
auto init = [] {
    cnt[0] = 1;
    rep(i, 1, MX - 1) { cnt[i] = cnt[i - 1] * 2 % MOD; }
    return 0;
}();
void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    ll ans = 0;
    ll f = 0, g = 0;
    ll pre = 0;
    rep(i, 0, n - 1) {
        if (s[i] == '(') {
            ans += cnt[i];
            ans %= MOD;
            pre++;
            f = (2 * f + g + 1) % MOD;
        } else {
            pre--;
            ans += (f + g + 1) % MOD;
            ans %= MOD;
            g = (2 * g + f + 1) % MOD;
        }
        if (pre < 2) f = 0;
    }
    cout << ans << endl;
    return;
}