联合权值——呆滞大佬der最骚操作?

2023-10-19 11:40

本文主要是介绍联合权值——呆滞大佬der最骚操作?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述:

无向连通图G 有n 个点,n - 1 条边。点从1 到n 依次编号,编号为 i 的点的权值为W i ,每条边的长度均为1 。图上两点( u , v ) 的距离定义为u 点到v 点的最短距离。对于图G 上的点对( u, v) ,若它们的距离为2 ,则它们之间会产生Wu×Wv 的联合权值。

请问图G 上所有可产生联合权值的有序点对中,联合权值最大的是多少?所有联合权值之和是多少?

输入格式:

第一行包含1 个整数n 。

接下来n - 1 行,每行包含 2 个用空格隔开的正整数u 、v ,表示编号为 u 和编号为v 的点之间有边相连。

最后1 行,包含 n 个正整数,每两个正整数之间用一个空格隔开,其中第 i 个整数表示图G 上编号为i 的点的权值为W i 。

输出格式:

输出共1 行,包含2 个整数,之间用一个空格隔开,依次为图G 上联合权值的最大值

和所有联合权值之和。由于所有联合权值之和可能很大,输出它时要对10007 取余。

样例输入:

5  
1 2  
2 3
3 4  
4 5  
1 5 2 3 10 

样例输出:

20 74

提示:

【样例说明】

1498614983226819123.png

本例输入的图如上所示,距离为2 的有序点对有( 1,3) 、( 2,4) 、( 3,1) 、( 3,5) 、( 4,2) 、( 5,3) 。

其联合权值分别为2 、15、2 、20、15、20。其中最大的是20,总和为74。

【数据说明】

对于30% 的数据,1 < n≤ 100 ;

对于60% 的数据,1 < n≤ 2000;

对于100%的数据,1 < n≤ 200 , 000 ,0 < wi≤ 10, 000 。

时间限制:1000ms
空间限制:256MByte

这个题目暴力枚举很明显不是正解,但是显然我们需要将各种点之间是否相连这个状态给保存下来,但是由题目可知,n<=200000,所以要是开二维数组开满的话起码得要20万*20万的数组,这个肯定是开不下的。所以这个时候又是STL上场的时候了,我们可以用vector来减少无用的空间。同时这个题目中所求的联合权值的总和可以用加法结合律来优化(虽然听起来很智障,但是用还是很好用的)。对于一个节点来说,可以被看成是其相连两个节点的中间点,假设有点s连着a,b,c,d四个点,所以对于s来说其联合权值的总和为ab+ac+ad+bc+bd+cd,所以就是加法结合律了,等等,你可能会发现一个东西,这怎么用加法结合律。其实,以上这个式子是错的,因为题目中有一句话讲到一下几个字,有!序!点!对!所以说,ac与ca都是要算一遍的,所以其实是,ab+ac+ad+ba+bc+bd+ca+cb+cd+da+db+dc,然后就是a*(b+c+d)+b*(a+c+d)+c*(a+b+d)+d*(a+b+c),(这个是不是乘法结合律?)所以我们可以看成a*(sum-a)+b*(sum-b)+c*(sum-c)+d*(sum-d),所以将每个节点边上节点权值之和求出放在结构体中,这个问题就被大大地简化了。

