[模拟,英语阅读] Codeforces 549D Haar Features

2024-02-03 09:30

本文主要是介绍[模拟,英语阅读] Codeforces 549D Haar Features,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:https://codeforces.com/contest/549/problem/D
D. Haar Features
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The first algorithm for detecting a face on the image working in realtime was developed by Paul Viola and Michael Jones in 2001. A part of the algorithm is a procedure that computes Haar features. As part of this task, we consider a simplified model of this concept.

Let's consider a rectangular image that is represented with a table of size n × m. The table elements are integers that specify the brightness of each pixel in the image.

A feature also is a rectangular table of size n × m. Each cell of a feature is painted black or white.

To calculate the value of the given feature at the given image, you must perform the following steps. First the table of the feature is put over the table of the image (without rotations or reflections), thus each pixel is entirely covered with either black or white cell. The value of a feature in the image is the value of W - B, where W is the total brightness of the pixels in the image, covered with white feature cells, and B is the total brightness of the pixels covered with black feature cells.

Some examples of the most popular Haar features are given below.

Your task is to determine the number of operations that are required to calculate the feature by using the so-called prefix rectangles.

A prefix rectangle is any rectangle on the image, the upper left corner of which coincides with the upper left corner of the image.

You have a variable value, whose value is initially zero. In one operation you can count the sum of pixel values ​​at any prefix rectangle, multiply it by any integer and add to variable value.

You are given a feature. It is necessary to calculate the minimum number of operations required to calculate the values of this attribute at an arbitrary image. For a better understanding of the statement, read the explanation of the first sample.

Input

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 100) — the number of rows and columns in the feature.

Next n lines contain the description of the feature. Each line consists of m characters, the j-th character of the i-th line equals to "W", if this element of the feature is white and "B" if it is black.

Output

Print a single number — the minimum number of operations that you need to make to calculate the value of the feature.

Examples
Input
Copy
6 8
BBBBBBBB
BBBBBBBB
BBBBBBBB
WWWWWWWW
WWWWWWWW
WWWWWWWW
Output
Copy
2
Input
Copy
3 3
WBW
BWW
WWW
Output
Copy
4
Input
Copy
3 6
WWBBWW
WWBBWW
WWBBWW
Output
Copy
3
Input
Copy
4 4
BBBB
BBBB
BBBB
BBBW
Output
Copy
4
Note

The first sample corresponds to feature B, the one shown in the picture. The value of this feature in an image of size 6 × 8 equals to the difference of the total brightness of the pixels in the lower and upper half of the image. To calculate its value, perform the following two operations:

  1. add the sum of pixels in the prefix rectangle with the lower right corner in the 6-th row and 8-th column with coefficient 1 to the variable value (the rectangle is indicated by a red frame);
  2. add the number of pixels in the prefix rectangle with the lower right corner in the 3-rd row and 8-th column with coefficient  - 2 and variable value.

Thus, all the pixels in the lower three rows of the image will be included with factor 1, and all pixels in the upper three rows of the image will be included with factor 1 - 2 =  - 1, as required.

题意:

给你一个n*m的特征表格,每个格要么是B要么是W,现在你有一个全为0的n*m的表格,目标是使格中的值与特征表格对应,B对应-1,W对应1,
为了达成这个目标你有一个操作,可以在表格中选定一个坐标,使从表格左上角到这个坐标形成的矩形中的格都加上你想要加的一个数,
问为了达成目标的最少操作次数是多少

思路:

这个题在训练时硬是没看懂(语文英语水平太弱了...TAT),当时看题时就在想一些问题:1,这个操作到底是干什么的? 2.那个prefix rectangle是怎么样的?3.最后要达成的目标是什么?回答:1.这个操作是选一个坐标,使得表格左上角到这个坐标的数全都加上一个选定的数.2.一个prefix rectangle指的是矩形左上角固定在表格左上角,并得到到一个坐标作为右下角形成的矩形.3.把一个初始值为0的表格,通过最少次数的上面那种操作,使得表格中的值对应特征矩阵中B为-1,W为1(为什么???这个是Note里说的,Note也可以作为条件啊)考虑尽可能少的操作,因为prefix rectangle左上角固定了,我们可以从右下角开始逐行从右到左从下到上检测是否需要改变,这样就不会有无用的重复操作.

感觉这是一道英语阅读题...我太菜了TAT
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int amn=1e2+5;
 4 char mp[amn][amn];
 5 int a[amn][amn];
 6 int main(){
 7     int n,m,ans,typ;
 8     ios::sync_with_stdio(0);
 9     while(cin>>n>>m){
10         memset(a,0,sizeof a);
11         for(int i=1;i<=n;i++){
12             for(int j=1;j<=m;j++){
13                 cin>>mp[i][j];
14             }
15         }
16         ans=0;
17         for(int i=n;i>=1;i--){
18             for(int j=m;j>=1;j--){
19                 typ=((mp[i][j]=='W')?1:-1);
20                 if(a[i][j]!=typ){
21                     ans++;
22                     for(int k=1;k<=i;k++){
23                         for(int l=1;l<=j;l++){
24                             a[k][l]+=typ-a[i][j];
25                         }
26                     }
27                 }
28             }
29         }
30         printf("%d\n",ans);
31     }
32 }
33 /**
34 给你一个n*m的特征表格,每个格要么是B要么是W,现在你有一个全为0的n*m的表格,目标是使格中的值与特征表格对应,B对应-1,W对应1,
35 为了达成这个目标你有一个操作,可以在表格中选定一个坐标,使从表格左上角到这个坐标形成的矩形中的格都加上你想要加的一个数,
36 问为了达成目标的最少操作次数是多少
37 这个题在训练时硬是没看懂(语文英语水平太弱了...TAT),当时看题时就在想一些问题:1,这个操作到底是干什么的? 2.那个prefix rectangle是怎么样的?
38 3.最后要达成的目标是什么?
39 回答:
40 1.这个操作是选一个坐标,使得表格左上角到这个坐标的数全都加上一个选定的数.
41 2.一个prefix rectangle指的是矩形左上角固定在表格左上角,并得到到一个坐标作为右下角形成的矩形.
42 3.把一个初始值为0的表格,通过最少次数的上面那种操作,使得表格中的值对应特征矩阵中B为-1,W为1(为什么???这个是Note里说的,Note也可以作为条件啊)
43 考虑尽可能少的操作,因为prefix rectangle左上角固定了,我们可以从右下角开始逐行从右到左从下到上检测是否需要改变,这样就不会有无用的重复操作
44 感觉这是一道英语阅读题...我太菜了TAT
45 **/

 

转载于:https://www.cnblogs.com/Railgun000/p/11537481.html

这篇关于[模拟,英语阅读] Codeforces 549D Haar Features的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听

【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<

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

hdu4431麻将模拟

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

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja

论文阅读笔记: Segment Anything

文章目录 Segment Anything摘要引言任务模型数据引擎数据集负责任的人工智能 Segment Anything Model图像编码器提示编码器mask解码器解决歧义损失和训练 Segment Anything 论文地址: https://arxiv.org/abs/2304.02643 代码地址:https://github.com/facebookresear