competitive_programming

경쟁 프로그래밍 및 연습

이들은 경쟁 프로그래밍 문제와 다양한 연습의 C ++ 솔루션입니다. 다른 알고리즘과 데이터 구조를 사용하여 비슷한 문제가 해결됩니다. 때로는 표준 라이브러리에서 제공하는 것, 때로는 내 자신의 것들을 사용하는 것입니다.

대부분의 솔루션은 EX-UVA 온라인 판사 제한으로 인해 C+11입니다. 성공적인 제출 후 일부는 C ++ 14/17 기능을 사용하도록 수정되었습니다.

Ex-UVA OJ 문제

문제 소스

ID	제목	카테고리
001 08	최대 합계	선형 검색, 최대 합계 서브 어레이, Kadane의 알고리즘
001 09	스커드 버스터	볼록한 선체
001 12	나무 합계	이진 트리
001 20	플랩 잭 스택	스택, 팬케이크 분류
001 22	레벨의 나무	이진 트리, 레벨 주문 트래버스, 폭이 넓은 첫 번째 검색
001 40	대역폭	순열, 역 추적
001 47	불화	동적 프로그래밍, 코인 변경
001 64	문자열 컴퓨터	동적 프로그래밍, 편집 거리
002 00	희귀 주문	토폴로지 분류, 깊이 우선 검색
002 16	줄을 서	동적 프로그래밍, 해밀턴 경로, 비트 마스크
002 18	나방 근절	볼록한 선체
002 22	예산 여행
002 40	가변 Radix Huffman 인코딩	허프만 트리, 깊이 우선 검색
002 59	소프트웨어 할당
002 64	Cantor를 믿으십시오
002 70	안감
002 94	분배기
003 34	동시 사건 식별
003 48	최적의 배열 멀티. 순서	동적 프로그래밍, 매트릭스 체인 곱셈
003 50	의사 임의 숫자
003 53	성가신 팔린 드롬	다항식 롤링 해시, 문자열 처리
003 57	방법을 세십시오
003 61	경찰과 강도
003 72	Whatfix 표기법	바이너리 트리, 사전//in-ter-order traversals 변환
003 74	큰 모드	이진 지수, 모듈 식 지수
004 29	단어 변환
004 37	바빌론 타워
004 39	기사 움직임	폭 넓은 첫 번째 검색
004 54	아나그램
004 55	주기적인 문자열	문자열, Knuth – Morris – Pratt 알고리즘
004 59	그래프 연결	Disjoint-Set/Union-Find, 그래프 연결된 구성 요소
004 69	플로리다의 습지
004 81	무슨 일이 일어나고 있는지	가장 긴 후속, 이진 검색
004 82	순열 배열
005 01	블랙 박스	AVL 트리, 이진 트리 반복자
005 07	Jill은 다시 타고 있습니다	선형 검색, 최대 합계 서브 어레이, Kadane의 알고리즘
005 16	주요 땅
005 26	문자열 거리	동적 프로그래밍, 편집 거리
005 36	나무 회복	바이너리 트리, 사전//in-ter-order traversals 변환
005 40	팀 대기열
005 43	Goldbach 추측	소수
005 48	나무
005 51	괄호로 묶여 있습니다
005 58	웜홀
005 62	동전을 분할
005 68	사실 만	계승, 재발 관계
005 74	요약 해요
005 82	무작위로 유선 신경망	깊이 우선 검색, 그래프 이항 구성 요소
005 83	주요 요인
006 12	DNA 분류	정렬, 반전 계산
006 23	500!	팩토 노트, 큰 정수
006 30	아나그램
006 39	루크하지 마십시오
006 74	동전 변경
006 79	공을 떨어 뜨립니다
006 84	적분 결정자	가우스 제거, 유클리드 알고리즘
006 86	골드 바흐 추측 II	소수
007 01	고고학자의 딜레마	로그
007 14	책을 복사합니다	선형 분할, 암시 적 이진 검색
007 19	유리 구슬	어휘식 최소 회전, Duvan의 알고리즘
007 27	방정식	표현 구문 분석, 세척 된 야드 알고리즘
007 29	해밍 거리 문제	역 추적
007 50	여덟 여왕 체스 문제	역 추적
007 87	최대 하단 시퀀스 제품	최대 제품 서브 어레이, 큰 정수
007 93	네트워크 연결
007 96	중요한 링크	깊이 우선 검색, 그래프 브리지
008 20	인터넷 대역폭
008 33	물이 떨어집니다
008 68	수치 미로	역 추적
008 72	주문
009 08	컴퓨터 사이트를 다시 연결합니다
009 29	숫자 미로
009 42	순환 숫자	합리적 번호, 소수 분수, 해시 테이블
009 90	금을위한 다이빙
009 91	안전한 경례	조합, 재발 관계, 카탈로니아어 번호
011 21	후속	슬라이딩 창
011 75	숙녀의 선택	안정적인 매칭 문제, 게일 캡리 알고리즘
012 10	연속 소수의 합	소수
012 52	20 가지 질문
012 60	매상
012 93	상징적 파생	표현 구문 분석, 세척 된 야드 알고리즘, 상징적 평가.
013 72	로그 점프
016 50	숫자 문자열	조합, 재발 관계
100 03	절단 막대
100 04	bicoloring
100 18	반전 및 추가	정수, 196- 전환
100 61	얼마나 많은 0과 숫자?	계승, 소수, 인수 화, 로그
100 79	피자 절단	조합, 중심 다각형 수
101 07	중앙값은 무엇입니까?	우선 큐, 온라인 알고리즘
101 71	회의 교수. 미구엘
101 93	당신이 필요한 것은 사랑뿐입니다	가장 큰 일반적인 구분
102 20	나는 큰 숫자를 좋아한다!	팩토 노트, 큰 정수
102 23	노드 수	조합, 재발 관계, 카탈로니아어 번호
102 29	모듈 식 피보나치	Fibonacci 번호, 모듈 식 지수
102 45	가장 가까운 쌍 문제	2d 가장 가까운 포인트
102 68	498-bis	호너의 규칙
102 82	바벨 피쉬	해시 테이블
102 98	파워 스트링
103 05	주문 작업
103 11	골드 바흐와 오일러	소수
103 19	맨해튼
103 27	플립 정렬	AVL 트리
103 41	그것을 해결하십시오	숫자, 뉴턴의 방법
103 64	정사각형	역 추적, 비트 마스크
103 82	급수 잔디	탐욕스럽고 간격 커버
104 28	뿌리	뿌리 찾기, 이등분법
104 54	trexpression	표현 구문 분석, 마당 분로, 카탈로니아어 번호
104 96	구불 구불 한 경사면
105 33	숫자 프라임
105 67	베이츠 채우기를 돕습니다
105 70	외계인과의 만남	순열, 스왑 계산, 사이클 계산
105 76	Y2K 회계 버그
105 86	다항식 유적
106 00	ACM 콘테스트 및 정전
106 04	화학 반응
106 51	페블 솔리테어
106 55	묵상! 대수학	재발 관계, 모듈 식 지수
106 64	수화물
106 84	공동 자금
106 99	요인을 세십시오	소수, 주요 분해
107 23	사이보그 유전자
107 38	Riemann vs Mertens	소수, Möbius 함수, Mertens 기능
108 01	리프트 호핑
108 10	울트라 QuickSort	병합/삽입 정렬, 반전 계산
108 55	회전 된 사각형	매트릭스 회전, 행렬 전달
108 70	재발
109 20	나선형 탭	분석 표현
109 31	둥가
109 34	물 풍선을 떨어 뜨립니다
109 35	카드를 버리고	대기열, 단일 연결된 목록
109 38	벼룩 서커스
109 54	모두 추가하십시오	더미
109 57	Su Doku Checker	역 추적, 비트 마스크
109 94	간단한 추가	분석 표현
110 57	정확한 합계
110 60	음료수
110 77	순열을 찾으십시오	조합, 재발 관계, 스털링 숫자
111 37	독창적 인 입방물
111 51	가장 긴 팔린 드롬	동적 프로그래밍, 문자열 처리
111 71	SMS	동적 프로그래밍, 문자열 처리, 트리
111 95	또 다른 N 퀘스트 문제	역 추적, 비트 마스크
112 27	은 총알
112 35	빈번한 값
112 36	식료품 점
112 57	새로운 마케팅 계획	다각형, 새겨진 원 반경, 우선 순위 대기열
112 58	문자열 파티션	동적 프로그래밍
112 60	홀수 루트 합	분석 표현, impl. 이진 검색, 모듈 식 산술
112 71	저항의 격자	재발 관계, 점근 팽창
112 83	Boggle을 연주합니다	역 추적
112 97	인구 조사	2D SQRT 분해
113 62	전화 목록	트리, 접두사 매칭
114 13	용기를 채우십시오
114 20	서랍장	조합, 재발 관계
114 56	기차
114 61	제곱 번호	암시 적 이진 검색
114 62	나이 정렬	정렬을 계산하십시오
114 63	특공대
114 75	Palindrome으로 확장하십시오
115 17	정확한 변화
115 36	가장 작은 하위 배열	슬라이딩 창
115 72	독특한 눈송이	선형 검색, 해시 테이블
115 84	Palindromes의 분할
116 21	작은 요인	로그
116 34	랜덤 숫자를 생성합니다
116 36	안녕하세요, 세상!	분석 표현, 로그
116 58	최고의 연합
116 86	막대기를 집어
116 91	알레르기 테스트
117 03	sqrt, log, sin	재발 관계
117 14	맹인 분류	주문 통계 (2 ND 최대)
117 33	공항
119 02	지배자
119 91	Rujia Liu의 쉬운 문제?	정렬, 이진 검색
119 97	K 작은 합계
120 86	전위차계	펜윅 트리
121 05	더 낫다 (1)
121 05	더 낫다 (2)
121 92	포도 나무	이진 검색
122 38	개미 식민지
123 47	이진 검색 트리	이진 검색 트리, 사전/후 순서 트래버스
124 55	바	완전한 검색, 역 추적
124 58	오, 내 나무!
124 62	구형	선형 검색, 스택, 비트 마스크
124 94	뚜렷한 서브 스트링	법률. 최소 회전, Duvan의 알고리즘, 해시 테이블
125 04	사전 업데이트	빠른 정렬
126 40	가장 큰 합계 게임	선형 검색, 최대 합계 서브 어레이, Kadane의 알고리즘
126 97	최소 서브 어레이 길이	선형 검색, 최대 합계 서브 어레이, Kadane의 알고리즘
127 02	팽창	이진 형태, 이진 이미지 확장
129 11	서브 세트 합계	서브 세트 합계, 완전한 검색, 중간에
130 50	경로 발견	조합, 재발 관계
132 82	Cakey McCakeface (1)	정렬, 선형 검색
132 82	Cakey McCakeface (2)	비트 마스크, 버킷 팅

