P4888 三去矩阵

给出一个字符矩阵，多次询问求以 \((x, y)\) 为中心的最长回文串长度（即横竖两种）

\(l, q <= 2000\)

Solution

数据范围小直接模拟即可

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#include<climits>

#define LL long long

using namespace std;

int RD(){

    int out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const int maxn = 4019;

int len, na;

char map[maxn][maxn];

int get_max(int x, int y){

	int ans = -1, lenth = 1;

	while(x + lenth <= len && x - lenth >= 1){

		if(map[x + lenth][y] == map[x - lenth][y])lenth++;

		else break;

		}

	ans = lenth, lenth = 1;

	while(y + lenth <= len && y - lenth >= 1){

		if(map[x][y + lenth] == map[x][y - lenth])lenth++;

		else break;

		}

	ans = max(ans, lenth);

	return 2 * ans - 1;

	}

int main(){

	len = RD(), na = RD();

	for(int i = 1;i <= len;i++)for(int j = 1;j <= len;j++)cin>>map[i][j];

	for(int i = 1;i <= na;i++){

		int x = RD(), y = RD();

		printf("%d\n", get_max(x, y));

		}

	return 0;

	}

巴特西

P4888 三去矩阵

P4888 三去矩阵

Solution

Code

最新文章

热门文章