Rikka with Candies (bitset 조작)
이 문 제 는 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<
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.