국제 고성능 컴퓨팅 콘테스트

문제 소스

ID	제목	카테고리
C2	이미지를 얻으십시오	Fractal, Mandelbrot Set, MPI, std::thread

다른 문제와 운동

다른 온라인 소스의 기타 문제.

제목	카테고리
이진 검색 트리에 배열	이진 검색 트리
장치 adj가있는 배열. 차이 검색	선형 검색
바이너리 정렬 된 배열 전환 지점	이진 검색
이진 트리 직경	이진 트리, 깊이 우선 순회
이진 트리 상단보기	이진 트리, 너비 우선 순회
Bitonic 어레이 검색	이진 검색
세 배열의 공통 요소	선형 검색
y 자형 링크 된 목록의 연결 지점	단일 연결된 목록
아나그램 하위 문자열을 계산하십시오	해시 테이블, 슬라이딩 창
오른쪽에 작은 요소를 계산하십시오	AVL 트리
우편 번호로 사각형을 계산하십시오	분석 표현
트리플렛을 세십시오	선형 검색, 쌍 합계 검색
이진 스트림에서의 분할	모듈 식 산술, 분할
평형 지점	선형 검색
괄호 생성 (1)	조합, 역 추적
합계가있는 서브 세트가 있습니다	동적 프로그래밍
링크 된 목록은 팔린 드롬입니다	단일 연결된 목록
하위 트리 (1)	이진 트리, 깊이 우선 순회
행 열의 K-th 요소 정렬 된 매트릭스	더미
K 스왑이있는 가장 큰 숫자	역 추적
히스토그램에서 가장 큰 사각형	선형 검색, 스택
가장 큰 사각형 부울 매트릭스	동적 프로그래밍, 가장 큰 정사각형 서브 매트릭스
Fibonacci의 마지막 두 자리	Fibonacci 번호, 모듈 식 산술, 이진 지수
목록 병합	단일 연결된 목록
목록은 정렬을 병합합니다	단일 연결된 목록, 병합 정렬
가장 긴 별개의 문자위	선형 검색
가장 긴 Palindromic Sum substring	선형 검색
다수 요소	Boyer – Moore 대다수 투표 알고리즘
배열을 엄격하게 늘리십시오	가장 긴 후속, 이진 검색
매트릭스 회전	매트릭스 회전, 행렬 전달
분류 된 요소 사이의 최대 거리	선형 검색
문자열의 최대 숫자 값	선형 검색, 사전 비교
각 하위 배열의 최대 값 (1)	슬라이딩 창, 균형 이진 트리
각 하위 배열의 최대 값 (1)	슬라이딩 창, Deque
3 개의 요소의 최대 제품	선형 검색
Min-Stack	스택
정렬 된 회전 배열의 최소 요소	이진 검색
최소 점프 수 (1)	동적 프로그래밍
최소 점프 수 (2)	선형 검색
거의 정렬되었습니다	힙 정렬, 삽입 정렬
다음에 더 큰 요소	선형 검색, 스택
이진 트리에서 거리 k의 노드	이진 트리, 깊이 우선 순회
그리드의 경로 수	조합
분할 균일하고 홀수 노드	단일 연결된 목록
두 개의 스택으로 대기열	대기열, 스택
중복 노드를 제거하십시오	단일 연결된 목록
중간 노드를 제거하십시오	단일 연결된 목록
사전에서 알파벳을 복원하십시오	토폴로지 분류, 칸의 알고리즘
단독으로 연결된 목록을 뒤집습니다	단일 연결된 목록
문자열의 리버스 단어	선형 검색
단독으로 연결된 목록을 회전시킵니다	단일 연결된 목록
회전 된 배열 검색	이진 검색, 선형 검색
두 번째로 큰	주문 통계, 두 번째로 큰 요소, 이진 카운터
행과 열을 설정하십시오	선형 검색
순열에서 가장 작은 숫자	선형 검색
크기 3의 차별화 된 후속도	선형 검색
크기 4의 차별화 된 후속도	선형 검색
제곱근	암시 적 이진 검색
주어진 합으로 서브 어레이	선형 검색
3 방향 파티션	배열 파티셔닝
주어진 합계가있는 두 가지 요소	선형 검색, 해시 테이블
정렬되지 않은 동일 배열	시퀀스, 해시 테이블
XOR 링크 된 목록	이중 연결 목록
제로섬 서브 어레이	선형 검색, 해시 테이블