Codeforces Contest 1107 problem D Compression—— 前缀和找压缩矩阵

2024-04-07 00:38

本文主要是介绍Codeforces Contest 1107 problem D Compression—— 前缀和找压缩矩阵,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

You are given a binary matrix A of size n×n. Let’s denote an x-compression of the given matrix as a matrix B of size nx×nx such that for every i∈[1,n],j∈[1,n] the condition A[i][j]=B[⌈ix⌉][⌈jx⌉] is met.

Obviously, x-compression is possible only if x divides n, but this condition is not enough. For example, the following matrix of size 2×2 does not have any 2-compression:

01
10
For the given matrix A, find maximum x such that an x-compression of this matrix is possible.

Note that the input is given in compressed form. But even though it is compressed, you’d better use fast input.

Input
The first line contains one number n (4≤n≤5200) — the number of rows and columns in the matrix A. It is guaranteed that n is divisible by 4.

Then the representation of matrix follows. Each of n next lines contains n4 one-digit hexadecimal numbers (that is, these numbers can be represented either as digits from 0 to 9 or as uppercase Latin letters from A to F). Binary representation of each of these numbers denotes next 4 elements of the matrix in the corresponding row. For example, if the number B is given, then the corresponding elements are 1011, and if the number is 5, then the corresponding elements are 0101.

Elements are not separated by whitespaces.

Output
Print one number: maximum x such that an x-compression of the given matrix is possible.

Examples
inputCopy
8
E7
E7
E7
00
00
E7
E7
E7
outputCopy
1
inputCopy
4
7
F
F
F
outputCopy
1

题意:

给你n*n的矩阵,但是是用16进制来给,每一位都是0或者1,问你它最大的压缩比是多少,压缩就是 i∈[1,n],j∈[1,n] the condition A[i][j]=B[⌈i/x⌉][⌈j/x⌉] 向上取整。

题解:

那么我们可以得到,压缩之后,就是将A矩阵分成了一块一块的小矩阵,并且小矩阵里所有元素是一样的,那我们枚举n的所有因子,再用前缀和检查每一个矩形是否全1或者全0

#include<bits/stdc++.h>
using namespace std;
char mp[5205][5205];
int sum[5205][5205];
int main()
{int n;scanf("%d",&n);char a;for(int i=1;i<=n;i++){getchar();for(int j=1;j<=n;j+=4){scanf("%c",&a);int x=a>'9'?a-'A'+10:a-'0';for(int k=0;k<4;k++)sum[i][j+k]=(x>>(3-k))&1;}}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];for(int i=n;i>=1;i--){if(n%i)continue;int flag=1;for(int j=1;j*i<=n;j++){for(int k=1;k*i<=n;k++){int s=sum[i*j][i*k]-sum[i*j][i*(k-1)]-sum[i*(j-1)][i*k]+sum[i*(j-1)][i*(k-1)];flag&=(s==0||s==i*i);}}if(flag)return 0*printf("%d\n",i);}
}

这篇关于Codeforces Contest 1107 problem D Compression—— 前缀和找压缩矩阵的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/881239

相关文章

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

Java图片压缩三种高效压缩方案详细解析

《Java图片压缩三种高效压缩方案详细解析》图片压缩通常涉及减少图片的尺寸缩放、调整图片的质量(针对JPEG、PNG等)、使用特定的算法来减少图片的数据量等,:本文主要介绍Java图片压缩三种高效... 目录一、基于OpenCV的智能尺寸压缩技术亮点:适用场景:二、JPEG质量参数压缩关键技术:压缩效果对比

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

《Python实现将MySQL中所有表的数据都导出为CSV文件并压缩》这篇文章主要为大家详细介绍了如何使用Python将MySQL数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到... python将mysql数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到另一个

Python利用PIL进行图片压缩

《Python利用PIL进行图片压缩》有时在发送一些文件如PPT、Word时,由于文件中的图片太大,导致文件也太大,无法发送,所以本文为大家介绍了Python中图片压缩的方法,需要的可以参考下... 有时在发送一些文件如PPT、Word时,由于文件中的图片太大,导致文件也太大,无法发送,所有可以对文件中的图

Qt实现文件的压缩和解压缩操作

《Qt实现文件的压缩和解压缩操作》这篇文章主要为大家详细介绍了如何使用Qt库中的QZipReader和QZipWriter实现文件的压缩和解压缩功能,文中的示例代码简洁易懂,需要的可以参考一下... 目录一、实现方式二、具体步骤1、在.pro文件中添加模块gui-private2、通过QObject方式创建

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

hdu1565(状态压缩)

本人第一道ac的状态压缩dp,这题的数据非常水,很容易过 题意:在n*n的矩阵中选数字使得不存在任意两个数字相邻,求最大值 解题思路: 一、因为在1<<20中有很多状态是无效的,所以第一步是选择有效状态,存到cnt[]数组中 二、dp[i][j]表示到第i行的状态cnt[j]所能得到的最大值,状态转移方程dp[i][j] = max(dp[i][j],dp[i-1][k]) ,其中k满足c