HDU 2859

逃离我推掉我的手 2023-08-17 16:37 33阅读 0赞

题意略。

思路：

因为这个对称的矩阵是按次对角线来定义对称的，那我们只需要考虑从左下到右上的这(2 \* n - 1)条对角线即可。

在考虑待检验的矩阵由k转移到k + 1这个大小时，我们只要考虑新增的一列和新增的一行是否对称即可，如果对称，则k+1这个大小的矩阵也是对称矩阵。

在这个过程中，采用尺取法，至于检查对称，我们暴力检查即可。

代码附上：

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1005;
    
    char matrix[maxn][maxn];
    int n;
    
    int nextpos(int up,int down){
        int x0 = up / n,y0 = up % n;
        int x1 = down / n,y1 = down % n;
        int len = (down - up) / (n - 1) + 1;
        int i;
        for(i = 0;i < len && matrix[x1 - i][y1] == matrix[x1][y1 + i];++i);
        return i == len ? -1 : down - (n - 1) * (i - 1);
    }
    
    int main(){
        while(scanf("%d",&n) == 1 && n){
            for(int i = 0;i < n;++i) scanf("%s",matrix[i]);
            int total = (n - 1)<<1,maxx = n * n - 1;
            int ans = 1;
            for(int t = 1;t < total;++t){
                for(int idx = t < n ? t : (t - n + 1) * n + (n - 1),tail = idx;idx <= maxx && tail <= maxx;tail += (n - 1)){
                    int temp = nextpos(idx,tail);
                    if(temp == -1) ans = max(ans,(tail - idx) / (n - 1) + 1);
                    else idx = temp;
                    if(idx % n == 0 || tail % n == 0) break;
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/tiberius/p/11300465.html

发表评论取消回复

表情：

评论列表（有 0 条评论，33人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 2859

题意略。思路：因为这个对称的矩阵是按次对角线来定义对称的，那我们只需要考虑从左下到右上的这(2 \ n - 1)条对角线即可。在考虑待检验的矩阵由k转移到k + 1

逃离我推掉我的手/ 2023年08月17日 16:37/ 0 赞/ 34 阅读

相关 hdu1130&&hdu1023

![博客图片][format_png] 题目链接 [hdu1130][] [hdu1023][] 题目概述 `hdu1130`让求的是 n n n个结点构成的

叁歲伎倆/ 2023年02月25日 15:24/ 0 赞/ 36 阅读

相关并查集 Hdu 1272 (判环)+ Hdu 1213 + Hdu 1232 + Hdu 3172

Hdu 1272 小希的迷宫思路：两点的根节点相同，并且他们又彼此连通，则说明构成环。如果无环且点数-1==边数则说明只有一个连通块 include <cst

我不是女神ヾ/ 2022年09月20日 15:09/ 0 赞/ 203 阅读

相关 hdu 2112 ——HDU Today

Problem Description 经过锦囊相助，海东集团终于度过了危机，从此，HDU的发展就一直顺风顺水，到了2050年，集团已经相当规模了，据说进入了钱江肉丝经济开发

朴灿烈づ我的快乐病毒、/ 2022年08月09日 13:46/ 0 赞/ 198 阅读

相关 HDU2859 Phalanx （DP）

Phalanx Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Oth

不念不忘少年蓝@/ 2022年07月21日 08:44/ 0 赞/ 84 阅读

相关 HDU - 2112 - HDU Today

-------------------- 题目连接：[http://acm.hdu.edu.cn/showproblem.php?pid=2112][http_acm.hdu

布满荆棘的人生/ 2022年06月12日 10:40/ 0 赞/ 191 阅读

相关 Q - Phalanx HDU - 2859——基础dp-最大对称子矩阵

Think: 1知识点：基础dp-最大对称子矩阵 2题意：给定一个矩阵，寻找一个最大对称子矩阵，当前题目最大对称子矩阵定义可理解为沿当前子矩阵的次对角线元素对称 3

超、凢脫俗/ 2022年06月10日 04:11/ 0 赞/ 147 阅读

相关 hdu 2110 - Crisis of HDU

地址 [http://acm.hdu.edu.cn/showproblem.php?pid=2110][http_acm.hdu.edu.cn_showproblem.p

缺乏、安全感/ 2022年05月28日 13:40/ 0 赞/ 164 阅读

相关 kmp1-HDU1711 HDU1686 HDU2087 HDU3746

HDU 1711 kmp模板题 [http://acm.hdu.edu.cn/showproblem.php?pid=1711][http_acm.hdu.edu.cn_sh

叁歲伎倆/ 2022年05月14日 11:24/ 0 赞/ 196 阅读

相关 2018CCPC吉林赛区 | 部分题解 (HDU6555 HDU6556 HDU6559 HDU6561)

// 杭电上的重现赛：[http://acm.hdu.edu.cn/contests/contest\_show.php?cid=867][http_acm.hdu.edu.

港控/mmm°/ 2021年10月26日 18:26/ 0 赞/ 271 阅读