SMU Summer 2024 Contest Round 2
[ABC357C] Sierpinski carpet - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:通过因为图形的生成过程是完全一样的。可以通过递归,不断分形。函数process(x,y,k)定义为以坐标(x,y)为左上角,填充sqrt3(k)级的地毯。
int n;
int c[800][800]; 默认全为0, 0对应'.' 1对应'#'
void process(int x,int y,int k){ 填充左上角为x,y的sqrt3(k)级地毯if(k==0) {c[x][y]=1; base casereturn;}int t=k/3;process(x,y,t);process(x,y+t,t);process(x,y+t*2,t);process(x+t,y,t);//process(x+t,y+t,t); 留白process(x+t,y+t*2,t);process(x+t*2,y,t);process(x+t*2,y+t,t);process(x+t*2,y+t*2,t);
}
[ABC357C] Sierpinski carpet
https://www.luogu.com.cn/problem/AT_abc357_c
void solve(){ 补A--递归 分型 "好题" 要清楚是怎么'跳跃',分型的,bask case是什么cin>>n;int t=pow(3,n);process(1,1,t);for(int i=1;i<=t;i++){for(int j=1;j<=t;j++){if(c[i][j]) cout<<"#";else cout<<".";}cout<<endl;}
}
// ######### ######### #########
// #.##.##.# #.##.##.# #.##.##.#
// ######### ######### #########
// ###...### ###...### ###...###
// #.#...#.# #.#...#.# #.#...#.#
// ###...### ###...### ###...###
// ######### ######### #########
// #.##.##.# #.##.##.# #.##.##.#
// ######### ######### #########
//
// ######### ......... #########
// #.##.##.# ......... #.##.##.#
// ######### ......... #########
// ###...### ......... ###...###
// #.#...#.# ......... #.#...#.#
// ###...### ......... ###...###
// ######### ......... #########
// #.##.##.# ......... #.##.##.#
// ######### ......... #########
//
// ######### ######### #########
// #.##.##.# #.##.##.# #.##.##.#
// ######### ######### #########
// ###...### ###...### ###...###
// #.#...#.# #.#...#.# #.#...#.#
// ###...### ###...### ###...###
// ######### ######### #########
// #.##.##.# #.##.##.# #.##.##.#
// ######### ######### #########
[ABC325D] Printing Machine - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:写的有点迷糊的贪心题。显而易见的是,在L相同的情况下,肯定是先选择R更小的。
所以可以把输入按照L从小到大排列,依次处理,L相同的 按L+R从小到大排列。之后怎么处理呢?
一秒一秒枚举时间是不可能的。但是可以知道的是,中间有很多间隔是没意义的。
那么可以从time=1开始,把开始时间L与当前时间一样的的物品的右区间放入优先队列中。之后一个一个取。直到队列为空。要注意的是!当且仅当队列为空时,才判断time跳跃到下一个区间的开始时间L。不然的话可能优先队列里面还有物品,并且时间大于time。仍然可以取,但是因为提前跳跃了,导致没取到。
int n;
pair<int,int> arr[200005];
//multiset<pair<int,int>> mst;
画个时间区间轴。
[ABC325D] Printing Machine
https://www.luogu.com.cn/problem/AT_abc325_d
void solve(){ 补D--贪心 "好题" 太头疼了这个题。。cin>>n;for(int i=1;i<=n;i++) {cin>>arr[i].first>>arr[i].second;arr[i].second=arr[i].first+arr[i].second;}sort(arr+1,arr+n+1); 按l从小到大排序,l相等的话,按l+r从小到大排序.priority_queue<int,vector<int>,greater<int>> pq;int ans=0,idx=1,time=1;while(idx<=n||pq.size()){//if(arr[idx].first!=time&&idx<=n) time=arr[idx].first; 这个代码会导致直接跳过很多if(pq.size()==0&&idx<=n) time=arr[idx].first;while(idx<=n&&arr[idx].first==time) {pq.emplace(arr[idx++].second);}while(pq.size()&&pq.top()<time) pq.pop();if(pq.size()) ans++,pq.pop();time++;}cout<<ans;
}
//的确是贪心,但是策略不对
//优先选晚结束或者早结束的贪心策略都不对:hack:
//expect:4 answer:3
//key:这个样例的问题是怎么处理在第三秒时候的选择.也是这题的关键.
5
1 3 [1,4] 1s
1 3 [1,4] 2s
1 3 [1,4] 3s
2 1 [2,3]
2 1 [2,3]
[ABC299E] Nearest Black Vertex - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:这个题不难出思路,也不难实现。注意细节即可。
o(k*n)预处理出每个pi满足约束时需要成为黑点的候选点mayBlack[pi]。同时记录不可能成为黑点的点notBlack.即在di范围内的点。
最后遍历每一个候选点的mayBlack[pi],排除不可能的点。如果某一个mayBlack[pi]里的点都是不可能的点notBlack,那么No,否则Yes.
yes的时候直接把所有非notBlack的点涂黑即可。
int n,m,k;
vector<int> vct[2005];
vector<int> mark,mayBlack[2005];
unordered_map<int,bool> notBlack;
思路:--AC
o(k*n)预处理出每个pi需要成为黑点的候选点。同时记录不可能成为黑点的点.即在di范围内的点。
最后遍历每一个候选点,排除不可能的点。如果某一个mayBlack[pi]里的点都是不可能的点,那么No,否则Yes.
[ABC299E] Nearest Black Vertex ---全1,不能用01bfs
https://www.luogu.com.cn/problem/AT_abc299_e
void bfs(int s,int d){int dis[2005]={0};queue<int> que;que.emplace(s);while(que.size()){int cur=que.front();que.pop();notBlack[cur]=true;for(auto v:vct[cur]){if(dis[v]!=0||v==s) continue;dis[v]=dis[cur]+1;if(dis[v]!=d) que.emplace(v);else mayBlack[s].emplace_back(v);}}
}
void solve(){ E 至少有一个顶点被涂成黑色。。cin>>n>>m;for(int i=1;i<=m;i++){int u,v; cin>>u>>v;vct[u].emplace_back(v);vct[v].emplace_back(u);}cin>>k;for(int i=1;i<=k;i++){ o(k*n)int p,d; cin>>p>>d;mark.emplace_back(p);if(d==0) mayBlack[p].emplace_back(p);else bfs(p,d);}bool check=true;for(auto mk:mark){ o(k*n)int cnt=0;for(auto mb:mayBlack[mk]){if(notBlack[mb]) cnt++;}if(cnt==mayBlack[mk].size()) check=false;if(!check) break;}if(check){ notBlack.size()==n也是可以的cout<<"Yes"<<endl;for(int i=1;i<=n;i++) {if(notBlack[i]) cout<<"0";else cout<<"1";}}else cout<<"No"<<endl;
}
相关文章:
SMU Summer 2024 Contest Round 2
[ABC357C] Sierpinski carpet - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路:通过因为图形的生成过程是完全一样的。可以通过递归,不断分形。函数process(x,y,k)定义为以坐标(x,y)为左上角,填充sqrt3(k)级的地毯。 int n; int c[800][800]; 默认全为…...
Qt:11.输入类控件(QLineEdit-单行文本输入控件、QTextEdit-多行文本输入控件、QComboBox-下拉列表的控件)
一、QLineEdit-单行文本输入控件: 1.1QLineEdit介绍: QLineEdit 是 Qt 库中的一个单行文本输入控件,不能换行。允许用户输入和编辑单行文本。 1.2属性介绍: inputMask 设置输入掩码,以限定输入格式。setInputMask(con…...
Qt 音频编程实战项目
一Qt 音频基础知识 QT multimediaQMediaPlayer 类:媒体播放器,主要用于播放歌曲、网络收音 机等功能。QMediaPlaylist 类:专用于播放媒体内容的列表。 二 音频项目实战程序 //版本5.12.8 .proQT core gui QT multimedia greate…...
C#委托事件的实现
1、事件 在C#中事件是一种特殊的委托类型,用于在对象之间提供一种基于观察者模式的通知机制。 1.1、事件的发送方定义了一个委托,委托类型的声明包含了事件的签名,即事件处理器方法的签名。 1.2、事件的订阅者可以通过运算符来注册事件处理器…...
Java策略模式在动态数据验证中的应用
在软件开发中,数据验证是一项至关重要的任务,它确保了数据的完整性和准确性,为后续的业务逻辑处理奠定了坚实的基础。然而,不同的数据来源往往需要不同的验证规则,如何在不破坏代码的整洁性和可维护性的同时࿰…...
【Linux】shell基础知识点(updating)
1.输出重定向2.多命令批量执行(; 、&&、 ||)3.脚本不同方式执行的区别(source、bash、sh、./)4.理解环境变量5.export6.引号的使用last.命令相关 1.输出重定向 3种数据流: stdin:标准输入…...
Python基础练习•二
# ## Python编程入门作业 # # ### 选择题 # 1. 假设等号右侧变量都已知的情况下,下列哪个语句在Python中是⾮法的?( B ) # A. x y z 1 # B. x (y z 1) # C. x, y y, x # D. x y # 2. 关于Python变量,下列…...
智慧科技照亮水利未来:深入剖析智慧水利解决方案如何助力水利行业实现高效、精准、可持续的管理
目录 一、智慧水利的概念与内涵 二、智慧水利解决方案的核心要素 1. 物联网技术:构建全面感知网络 2. 大数据与云计算:实现数据高效处理与存储 3. GIS与三维可视化:提升决策支持能力 4. 人工智能与机器学习:驱动决策智能化 …...
Vue3学习笔记(n.0)
vue指令之v-for 首先创建自定义组件(practice5.vue): <!--* Author: RealRoad1083425287qq.com* Date: 2024-07-05 21:28:45* LastEditors: Mei* LastEditTime: 2024-07-05 21:35:40* FilePath: \Fighting\new_project_0705\my-vue-app\…...
基于Spring Boot的在线考试系统
您好!我是专注于计算机技术研究的码农小野。如果您对在线考试系统感兴趣或有相关开发需求,欢迎随时联系我。 开发语言:Java 数据库:MySQL 技术:Spring Boot框架,Java技术 工具:Eclipse&…...
Day65 代码随想录打卡|回溯算法篇---组合总和II
题目(leecode T40): 给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意:解集不能包含…...
C++ 入门03:函数与作用域
往期回顾: C 入门01:初识 C-CSDN博客C 入门02:控制结构和循环-CSDN博客 一、前言 在前面的文章学习中,我们了解了C语言的基础,包括如何定义变量来存储数据,以及如何利用输入输出流实现程序与用户之间的无缝…...
在Linux/Debian/Ubuntu中出现“Could not get lock /var/lib/dpkg/lock-frontend”问题的解决办法
在Linux/Debian/Ubuntu中出现“Could not get lock /var/lib/dpkg/lock-frontend”问题的解决办法 在使用 apt 或 apt-get 进行软件包管理时,有时会遇到以下错误提示: Could not get lock /var/lib/dpkg/lock-frontend - open (11: Resource temporari…...
odoo中的钩子 Hooks
钩子 钩子(Hooks)是一种在特定时间点或特定事件发生时执行自定义代码的机制。它们允许开发者在不修改核心代码的情况下,为Odoo添加自定义功能或扩展现有功能。以下是关于Odoo钩子的一些关键点和常见用法: 一、钩子的类型 pre_i…...
05.C1W4.Machine Translation and Document Search
往期文章请点这里 目录 OverviewWhat you’ll be able to do!Learning Objectives Transforming word vectorsOverview of TranslationTransforming vectors Align word vectorsSolving for RFrobenius normFrobenius norm squaredGradient K nearest neighborsFinding the tr…...
计算机网络——数据链路层(点对点协议PPP)
点对点协议PPP的概述 对于点对点的链路,目前使用得最广泛的数据链路层协议是点对点协议 PPP (Point-to-Point Protocol)。 它主要应用于两个场景: 用户计算机与ISP之间的链路层协议就是点对点协议 PPP,1999年公布了回以在以太网上运行的PPP协…...
信息安全概述
名词解释 大数据:指的是所涉及的资料量规模巨大到无法透过主流软件工具,在合理时间内达到撷取、管理、处理、并整理成为帮助企业经营决策更积极目的的资讯。 云计算:是指通过网络提供计算资源(如服务器、存储、数据库、软件开发…...
UE5.3-基础蓝图类整理一
常用蓝图类整理: 1、获取当前关卡名:Get Current LevelName 2、通过关卡名打开关卡:Open Level(by name) 3、碰撞检测事件:Event ActorBeginOverlap 4、获取当前player:Get Player Pawn 5、判断是否相等࿱…...
Python面试题: 如何在 Python 中实现一个线程池?
在 Python 中,实现线程池可以使用内置的 concurrent.futures 模块,该模块提供了一个高层次的接口来管理并发任务。ThreadPoolExecutor 类是实现线程池的主要工具。以下是一些使用示例,展示如何在 Python 中实现和使用线程池: 1. …...
☺初识c++(语法篇)☺
目录 一命名空间(namespace): 二cout与cin简述: 三缺省参数: 四函数重载: 五引用: 六内联函数: 七c中的nullptr简述: 一命名空间(namespace)࿱…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
