전체 글 썸네일형 리스트형 BOJ)12844 XOR 문제: icpc.me/12844 특정 구간에 XOR을 하거나 구간을 XOR한 값을 출력하는 문제이다. N,M이 50만이므로 구간에 대한 쿼리를 빠르게 처리 하기 위해 세그먼트 트리를 사용해야 한다. 이때 한 지점에 대해서가 아닌 구간에 대한 업데이트가 이루어지므로 lazy propagation을 이용하여 최적화 시켜줄 필요가 있다. 주의해야 할 점은 항상 a가 b보다 작지는 않다는 것이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include #include using namespace std;int n, m, a, b, c, d;in.. 더보기 BOJ)10815 숫자 카드 문제: icpc.me/10815 N개의 카드와 M개의 카드가 있을 때 M개의 카드 들이 각각 N개에 카드에 속해 있나 확인하는 문제이다.O(NM)의 방법으로 풀 경우 TL을 받으므로 binary_search를 이용하여 O(logNM)의 방법으로 해결하면 된다. 1234567891011121314151617181920212223#include #include #include using namespace std;int n, m, x;vector vt;int main() { scanf("%d", &n); for (int i = 0; i 더보기 BOJ)1733 등번호 문제: icpc.me/1733 참가자와 등번호들로 이루어진 이분 그래프를 이분매칭하는 문제이다. 이분 매칭의 역추적은 매칭을 시킬 때 배열등에 저장하여 쉽게 할 수 있다. 다만 N이 100만이므로 매칭때마다 memset을 사용할 경우 TL을 볼 수도 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #include #include using namespace std;vector vt;int check[1000100];int backmatch[1000100];int r[1000100];int n, x, y, s;bool dfs(int here) { .. 더보기 이전 1 ··· 112 113 114 115 116 117 118 다음