当前位置：首页 > news >正文

CodeForces 611：New Year and Domino ← 二维前缀和

news 来源：原创 2025/5/22 5:20:03

【题目来源】
https://codeforces.com/contest/611/problem/C

【题目描述】
They say "years are like dominoes, tumbling one after the other". But would a year fit into a grid? I don't think so.
Limak is a little polar bear who loves to play. He has recently got a rectangular grid with h rows and w columns. Each cell is a square, either empty (denoted by '.') or forbidden (denoted by '#'). Rows are numbered 1 through h from top to bottom. Columns are numbered 1 through w from left to right.
Also, Limak has a single domino. He wants to put it somewhere in a grid. A domino will occupy exactly two adjacent cells, located either in one row or in one column. Both adjacent cells must be empty and must be inside a grid.
Limak needs more fun and thus he is going to consider some queries. In each query he chooses some rectangle and wonders, how many way are there to put a single domino inside of the chosen rectangle?
大意：给出一个由 '.' 及 '#' 构成的 h×w 的矩形格子，其中 “." 代表空，"#" 代表满。现在将一个大小为 1*2 的长方形多米诺骨牌，放进这个 h×w 的矩形格子的多个子矩形中，问在每个子矩形里有多少种放法。

【输入格式】
The first line of the input contains two integers h and w (1≤h,w≤500) – the number of rows and the number of columns, respectively.
The next h lines describe a grid. Each line contains a string of the length w. Each character is either '.' or '#' — denoting an empty or forbidden cell, respectively.
The next line contains a single integer q (1≤q≤100000) — the number of queries.
Each of the next q lines contains four integers r1i, c1i, r2i, c2i (1≤r1i≤r2i≤h,1≤c1i≤c2i≤w) — the i-th query. Numbers r1i and c1i denote the row and the column (respectively) of the upper left cell of the rectangle. Numbers r2i and c2i denote the row and the column (respectively) of the bottom right cell of the rectangle.
大意：第一行，两个整数 h 和 w，表示矩形格子的行数和列数；接下来 h 行，每行是由 '.' 或 '#' 构成的长度为 w 的字符串。其中，“." 代表空，"#" 代表满；接下来一行，为一个整数 q，表示询问次数；接下来 q 行，每行 4 个整数，每行的头两个数，表示子矩形的左上角坐标，每行的后两个数，表示子矩形的右下角坐标。

【输出格式】
Print q integers, i-th should be equal to the number of ways to put a single domino inside the i-th rectangle.
大意：q 行，每行一个整数，表示在给定子矩形中放置一块多米诺骨牌的方法数。

【输入样例1】

5 8
....#..#
.#......
##.#....
##..#.##
........
4
1 1 2 3
4 1 4 1
1 2 4 5
2 5 5 8

【输出样例1】

【输入样例2】

7 39
.......................................
.###..###..#..###.....###..###..#..###.
...#..#.#..#..#.........#..#.#..#..#...
.###..#.#..#..###.....###..#.#..#..###.
.#....#.#..#....#.....#....#.#..#..#.#.
.###..###..#..###.....###..###..#..###.
.......................................
6
1 1 3 20
2 10 6 30
2 10 7 30
2 2 7 7
1 7 7 7
1 8 7 8

【输出样例2】

【说明】
A red frame below corresponds to the first query of the first sample. A domino can be placed in 4 possible ways.
大意：下面的红色框对应于第一个示例的第一个查询。针对此查询，多米诺骨牌有4种摆放方式。

【算法分析】
● 前缀和及差分：https://blog.csdn.net/hnjzsyjyj/article/details/145290457

【算法代码】