#include<bits/stdc++.h>
using namespace std;
vector v[200001];
long long s[200001],w[200001],n,maxn,sum;
int main(){cin>>n;for (int i=1,a,b; i<n; i++){cin>>a>>b;v[a].push_back(b);//将与a相连的点存在v[a]中v[b].push_back(a);//将与b相连的点存在v[b]中}for (int i=1; i<=n; i++)cin>>w[i];//w记录点的权值for (int i=1; i<=n; i++){long long maxn1,maxn2;maxn1=0;maxn2=0;for (int l=0; l<v[i].size(); l++){s[i]+=w[v[i][l]];//s[i]存与i节点相连的节点权值之和if (s[i]>10007) s[i]-=10007;//玄学,减比取模快if (w[v[i][l]]>maxn1){maxn2=maxn1;maxn1=w[v[i][l]];}//maxn1与maxn2分别为与i节点相连节点中第一和第二大的权值else if (w[v[i][l]]==maxn1 || w[v[i][l]]>maxn2)maxn2=w[v[i][l]];}//随时准备更新manx2if (maxn1*maxn2>maxn)maxn=maxn1*maxn2;//maxn即为最大权值}for (int i=1; i<=n; i++){for (int l=0; l<v[i].size(); l++){sum+=(s[i]-w[v[i][l]])*w[v[i][l]];//迷之加法结合律(乘法结合律)sum%=10007;	}}cout<<maxn<<" "<<sum%10007;return 0;
}

你以为这篇博客到这里就完了?大错特错,标题告诉我们,接下来才是正题,那就是呆滞大佬der最骚操作。呆滞大佬当初写这个题目的时候,就想到了他之前那写过的天天爱跑步,于是他就写了一个弱化的天天爱跑步(虽然感觉这两个题目没有任何关系)。呆滞大佬的想法就是,用两个结构体,分别是点和边,其中的边是有向边,题目中为无向边,只要看成两条无向边即可。我们可以先贴代码,然后再讲些别的东西。

#include<bits/stdc++.h>
using namespace std;
const int mos=200005;
struct point{long long ti,value,first,second,sum;
}b[mos<<1];
struct edge{int sta,ed;//就是start和end
}a[mos<<1];
bool mmp(edge a,edge b){return a.sta<b.sta;
}
long long num1=0,num2=0,x,n,ss;
int main(){cin>>n;for (int i=1; i<n; i++){cin>>a[(i<<1)-1].sta>>a[(i<<1)-1].ed;a[i<<1].sta=a[(i<<1)-1].ed;a[i<<1].ed=a[(i<<1)-1].sta;b[a[i<<1].sta].ti++;b[a[i<<1].ed].ti++;}sort(a+1,a+(n<<1)-1,mmp);//将边按照起点从小到大排序for (int i=1; i<=n; i++)b[i].ti+=b[i-1].ti;//求ti的前缀和。for (int i=1; i<=n; i++)cin>>b[i].value;for (int i=1; i<=n; i++){for (int l=b[i-1].ti+1; l<=b[i].ti; l++){b[i].sum+=b[a[l].ed].value;if (b[a[l].ed].value>b[i].first){b[i].second=b[i].first;b[i].first=b[a[l].ed].value;}else if (b[a[l].ed].value>b[i].second) b[i].second=b[a[l].ed].value;}b[i].sum%=10007;}for (int i=1; i<=n; i++){for (int l=b[i-1].ti+1; l<=b[i].ti; l++){num2+=b[i].value*(b[a[l].ed].sum-b[i].value);num2%=10007;if (ss<b[a[l].ed].first*b[a[l].ed].second)ss=b[a[l].ed].first*b[a[l].ed].second;if (ss>num1) num1=ss;}}cout<<num1<<" "<<num2;return 0;
}

其中最迷离的应该是在point结构体中的ti变量了,ti所代表的意思即为b节点在边中为起点的次数。其中最骚的就是这个ti的前缀和了!看完这个代码你就会发现呆滞大佬用ti的前缀和解决了开无用数组所造成的浪费,其中b[i].ti-b[i-1].ti-1就是在上一个程序中的vector v.size(),这样是坠骚滴。b[i].ti和a[b[i].ti]的关系就是不言而喻的,慢慢体会就会感觉……异常地骚。震惊!明天居然还要考试!

made by cain-

转载于:https://www.cnblogs.com/cain-/p/7306003.html

这篇关于联合权值——呆滞大佬der最骚操作?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Mysql表的简单操作(基本技能)

《Mysql表的简单操作(基本技能)》在数据库中,表的操作主要包括表的创建、查看、修改、删除等,了解如何操作这些表是数据库管理和开发的基本技能,本文给大家介绍Mysql表的简单操作,感兴趣的朋友一起看... 目录3.1 创建表 3.2 查看表结构3.3 修改表3.4 实践案例:修改表在数据库中,表的操作主要

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

Python使用DrissionPage中ChromiumPage进行自动化网页操作

《Python使用DrissionPage中ChromiumPage进行自动化网页操作》DrissionPage作为一款轻量级且功能强大的浏览器自动化库,为开发者提供了丰富的功能支持,本文将使用Dri... 目录前言一、ChromiumPage基础操作1.初始化Drission 和 ChromiumPage

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

Redis中管道操作pipeline的实现

《Redis中管道操作pipeline的实现》RedisPipeline是一种优化客户端与服务器通信的技术,通过批量发送和接收命令减少网络往返次数,提高命令执行效率,本文就来介绍一下Redis中管道操... 目录什么是pipeline场景一:我要向Redis新增大批量的数据分批处理事务( MULTI/EXE

使用Python高效获取网络数据的操作指南

《使用Python高效获取网络数据的操作指南》网络爬虫是一种自动化程序,用于访问和提取网站上的数据,Python是进行网络爬虫开发的理想语言,拥有丰富的库和工具,使得编写和维护爬虫变得简单高效,本文将... 目录网络爬虫的基本概念常用库介绍安装库Requests和BeautifulSoup爬虫开发发送请求解

Oracle存储过程里操作BLOB的字节数据的办法

《Oracle存储过程里操作BLOB的字节数据的办法》该篇文章介绍了如何在Oracle存储过程中操作BLOB的字节数据,作者研究了如何获取BLOB的字节长度、如何使用DBMS_LOB包进行BLOB操作... 目录一、缘由二、办法2.1 基本操作2.2 DBMS_LOB包2.3 字节级操作与RAW数据类型2.

JDK多版本共存并自由切换的操作指南(本文为JDK8和JDK17)

《JDK多版本共存并自由切换的操作指南(本文为JDK8和JDK17)》本文介绍了如何在Windows系统上配置多版本JDK(以JDK8和JDK17为例),并通过图文结合的方式给大家讲解了详细步骤,具有... 目录第一步 下载安装JDK第二步 配置环境变量第三步 切换JDK版本并验证可能遇到的问题前提:公司常