joseph0528 코딩 블로그

solved.ac 티어 : 플래 3 www.acmicpc.net/problem/18437 18437번: 회사 문화 5 총 N명의 직원이 재직 중인 회사가 있고, 각 직원은 1번부터 N번까지 번호가 매겨져 있다. 이 회사는 수직적인 구조를 가지고 있고, 대표를 제외한 모든 직원은 한 명의 직속 상사를 갖고 있다. www.acmicpc.net 컴퓨터가 켜져 있는 상태를 1, 컴퓨터가 꺼져있는 상태를 0으로 두고 구간을 1 또는 0으로 변경한 뒤 구간 합을 출력하면 된다. #include using namespace std; typedef long long ll; typedef pair nod; const ll N=1000000; ll n,m; vector graph[N]; nod Qu[N]; ll cnf=0..

solved.ac 티어 : 플래 3 www.acmicpc.net/problem/14288 14288번: 회사 문화 4 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 이 문제는 회사 문화 2, 회사 문화 3를3을 합친 문제인데 회사 문화 2를 저장하는 트리와 회사 문화 3을 저장하는 트리를 만들고 각각 업데이트를 해준 뒤 출력할 때 회사 문화 2의 출력 값+회사 문화 3의 출력 값을 해주면 된다. BOJ 14268(회사 문화 2)풀이 solved.ac 티어 : 플래티넘 3 www.acmicpc.net/problem/14268 14268번..

solved.ac 티어 : 플래티넘 4 www.acmicpc.net/problem/14287 14287번: 회사 문화 3 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 이 문제는 다른 회사 문화 문제와는 다르게 위에서 아래로 값을 더해주는 것이 아닌 밑에서 위로 값을 더해주는 문제이다. 이 문제의 풀이는 생각보다 간단하다. dfs으로 새로 해당 구간을 만들고 그 구간에 대한 이진트리를 그리고 x노드의 값에 w를 더한다고 해보자. 그러면 x를 가지고 있는 구간에만 변경이 생긴다. 그러므로 구간이 (x,x)인 위치에 w를 더해주면 x를 포..

solved.ac 티어 : 플래티넘 3 www.acmicpc.net/problem/14268 14268번: 회사 문화 2 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 회사 문화 1과 같은 문제인데 1은 마지막에 모든 정점마다 합을 구해주는 거고 2는 2가 들어올 때마다 구간의 합을 구해주는 것이다. BOJ 14267(회사 문화 1)풀이 solved.ac 티어 : 골드 4 www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가..

solved.ac 티어 : 플래 3 www.acmicpc.net/problem/16404 16404번: 주식회사 승범이네 첫 번째 줄에 승범이를 포함한 판매원들의 수 N(1 ≤ N ≤ 100,000), 명령의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 판매원들은 1번부터 N번까지 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 판 www.acmicpc.net 이문제는 트리에 어떤 노드가 선택되었을 때 그 노드와 노드의 자식들에게 w만큼 값이 더해지는 문제다 대신 이 문제는 다른 평범한 세그먼트 트리처럼 이진트리가 아니다. 그럼 어떻게 할 수 있을까? 예시에 있는 입력을 가지고 트리를 만들면 이렇게 된다.(좀 이상한 건 어쩔 수 없다) A부터 E까지 순서대로 1,2,3,4,5라고 할 때 A..

solved.ac 티어 : 골드 4 www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 이문제는 설명은 길지만 요약하자면 m개의 줄에 2개의 점이 주어질 때 그 2개의 점이 같은 집합에 속하는 번째수를 출력하는 것이다. 이문제는 유니온 파인드로 풀 수 있다. import sys sys.setrecursionlimit(10**9) input=sys.stdin.readline n,m=map(int,input().split()) uf=[-1]*(n+1) def ..

solved.ac 티어 : 다이아 4 www.acmicpc.net/problem/16910 16910번: mex와 쿼리 mex는 어떤 수열에 포함되지 않은 수 중에서 가장 작은 자연수를 찾는 함수이다. 예를 들어, mex([1,2,3]) = 4, mex([5,3,1,1,4]) = 2, mex([1,5,2,1,5,2,1,2]) = 3이다. 비어있는 배열 A와 쿼리 N개가 주어졌을 때, www.acmicpc.net 생각보다 간단한 세그레이지이다. 1 l r: 구간 [l, r]에 속하는 모든 자연수를 배열 A에 추가한다. 배열에 이미 있는 자연수는 또 추가하지 않는다. 2 l r: 구간 [l, r]에 속하는 모든 자연수를 배열 A에서 제거한다. 3 l r: 구간 [l, r]에 속하는 모든 자연수 x에 대해서,..

solved.ac 티어 : 플래 4 www.acmicpc.net/problem/20052 20052번: 괄호 문자열 ? 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이 www.acmicpc.net 이문제도 보자마자 버거운 버거라 응요이라는 거를 알 수 있다 그렇기 때문에 이것도 버거운 버거를 풀면 날먹이다. 이문제는 변경이 없는 대신 올바른 괄호 문자열인지 확인하는 것이 입력으로 주어진다. 그러므로 변경 부분을 지우고 입력을 받은 값을 구간에 넣어주면 끝이다. #include #include using namespace std; typedef long lo..

solved.ac 티어 : 플래 2 www.acmicpc.net/problem/17407 17407번: 괄호 문자열과 쿼리 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이 www.acmicpc.net 이문제는 딱 봐도 버거운 버거랑 비슷한 문제이다. 버거운 버거를 풀고 오면 거저로 얻는 문제이다. 버거운 버거:joseph0528.tistory.com/8 BOJ 19851(버거운 버거)풀이 세그 레이지를 이용했습니다. solved.ac 티어 : 다이아 5 www.acmicpc.net/problem/19851 19851번: 버거운 버거 드디어 산업기능요원 복무..

solved.ac 난이도 :플래 3 www.acmicpc.net/problem/12844 12844번: XOR 크기가 N인 수열 A0, A1, ..., AN-1이 주어졌을 때, 다음 두 종류의 쿼리를 수행해보자. 1 i j k: Ai, Ai+1, ..., Aj에 k를 xor한다. 2 i j: Ai, Ai+1, ..., Aj를 모두 xor한 다음 출력한다. www.acmicpc.net 이문제는 일반 세그 레이지에서 +를 XOR(^)로 바꿔주면 된다. 하지만 이렇게만 바꿨을 경우 틀리게 된다. tree[n]=lazytree[n]*(e-s+1); 이거를 if((e-s+1)%2!=0){ tree[n]^=lazytree[n];//*(e-s+1); } 이렇게 바꿔주면 된다. 저렇게 바꿔 주는 이유는 어떤수를 a라고..