用记忆化搜索过的，然而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';
}
另一道题
依然可以用可达性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;
}