알고리즘 경기 입문 고전 (2 판) 유 여가 - 제8 장 고 효율 알고리즘 디자인 예제 (13 / 19)
본 고 는 제 가 제8 장 19 개 예제 에 대한 연습 총 결 로 자서 인 에 맞 춰 본 고 를 읽 는 것 을 권장 합 니 다.그리고 문 제 를 쉽게 풀 수 있 도록 저 는 VOJ 에서 contest 를 열 었 습 니 다. 같이 하 는 것 을 환영 합 니 다. 제8 장 예제 contest 는 어떤 문 제 를 직접 보고 싶 으 면 목록 을 클릭 하고 해당 하 는 문 제 를 푸 세 요!!
예제
예 8 - 1 UVA 120 부침 개
제목 은 부침 개 한 묶음 이 솥 안에 있다 는 것 이다.부침 개 는 모두 n (n ≤ 30) 장 으로 장 당 하나의 숫자 가 있어 크기 를 나타 낸다.요리 사 는 매번 하 나 를 선택 하여 k 를 셀 수 있 습 니 다. 냄비 밑 에서 부터 K 장 위의 부침 개 를 모두 뒤 집 을 수 있 습 니 다. 즉, 위 에 있 던 부침 개가 지금 아래로 내 려 왔 습 니 다.모든 부침 개 를 작은 것 에서 큰 것 으로 정렬 하 는 방법 을 설계 하 다.입력 시 각 부침 개 는 위 에서 아래로 순서대로 드 립 니 다.
사고 라 는 문 제 는 정렬 을 요구 하지만 기본 적 인 조작 은 '연속 적 인 하위 서열 을 뒤 바 꾸 는 것' 이다.그러나 괜 찮 습 니 다. 우 리 는 선택 에 따라 정렬 하 는 사상 에 따라 큰 것 부터 작은 것 까지 순서대로 모든 수 를 정확 한 위치 로 배열 할 수 있 습 니 다.방법 은 먼저 맨 위로 넘 긴 다음 에 정확 한 위치 로 넘 기 는 것 이다.큰 것 부터 작은 것 까지 순서대로 처리 하기 때문에 i 큰 부침 개 를 처리 할 때 1, 2, 3, i - 1 큰 부침 개 에 영향 을 주지 않 습 니 다.
소홀 해 지기 시 작 했 습 니 다. if (j > 1) 판단 조건 을 if (j < 1) 로 잘못 적 었 습 니 다. 제출 후 WA 는 두 발 을 보 냈 습 니 다. 자신 에 게 반드시 세심 해 야 한다 고 일 깨 워 주 었 습 니 다!
코드
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<vector>
using namespace std;
int n;
int a[31];
void flip(int k)
{
for (int i = 1; i <= k/2; i++)
swap(a[i], a[k-i+1]);
}
int main()
{
string s;
//freopen("in", "r", stdin);
while (getline(cin, s)) {
stringstream ss(s);
int x;
n = 0;
while (ss >> x)
a[++n] = x;
int b[31];
memcpy(b, a, sizeof(a));
sort(b+1, b+n+1);
vector<int> res;
for (int i = n; i >= 1; i--) {
if (a[i] != b[i]) {
int j = 1;
for (; a[j] != b[i]; j++);
if (j > 1) {flip(j); res.push_back(n-j+1);}
flip(i); res.push_back(n-i+1);
}
}
cout << s << endl;
for (int i = 0; i < res.size(); i++)
printf("%d ", res[i]);
printf("0
");
}
return 0;
}예 8 - 2 UVA 1605 유엔 빌딩
당신 의 임 무 는 몇 층 을 포함 하 는 유엔 빌딩 을 설계 하 는 것 입 니 다. 그 중에서 각 층 은 하나의 큰 격자 입 니 다.몇몇 국가 들 이 유엔 빌딩 에서 업 무 를 봐 야 한다. 너 는 각 칸 을 한 나라 에 분배 하여 임의의 두 나라 가 서로 인접 한 칸 을 가지 도록 해 야 한다.네가 설계 한 빌딩 은 최대 1000000 칸 을 초과 해 서 는 안 된다.국가의 개수 n (n ≤ 50) 을 입력 하고 빌딩 의 층수 H, 각 층 의 행 수 W 와 열 수 L 을 수출 한 다음 에 각 층 의 평면도 이다.나라 마다 대소 문자 로 표시 한다.
사고 본 문제 의 제한 이 매우 적 고 층수, 행 수 와 열 수 는 모두 선택 할 수 있다.그 렇 기 때문에 본 문제 의 해법 은 매우 많다.내 가 사용 한 것 은 책 에서 제시 한 해법 이다. 모두 2 층 만 있 고 각 층 은 n * n 이 며 1 층 i 행 은 모두 국가 i 이 고 2 층 j 열 은 모두 국가 j 이다.
코드
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
char ans[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
int main()
{
int n;
while (scanf("%d", &n) != EOF){
printf("2 %d %d
", n, n);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++)
printf("%c", ans[i]);
printf("
");
}
printf("
");
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++)
printf("%c", ans[j]);
printf("
");
}
}
return 0;
}예 8 - 3 UVA 1152 와 0 의 4 개 값
제목 은 n (1 ≤ n ≤ 4000) 요소 집합 A, B, C, D 를 4 개 정 하고 그 중에서 각각 하나의 요소 a, b, c, d 를 선택 하여 a + b + c + d = 0 을 선택 하도록 요구 합 니 다.가: 몇 가지 선택 방법 이 있 습 니까?
사고 중도 만 남 법.이것 은 특수 한 알고리즘 으로 대체적인 사고방식 은 두 가지 서로 다른 방향 에서 문 제 를 해결 하고 최종 적 으로 '집합' 을 함께 하 는 것 이다.
가장 생각 하기 쉬 운 알고리즘 은 4 중 순환 매 거 진 a, b, c, d 를 써 서 합치 면 0 인지, 시간 복잡 도 는 O (n4) 이 고 시간 을 초과 하 는 지 보 는 것 이다.조금 좋 은 방법 은 a, b, c 를 매 거 하 는 것 입 니 다. 집합 D 에서 요소 - a - bc 가 있 는 지 찾 아야 합 니 다. 존재 하면 방안 에 1 을 추가 합 니 다.정렬 후 2 분 검색 을 사용 하면 시간 복잡 도 는 (n3 logn) 입 니 다.방금 전의 방법 을 홍보 하면 더욱 빠 른 알고리즘 을 얻 을 수 있 습 니 다. 먼저 a 와 b 를 매 거 하고 모든 a + b 를 질서 있 는 배열 이나 STL 의 map 에 기록 한 다음 에 c 와 d 를 매 거 진 다음 에 - c - d 가 a + b 로 쓰 이 는 방법 이 몇 가지 가 있 는 지 찾 아 보 세 요.두 단 계 는 모두 O (n2logn) 이 고 전체 시간 복잡 도 역시 O (n2logn) 이다.
코드
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 4000;
int n, m;
int a[4][N];
int x[N*N], y[N*N];
int main(void)
{
int kase;
cin >> kase;
while (kase--) {
cin >> n;
m = n*n;
for (int i = 0; i < n; i ++)
for (int j = 0; j < 4; j ++)
scanf("%d", &a[j][i]);
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
x[i*n+j] = a[0][i] + a[1][j];
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
y[i*n+j] = a[2][i] + a[3][j];
sort(y, y+m);
long long ans = 0;
for (int i = 0; i < m; i ++)
ans += (upper_bound(y, y+m, -x[i]) - lower_bound(y, y+m, -x[i]));
printf("%lld
", ans);
if (kase) printf("
");
}
return 0;
}예 8 - 4 UVA 11134 전설의 차
당신 의 임 무 는 n * n 의 바둑판 에 n (n ≤ 5000) 개의 차 를 놓 아 임의의 두 차 가 서로 공격 하지 않도록 하 는 것 이 며, i 번 째 차 는 주어진 사각형 Ri 안에 있 습 니 다.4 개의 정수 xli, yli, xri, yri (1 ≤ xli ≤ xri ≤ n, 1 ≤ yli ≤ yri ≤ n) 로 제 i 의 사각형 을 묘사 하 는데 그 중에서 (xli, yli) 는 왼쪽 상단 좌표 이 고 (xri, yri) 는 오른쪽 하단 좌표 이 며 제 i 차 의 위치 (x, y) 는 xli ≤ x ≤ xri, yli ≤ y ≤ yri 를 만족 시 켜 야 한다.풀 리 지 않 으 면 IMPOSSIBLE 을 출력 합 니 다.그렇지 않 으 면 n 줄 을 출력 하고 1, 2, n 차 의 좌표 순 으로 출력 합 니 다.
두 차 가 서로 공격 하 는 조건 은 같은 줄 이나 같은 열 에 있 기 때문에 서로 공격 하지 않 는 조건 은 같은 줄 에 있 지 않 고 같은 열 에 있 지 않다 는 것 이다.행 과 열 은 무관 하기 때문에 원 제 를 2 차원 문제 로 분해 할 수 있다.구간 [1 ~ n] 에서 n 개의 서로 다른 정 수 를 선택 하여 i 의 정 수 를 폐 구간 [n1i, n2 i] 안에 있 게 합 니 다.욕심 법 은 풀 수 있다.복잡 도 O (n ^ 2).
코드
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 5001;
int n;
int rangeA[2][N], rangeB[2][N];
int pos[2][N];
bool put_rook(int i)
{
int *ra = rangeA[i], *rb = rangeB[i];
int *p = pos[i];
int c[N];
memset(c, 0, sizeof(c));
for (int j = 1; j <= n; j++) {
int mink = n+1, minb = n+1;
for (int k = 1; k <= n; k++) {
if (!c[k] && ra[k] <= j && rb[k] >= j && rb[k] < minb) {
mink = k;
minb = rb[k];
}
}
//printf("j=%d, mink=%d, ra[mink]=%d, rb[mink]=%d
", j, mink, ra[mink], rb[mink]);
if (mink == n+1) return false;
p[mink] = j;
c[mink] = 1;
}
return true;
}
int main()
{
while (scanf("%d", &n) && n) {
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 2; j++)
scanf("%d", &rangeA[j][i]);
for (int j = 0; j < 2; j++)
scanf("%d", &rangeB[j][i]);
}
if (!put_rook(0) || !put_rook(1)) printf("IMPOSSIBLE
");
else {
for (int i = 1; i <= n; i++)
printf("%d %d
", pos[0][i], pos[1][i]);
}
}
return 0;
}예 8 - 5 UVA 11054 Gergovia 의 술 거래
제목 직선 에 n (2 ≤ n ≤ 100000) 개의 등거리 마을 이 있 으 며, 각 마을 마다 술 을 사 거나 술 을 판다.제 i 개 마을 의 술 에 대한 수 요 는 ai (- 1000 ≤ ai ≤ 1000) 이 고 그 중에서 ai > 0 은 술 을 사 는 것 을 나타 내 며 ai < 0 은 술 을 파 는 것 을 나타 낸다.모든 마을 의 공급 과 수요 의 균형, 즉 모든 ai 의 합 은 0 이다.k 개 단위 의 술 을 한 마을 에서 이웃 마을 로 운반 하려 면 k 개 단위 의 노동력 이 필요 하 다.최소한 얼마나 많은 노동력 이 필요 한 지 계산 하면 모든 마을 의 수 요 를 만족 시 킬 수 있다.출력 은 64 비트 기호 정수 범위 내 에서 보장 합 니 다.
생각 은 가장 왼쪽 마을 을 고려한다.술 을 사 야 한다 면 a1 > 0 은 마을 2 에서 왼쪽으로 마을 1 에 게 노동력 이 있 을 것 이다. 이 술 들 이 어디서 나 왔 든 (마을 2 산 일 수도 있 고 더 오른쪽 마을 에서 마을 2 로 운 송 될 수도 있다).이렇게 되면 문 제 는 마을 2 ~ n 만 있 고 두 번 째 마을 의 수요 가 a1 + a2 인 경우 와 같다.ai < 0 시 에 이 추리 도 성립 되 었 다 는 것 을 발견 하기 어렵 지 않다.
코드
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int main( ) {
int n;
while(cin >> n && n) {
long long ans = 0, a, last = 0;
for(int i = 0; i < n; i++) {
cin >> a;
ans += abs(last);
last += a;
}
cout << ans << "
";
}
return 0;
}예 8 - 6 UVA 1606 양친 성 분자
제목
사고의 방향
코드
8-7 UVA 11572
n（n≤106） A， AL～AR， 。
0 ， L， R。 L=0 。 R=0 R， 。 （ A[R+1] A[L～R] ） ， L， R。 A[L～R] ，L ， R， 。
， 。 “ ” ， R 1， L 1， L R 0 n-1， O(n) 。
“ ” 。 STL set， A[L～R] ， R A[R+1] set ， R 1 A[R+1] set ，L+1 A[L] set 。 set O(logn) ， O(nlogn)。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
const int N = 1000001;
int n;
int a[N];
int main()
{
int kase;
scanf("%d", &kase);
while (kase--) {
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
int ans = 1, l = 0, r = 0;
set<int> sa;
while (true) {
while (r < n && !sa.count(a[r]))
sa.insert(a[r++]);
ans = max(ans, r-l);
if (r == n) break;
sa.erase(a[l++]);
}
printf("%d
", ans);
}
return 0;
} 8-8 UVA 1471
8-9 UVA 1451
8-10 UVA 714
m k （1≤k≤m≤500） ， 。 i S(i)， S(i) 。 ， 1 2 3 2 5 4 3 1 2 3 | 2 5 | 4， S(1)、S(2)、S(3) 6、7、4， 7； 1 2 | 3 2 | 5 4， 9， 。 107。 ，S(1) 。 ，S(2) ， 。
“ ” 。 ： m ， S(i) x？ P(x) ， P(x) x 。P(x) ， （ ， ）。
—— x0， P(x0) ， x0 ； P(x0) ， x0。 ， ： x， P(x)。 M， O(logM)， P(x) O(n)（ ）， O(nlogM)(4)。
。 ， 。 。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 501;
const int INF = 10000000;
typedef long long LL;
int n, k;
int a[N];
bool check(LL mid)
{
int cnt = 1;
LL sum = 0;
for (int i = 0; i < n; i++) {
if (a[i] > mid) return false;
if (sum + a[i] > mid) {
cnt++;
sum = a[i];
} else
sum += a[i];
}
return cnt <= k;
}
void get_div(vector<int>& div, LL mid)
{
int cnt = 1;
LL sum = 0;
for (int i = n-1; i >= 0; i--) {
if (i < k-cnt || sum + a[i] > mid) {
cnt++;
sum = a[i];
div.push_back(i+1);
} else
sum += a[i];
}
}
int main(void)
{
int kase;
cin >> kase;
while (kase--) {
cin >> n >> k;
LL sum = 0;
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
sum += a[i];
}
LL lb = 0, ub = sum;
while (ub - lb > 1) {
LL mid = (lb + ub) / 2;
if (check(mid)) ub = mid;
else lb = mid;
}
vector<int> div;
get_div(div, ub);
int j = k-2;
for (int i = 0; i < n; i++) {
if (div[j] == i) { printf("/ "); j--;}
printf("%d%c", a[i], i == n-1 ? '
' : ' ');
}
}
return 0;
} 8-11 UVA 10954
n（n≤5000） S， S ， ， 。 ， 。 10^5。
Huffman ？ n ， —— 。
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int main(void)
{
int n;
while(cin >> n && n)
{
priority_queue<int, vector<int>, greater<int> > Queue;
for(int i = 1; i <= n; i++)
{
int temp;
scanf("%d", &temp);
Queue.push(temp);
}
int mincost = 0;
while (Queue.size() > 1)
{
int a = Queue.top();
Queue.pop();
int b = Queue.top();
Queue.pop();
Queue.push(a+b);
mincost += a+b;
}
printf("%d
", mincost);
while(!Queue.empty())
Queue.pop();
}
return 0;
} 8-12 UVA 12627
。 ， 3 ， 4 ， 8-19 0, 1, 2, 3 。 k ， A～B ？ ，k=3，A=3，B=7， 14。
k 4 k-1 ， ， 。 3 ： k-1 “ ” “ ” 。
， f(k, i) k i ，g(k,i) k i （ i≤0 f(k,i)=g(k,i)=0）， f(k,b) - f(k, a-1)。
f(k,i) g(k,i) ？ g(k,i) ， .
i≥2k-1， g(k,i)=2g(k-1,i-2k-1)+c(k)， g(k,i)=g(k-1,i)。 ，c(k) k ， c(k)=3c(k-1)， c(0)=1， c(k)=3k。
，g(k,i) k-1 ， g(k,i) O(k)。 ，f(k,i) O(k)， O(k)。
f(k, a, b)， k a b 。 f(k, a, b) = 2*f(k-1, a1, b1) + f(k-1, a2, b2) ， TLE 。 ， O(2^k) ， ！ AC 。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int exp2[31];
LL exp3[31];
LL f1(int k, int a) //up
{
if (a == 0) return 0;
if (k == 0) return 1;
if (a <= exp2[k-1]) return 2*f1(k-1, a);
else return 2*exp3[k-1] + f1(k-1, a-exp2[k-1]);
}
LL f2(int k, int b) //up
{
if (b == exp2[k]+1) return 0;
if (k == 0) return 1;
if (b > exp2[k-1]) return f2(k-1, b-exp2[k-1]);
else return exp3[k-1] + 2*f2(k-1, b);
}
int main(void)
{
exp2[0] = exp3[0] = 1;
for (int i = 1; i <= 30; i++) {
exp2[i] = exp2[i-1]*2;
exp3[i] = exp3[i-1]*3;
}
int kase;
scanf("%d", &kase);
for (int t = 1; t <= kase; t++) {
int k, a, b;
scanf("%d%d%d", &k, &a, &b);
printf("Case %d: %lld
", t, exp3[k] - f1(k, a-1) - f2(k, b+1));
}
return 0;
} 8-13 UVA 11093
n（n≤100000） ， 1～n。 i pi 。 i qi 。 ， （ ）。 ， 。 。 ， Not possible， 。
1 ， 。 ， ； ， p， p+1 。 ， 2, 3,…, p （ ， ）。 ， ， O(n)。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100001;
int n;
int p[N], q[N];
int main()
{
int kase;
scanf("%d", &kase);
for (int t = 1; t <= kase; t++) {
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &p[i]);
for (int i = 0; i < n; i++)
scanf("%d", &q[i]);
int bg = 0;
while (bg < n) {
int i = bg, sp = 0, sq = 0;
for (; i < bg+n; i++) {
sp += p[i%n], sq += q[i%n];
if (sp < sq) break;
}
if (i == bg+n) break;
bg = i+1;
}
printf("Case %d: ", t);
if (bg < n) printf("Possible from station %d
", bg+1);
else printf("Not possible
");
}
return 0;
} 8-14 UVA 1607
（NAND） 。 NAND ， 。 0 1。 m（m≤200000） NAND ， n （n≤100000） x。
， x 。 。
x， 4 ： 0、 1、x x。 x 0， x 1， ， ， 。
x=0 x=1 ， x x， 1。 x=0 0，x=1 1。 1， 0（ 1000…0）， 1， x000…0。
1000…0 0， 1100…0， 1， 1x00…0。 0， 1110…0， 。 1 1， 。
m ， “ ” O(m) ， 。 ： 1 ， O(Logm) ， O(mlogm)。
， x 。 x。 。
， 。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100001;
const int M = 200001;
int n, m;
bool in[N], out[M];
int gate[M][2];
bool get_out(int k)
{
fill(in+1, in+k+1, 1);
fill(in+k+1, in+n+1, 0);
bool a, b;
for (int i = 1; i <= m; i++) {
a = gate[i][0] < 0 ? in[-gate[i][0]] : out[gate[i][0]];
b = gate[i][1] < 0 ? in[-gate[i][1]] : out[gate[i][1]];
out[i] = !(a&&b);
}
return out[m];
}
void print(int posx)
{
for (int i = 1; i < posx; i++)
printf("1");
if (posx) printf("x");
for (int i = posx+1; i <= n; i++)
printf("0");
printf("
");
}
int main()
{
int kase;
scanf("%d", &kase);
while (kase--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
scanf("%d%d", &gate[i][0], &gate[i][1]);
int posx = 0;
int res[2];
res[0] = get_out(0);
res[1] = get_out(n);
if (res[0] != res[1]) {
int lb = 0, ub = n;
while (ub - lb > 1) {
int mid = (lb + ub) / 2;
if (get_out(mid) == res[1]) ub = mid;
else lb = mid;
}
posx = ub;
printf("%d
", ub);
}
print(posx);
}
return 0;
} 8-15 UVA 12174
， 。 s ， s ， 、 ， 。 ， s 。 ， s 1～s 。
n（1≤s，n≤100000） （ ）xi（1≤xi≤s）， 。
，s=4， 3, 4, 4, 1, 3, 2, 1, 2, 3, 4， ： ， ， 1； s=3 ， 1, 2, 1 ： ， ； ， 。 2。
“ s ” ？ ， ！ “ ” （ ）， ； 1～s ， STL set， 。 ， O(n) （ ）。
， ， ， 。
， 。s n ， s ， ， WA。
， AC ：
INPUT
1
6 4
1 4 6 4
OUTPUT
2
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100001;
int s, n;
int a[N], c[N];
bool flag[N];
int main()
{
int kase;
scanf("%d", &kase);
while (kase--) {
scanf("%d%d", &s, &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
memset(c, 0, sizeof(c));
memset(flag, true, sizeof(flag));
int num = 0;
for (int i = 0; i < n+s; i++) {
if (i < n && !(c[a[i]]++)) num++;
if (i >= s && !(--c[a[i-s]])) num--;
if (i < s) {
if (num < min(n, i+1)) flag[i%s] = false;
} else if (i < n) {
if (num < s) flag[i%s] = false;
} else if (num < n-max(i-s+1, 0)) {
flag[i%s] = false;
}
}
num = 0;
for (int i = 0; i < s; i++)
if (flag[i]) num++;
printf("%d
", num);
}
return 0;
} 8-16 UVA 1608
， （non-boring） 。 n（n≤200000） A（ 109 ）， 。
： ， ， ； A[p]， A[1…p-1] A[p+1…n] 。
？ （ 《 》 ？）， O(1) ， 。
O(n^2)， O(nlogn)， 。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
const int N = 200001;
int n;
int a[N], lnext[N], rnext[N];
bool check(int l, int r)
{
if (r-l < 1) return true;
for (int i = 0; i <= (r-l)/2; i++) {
int ll = l+i;
if (lnext[ll] < l && rnext[ll] > r)
if (check(l, ll-1) && check(ll+1, r)) return true;
int rr = r-i;
if (rr == ll) break;
if (lnext[rr] < l && rnext[rr] > r)
if (check(l, rr-1) && check(rr+1, r)) return true;
}
return false;
}
int main(void)
{
int kase;
scanf("%d", &kase);
for (int t = 1; t <= kase; t++) {
scanf("%d", &n);
map<int, int> mp;
mp.clear();
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
lnext[i] = mp.count(a[i]) ? mp[a[i]] : -1;
mp[a[i]] = i;
}
mp.clear();
for (int i = n-1; i >= 0; i--) {
rnext[i] = mp.count(a[i]) ? mp[a[i]] : n;
mp[a[i]] = i;
}
if (check(0, n-1)) printf("non-boring
");
else printf("boring
");
}
return 0;
} 8-17 UVA 1609
8-18 UVA 1442
8-19 UVA 12265
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
