typedef long long ll; ll cache[MAX_N][MAX_N]; //use dp ll comb(int n,int r) { if(r==0||n==r)return 1; ll&ret=cache[n][r]; if(ret!=-1)return ret; return ret=comb(n-1,r-1)+comb(n-1,r); } //if n is small ll comb(int n,int r) { if(r==0||n==r)return 1; return comb(n-1,r-1)+comb(n-1,r); } nCr=(n-1)C(r-1)+(n-1)Cr 점화식을 이용한 간단한 재귀함수이다. 경우의 수의 특성상 수가 조금만 커져도 int범위를 간단히 넘어버리니 왠만한 경우에는 long long 을 선언해서 풀어주어..
본 포스팅은 구종만님의 블로그를 스크랩한 글임을 밝힙니다. http://theyearlyprophet.com/heavy-light-decomposition.html Heavy-Light Decomposition Heavy-Light Decomposition @jongman 팔로우하기 트윗하기 [처음으로] [모든 글 보기] [같은 카테고리의 글 보기: 알고리즘] 작년에 1년동안 쉬면서 한 여러 가지 일 중 하나가, 오랜만에 다시 프로그래밍 대회에 참가하는 것이었다. 비록 연습만 열심히 하고 대회에 제대로 참가하진 못했지만, 최근 나온 문제들을 풀어볼 기회가 되어서 좋았다. 최근 문제 출제 경향은 과거에 비해 꽤 바뀌었음을 느꼈는데, 기존에 출제되지 않았던 테크닉들 theyearlyprophet.com 1/..
https://www.acmicpc.net/problem/10590 10590번: Burrito King The first line contains three integers \(n\), \(A\), and \(B\) (1 ≤ \(n\) ≤ 100 000, 0 ≤ \(A\), \(B\) ≤ 109), the number of ingredients, the least amount of Albert’s joy and the maximal amount of Barney’s unhappiness. Each of the following \(n\) lines cont www.acmicpc.net 입력 The first line contains three integers n, A, and B (1 ≤ n ≤ 100..
https://www.acmicpc.net/problem/17408 17408번: 수열과 쿼리 24 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오 1 i v: Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 l r: l ≤ i >M; while(M--) { int type; cin>>type; if(type==1) { int a,b; cin>>a>>b; seg.update(a-1,b); } else { int l,r; //first Max,second Left Max,second Right Max pairfMax,sLMax,sRMax; cin>>l>>r; fMax=seg.query(l-1,r-1); sLMax=seg.qu..
https://www.acmicpc.net/problem/18118 18118번: 7-세그먼트 디스플레이 각 테스트 케이스마다 n개의 7-세그먼트 디스플레이에 표현할 수 있는 가장 큰 m의 배수를 한 줄에 하나씩 출력한다. www.acmicpc.net 문제 7-세그먼트 디스플레이란 아래와 같이 7개의 선분으로 글자를 표시할 수 있는 장치를 말한다. 최근 시프트는 디지털 회로에 관한 강의를 듣고 있다. 시프트가 이번 주에 받은 과제의 내용은 아래와 같다. 7-세그먼트 디스플레이 n개를 사용한 회로를 구성한다. 양의 정수 m을 입력받아, n개의 7-세그먼트 디스플레이에 표현할 수 있는 가장 큰 m의 배수를 표시하시오. 다행히도 입출력은 강의자료에 전부 나와 있어서 그대로 따라 하면 됐기 때문에 별로 문제가 ..
https://www.acmicpc.net/problem/18170 18170번: 두 동전 언리미티드 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, 두 동전의 위치는 다르다. 버튼은 "왼쪽", "오른쪽", "위", "아래"와 같이 4가지가 있다. 버튼을 누르면 두 동전이 버튼에 쓰여 있는 방향으로 동시에 이동하게 된다. 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다. 동전이 이동하려는 방향에 칸이 없 www.acmicpc.net 문제 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각..