NOIP-模拟试题之--矩阵

2024-04-04 05:08
文章标签 模拟 矩阵 noip 试题

本文主要是介绍NOIP-模拟试题之--矩阵,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2018 NOIP 全套资料下载-提取码:072k

【问题描述】

Mr_he有一个 n* m 的矩阵,并且把1~n* m 这n*m填写在这个矩阵中(注意,每个整数在矩阵出现一次,且仅出现一次)。
  Mr_he同时约定一个矩阵权值等于这个子矩阵中的所有数的最小值。
  现在Mr_he想知道,在给出的矩阵中,权值为i的子矩阵可能有多少种?

【输入格式】

第一行, 两个整数 N, M。接下来的 N 行, 每行 M 个整数, 表示矩阵中的元素。

【输出格式】

N×M 行, 每行一个整数, 其中第 i 行的整数表示如果小 A 选择的子矩阵权值为 i, 他选择的子矩阵的种类数。

【输入样例】

2 3
2 5 1
6 3 4

【输出样例】

6
4
5
1
1
1

【样例解释】

balabalabala(好吧只是我不想粘图而已AuA)
  其他情况不再赘述!

【数据范围】

对于 30%的数据, 1<=N, M<=50;
对于全部的数据, 1<=N, M<=300。

———————————————————————————————————————————————————————
枚举矩阵的上下行(简单来说就是两根线),对于两根线之间形成的矩阵我们发现实际上只有每一列上最小的元素可能是以这两根线为上下界的矩阵中的最小值,所以压缩一下就成了一个序列了。

思考序列上怎么办,可以发现对于一个位置i的元素以其为最小值的线段的端点只可能在L[i]+1和R[i]-1,L[i]表示i左边第一个小于它的元素的下标,R[i]类似。然后以这个点i为最小元素的线段数量就应该是(i-L[i])*(R[i]-i)。这个直接用单调队列就好了。

也就是说对于每一种上下界枚举的情况我们都可以算出这个上下界对某一个元素最终答案的贡献,最后枚举完之后答案自然就出来了。QAQ

AC代码:

#include< iostream>
#include< cstdio>
#include< cstring>
#include< cstdlib>
#include< algorithm>
#include< cmath>
#include< queue>
#include< set>
#include< map>
#include< vector>
#include< cctype>
#define inf 1e9+5
using namespace std;
const int maxn=305;

int N,M,A[maxn][maxn];
int ans[maxn*maxn],minv[maxn];
struct data{ int pos,v; }q[maxn];
int front,rear,L[maxn],R[maxn];

void _scanf(int &x)
{
x=0;
char ch=getchar();
while(ch<‘0’||ch>‘9’) ch=getchar();
while(ch>=‘0’&&ch<=‘9’) x=x10+ch-‘0’,ch=getchar();
}
void data_in()
{
_scanf(N);_scanf(M);
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++) _scanf(A[i][j]);
}
void calc()
{
front=rear=0;
for(int j=1;j<=M;j++)
{
while(front!=rear&&q[rear-1].v>minv[j]) rear–;
L[j]= front!=rear ? q[rear-1].pos : 0;
q[rear++]=(data){j,minv[j]};
}
front=rear=0;
for(int j=M;j>=1;j–)
{
while(front!=rear&&q[rear-1].v>minv[j]) rear–;
R[j]= front!=rear ? q[rear-1].pos : M+1;
q[rear++]=(data){j,minv[j]};
}
}
void work()
{
for(int i=1;i<=N;i++)
{
for(int j=1;j<=M;j++) minv[j]=inf;
for(int ii=i;ii<=N;ii++)
{
for(int j=1;j<=M;j++) minv[j]=min(minv[j],A[ii][j]);
calc();
for(int j=1;j<=M;j++)
ans[minv[j]]+=(j-L[j])
(R[j]-j);
}
}
for(int i=1;i<=N*M;i++)
printf("%d\n",ans[i]);
}
int main()
{
freopen(“matrix.in”,“r”,stdin);
freopen(“matrix.out”,“w”,stdout);
data_in();
work();
return 0;
}


原文:https://blog.csdn.net/qq_39439314/article/details/78174152

这篇关于NOIP-模拟试题之--矩阵的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值: Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中: 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令: An=(a+b√)n A_n = (a +

hdu4431麻将模拟

给13张牌。问增加哪些牌可以胡牌。 胡牌有以下几种情况: 1、一个对子 + 4组 3个相同的牌或者顺子。 2、7个不同的对子。 3、13幺 贪心的思想: 对于某张牌>=3个,先减去3个相同,再组合顺子。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOExcepti

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

【算法专场】模拟(下)

目录 前言 38. 外观数列 算法分析 算法思路 算法代码 1419. 数青蛙 算法分析 算法思路 算法代码  2671. 频率跟踪器 算法分析 算法思路 算法代码 前言 在前面我们已经讲解了什么是模拟算法,这篇主要是讲解在leetcode上遇到的一些模拟题目~ 38. 外观数列 算法分析 这道题其实就是要将连续且相同的字符替换成字符重复的次数+