【学习笔记】[PA2019] Osady i warownie 2
这题好抽象😱
EI 说这题可以转化为对偶图,但是我完全没看懂😅
考虑维护最向右和向下的两条路径,那么不能放的位置就是两条路径的交(感性理解一下)
考虑抽象的描述这条路径, r i r_i ri表示第 i i i行能到达的最大的列,那么 { r i } \{r_i\} {ri}是单调不降的,等价于我们要维护字典序最大/最小的路径
考虑向下的怎么维护。首先,这个点一定要在路径上,即 r x − 1 ≤ y ≤ r x r_{x-1}\le y\le r_x rx−1≤y≤rx(假设插入的点是 ( x , y ) (x,y) (x,y));其次,我们希望以最小的代价调整(尽量保持前缀不变),但是又必须绕过 ( x , y ) (x,y) (x,y),这等价于 ∀ i ≥ x − 1 , r i = max ( r i , y + 1 ) \forall i\ge x-1,r_i=\max(r_i,y+1) ∀i≥x−1,ri=max(ri,y+1)。注意到每次调整时至少有一个障碍以后不会被考虑到,因此总调整数目不会超过 O ( k ) O(k) O(k)。
因此递归下去即可。
复杂度 O ( k log k ) O(k\log k) O(klogk)。
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int n,m,K,v;
struct node{set<int>sx[100005],sy[100005];int bit[100005];int n,m;int get(int x,int y){return sx[x].count(y);}void add(int x,int y){for(x++;x<=n;x+=x&-x)bit[x]=max(bit[x],y);}int qmax(int x){int y(0);for(x++;x;x-=x&-x)y=max(y,bit[x]);return y;}int query(int x,int y){if(x==0)return qmax(x)>=y;return qmax(x-1)<=y&&y<=qmax(x);}void upd(int x,int y){if(!query(x,y))return;add(x-1,y+1),x--,y++;if(sx[x].size()&&sx[x].upper_bound(y)!=sx[x].begin()){auto it=--sx[x].upper_bound(y);upd(x,*it);}if(sy[y].size()&&sy[y].lower_bound(x)!=sy[y].end()){auto it=sy[y].lower_bound(x);upd(*it,y);}}void ins(int x,int y){sx[x].insert(y),sy[y].insert(x);upd(x,y);}
}R,D;
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m>>K;D.n=n,D.m=m;R.n=m,R.m=n;D.add(n-1,m-1);R.add(m-1,n-1);for(int i=1;i<=K;i++){int r,c,z;cin>>r>>c>>z;r=(r^v)%n,c=(c^v)%m;if(D.get(r,c)){cout<<"NIE"<<"\n";}else if(D.query(r,c)&&R.query(c,r)){cout<<"TAK"<<"\n";v^=z;} else{cout<<"NIE"<<"\n";D.ins(r,c),R.ins(c,r);}}
}
相关文章:
【学习笔记】[PA2019] Osady i warownie 2
这题好抽象😱 EI 说这题可以转化为对偶图,但是我完全没看懂😅 考虑维护最向右和向下的两条路径,那么不能放的位置就是两条路径的交(感性理解一下) 考虑抽象的描述这条路径, r i r_i ri表示…...
Flask——接口路由技术
接口路由技术 一、Flask 简介1、环境安装:2、一个最小的应用3、两种运行方式 二、定义路由1、普通路由2、动态路由3、限定类型4、地址尾部的“/” 三、请求与响应-请求方法四、请求与响应-处理请求数据1、request的常用属性/方法2、get 请求参数3、json 请求4、表单…...
Dubbo篇---第一篇
系列文章目录 文章目录 系列文章目录一、说说一次 Dubbo 服务请求流程?二、说说 Dubbo 工作原理三、Dubbo 支持哪些协议?一、说说一次 Dubbo 服务请求流程? 基本工作流程: 上图中角色说明: 二、说说 Dubbo 工作原理 工作原理分 10 层: 第一层:service 层,接口层,…...
powermock-成员变量赋值
powermock成员变量设置 //被测试类 Service public class Demo {private String aaa ;public String method1(){return aaa;} }//测试类,测试类中使用了mockito、和powermock,用powermock设置成员变量相较于mockito简洁一些,一般mockito和po…...
Axios请求成功和失败时分别执行哪个函数?
在 Axios 中,请求成功和失败时分别执行的函数是 then 和 catch。 特点: then 函数用于处理请求成功的情况,它接受一个回调函数作为参数,在请求成功时会调用该回调函数。catch 函数用于处理请求失败的情况,它也接受一…...
【Linux】进程概念III --fork函数解析
Halo,这里是Ppeua。平时主要更新C语言,C,数据结构算法…感兴趣就关注我吧!你定不会失望。 本篇导航 0. 创建进程1. 认识fork函数2.使用Fork函数3.关于fork的为什么3.1 一个函数如何返回两次?fork究竟在干什么?3.2 为什么要给子…...
关闭 Android SplashScreen(闪屏)
SplashScreen在Android 12上是强制的,如果你什么都不做,你的App在Android 12上就会自动拥有SplashScreen界面 但是这个SplashScreen界面太局限了能改的地方太少了 其实也没什么他主要作用是为了在App启动初始化的时候避免让用户在一个空白界面等待过长时…...
react_16
主页 import {DownCircleOutlined,MenuFoldOutlined,VerticalAlignTopOutlined, } from "ant-design/icons"; import { Button, Layout, Menu } from "antd"; import { ItemType } from "antd/es/menu/hooks/useItems"; import { Link, Navigat…...
前端性能分析工具
前段时间在工作中,需要判断模块bundle size缩减对页面的哪些性能产生了影响, 因此需要了解前端的性能指标如何定义的,以及前端有哪些性能分析工具, 于是顺便整理了一篇笔记, 以供前端小白对性能这块知识点做一个入门级的了解. 页面渲染 在了解性能指标和分析工具之前,有必要先…...
根据Aurora发送时序,造Aurora 数据包,从而进行AXIS接口数据位宽转换仿真
首先Aurora采用AXIS接口 由于后续需要进行AXIS接口 不同时钟域的数据位宽转换(64bit和256bit之间的转换),因此分两次走。 第一种方法:采用AXIS数据位宽转换IP AXIS跨时钟域IP 第二种方法:逻辑完成 下面记录逻辑…...
java后端响应结果Result
目录 一、Result1-1、响应代码1-2、调用响应1-3、在前端vue页面使用方法 一、Result 1-1、响应代码 package com.aaa.common;import lombok.AllArgsConstructor; import lombok.Data; import lombok.NoArgsConstructor;Data AllArgsConstructor NoArgsConstructor public cla…...
react_11
MobX 介绍 需求,组件0 改变了数据,其它组件也想获得改变后的数据,如图所示 这种多个组件之间要共享状态数据,useState 就不够用了,useContext 也不好用了 能够和 react 配合使用的状态管理库有 MobX Redux 其中…...
AI:52-基于深度学习的垃圾分类
🚀 本文选自专栏:AI领域专栏 从基础到实践,深入了解算法、案例和最新趋势。无论你是初学者还是经验丰富的数据科学家,通过案例和项目实践,掌握核心概念和实用技能。每篇案例都包含代码实例,详细讲解供大家学习。 📌📌📌本专栏包含以下学习方向: 机器学习、深度学…...
[shell,hive] 在shell脚本中将hiveSQL分离出去
将Hive SQL语句写在单独的.hql文件中, 然后在shell脚本中调用这些文件来执行Hive查询。 这样可以将SQL语句与shell脚本分离,使代码更加清晰和易于维护。 基本用法 以下是一个示例,展示如何在shell脚本中使用.hql文件执行Hive查询…...
求两个(法)向量之间的rpy夹角
主要使用Eigen库实现: 1. 四元素到欧拉角的转换 #include <array> #include <Eigen/Geometry>template <typename T> inline Eigen::Matrix<typename std::remove_reference<T>::type::Scalar, 3, 1> eulerAnglesZYX(T q_in) {typedef typenam…...
[100天算法】-每个元音包含偶数次的最长子字符串(day 53)
题目描述 给你一个字符串 s ,请你返回满足以下条件的最长子字符串的长度:每个元音字母,即 a,e,i,o,u ,在子字符串中都恰好出现了偶数次。示例 1:输入:s &qu…...
从科幻走向现实,LLM Agent 做到哪一步了?
LLM 洪流滚滚,AI 浪潮席卷全球,在这不断冲击行业认知的一年中,Agent 以冉冉新星之态引起开发者侧目。OpenAI 科学家 Andrej Karpathy 曾言“OpenAI 在大模型领域快人一步,但在 Agent 领域,却是和大家处在同一起跑线上。…...
[笔记] 数据类型
整形 一字节(Byte,也就是平时KB、MB里面的B)就是八个二进制位(bit) 整形——int——4B无符号整形——unsigned int——4B短整形——short——2B长整型——long——4B双长整型——long long——8B 浮点型 参考博客:C 语言的浮点类型…...
QT学习之QT概述
1.1 什么是QT? Qt是一个跨平台的C图形用户界面应用程序框架。 QT特点: 跨平台,几乎支持所有的平台接口简单,容易上手,学习QT框架对学习其他框架有参考意义。一定程度上简化了内存回收机制开发效率高,能够…...
编写shell脚本,利用mysqldump实现MySQL数据库分库分表备份
查看数据和数据表 mysql -uroot -p123456 -e show databases mysql -uroot -p123456 -e show tables from cb_d 删除头部Database和数据库自带的表 mysql -uroot -p123456 -e show databases -N | egrep -v "information_schema|mysql|performance_schema|sys"编写…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
