首页 程序设计 AtCoder

# A

水题

C++
1
2
3
4
5
void solve () {
    int t;
    cin >> t;
    cout << (t >= 200 && t <= 299 ? "Success" : "Failure") << endl;
}

# B

水题

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve () {
    bool init = 0;
    int n, res = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        string now;
        cin >> now;
        if (!init && now == "private")
            res++;
        else if (now == "login")
            init = 1;
        else if (now == "logout")
            init = 0;
    }

    cout << res<< endl;
}

# C

# 题目大意

给你一个 nn 一个 kk，有一个长度为 n+1n+1 的序列 AA，它满足

  • ai=1,0≤i<ka_i = 1, 0 \le i < k
  • ai=∑j=i−ki−1ai,i≥ka_i = \sum\limits_{j=i-k}^{i-1}a_i, i \ge k
    请你计算，an%109a_n \% 10^9

# 数据范围

  • 1≤n,k≤1061 \le n,k \le 10^6

# 题解

我的思路就是滑动窗口，O(N)O(N) 的复杂度，但是不知道为什么 C/C++C/C++ 的代码错了，PyPy 的能过

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve() {
    cin >> n >> k;
    if (k >= n) {
        cout << 1 << endl;
        return;
    }
    vector<int> a(n + 10);
    int pre = k;
    for (int i = 0; i < k; i++)
        a[i] = 1;

    for (int i = k; i <= n; i++) {
        a[i] = pre % MOD;
        pre = (pre + a[i]) % MOD;
        pre = (pre - a[i - k] + MOD) % MOD;
    }

    cout << a[n] << endl;
}

正解 PyPy 代码：
Python
1
2
3
4
5
6
7
8
9
n, k = map(int, input().split())
s = k
a = [1 for i in range(n + 1)]
for i in range(k, n + 1):
    a[i] = s
    s -= a[i-k]
    s += a[i]
    s %= 1000000000
print(a[n])

# D

# 题目大意

给定一个字符串 ss 和一个整数 kk，字符串由 o ， ? ， . 三种字符组成，你现在要对这个字符串做一种操作

将 ? 替换为 o 或者 .

你可以执行这种操作若干次，但是操作后，这个字符串要满足

  • 有且仅有 kk 个 o
  • 任意两个 o 之间不相邻

你可能能得到不止一个字符串，那么现在要求你输出

  • 若第 ii 个位置只能是 . 或 o 其一的话，则输出其本身
  • 若第 ii 个位置可以是 . 或 o 任一的话，则输出 ?
  • 注意，保证至少你能得到一个字符串

# 题解

以 o.o..o?????o????o 为例，因为题目至少能得到一个字符串，所以将所有 o 的左右两边的 ? 变成 .
即得到， o.o..o.???.o.??.o ，其中有 O1O_1 个 o ，那么还需要从剩下的 ? 中，操作出 k−O1k - O_1 个 o 出来

# 先对问号序列能产生的最多的 o 进行讨论

将产生最多的 o 总数记为 O2O_2

  • 若 ? 个数是奇数：那么若全部变化后，则必为 o.o 交替方能最多
  • 若 ? 个数是偶数：那么可以有两种
    • o.o.
    • .o.o
  • 也就是说，一个长度为 lenilen_i 的 ? 序列，最多能产生 ⌊leni+12⌋\lfloor{\frac{len_i + 1}{2}}\rfloor

# 再对 O1、O2 和 k 的关系进行讨论

  • O1=kO_1=k，不需要额外操作，就能实现题目要求
    • 则问号必须是 .
  • O1+O2==kO_1+O_2==k，若恰好相等
    • 奇数长度的 ? 序列只能是 o.o.o 的模式
    • 偶数长度的问号序列因为即可以是 o.o. 的模式也可以是 .o.o 的模式，所以取全 ?
  • O1+O2>kO_1+O_2 > k，最多能变出的 o 比需要的还多
    • 那么任意一段都可能少 o ，所以全部 ? 都保持不变

# 代码

C++
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
void solve () {
    int n, k, t = 0;
    string s;

    cin >> n >> k >> s;

    for (int i = 0; i < n; i++)
        if (s[i] == 'o') {
            k--;
            if (i != n - 1)
                s[i + 1] = '.';
            if (i != 0)
                s[i - 1] = '.';
        }

    vector<int> res;

    for (int i = 0; i < n; i++) {
        if (s[i] == '?') {
            int j = i;
            while (j < n && s[j] == '?')
                j++;
            res.push_back(j - i), t += (j - i + 1) / 2, i = j - 1;
        }
    }

    if (k == 0) {
        for (int i = 0; i < n; i++)
            cout << (s[i] == 'o' ? 'o' : '.');
    }
    else if (t == k) {
        int idx = 0;

        for (int i = 0; i < n; i++) {
            if (s[i] == '?') {
                int ttt = res[idx++];
                if (ttt & 1)
                    for (int z = 0; z < ttt; z++)
                        cout << ((z & 1) ? '.' : 'o');
                else
                    for (int z = 0; z < ttt; z++)
                        cout << "?";
                i = i + ttt - 1;
            }
            else
                cout << s[i];
        }
    }
    else
        cout << s << endl;
}

更新于 阅读次数 次

请我喝[茶]~(￣▽￣)~*

duoxichangan 微信支付

微信支付

duoxichangan 支付宝

支付宝