【过题记录】8.4(robocom补题,网络流)

今天robocom国赛,因为一个bool函数忘记return 1而裂开(错失21分)
以此为戒


贪心消消乐

在这里插入图片描述


其实就是一个求最大子矩阵和的板子题
利用最大子段和的思想
枚举矩阵中的上下界
压成一维后利用最大子段和 O ( n ) O(n) O(n)处理
复杂度 O ( n 3 ∗ k ) O(n^3*k) O(n3k)
k为执行次数


#include<bits/stdc++.h>
using namespace std;#define int long longconst int N = 5010;
int a[N][N];
int n;
int sum[N][N];
int maxn = 0;
int s[N][N],ss[N][N];
int tot = 0;
int stx,sty,edx,edy,xx,XX,yy,YY;
int cnt = 0;void Swap(){xx = sty; XX = edy; yy = stx; YY = edx;
} 
int ce =0 ;
bool Work(){for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++){s[j][i] = s[j][i-1]+a[i][j];ss[j][i] = ss[j][i-1];if (a[i][j] == 0) ss[j][i]++; }int maxx = 0;xx = n+1; yy = n+1; XX = n+1; YY = n+1;for (stx = 1; stx <= n; stx++){for (edx = stx; edx <= n; edx++){int sum = 0;sty = 1;for (edy = 1; edy <= n; edy++){if (sum > maxx) Swap();int now = s[edy][edx]-s[edy][stx-1];int nowz = ss[edy][edx]-ss[edy][stx-1];if (nowz!=0){sty = edy+1;sum = 0;continue;}if (sum < 0){sum = 0;sty = edy;}sum+=now;if (sum > maxx) maxx = sum,Swap();if (sum == maxx){if (sty < xx) Swap();else if (sty == xx&&stx < yy) Swap();else if (sty == xx && stx == yy&&edy < XX) Swap();else if (sty == xx && stx == yy&&edy == XX && edx < YY) Swap();}}}}if (maxx == 0) return 0;tot+=maxx;printf("(%lld, %lld) (%lld, %lld) %lld\n",xx,yy,XX,YY,maxx);swap(xx,yy); swap(XX,YY);int delx = XX-xx+1;for (int i = xx-1; i >= 1; i--)for (int j = yy; j <= YY; j++)a[i+delx][j] = a[i][j];for (int i = 1; i <= delx; i++)for (int j = yy; j <= YY; j++) a[i][j] = 0;cnt++;bool f = 0;return 1;
}signed main(){cin>>n;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++){cin>>a[i][j];if (a[i][j] > 0) maxn+=a[i][j],ce++;}while (Work()); cout<<tot<<endl;
}

拍照

一道最大权值闭合图的板子题
按如下方式连边:
在这里插入图片描述

最大全职就是 s u m − m a x f l o w sum-maxflow summaxflow
证明尚未完全理清
等我理清了来补


#include<bits/stdc++.h>
using namespace std;const int N = 7e3+100,inf = 1e9+7;
struct Node{int y,Next,v;
}e[2*N];
int len,Linkk[N];
int st,ed;void Insert(int x,int y,int v){e[++len] = (Node){y,Linkk[x],v};Linkk[x] = len;
}queue < int > q;
int d[N];bool bfs(){for (int i = 1; i <= ed; i++) d[i] = 0;while (q.size()) q.pop();d[st] = 1; q.push(st);while (q.size()){int x = q.front(); q.pop();for (int i = Linkk[x]; i; i = e[i].Next){int y = e[i].y; if (!e[i].v ||d[y]) continue;d[y] = d[x]+1; q.push(y);if (y == ed) return 1;}}return 0;
}int dinic(int x,int flow){if (x == ed) return flow;int re = flow , k;for (int i = Linkk[x]; i; i = e[i].Next){int y = e[i].y; if (!e[i].v || d[y] != d[x]+1) continue;k = dinic(y,min(re,e[i].v));if (!k) d[y] = 0;re-=k;e[i].v-=k; e[i^1].v+=k;}return flow-re;
}int n,m;
int main(){cin.tie(0);ios::sync_with_stdio(false);cin>>m>>n; len = 1;st = n+m+1; ed = n+m+2;int sum = 0;for (int i = 1; i <= m; i++){int v; cin>>v; sum+=v;Insert(st,i,v); Insert(i,st,0);int x;cin>>x;while (x){Insert(i,x+m,inf); Insert(x+m,i,0);cin>>x;}}for (int i = m+1,x; i <= m+n; i++)cin>>x,Insert(i,ed,x),Insert(ed,i,0);int flow;int maxf = 0;while (bfs())while (flow = dinic(st,inf)) maxf+=flow;cout<<sum-maxf<<endl;return 0;
}