#include<bits/stdc++.h>
using namespace std;const int maxn=505;
char g[maxn][maxn];
int s[maxn][maxn];
int tx[maxn][maxn],ty[maxn][maxn];int main() {int n,m;cin>>n>>m;for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {cin>>g[i][j];}}for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {if(g[i-1][j]=='.' && g[i][j]=='.') {s[i][j]++;tx[i][j]=1;}if(g[i][j-1]=='.' && g[i][j]=='.') {s[i][j]++;ty[i][j]=1;}s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];}}int q;cin>>q;while(q--) {int x1,x2,y1,y2;cin>>x1>>y1>>x2>>y2;int ans=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];for(int i=x1; i<=x2; i++) ans-=ty[i][y1];for(int i=y1; i<=y2; i++) ans-=tx[x1][i];cout<<ans<<endl;}return 0;
}/*
in:
5 8
....#..#
.#......
##.#....
##..#.##
........
4
1 1 2 3
4 1 4 1
1 2 4 5
2 5 5 8out:
4
0
10
15
*/

【参考文献】
https://zhuanlan.zhihu.com/p/568454667
https://blog.csdn.net/hnjzsyjyj/article/details/145292538
https://blog.csdn.net/hnjzsyjyj/article/details/145290457
https://www.cnblogs.com/WABoss/p/5700154.html
https://blog.csdn.net/Z_sea/article/details/81180751

CodeForces 611：New Year and Domino ← 二维前缀和

【题目来源】 https://codeforces.com/contest/611/problem/C 【题目描述】 They say "years are like dominoes, tumbling one after the other". But would a year fit into a grid? I dont think so. Limak is a little polar bear who loves to play. He has r…...

编程日记 2025/5/22 5:20:03

【ROS2】RViz2界面类 VisualizationFrame 详解

1、简述 VisualizationFrame 继承自 QMainWindow 和 WindowManagerInterface；窗口顶部是常规布局：菜单栏和工具栏窗口中心是 RenderPanel，用来渲染3D画面周围是dock区域，包括：DisplaysPanel、ViewsPanel、TimePanel、SelectionPanel 和 ToolPropertiesPanel Windo…...

编程日记 2025/5/22 1:38:38

梯度下降法 (Gradient Descent) 算法详解及案例分析

梯度下降法 (Gradient Descent) 算法详解及案例分析目录梯度下降法 (Gradient Descent) 算法详解及案例分析1. 引言2. 梯度下降法 (Gradient Descent) 算法原理2.1 基本概念2.2 算法步骤2.3 梯度下降法的变种3. 梯度下降法的优势与局限性3.1 优势3.2 局限性4. 案例分析4.1 案…...

编程日记 2025/5/22 3:03:56

【Flutter】旋转元素（Transform、RotatedBox ）

这里写自定义目录标题 Transform旋转元素可以改变宽高约束的旋转 - RotatedBox Transform旋转元素说明：Transform旋转操作改变了元素的方向，但并没有改变它的布局约束。因此，虽然视觉上元素看起来是旋转了，但它仍然遵循原始的宽…...

编程日记 2025/5/22 3:27:49

大数运算之C语言实现

一、前言在我们代码编程过程中，我们经常需要处理各种规模的数值。从日常工作中的一些简单算术在到科学研究中的复杂计算，数字无处不在。然而，当数值变的异常庞大时，就需要用到大数运算来进行实现。本文我们将介绍大数运算的基本…...

编程日记 2025/5/22 2:54:50

三高“高性能、高并发、高可靠”系统架构设计系列文章

目录高并发系统的艺术：如何在流量洪峰中游刃有余《数据密集型应用系统设计》读后感与高并发高性能实践案例系统稳定性与高可用保障的几种思路软件系统限流的底层原理解析技术解决方案调研延迟队列调研重试调研异步回调调研分库分表调研分布式事…...

编程日记 2025/5/22 3:59:25

Java设计模式十八状态模式 (State Pattern)

状态模式 (State Pattern) 状态模式是一种行为型设计模式，它允许对象在其内部状态改变时改变其行为。状态模式让一个对象在其状态改变时，其行为也随之改变，看起来就像是改变了对象的类。通过将状态的变化封装到不同的状态对象中，…...

编程日记 2025/5/22 3:51:13

Django创建纯净版项目并启动

1.Django的基本目录结构 2. 创建app项目 python manage.py startapp user# python manage.py 是固定的，代表python脚本，主要用于django中的项目管理 # startapp 创建app # user 你的app名字，也就是功能模块名称3.数据库进入settings.…...

编程日记 2025/5/21 10:19:15

