본문 바로가기

알고리즘19

유량 테크닉 유량의 간선의 cap 1 증가 시켰을 때말 그대로 하나만 1을 증가시켜서 dinic을 구한다. 변화량이 많아봐야 1이다.O(V+E) 차있는 상태에서 한번 더 dinic 을 구하는 것. 유량 cap 1 감소시키는 것.u->v 로 가는 간선에서, f == c 일때만 중요해.u->v 에 풀 수 있다. (V+E) 간선 우선순위를 정한다. ==> 응용하기 1,2,3,4 를 mcmf 로 간선의 cost 2^1, 2^2, 2^3, 2^4 ...로 정해서 구한다. 2018. 3. 31.
codeforces)447b B번 문제인데 나름 까다로운 예외케이스가 존재한다.n행, m열 이 주어질 때, n-1, m-1 개로 만들 수있는 모든 경우의수가 답이된다이 때 짝수행, 홀수열 이나 홀수행, 짝수 열인 경우 -1 이 오게되면 답이 존재하지 않는다. 또한 범위가 10 의18승이므로 단순한 n*m 으로는 long long 조차 오버플로우가 난다.따라서 리턴값에 함수를 한번더 사용하였다. 시간복잡도 O(log^2) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include #include using namespace std;typedef long long ll;ll n,m,k;const ll mod = 10.. 2017. 12. 21.
알고리즘)(pow(A,B))mod C 를 logB 시간에 구하는 함수 1234567891011121314151617181920212223#include #include typedef long long ll;ll a,b,c; ll mypow(ll a,ll b,ll c){ ll ret = 1ll; while(b>0){ if(b&1){ ret = (ret* a) % c; } b /= 2; a = (a*a) % c; } return ret;} int main(){ freopen("input.txt","r",stdin); scanf("%lld %lld %lld",&a,&b,&c); printf("%lld",mypow(a,b,c));}Colored by Color Scriptercs 간단하다. 2017. 11. 26.
acm-cicpc 수학정복 1.애드혹 수학문제(기초적인 수학 지식) * 수학적 시뮬레이션 : 특정 혀애의 루프를 사용해서 무식하게 풀리는 유형* 패턴이나 공식찾기 : 문제 설명을 주의 깊게 읽고 패턴이나 간략화 된 공식을 찾도록 요구하는 문제* 격자 : 복잡한 형태의 격자도 있긴하지만 문제를 푸는 사람이 창의적으로 패턴을 찾아내야 하는 문제.* 수 체계 및 수열 : 실존하는 수체계나 수열의 정의가 등장한다. 일정 범위의 속하는 수(수열) 을 만들어내기, n번째 수 구하기, 주어진 수(수열)이 정의에 부합하는지 검사해보기 등이있다. 보통은 문제 설명에 나온 정의를 주의 깊게 따라가는 것이 풀이의 핵심이나 어려운 문제는 공식을 먼저 단순화해야 하는 경우도 있다. 1) 피보나치수2) 팩토리얼3) 교란4) 카탈란 수5) 등차급수(산술급수.. 2017. 9. 15.

티스토리툴바