题目大意

有 $n$ 个人投球，投了 $m$ 次。第 $i$ 次投球时想左、右或者随便一个方向投掷 $r_i$ 个人。从第 $x$ 个人开始投球，询问最后球在最后有可能在谁的手里。

其中 $1\le n,m \le 1000,1\le x,r\le n,\sum n\cdot m \le 2\times 10^5$。

思路

如果遇到方向不确定的情况，可以暴力的考虑直接枚举。考虑在最坏的情况下，全部的投球肯能方向不确定，那么我们就需要枚举 $2^m$，因为这些人一共会接到 $2^m$ 次球。

在一轮投球中只有 $n$ 个人但是却接到了 $2^m$ 次球，可见一个人可能会多次接到球。因为在一轮中，不论一个人接到多少次球那么效果其实都是一样的。

所以设 $f_{i,j}$ 表示在第 $i$ 次投球时，第 $j$ 个人是否有可能拿到球。假设 $g(j,r_i)$ 表示第 $j$ 个人移动 $r_i$ 后的位置，发么状态转移方程为

$f_{i,g(j,r_i)}=\max(f_{i,g(j,r_i)},f_{i-1,j})$

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005;
int n,m,a[N],f[N][N],x;
char c[N];
void solve(){
	cin>>n>>m>>x;
	for(int i=1;i<=m;i++) cin>>a[i]>>c[i];
	for(int i=0;i<=m;i++) for(int j=0;j<=n;j++) f[i][j]=0;
	f[0][x-1]=1;
	for(int i=1;i<=m;i++){
		for(int j=0;j<n;j++){
			if(c[i]=='0'||c[i]=='?') f[i][(j+a[i])%n]|=f[i-1][j];
			if(c[i]=='1'||c[i]=='?') f[i][(j-a[i]+n)%n]|=f[i-1][j];
		}
	}
	vector<int> ans;
	for(int i=0;i<n;i++) if(f[m][i]) ans.push_back(i+1);
	cout<<ans.size()<<'\n';
	for(int i:ans) cout<<i<<' ';
	cout<<'\n';
}signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;cin>>T;
	while(T--) solve();
	return 0;
}