[b01lers2020]Life on Mars1

打开题目页面如下看了旁边的链接，也没有什么注入点，是正常的科普利用burp suite抓包，发现传参访问一下 http://5edaec92-dd87-4fec-b0e3-501ff24d3650.node5.buuoj.cn:81/query?searchtharsis_rise 接下来进行sql注入方法一&#xf…...

编程日记 2025/5/21 10:33:53

element-plus 的table section如何实现单选

如果是单选那么全新的按钮应该隐藏或者不可编辑的状态。但是我没找到改变成不可编辑的方法，只能采取隐藏 <template><div><el-table ref"proTab…...

编程日记 2025/5/22 2:57:23

利用Qt5.15.2编写Android程序时遇到的问题及解决方法

文章目录背景1.文件读写背景目前我用的是Qt5.15.2来编写Qt程序，环境的配置看我这篇文章【Qt5.15.2配置Android开发环境】项目中的一些配置的截图： 1.文件读写假如直接用 QFileDialog::getExistingDirectory来获取路径的话，会得到类…...

编程日记 2025/5/19 17:51:07

奇怪的单词（快速扩张200个单词）

这是一些非常奇怪的单词： screw n.螺丝；螺丝钉 screwdriver n.起子，螺丝刀，改锥 copulation n.连接 copulate a.配合的 bonk n.撞击；猛击 v.轻击；碰撞ebony n.黑檀couple n.夫妇blonde n.金发女郎intimacy…...

编程日记 2025/5/21 18:07:08

three.js+WebGL踩坑经验合集(4.1):THREE.Line2的射线检测问题（注意本篇说的是Line2，同样也不是阈值方面的问题）

上篇大家消化得如何了？ 笔者说过，1级编号不同的两篇博文相对独立，所以这里笔者还是先给出完整代码，哪怕跟（3）没有太大区别。这里我们把线的粗细调成5（排除难选中的因素）&#xff…...

编程日记 2025/5/22 2:56:29

postgresql根据主键ID字段分批删除表数据

生产环境针对大表的处理相对比较麻烦。方案1、直接truncate，可能会遇到系统卡主的情况，因为truncate的过程中会对表进行加锁，会导致数据不能正常的写入方案2、创建一个同结构的表结构，rename旧表，不停业务rename表担…...

编程日记 2025/5/22 2:48:22

NIO 和 Netty 在 Spring Boot 中的集成与使用

Netty到底是个啥，有啥子作用 1. Netty 的本质：对 NIO 的封装 NIO 的原生问题： Java 的 NIO 提供了非阻塞 I/O 和多路复用机制，但其使用较为复杂（如 Selector、Channel、Buffer 的配置和管理）。开发者需要自…...

编程日记 2025/5/21 10:23:40

【AI论文】Sigma：对查询、键和值进行差分缩放，以实现高效语言模型

摘要：我们推出了Sigma，这是一个专为系统领域设计的高效大型语言模型，其独特之处在于采用了包括DiffQKV注意力机制在内的新型架构，并在我们精心收集的系统领域数据上进行了预训练。DiffQKV注意力机制通过根据查询（Q&…...

编程日记 2025/5/21 22:46:34

ThinkPHP 8请求处理-获取请求对象与请求上下文

【图书介绍】《ThinkPHP 8高效构建Web应用》-CSDN博客《2025新书 ThinkPHP 8高效构建Web应用编程与应用开发丛书夏磊清华大学出版社教材书籍 9787302678236 ThinkPHP 8高效构建Web应用》【摘要书评试读】- 京东图书使用Composer初始化ThinkPHP 8应用_thinkphp8 compos…...

编程日记 2025/5/22 5:02:05

【设计模式】JAVA 策略工厂模式彻底告别switch if 等

【设计模式】JAVA 策略工厂模式彻底告别switch if 等目录【设计模式】JAVA 策略工厂模式彻底告别switch if 等优势适用场景项目结构关键代码优势消除 switch：将分支逻辑分散到独立的策略类中。开闭原则：新增类型只需添加新的 TypeHa…...

编程日记 2025/5/22 4:58:58

