Rikka with Candies (bitset 조작)

제목: A 배열 n 개 수, B 배열 m 개 수, q 개 조회, 매번 k 를 주 고 몇 쌍 (i, j) 이 있 는 지 물 어보 면 Ai% Bj = k, 출력 대수 대 모드 2 의 값 
이 문 제 는 bitset 로 풀 수 있 습 니 다. bitset 는 배열 과 유사 하지만 한 사람 당 0 또는 1 로 2 진법 의 한 사람 을 저장 할 수 있 습 니 다.
전체 값 형식 으로 27 위 를 1 로 설정 합 니 다. quiz 1 | = 1 < 27;bitset 로 하면 quizl [27] = 1 을 쓸 수 있 습 니 다.또는 quiz1. set (27);
두 개의 bitset 클래스 로 조작 합 니 다. 첫 번 째 ac, ac. set (i) 는 ac 의 i 위 할당 1 을 표시 하여 i 라 는 숫자 가 존재 하 는 지 여 부 를 표시 합 니 다.
ans[i]= ( bs & (ac>>i) ).count() &1;  ac 가 오른쪽으로 i 자 리 를 옮 겼 습 니 다. 즉, ac 의 모든 수 에서 i 를 빼 는 것 과 비슷 합 니 다. 이것 이 바로 bitset 의 편리 한 점 입 니 다.
& 연산 자 는 두 개의 숫자 만 1 이 고 ac 와 bs 두 개의 bitset & 1 파 는 ac 와 bs 중 한 명 이 서로 같다 &
비트 셋 재 count () 를 되 돌려 주 었 습 니 다. 이 비트 셋 중 1 의 개 수 를 얻 었 습 니 다. 마지막 으로 & 1,% 2 에 해당 합 니 다.
 
두 번 째 bs 는 일련의 남 은 수 를 저장 하 는 데 사용 되 며, 최종 결과% 2 를 알 기 때문에 bs.flip(j); 이 단 계 는 반전 으로 상쇄 할 수 있다.
예 를 들 어 a 는 8b 에 6 과 3 이 있 으 면 8% 6 과 8% 3 이 모두 2 이 고 공헌 은 모두 2 가지 이 며% 2 후 와 0 은 같다. 
 
#include
using namespace std;
const int N=50005;

int a[N],b[N],k[N],ans[N];
bool flag[N];
bitset bs,ac;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int t,n,m,q;
    int maxk;
    cin>>t;
    while(t--)
    {
        ac.reset();//ac     0
        bs.reset();
        memset(flag,0,sizeof(flag));
        maxk=0;
        cin>> n >> m >> q;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            ac.set(a[i]);//ac  a[i]   1
        }
        for(int i=1;i<=m;i++)
        {
             cin>>b[i];
             flag[b[i]]=true;
             maxk=max(maxk,b[i]);
        }

        for(int i=1;i<=q;i++)
        {
            cin>>k[i];
        }
        for(int i=maxk;i>=0;i--)
        {
            ans[i]= ( bs & (ac>>i) ).count() &1;
            if(flag[i])
            {
                for(int j=0;j<=maxk;j+=i)
                {
                    bs.flip(j);// bc  j   ,0 1,1 0
                }
            }
        }
        for(int i=1;i<=q;i++)
        {
            cout<

 
 
 
 
 
 

좋은 웹페이지 즐겨찾기