Problem – D – Codeforces

用记忆化搜索过的，然而DP能快300ms

记忆化搜索 | \(\texttt{set}\)模拟

核心思路一致，都是通过定义一个状态，即在第t次到达第now点来去重剪枝

记忆化搜索

int n, m, x;
std::vector<std::pair<int, char>> step;
std::set<int> S;

int getClock(int x, int dis) {
    dis %= n;
    if (x + dis > n) return (x + dis) % n;
    else return x + dis;
}

int getAntiClock(int x, int dis) {
    dis %= n;
    if (x - dis < 1) return n - (dis - (x - 1)) + 1; 
    else return x - dis;
}

bool vis[1010][1010];

void dfs(int now, int t) {
    if (t == m) {S.insert(now); return ;}
    if (vis[now][t]) {return ;}
    vis[now][t] = true;
    auto[dis, opt] = step[t];
    if (opt == '?' or opt == '0') {
        dfs(getClock(now, dis), t + 1);
    }
    if (opt == '?' or opt == '1') {
        dfs(getAntiClock(now, dis), t + 1);
    }
}

\(\texttt{set}\)​模拟

这里STD还利用了几个取模trick

首先是把 \(x \mod{n}\) 转化成 \((x – 1)\mod {n} + 1\) ，防止 \(x = n\) 时想要得到 \(n\) 却得到 \(0\)。

首先是逆时针可能是负数，所以最后再加上 \(n\) 防止取模失效。

//本质上也是记忆化搜索
//通过set自动把当前位置且次数都相同的状态去重了

void solve() {
    int n, m, x;
    std::cin >> n >> m >> x;
    std::set<int> S[2];
    bool cur(false);
    S[cur].insert(x);
    while (m--) {
        int d; char opt;
        std::cin >> d >> opt;
        while (!S[cur].empty()) {
            int now(*S[cur].begin());
            S[cur].erase(now);
            if (opt == '?' or opt == '0') {
                S[cur ^ 1].insert((now + d - 1) % n + 1);
            }
            if (opt == '?' or opt == '1') {
                S[cur ^ 1].insert((now - d + n - 1) % n + 1);
            }
        }
        cur ^= 1;
    }
    std::cout << sz(S[cur]) << '\n';
    for (auto& x : S[cur]) std::cout << x << ' ';
    std::cout << '\n';
}

可达性DP

即定义状态 \(dp_{i, j}\) 为第 \(i\) 次操作第 \(j\) 点的可达性。

转移方程很直接

\[dp_{i, j} = dp_{i – 1, (j + d – 1)\mod n + 1}(opt = \text{?} \| opt = \text{0}) \]

\[dp_{i, j} = dp_{i – 1, (j – d + n – 1)\mod n + 1}(opt = \text{?} \| opt = \text{1}) \]

原始写法

因为该题没有卡空间，所以能过

void solve() {
    int n, m, x;
    std::cin >> n >> m >> x;
    std::vector dp(m + 1, std::vector<short>(n + 1));
    dp[0][x] = 1;
    for (int i = 1; i <= m; i++) {
        int d; char opt;
        std::cin >> d >> opt;
        if (opt == '?' or opt == '0') {
            for (int j = 1; j <= n; j++) {
                dp[i][j] |= dp[i - 1][(j - d + n - 1) % n + 1];
            }
        }
        if (opt == '?' or opt == '1') {
            for (int j = 1; j <= n; j++) {
                dp[i][j] |= dp[i - 1][(j + d - 1) % n + 1];
            }
        }
    }
    std::cout << std::count(all(dp[m]), 1) << '\n';
    for (int i = 0; i <= n; i++) if (dp[m][i] == 1) {
        std::cout << i << ' ';
    }
    std::cout << '\n';
}

优化空间

t宝和jls都是进一步优化了空间，因为该状态只会从上一步转移而来，所以完全可以省去第一维

void solve() {
    int n, m, x;
    std::cin >> n >> m >> x;
    x--;
    std::vector<bool> dp(n);
    dp[x] = true;
    for (int i = 0; i < m; i++) {
        int d; char opt;
        std::cin >> d >> opt;
        std::vector<bool> newDp(n);
        for (int j = 0; j < n; j++) if(dp[j]) {//从0开始，直接避免了取模会为0的问题
            if (opt != '1') {
                newDp[(j + d) % n] = true;
            }
            if (opt != '0') {
                newDp[(j - d + n) % n] = true;
            }
        }
        dp = newDp;
    }
    std::cout << std::count(all(dp), 1) << '\n';
    for (int i = 0; i < n; i++) if (dp[i]) {
        std::cout << i + 1 << ' ';
    }
    std::cout << '\n';
}

另一道题

Problem – E – Codeforces

依然可以用可达性DP。

定义 \(dp_i\) 为 \([1, i]\) 区间是否合法

假设 \(a_i\)​ 就是表示区间长度的值，则通过之前合法的情况递推

这里取 \(i – 1\) 是因为 \(i\) 时表示长度的那个数的下标，不用算进去

如果他在他表示区间的左边，则 \([1, i + a_i]\) 的合法条件是 \([1, i – 1]\) 合法

如果他在他表示区间的右边，则 \([1, i]\) 的合法条件是 \([1, i – 1 – a_i]\) 合法

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    std::vector<bool> dp(n + 1);
    dp[0] = true;
    for (int i = 1; i <= n; i++) {
        if (i + a[i] <= n and dp[i - 1]) {
            dp[i + a[i]] = true;
        }
        if (i - 1 - a[i] >= 0 and dp[i - 1 - a[i]]) {
            dp[i] = true;
        }
    }
    dp[n] ? YES : NO;
}