(25672) Even and Odd Combinations

https://www.acmicpc.net/problem/25672

단계별로 풀어보기

41단계(인터랙티브와 투 스텝 1) 8번째

 

 

 

어떤 집합의 부분집합 중 원소의 개수가 홀수인 것과 짝수인 것은 같다는 것을 보이기 위해 일대일 대응 함수를 만들어야 하는 문제

대응시키는 방법은 여러가지가 있지만 가장 간단한 구현은 임의의 원소를 잡고 해당 원소의 포함 여부를 토글하는 것이다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

void answer(int n, int k){
  vector<bool> v(n+1);
  
  for(int i=0;i<k;i++){
    int t;
    
    cin >> t;
    
    v[t]= true;
  }
  
  if(v[1]){
    cout << n << " " << k-1 << "\n";
    v[1]= false;
  }else{
    cout << n << " " << k+1 << "\n";
    v[1]= true;
  }
  
  for(int i=1;i<=n;i++){
    if(v[i]) cout << i << " ";
  }
  
  cout << endl;
}

int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
  
  cin >> T;
  
  while(T--){
    int n, k;
    
    cin >> n >> k;
    
    answer(n, k);
  }
  
  return 0;
}