HDU 4618 Palindrome Sub - Array (Manacher, 2 점)
주어진 N×M, N, M ≤ 300 의 행렬, 최대 회 문 정사각형 의 변장 구하 기
분석:
현장 에 120 이 넘 었 습 니 다. 저 는 정말 늙 은 피 입 니 다. 분명히 어 려 운 문제 가 있 었 습 니 다. 경기 후에 니 마 가 보 니 와 조 O (n5) 의 알고리즘 이 지 났 습 니 다. n2 매 거 진 점, n 매 거 진 변장, n2 판단 회 문 경기 에서 생각 이 맞 았 습 니 다. 그런데 쓰기 가 너무 복잡 해서 저 를 오래 돌 았 습 니 다. 니 마 Manacher 는 정말 먹 을 공간 을 늘 렸 습 니 다. hdu 는 정말 공간 을 파고 들 었 습 니 다. 제 가 생각 하 는 이 정 해 는 정말 귀 찮 습 니 다. - - - 생각 을 다.팀 원 들 한테 힌트 를 받 으 면 2 점 이면 됩 니 다.
p1 [i] [j]: = i 행 의 j 중심 회 문 반경, p2 [i] [j]: = i 열 의 j 중심 회 문 반경 - − 가 공간 에 걸 렸 다. 나 는 이 배열 을 반복 적 으로 이용 하여 구법 에 대해 한 줄 에 한 번 씩 Manacher 를 한 다음 에 열 에 한 번 씩 (행렬 을 옮 긴 후에 한 줄 에 한 번 씩) 그리고 사람 을 돌아 서 시작 했다 - − - 를 보 았 다.삽입 되 었 습 니 다.
123456789
1 #########
2 #2#3#3#2#
3 #########
4 #2#3#3#2#
5 #########
6 #2#3#3#2#
7 #########
8 #2#3#3#2#
9 #########
우 리 는 이미 다섯 번 째 줄 마다 \ # 의 수직 회 문 반지름 길이 와 다섯 번 째 열 마다 \ # 의 가로 회 문 반지름 길 이 를 알 고 있 습 니 다. 분명히 행 을 통 해 우 리 는 열 회 문 길이 (가장 작은 것) 를 알 수 있 습 니 다. 열 을 통 해 우 리 는 행 회 문 길이 (가장 작은 것) 가 어떻게 빠 른 조회 인지 알 수 있 습 니 다. - − 분명 구간 RMQ.행렬 은 각각 300 * 8727 ° 2 개의 SparseTable 을 유지 하면 됩 니 다. 분명히 이 판단 은 답문 의 정사각형 의 복잡 도 는 O (logn) 의 파란색 입 니 다. 우 리 는 매 거 진 점, 매 거 진 길 이 를 가 져 야 합 니 다. 그리고 대응 하 는 2 개의 st 에서 RMQ 를 조회 하여 합 법 적 인지 판단 해 야 합 니 다. 이런 복잡 도 는 O (n3 logn) 입 니 다. 이렇게 T 를 할 수 있 는 것 은 제 가 원 하 는 것 이 아 닙 니 다. 경기 에서 저 는 여기 가 생각 났 습 니 다.그 러 자 동료 들 이 갑자기 2 점 이 튀 어 나 왔 습 니 다. 단조 성 이 없다 고 했 습 니 다. 그리고 바로 인형 이 헤 어 질 생각 을 했 습 니 다.침대, 왼쪽 상단 점, 패 리 티 길이 2 점 을 매 거 진 다음 에 복잡 도 는 순간 O (n2log 2n) 가 되 었 습 니 다. 그리고 AC 가 될 수 있 습 니 다. 사실은 하 쉬 가 판단 할 생각 이 었 습 니 다. 그런데 저 는 그들 에 게 쓰 지 말 라 고 했 습 니 다. 꼬치 가 너무 많아 서 하 쉬 가 부 딪 히 면 울 었 습 니 다. 블 루 아 는 이런 데이터 가 약 해서 칼날 을 보 내야 합 니 다.
코드:
//
// Created by TaoSama on 2016-02-25
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 3e2 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n, m, a[N][N], b[N][N];
int s[N << 1], p[N][N << 1];
void manacher(int *a, int *p, int n) {
s[0] = '@'; s[1] = '#';
int l = 2;
for(int i = 1; i <= n; ++i) {
s[l++] = a[i];
s[l++] = '#';
}
s[l] = 0;
int mx = 0, id;
for(int i = 1; i < l; ++i) {
if(mx > i) p[i] = min(mx - i, p[2 * id - i]);
else p[i] = 1;
while(s[i - p[i]] == s[i + p[i]]) ++p[i];
if(mx < p[i] + i) mx = p[i] + i, id = i;
}
}
struct SparseTable {
int n, dp[10][N << 1];
void init(int _n) {
n = _n;
for(int i = 1; (1 << i) <= n; ++i)
for(int j = 1; j + (1 << i) - 1 <= n; ++j)
dp[i][j] = min(dp[i - 1][j], dp[i - 1][j + (1 << i - 1)]);
}
int RMQ(int l, int r) {
int k = 31 - __builtin_clz(r - l + 1);
return min(dp[k][l], dp[k][r - (1 << k) + 1]);
}
} hor[N << 1], ver[N << 1];
bool check(int x) {
int ret = 0;
for(int i = 1; i <= 2 * n + 1; i += 2) {
for(int j = 1; j <= 2 * m + 1; j += 2) {
int right = j + 2 * x, down = i + 2 * x;
if(right > 2 * m + 1 || down > 2 * n + 1) continue;
int h = hor[i + x].RMQ(j, right), v = ver[j + x].RMQ(i, down);
int cur = min(h, v);
if(cur - 1 >= x) {
return true;
}
}
}
return false;
}
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
int t; scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
scanf("%d", &a[i][j]), b[j][i] = a[i][j];
//rows
for(int i = 1; i <= n; ++i) manacher(a[i], p[i], m);
for(int i = 1; i <= 2 * m + 1; ++i) {
for(int j = 1; j <= 2 * n + 1; ++j) {
int tmp = INF;
if(!(j & 1)) tmp = p[j / 2][i];
ver[i].dp[0][j] = tmp;
}
ver[i].init(2 * n + 1);
}
//columns
for(int i = 1; i <= m; ++i) manacher(b[i], p[i], n);
for(int i = 1; i <= 2 * n + 1; ++i) {
for(int j = 1; j <= 2 * m + 1; ++j) {
int tmp = INF;
if(!(j & 1)) tmp = p[j / 2][i];
hor[i].dp[0][j] = tmp;
}
hor[i].init(2 * m + 1);
}
int ans = 0;
{
int l = 0, r = 150;
while(l <= r) {
int m = l + r >> 1;
if(check(2 * m)) l = m + 1;
else r = m - 1;
}
--l;
ans = max(ans, 2 * l);
}
{
int l = 0, r = 150;
while(l <= r) {
int m = l + r >> 1;
if(check(2 * m + 1)) l = m + 1;
else r = m - 1;
}
--l;
ans = max(ans, 2 * l + 1);
}
printf("%d
", ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
|NOIOJ|2분|04: 네트워크 관리자심판위원회는 인터넷 라인을 구매하기 위해 현지의 한 인터넷 솔루션 제공 업체에 연락하여 일정한 수량의 등장망 라인을 제공할 수 있도록 요구했다.심판위원회는 네트워크가 길어질수록 좋아져 선수들 사이의 거리가 가능한 한...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.