# C

# 题目大意

给你一个 $n$ 一个 $k$ ，有一个长度为 $n+1$ 的序列 $A$ ，它满足

$a_i = 1, 0 \le i < k$
$a_i = \sum\limits_{j=i-k}^{i-1}a_i, i \ge k$
请你计算， $a_n \% 10^9$

# 数据范围

$1 \le n,k \le 10^6$

# 题解

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

C++

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

正解

Py

代码：

Python

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

# 题目大意

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

将 ? 替换为 o 或者 .

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

有且仅有 $k$ 个 o
任意两个 o 之间不相邻

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

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

# 题解

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

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

将产生最多的 o 总数记为 $O_2$

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

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

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

# 代码

C++

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

ABC

# C

# 题目大意

# 数据范围

# 题解

# D

# 题目大意

# 题解

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

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

# 代码

Kruskal算法

requests模块与简单实践