首页 > 其他分享 >abc282E - Choose Two and Eat One

abc282E - Choose Two and Eat One

时间:2023-10-14 15:11:38浏览次数:43  
标签:f2 abc282E tot define Choose fo include Eat lld

E - Choose Two and Eat One
非常巧妙的一集

可以将整个局面看作一张图,选两个数获得的score就是它们的边权,然后做最大生成树,不难发现操作和建树之间是一一对应的。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef double db;
typedef long long ll;
const int N=500+5;
const ll inf=1ll<<60;
struct node{
	ll x,y,v;
};
node v[N*N];

ll f[N],a[N],n,m,tot,f1,f2;
ll find(ll x){
	if (x==f[x]) return x;
	return f[x]=find(f[x]);
}
ll power(ll a,ll b){
	ll t=1,y=a;
	while (b){
		if (b&1) t=t*y%m;
		y=y*y%m;
		b/=2;
	}
	return t;
}
bool cmp(node a,node b){
	return a.v>b.v;
}
int main()
{ 
//	freopen("data.in","r",stdin);
	
	scanf("%lld %lld",&n,&m);
	fo(i,1,n) scanf("%lld",&a[i]);
	
	fo(i,1,n) {
		fo(j,i+1,n) {
			v[++tot]=(node){i,j, (power(a[i],a[j])+power(a[j],a[i]))%m };
		}
	}
	
	sort(v+1,v+tot+1,cmp);
	
	fo(i,1,n) f[i]=i;
	
	ll ans=0;
	fo(i,1,tot) {
		f1=find(v[i].x);
		f2=find(v[i].y);
		if (f1^f2) {
			ans+=v[i].v;
			f[f1]=f2;
		}
	}
	
	printf("%lld",ans);
	return 0;
}

标签:f2,abc282E,tot,define,Choose,fo,include,Eat,lld
From: https://www.cnblogs.com/ganking/p/17764184.html

相关文章

  • How to use Linux shell script to create a command line interactive menu window i
    HowtouseLinuxshellscripttocreateacommandlineinteractivemenuwindowinterfaceAllInOne如何使用Linuxshellscript制作一个命令行交互式菜单窗口界面AllInOneQ:如何实现一个类似raspi-config的交互式命令行菜单功能raspi-configistheRaspberr......
  • world creator地形编辑器的基础操作
    worldcreator地形编辑器的基础操作worldcreator是一款实时地形、景观生成器。不仅好上手,生成的高度图和纹理贴图和obj模型可以导入Blender、ue4、ue5、Unity、C4D等三维软件、利用它快速设置地形。打开软件,在界面,左边是新建文件,右边是打开文件。界面基本移动:键盘的WAS......
  • Vue3| create-vue 脚手架工具
    create-vue是Vue官方新的脚手架工具,底层切换到了vite(下一代构建工具),为开发提供极速响应 使用 create-vue创建项目:1.前提环境条件:  已安装16.0或更高版本的Node.js(node-v)2.创建一个Vue应用:npminitvue@latest(这一指令将会安装并执行create-vue)启动项目:......
  • leaflet使用heatmap.js出现heatmap.js:527 Uncaught TypeError: Cannot assign to rea
    一、问题背景问题是这样发生的,因为项目中需要实现热力图的功能,所以使用了第三方的库heatmap.js。但是在一些浏览器中使用它时,会出现这个错误:>UncaughtTypeError:Cannotassigntoreadonlyproperty'data'ofobject'#<ImageData>'出现问题的原因是因为img.data=im......
  • Windows使用filebeat+ELK搭建日志搜集系统
     Jdk与Elastic版本对应关系:https://www.elastic.co/cn/support/matrix#matrix_jvm下载地址:Elasticsearch:https://www.elastic.co/cn/downloads/elasticsearchLogstash:https://www.elastic.co/cn/downloads/logstashKibana:https://www.elastic.co/cn/downloads/kibana......
  • Fi-GNN: Modeling Feature Interactions via Graph Neural Networks for CTR Predicti
    目录概Fi-GNN代码LiZ.,CuiZ.,WuS.,ZhangX.andWangL.Fi-GNN:Modelingfeatureinteractionsviagraphneuralnetworksforctrprediction.CIKM,2019.概"图网络"用在精排阶段(算哪门子图网络啊).Fi-GNN一个item可能有多种field,比如:\[\underbrace......
  • K8s部署轻量级日志收集系统EFK(elasticsear + filebeat + kibana)
    目录K8s部署EFK(elasticsearch+filebeat+kibana)日志收集一.准备镜像二.搭建Elasticsearch+kibana1.在可执行kubectl命令的服务器准备安装的yml文件2.在elasticsearch-kibana目录下创建配置文件elasticsearch.yml3.创建kibana配置文件kibana.yml4.在k8s中创建elasticsearch和k......
  • seata事务管理
    seata事务管理中三个重要角色:TC事务协调者,维护全局和分支事务的状态,协调全局事务的提交与回滚TM事务管理者,定义全局事务的范围,全局事务的开始,事务的提交与回滚RM资源管理者,管理分支事务处理的资源,和TC交谈以注册分支事务,报告分支事务状态,并驱动事务的提交和回滚......
  • Go - Creating Images
    Problem: Youwanttocreateanimagefromscratch.Solution: CreateoneoftheImageimplementationstructs(e.g.,NRGBA)andpopulateitwiththeappropriatedata. Asyourememberfromearlier,NRGBAhasthreeattributes:Pix•Asliceofbytesthat......
  • Go - Creating Graphs
    Problem: Youwanttocreateaweightedgraphdatastructure.Solution: CreatestructsfornodesandedgesandplacetheminaGraphstruct.CreateandattachfunctionstoGraphtocreatenodesandedgesforthegraph. Graphsareverycommonnonlineard......