D. Rudolf and the Ball Game

题解：模拟+去重

每一次扔球都将所有可能性加入队列，并设为一层；然后将一层的可能性挨个出列并进行 ((qj+ri−1) mod n+1)，((qj−ri−1+n) mod n+1)操作，然后去重后入列。

code

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N],b[1005];
int main(){
//    freopen("input.txt","r",stdin);
    int t;
    cin>>t;
    while (t--){
        int n,m,x;
        cin>>n>>m>>x;
        int r=0,l=0;
        a[r++]=x;
        for (int i=1;i<=m;i++){
            memset(b,0,sizeof(b));
            int ri,R=r;
            char c;
            cin>>ri>>c;
            while (l<R){
                int zero=(a[l]+ri-1)%n+1,one=(a[l]+n-ri-1)%n+1;
                if (c=='?') {
                    if (b[zero]==0){
                        a[r++]=zero;
                        b[zero]=1;
                    }
                    if (b[one]==0){
                        a[r++]=one;
                        b[one]=1;
                    }
                }
                if (c=='0')
                    if (b[zero]==0){
                        a[r++]=zero;
                        b[zero]=1;
                    }
                if (c=='1') 
                    if (b[one]==0){
                        a[r++]=one;
                        b[one]=1;
                    }
                l++;
            }
        }
        cout<<r-l<<endl;
        sort(a+l,a+r);
        cout<<a[l++];
        while (l<r) cout<<" "<<a[l++];
        cout<<endl;
    }
    return 0;
}