https://codeforces.com/contest/1550

D. Excellent Arrays

题意
要求构造一个数列 a ，使得 a_i + a_j = i + j 且 a_i \neq i
给定数列长度 n，元素上下界 l, r
求数列的种类数模 10^9 + 7

数据范围
2\leq n \leq 2\sdot 10^5, -10^9 \leq l \leq 1, n \leq r \leq 10^9
多组数据保证 n 的和不超过上界

做法
首先很容易发现，数列一定是由 i - x 或 i + x 一半一半构成的（奇数有一个可任选）
再看复杂度，很显然，枚举一个量级为 n 的东西即可
进一步地，发现 l, r, x 要满足下列关系
不妨考虑数列分为三段：分界点为最靠前的- x 与 最靠后的+ x，不妨记为ll, rr
那么有关系 ll - x \geq l, rr + x \leq r，即 rr \leq r - x, ll \geq l + x
即给定 x，大于 r - x 的 i 必须全取 i - x, 小于 l + x 的 i 必须全取 i + x，剩下的可任意取
注意到只有当 r - x < n 或 l + x > 1 的时候会受上下界影响，且不能过半，只用枚举一个 O(n) 的范围即可

AC代码

#include <iostream>
using namespace std;

#define int long long

const int MAX_N = 2E5 + 100;
const int MOD = 1E9 + 7;

int bin(int x, int n) {
    int ret = 1;
    for (; n; n >>= 1, x = x * x % MOD)
        if (n & 1) ret = ret * x % MOD;
    return ret;
}

int fac[MAX_N], facInv[MAX_N];
void initInv(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % MOD;
    for (int i = 0; i <= n; ++i) facInv[i] = bin(fac[i], MOD - 2);
}

// 0 <= n <= m
inline int C(int n, int m) {
    return fac[m] * facInv[n] % MOD * facInv[m - n] % MOD;
}

int T;
int n, l, r;

signed main() {
    initInv(2E5);

    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        cin >> n >> l >> r;
        int ans = 0;
        int ll = min(r - n, 1 - l);
        int rr = ll + (n + 1) / 2;

        if (n & 1) {
            ans += 2 * max(0ll, ll - 1) * C(n / 2, n) % MOD;
            for (int x = max(1ll, ll); x <= rr; ++x) {
                int rp = max(0ll, n - r + x);
                int lp = max(0ll, l + x - 1);
                if (lp <= n / 2 && rp <= n / 2 + 1) {
                    ans = (ans + C(n / 2 - lp, n - lp - rp)) % MOD;
                }
                if (lp <= n / 2 + 1 && rp <= n / 2) {
                    ans = (ans + C(n / 2 + 1 - lp, n - lp - rp)) % MOD;
                }
            }
        } else {
            ans += max(0ll, ll - 1) * C(n / 2, n) % MOD;
            for (int x = max(1ll, ll); x <= rr; ++x) {
                int rp = max(0ll, n - r + x);
                int lp = max(0ll, l + x - 1);
                if (lp <= n / 2 && rp <= n / 2) {
                    ans = (ans + C(n / 2 - lp, n - lp - rp)) % MOD;
                }
            }
        }

        cout << ans << '\n';
    }

    return 0;
}

心路历程
最开始考虑枚举 ll,rr，利用式子 1 \leq x \leq Min\{ll - l, r - rr\} 确定 x
发现做不了，枚举 x 更方便，遂改邪归正

E. Stringforces

题意
给一个长度为 n 的包含前 k 个小写字母与 ? 的字符串
要求将 ? 替换为小写字母，使得以每个小写字母为全部元素的最长连续子串长度的最小值最大
例如串 aaababbbb a的长为3，b的长为4，最小值为3

数据范围
1\leq n \leq 2 \sdot 10^5, 1\leq k \leq 17

做法
挺明显的二分答案，关键在于如何check
因为 k 给的很小，所以check往 O(2^k) 上考虑，但是在那之前首先考虑更小的做法
题意转化为，给定一个长度 m，要求对于每种字母都构造出至少一段这样长度的子串
假如给定这些子串的排列顺序，那么贪心可以 O(k + n) 解决
即只要使每个子串尽量靠左即可，具体做法为dp记录每种元素的最靠左的完成子串位置即可
但是枚举排列顺序需要 O(k!) 显然不行
不过显然这 k! 种排列大量重叠，具有相同前缀
很容易想到优化成 O(2^k) 的做法，类似dfs弄一下，2^k 状态，O(k) 转移，再 O(kn) 预处理
check总复杂度为 O(k2^k + kn)

AC代码

#include <iostream>
#include <queue>
using namespace std;

const int MAX_N = 2E5 + 100;
const int MAX_K = 20;

int n, k;
char s[MAX_N];
int a[MAX_N], dp[MAX_N];
int b[MAX_N][MAX_K];

bool check(int m) {
    static int tmp[MAX_K];
    for (int i = 1; i <= k; ++i) {
        tmp[i] = -1;
        b[n + 1][i] = n + 1;
    }
    for (int i = n; i >= 1; --i) {
        if (a[i]) {
            for (int j = 1; j <= k; ++j) {
                if (j != a[i]) tmp[j] = -1;
            }
            if (-1 == tmp[a[i]]) tmp[a[i]] = i;
        } else {
            for (int j = 1; j <= k; ++j) {
                if (-1 == tmp[j]) tmp[j] = i;
            }
        }

        for (int j = 1; j <= k; ++j) {
            if (tmp[j] - i + 1 >= m) {
                b[i][j] = i + m - 1;
            } else {
                b[i][j] = b[i + 1][j];
            }
        }
    }
    // init

    for (int i = 0; i <= (1 << k) - 1; ++i) {
        dp[i] = n + 2;
    }
    queue<int> que;
    que.push(0);
    dp[0] = 1;
    while (!que.empty()) {
        int u = que.front();
        que.pop();

        for (int i = 1, j = 1; j <= k; i <<= 1, j += 1) {
            if (~u & i) {
                int v = u | i;
                int w = b[dp[u]][j];
                if (w <= n) {
                    if (n + 2 == dp[v]) que.push(v);
                    dp[v] = min(dp[v], w + 1);
                }
            }
        }
    }

    return dp[(1 << k) - 1] <= n + 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> k;
    cin >> (s + 1);
    for (int i = 1; i <= n; ++i) {
        a[i] = '?' == s[i] ? 0 : s[i] - 'a' + 1;
    }
    a[n + 1] = -1;
    // init

    int l = 1, r = n;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    if (!check(r)) r -= 1;

    cout << r << endl;

    return 0;
}

心路历程
自己想的时候只想到二分答案和 2^k，之后就懵逼了
最后看了题解才捋清了思路
转移的时候忘记规划取min以及多次入队了，WA一发MLE一发，数据似乎挺水的