太空飞行计划问题


与上体一样
所多的就是输出方案
这里最大流用的是dinic算法
如果最后对于一个点i,d[i]不为0,说明这个点在分层图中出现,并且用上了
那么就说明这个仪器用上了


#include<bits/stdc++.h>
using namespace std;const int N = 7e3+100,inf = 1e9+7;
struct Node{int y,Next,v;
}e[2*N];
int len,Linkk[N];
int st,ed;void Insert(int x,int y,int v){e[++len] = (Node){y,Linkk[x],v};Linkk[x] = len;
}queue < int > q;
int d[N];bool bfs(){for (int i = 1; i <= ed; i++) d[i] = 0;while (q.size()) q.pop();d[st] = 1; q.push(st);while (q.size()){int x = q.front(); q.pop();for (int i = Linkk[x]; i; i = e[i].Next){int y = e[i].y; if (!e[i].v ||d[y]) continue;d[y] = d[x]+1; q.push(y);if (y == ed) return 1;}}return 0;
}int dinic(int x,int flow){if (x == ed) return flow;int re = flow , k;for (int i = Linkk[x]; i; i = e[i].Next){int y = e[i].y; if (!e[i].v || d[y] != d[x]+1) continue;k = dinic(y,min(re,e[i].v));if (!k) d[y] = 0;re-=k;e[i].v-=k; e[i^1].v+=k;}return flow-re;
}int flag;
int re(){char c;int r=0;while (c<'0' || c>'9') c=getchar();while (c>='0' && c<='9'){r=r*10+c-'0';c=getchar();}if (c=='\r') flag=1;return r;
}int n,m;
int main(){
//	cin.tie(0);
//	ios::sync_with_stdio(false);scanf("%d %d",&m,&n); len = 1;st = n+m+1; ed = n+m+2;int sum = 0;for (int i = 1; i <= m; i++){int v; scanf("%d",&v); sum+=v;Insert(st,i,v); Insert(i,st,0);int x; flag = 0;while (getchar() == ' '){scanf("%d",&x);Insert(i,x+m,inf); Insert(x+m,i,0); 
//			cout<<"x = "<<x<<endl; }}
//	cout<<"OK";for (int i = m+1,x; i <= m+n; i++)scanf("%d",&x),Insert(i,ed,x),Insert(ed,i,0);int flow;int maxf = 0;while (bfs())while (flow = dinic(st,inf)) maxf+=flow;for (int i = 1; i <= m; i++) if (d[i]) cout<<i<<' ';cout<<endl;for (int i = 1; i <= n; i++) if (d[i+m]) cout<<i<<' '; cout<<endl;cout<<sum-maxf<<endl;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/391352.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

nginx: [error] open() “/run/nginx.pid“ failed (2: No such file or directory)

今天 准备访问下Nginx服务&#xff0c;但是 启动时出现如下报错&#xff1a;&#xff08;80端口被占用&#xff0c;没有找到nginx.pid文件&#xff09; 解决思路&#xff1a; 1、 查看下排查下nginx服务 #确认下nginx状态 ps -ef|grep nginx systemctl status nginx#查看端口…

[CTF]-PWN:格式化字符串漏洞题综合解析

printf型格式化字符串漏洞&#xff1a; 任意地址写&#xff1a; 32位&#xff1a; 例题&#xff08;inndy_echo&#xff09;&#xff1a; 有格式化字符串漏洞&#xff0c;可以修改printf的got表内地址为system&#xff0c;传参getshell 解法一&#xff1a; 在32位中可以使…

vscode的json文件解析

vscode的json文件解析 0.参考链接1.什么是JSON2.JSON语法2.0数据类型2.1对象2.2数组2.3嵌套 3.vscode包含的JSON文件介绍4.vscode包含的JSON文件解析4.1 task.json4.2 launch.json4.3 settings.json4.4 c_cpp_properties.json4.5 package.json&#xff08;详细的看参考链接&…

Python设计模式 - 抽象工厂模式

定义 抽象工厂模式是一种创建型设计模式&#xff0c;它提供了一种创建一系列相关或相互依赖对象的接口&#xff0c;而无需指定它们具体的类。 产品等级结构与产品族 为了更好地理解抽象工厂模式&#xff0c;先引入两个概念&#xff1a; 产品等级结构&#xff1a;就是产品的…

试用AWS全新神器:Amazon Bedrock的「Open Artifacts」版Claude.ai Artifacts

Claude.ai的Artifacts真是太方便了。 GitHub上的AWS Samples仓库中有一个仿制Artifacts的应用程序。 Open Artifacts for Amazon Bedrock https://github.com/aws-samples/open_artifacts_for_bedrockhttps://github.com/aws-samples/open_artifacts_for_bedrock本文将介绍「…

【C++】数组案例 五只小猪称体重

题目&#xff1a;给出五只小猪体重&#xff0c;找出最大的体重的值并打印 思路&#xff1a;利用数组写入五只小猪的体重&#xff0c;让每一个元素都赋值给一个整型变量并每赋值一次就于下一个数组中的元素比&#xff0c;若是大就继续赋值给这个变量&#xff0c;若是小则不赋值…

H81002S 1.7mm网络变压器:BMS汽车蓝牙接收器中的超薄共模电感科技

华强盛导读&#xff1a;在当今这个日新月异的汽车科技领域&#xff0c;每一处细节都蕴含着创新与突破。作为电动汽车心脏的电池管理系统&#xff08;BMS&#xff09;&#xff0c;其高效稳定的运行不仅关乎续航与安全&#xff0c;更是智能化驾驶体验的基石。而在这背后&#xff…

win7安装mysql-installer-community-8.0.11.0

1、安装Microsoft Visual C 2019 Redistributable Package (x64) 官网下载地址&#xff1a;https://learn.microsoft.com/en-us/cpp/windows/latest-supported-vc-redist?viewmsvc-160#latest-microsoft-visual-c-redistributable-version 通过百度网盘分享的文件&#xff1…

Ubuntu安装nvidia-docker并使用的正确方式

Ubuntu安装docker: ubuntu(24.04)以及WSL2安装docker的详细教程_unbantu安装docker-CSDN博客文章浏览阅读646次,点赞5次,收藏3次。默认情况下,只有root用户和docker组的用户才能运行Docker命令。我们可以将当前用户添加到docker组,以避免每次使用Docker时都需要使用sudo。…

DAP-Seq:解锁转录因子结合位点的新钥匙

引言&#xff1a; 在基因组学的浩瀚宇宙中&#xff0c;转录因子如同掌管基因表达的神秘钥匙。它们与DNA上的特定序列结合&#xff0c;调控着生命活动的每一个节拍。然而&#xff0c;传统的研究方法在探索这些结合位点时面临诸多挑战。今天&#xff0c;我们将一起了解一种创新技…

多路I/O复用之select、poll、epoll

一、多进程/多线程模型的不足 为每个请求分配一个进程或线程的方式会带来较大的资源开销。创建和切换进程/线程需要消耗系统资源&#xff0c;包括内存、CPU 时间等。例如&#xff0c;在一个大规模的服务器环境中&#xff0c;如果同时有数千个请求到来&#xff0c;为每个请求创建…

01 LVS负载均衡群集

集群 在互联网应用中&#xff0c;随着站点对硬件的性能、响应速度、服务稳定性、数据可靠性等要求越来越高&#xff0c;单台服务器越来越力不从心 集群的含义 Cluster&#xff0c;集群也叫群集由多台主机构成&#xff0c;但对外只表现为一个整体 集群分类 类型 负载均衡集…

C++初学(10)

10.1、共用体 共用体是一种数据格式&#xff0c;它能够存储不同的数据类型&#xff0c;但只能同时存储其中的一种类型。比如说&#xff1a;结构可以同时存储int、long、和double&#xff0c;而共用体只能存储int、long、或double。共用体的句式与结构相似&#xff0c;但含义不…

《Milvus Cloud向量数据库指南》——Zilliz Cloud 高可用性深度解析:赋能GenAI应用,引领非结构化数据新纪元

在人工智能与大数据技术日新月异的今天,非结构化数据的处理与分析已成为推动行业智能化转型的关键驱动力。Zilliz Cloud,作为基于开源向量数据库Milvus构建的全托管解决方案,不仅革新了非结构化数据的存储与查询方式,更以其卓越的高可用性设计,为开发人员构建高效、可靠的…

c++----内存管理

okk&#xff0c;大家好。我们大家学习了鄙人的前面前面几篇博客&#xff0c;并且还稍微使用了一些c的基础知识。并且我们前面都说过&#xff0c;我们前面学习的知识都说过。我们前面的几篇博客都是我们以后使用c基础。但是我们大家都知道现在代码都关注什么时间啊&#xff0c;内…

【linux深入剖析】初识线程---线程概念

&#x1f341;你好&#xff0c;我是 RO-BERRY &#x1f4d7; 致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f384;感谢你的陪伴与支持 &#xff0c;故事既有了开头&#xff0c;就要画上一个完美的句号&#xff0c;让我们一起加油 目录 1. Linux线程概念什么是线…

k8s中yaml文件的编写

目录 1.编写pod.yaml 2.编写deploment.yaml 3.编写service.yaml关联创建的pod 4.总结获取K8S资源配置清单文件模板方法 方法1&#xff1a;根据现有资源导出yaml文件修改配置&#xff0c;重新创建 方法2&#xff1a;根据现有资源&#xff0c;进入其配置中&#xff0c;复制…

中国AI大模型场景探索及产业应用调研报告

AI大模型发展态势 定义 AI大模型是指在机器学习和深度学习领域中&#xff0c;采用大规模参数(至少在一亿个以上)的神经网络模型&#xff0c;AI大模型在训练过程中需要使用大量的算力和高质量的数据资源。 产业规模 2023年&#xff0c;中国大模型市场规模为147亿。结合《202…

滚雪球学Java(65-5):面对Properties的各种坑,你需要知道的Java小技巧

咦咦咦&#xff0c;各位小可爱&#xff0c;我是你们的好伙伴——bug菌&#xff0c;今天又来给大家普及Java SE相关知识点了&#xff0c;别躲起来啊&#xff0c;听我讲干货还不快点赞&#xff0c;赞多了我就有动力讲得更嗨啦&#xff01;所以呀&#xff0c;养成先点赞后阅读的好…

C++初学者指南-5.标准库(第二部分)--移除元素算法

C初学者指南-5.标准库(第二部分)–移除元素算法 文章目录 C初学者指南-5.标准库(第二部分)--移除元素算法remove / remove_ifremove_copy / remove_copy_ifunique / unique_copyerase / erase_if相关内容 不熟悉 C 的标准库算法&#xff1f; ⇒ 简介 remove / remove…