Pyecharts之词云图、面积图与堆叠面积图

在数据可视化的精彩世界里，我们可以运用各种各样的图表来展现数据的魅力，帮助我们更好地理解和分析数据。Pyecharts 作为一款功能强大的数据可视化工具，为我们提供了丰富的图表类型，今天我们将深入探讨词云图、面积图和堆叠面积图…...

编程日记 2025/5/15 17:23:31

SpringBoot3+Vue3开发学生选课管理系统

功能介绍分三个角色登录：学生登录，老师登录，教务管理员登录，不同用户功能不同！ 1.学生用户功能选课记录，查看选课记录，退选。选课管理，进行选课。通知管理，查看通知消…...

编程日记 2025/5/22 4:21:56

71.在 Vue 3 中使用 OpenLayers 实现按住 Shift 拖拽、旋转和缩放效果

前言在前端开发中，地图功能是一个常见的需求。OpenLayers 是一个强大的开源地图库，支持多种地图源和交互操作。本文将介绍如何在 Vue 3 中集成 OpenLayers，并实现按住 Shift 键拖拽、旋转和缩放地图的效果。实现效果按住 Shift 键&#…...

编程日记 2025/5/22 3:21:51

Mybatis——sql映射文件中的增删查改

映射文件内的增删查改准备工作准备一张数据表，用于进行数据库的相关操作。新建maven工程， 导入mysql-connector-java和mybatis依赖。新建一个实体类，类的字段要和数据表的数据对应编写接口编写mybatis主配置文件 public class User {priva…...

编程日记 2025/5/19 18:04:12

Git进阶笔记系列(01)Git核心架构原理 | 常用命令实战集合

读书笔记：卓越强迫症强大恐惧症，在亲子家庭、职场关系里尤其是纵向关系模型里，这两种状态很容易无缝衔接。尤其父母对子女、领导对下属，都有望子成龙、强将无弱兵的期望，然而在你的面前，他们才是永远强大的…...

编程日记 2025/5/21 14:33:23

立创开发板入门ESP32C3第八课修改AI大模型接口为deepseek3接口

#原代码用的AI模型是minimax的API接口，现在试着改成最热门的deepseek3接口。# 首先按理解所得，在main文件夹下，有minimax.c和minimax.h, 它们是这个API接口的头文件和实现文件，然后在main.c中被调用。所以我们一步步更改。申请…...

编程日记 2025/5/17 16:37:02

【云安全】云原生-Docker（五）容器逃逸之漏洞利用

漏洞利用逃逸通过漏洞利用实现逃逸，主要分为以下两种方式： 1、操作系统层面的内核漏洞这是利用宿主机操作系统内核中的安全漏洞，直接突破容器的隔离机制，获得宿主机的权限。攻击原理：容器本质上是通过 Linux 的…...

编程日记 2025/5/18 4:50:11

为什么IDEA提示不推荐@Autowired❓️如果使用@Resource呢❓️

前言在使用 Spring 框架时，依赖注入（DI）是一个非常重要的概念。通过注解，我们可以方便地将类的实例注入到其他类中，提升开发效率。Autowired又是被大家最为熟知的方式，但很多开发者在使用 IntelliJ IDEA …...

编程日记 2025/5/19 20:08:10

PHP：动态网站开发的强大引擎

在互联网技术日新月异的今天，PHP（Hypertext Preprocessor，超文本预处理器）作为一种开源的服务器端脚本语言，凭借其灵活性和易用性，依然是构建动态网站和Web应用程序的首选之一。从简单的个人博客到复杂的企…...

编程日记 2025/5/17 0:43:17

Linux 目录操作详解

Linux目录操作详解 1. 获取当前工作目录1.1 getcwd()1.2 get_current_dir_name() 2. 切换工作目录2.1 chdir() 3. 创建和删除目录3.1 mkdir()3.2 rmdir() 4. 获取目录中的文件列表4.1 opendir() 打开目录4.2 readdir() 读取目录内容4.3 closedir() 关闭目录 5. dirent 结构体6.…...

编程日记 2025/5/17 17:40:54

IMX6ull项目环境配置

文件解压缩： .tar.gz 格式解压为 tar -zxvf .tar.bz2 格式解压为 tar -jxvf 2.4版本后的U-boot.bin移植进SD卡后，通过串口启动配置开发板和虚拟机网络。 setenv ipaddr 192.168.2.230 setenv ethaddr 00:04:9f:…...

编程日记 2025/5/20 23:18:59

redis实现lamp架构缓存

redis服务器环境下mysql实现lamp架构缓存 ip角色环境192.168.242.49缓存服务器Redis2.2.7192.168.242.50mysql服务器mysql192.168.242.51web端php ***默认已安装好redis，mysql 三台服务器时间同步（非常重要） # 下载ntpdate yum -y install…...

编程日记 2025/5/20 20:39:38

与机器学习相关的概率论重要概念的介绍和说明

概率论一些重要概念的介绍和说明 1、试验 （1）试验是指在特定条件下，对某种方法、技术、设备或产品（即，事物）进行测试或验证的过程。 （2）易混淆的概念是，实验。实验&…...

编程日记 2025/5/21 19:29:46

深度学习 Pytorch 单层神经网络

神经网络是模仿人类大脑结构所构建的算法，在人脑里，我们有轴突连接神经元，在算法中，我们用圆表示神经元，用线表示神经元之间的连接，数据从神经网络的左侧输入，让神经元处理之后，从右…...

编程日记 2025/5/13 17:43:59

常用集合-数据结构-MySql

目录 java核心： 常用集合与数据结构: 单例集合: 双列集合: 线程安全的集合: ConcurrentHashMap集合: HashTable集合: CopyOnWriteArrayList集合: CopyOnWriteArraySet集合: ConcurrentLinkedQueue队列: ConcurrentSkipListMap和ConcurrentSkipListSet&…...

编程日记 2025/5/18 7:12:10

策略模式 - 策略模式的使用

引言在软件开发中，设计模式是解决常见问题的经典解决方案。策略模式（Strategy Pattern）是行为型设计模式之一，它允许在运行时选择算法的行为。通过将算法封装在独立的类中，策略模式使得算法可以独立于使用它的客户端…...

编程日记 2025/5/20 4:56:16

【贪心算法】在有盾牌的情况下能通过每轮伤害的最小值（亚马逊笔试题）

思路： 采用贪心算法，先计算出来所有的伤害值，然后再计算每轮在使用盾牌的情况下能减少伤害的最大值，最后用总的伤害值减去能减少的最大值就是最少的总伤害值 public static long getMinimumValue(List<Integer> power, int…...

编程日记 2025/5/22 4:24:41

零基础Vue学习1——Vue学习前环境准备

目录环境准备创建Vue项目项目目录说明后续开发过程中常用命令环境准备安装开发工具：vscode、webstorm、idea都可以安装node:V22以上版本即可安装pnpm 不知道怎么安装的可以私信我教你方法创建Vue项目本地新建一个文件夹，之后在文件夹下打开…...

编程日记 2025/5/18 21:55:20

小游戏源码开发搭建技术栈和服务器配置流程

近些年各种场景小游戏开发搭建版本层出不穷,山东布谷科技拥有多年海内外小游戏源码开发经验，现为从事小游戏源码开发或游戏运营的朋友们详细介绍小游戏开发及服务器配置流程。一、可以对接到app的小游戏是如何开发的 1、小游戏源码开发的需求分析： 明…...

编程日记 2025/5/19 7:40:24

【Rust自学】15.3. Deref trait Pt.2：隐式解引用转化与可变性

喜欢的话别忘了点赞、收藏加关注哦（加关注即可阅读全文），对接下来的教程有兴趣的可以关注专栏。谢谢喵！(･ω･) 15.3.1. 函数和方法的隐式解引用转化(Deref Coercion) 隐式解引用转化(Deref Coercion)是为…...

编程日记 2025/5/20 1:59:00

SQL-leetcode—1174. 即时食物配送 II

1174. 即时食物配送 II 配送表: Delivery ------------------------------------ | Column Name | Type | ------------------------------------ | delivery_id | int | | customer_id | int | | order_date | date | | customer_pref_delivery_date | date | -------------…...

编程日记 2025/5/15 17:50:46

css3 svg制作404页面动画效果HTML源码

源码介绍 css3 svg制作404页面动画效果HTML源码，源码由HTMLCSSJS组成，记事本打开源码文件可以进行内容文字之类的修改，双击html文件可以本地运行效果效果预览源码如下 <!doctype html> <html> <head> <meta charse…...

编程日记 2025/5/18 18:03:38

MATLAB提供的颜色映射表colormap——伪彩色

图像处理领域的一个习惯：不是真实的颜色，一般用伪彩色。一是说明不是物体本身的颜色，二是彩色更容易分辨。 MATLAB陆续提供了16种颜色映射表colormap。之前的都很丑，近5年新增的4种还可以。总的说来还是丑。这是一种鸟的名字。…...

编程日记 2025/5/18 9:18:26

2013年蓝桥杯第四届CC++大学B组真题及代码

目录 1A：高斯日记（日期计算） 2B：马虎的算式（暴力模拟） 3C：第39级台阶（dfs或dp） 4D：黄金连分数（递推大数运算） 5E：前缀…...

编程日记 2025/5/20 4:24:34

我的创作纪念日——1/23

机缘想起写博客，其实是当时看鹏哥C语言时，他说通过写博客的方式来记录自己学习过程，有利于提升自己。尽管我只看了几集就没怎么看，但是写博客的习惯保留下来。至于为什么，一方面单纯当作单个代码库，把自…...

编程日记 2025/5/21 23:34:16

C# Interlocked 类使用详解

总目录前言在多线程编程中，确保多个线程对共享资源的安全访问是一个关键挑战。C# 提供了多种同步机制来处理并发问题，其中 System.Threading.Interlocked 类提供了一种轻量级的方法来进行原子操作。它允许您执行一些常见的增量、减量、交换等操作&…...

编程日记 2025/5/20 5:57:29

SYN Flooding的攻击原理

SYN Flooding是一种常见的网络攻击方式，属于拒绝服务攻击（DoS）的一种，其攻击原理主要是利用了TCP协议的三次握手过程，以下是具体介绍： TCP三次握手正常流程第一次握手：客户端向服务器发送一个…...

编程日记 2025/5/19 3:16:04

Mono里运行C#脚本35—加载C#语言基类的过程

前面大体地分析了整个Mono运行过程，主要从文件的加载，再到EXE文件的入口点，然后到方法的编译，机器代码的生成，再到函数调用的跳板转换，进而解析递归地实现JIT。但是还有很多功能没有解析的，就是C#语言相关最多的，就是类的加载，以及类语言设计的实现属性，比如类的…...

编程日记 2025/5/19 16:01:56

类包含类三角分形面向对象

Cad c# Sj类的构造函数，直接包含电线和三个分形三角形。...

编程日记 2025/5/16 2:56:04

Flutter：搜索页，搜索bar封装

view 使用内置的Chip简化布局 import package:chenyanzhenxuan/common/index.dart; import package:ducafe_ui_core/ducafe_ui_core.dart; import package:flutter/material.dart; import package:get/get.dart; import package:tdesign_flutter/tdesign_flutter.dart;import i…...

编程日记 2025/5/18 8:43:13

chrome插件：网页图片高清下载

前置条件： 安装有chrome谷歌浏览器的电脑使用步骤： 1.打开chrome扩展插件 2.点击管理扩展程序 3.加载已解压的扩展程序 4.选择对应文件夹 5.成功后会出现一个扩展小程序 6.点击对应小程序 7.输入需要访问的网址，点击扩展插件即可进行图片…...

编程日记 2025/5/17 3:51:27

docker 简要笔记

文章目录一、前提内容1、docker 环境准备2、docker-compose 环境准备3、流程说明二、打包 docker 镜像1、基础镜像2、国内镜像源3、基础的dockerfile4、打包镜像四、构建运行1、docker 部分2、docker-compose 部分2.1、构建docker-compose.yml2.1.1、同目录构建2.1.2、利用镜…...

编程日记 2025/5/20 8:57:17

相关文章：