首页 > 其他分享 >比赛题目选讲(2023)

比赛题目选讲(2023)

时间:2023-06-07 23:12:48浏览次数:59  
标签:10 题目 int 选讲 2023 return include dist size

5 月

NOIP 2018 模拟 Day2:

ending:给定一棵 \(n\) 个点的树,边权 \(w\in\{0,1\}\)。求出有多少个三元组 \((i,j,k)\),满足 \(dist(i,j),dist(i,k)>0\)。\(1\le n\le 10^5\)。

题解:

若 \(w(i,j)=0\),则将 \(i,j\) 合并进一个连通块内。对于一个连通块,设其大小为 \(size\),则对于该连通块内的一个节点 \(i\),满足 \(dist(i,j)=0\) 或 \(dist(i,k)=0\) 的三元组 \((i,j,k)\) 的数量为 \((size-1)(size-2)+2(size-1)(n-size)\)。

那么 \(ans=n(n-1)(n-2)-\sum size((size-1)(size-2)+2(size-1)(n-size))\)。

时间复杂度 \(O(n\log n)\)。

点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

#define int long long 

const int N = 1e5+10;

int n, ans, p[N], siz[N];

int check(int w) {
	while (w) {
		if (w % 10 != 4 && w % 10 != 7) return 0;
		w /= 10;
	}
	return 1;
}

int find(int x) {
	if (p[x] != x) return find(p[x]);
	return x;
}

void merge(int u, int v) {
	int fu = find(u), fv = find(v);
	if (fu == fv) return ;
	siz[fv] += siz[fu], p[fu] = fv;
	return ;
}

signed main() {
	// freopen("ending.in", "r", stdin);
	// freopen("ending.out", "w", stdout);
	
	scanf("%lld", &n);

	for (int i = 1; i <= n; ++i) p[i] = i, siz[i] = 1;

	
	int u, v, w;
	for (int i = 1; i < n; ++i) {
		scanf("%lld%lld%lld", &u, &v, &w);
		w = check(w);
		if (!w) merge(u, v); // 分割成内部不能到达的连通块
	}

	for (int i = 1; i <= n; ++i) {
		if (i != find(i) || siz[i] < 2) continue ;
		int size = siz[i];
		ans += size*(size-1)*(size-2) + size*(size-1)*(n-size)*2;
	}
	printf("%lld\n", n*(n-1)*(n-2)-ans);
	return 0;
}

/*
10
1 2 8
1 3 7
3 4 47
5 7 23
4 6 4
6 10 747
8 6 57
9 3 447
9 5 88

566
*/

标签:10,题目,int,选讲,2023,return,include,dist,size
From: https://www.cnblogs.com/Jasper08/p/17464839.html

相关文章

  • 2023.06.07训练日志
    TrustNobody简单题,桶排序+前缀和以后直接找\(n-sum_i=i\)的\(i\)LunaticNeverContent对于原序列的每一对不满足回文的位置,记录其差的绝对值取\(\gcd\)。对于已经满足回文的,\(x\)可以为\(\infty\),因此输出\(0\)DreamingofFreedom这道题主要考察线性筛。观察样......
  • 2023.6.701.Linux系统计划任务
    01.Linux系统计划任务1.Crond计划任务概述2.crond配置⽂件详解3.crond计划任务管理4.crond配置编写实例5.crond计划任务调试Atuor:Wingvx:WingspanGo1.Crond计划任务概述什么是计划任务,计划任务类似于我们平时⽣活中的闹钟。在Linux系统的计划任务服务crond可以满......
  • 2023年3月阅读笔记1
    焦油坑入坑前,都会觉得自己战无不胜,就像陷入焦油坑的巨兽,自以为有着庞大的身躯就能在各种的地形中安然度过。在填写志愿的时候,对未来充满希望的孩子们还不知道自己将面临什么,只觉得代码的世界奇妙酷炫,然而代码对于软件系统的开发来说只是水面上的冰山。前人的智慧告诉我们如果没有......
  • 2023年3月阅读笔记3
    画蛇添足过度设计的现象常常存在,据我的观察,这种现象往往出现于极度追求完美的人和刚刚经历过首次开发设计不足的经验教训的人。过度设计的系统在最初就引入了过多的复杂性,导致开发举步维艰,这个问题或许在一个架构师有了一定经历后就自然能够解决,但是“第二个系统”的困境出现时,我......
  • 2023年3月阅读笔记2
    外科手术队伍软件开发的团队选择往往是一个难题。在课程实践的过程中,大家往往渴望抱到大牛的大腿,因为经验丰富的程序员能起到以一敌十的效果,当一个团队中每个人的能力都很强那么这个队伍几乎就成了神话般的精英小队。对于大型的项目,小而美的团队往往有些力不从心,精英也不可能大量......
  • 每日随笔20230607
      这几天临近考试,抓紧复习了已经,一直待在自习室,但是感觉还是有点学不上来,很无力的感觉,但是绝对可以过,估计应该都是七八十分的样子,但是对于知识的掌握还是欠缺,就比如明天要考的工程数学,很迷惑,根本不怎么会,全靠老师给的考点进行突破,但是也有点力不从心,因为看不懂,而且会跳着看,导致......
  • Xshell/Xftp/Xlpd Plus 7:官方免破全功能无限制版(2023更新)
    XshellPlus7是一款集成了Xshell7(SSH客户端)和Xftp7(SFTP客户端)的软件套餐,可以让您在访问远程终端的同时,进行多窗口的文件传输和编辑,大大提高您的工作效率。XshellPlus7支持多种协议,如SSH,SFTP,TELNET,RLOGIN,SERIAL等,还具有强大的安全性和可定制性。本文将为您详细介绍XshellPlus......
  • English Learning Articles 2023-06-07 Nonsurgical cat contraception could help cu
    Nonsurgicalcatcontraceptioncouldhelpcurboverpopulation,studysaysThereareanestimated600milliondomesticcatsintheworld,and80%ofthemareferalorstrayanimals.Spayingandneuteringcatshelpspreventhomelesskittensandovercrowdeda......
  • 2023-06-07:Redis 持久化方式有哪些?以及有什么区别?
    2023-06-07:Redis持久化方式有哪些?以及有什么区别?答案2023-06-07:Redis提供了两种持久化机制:RDB和AOF。RDBRDB持久化是将Redis当前进程中的数据生成快照并保存到硬盘的过程。快照指的是Redis在某一时刻的内存状态的记录,类似于拍照一样把数据保存下来,因此也被称为Redis的数据库快照(Re......
  • 2023-06-07:Redis 持久化方式有哪些?以及有什么区别?
    2023-06-07:Redis持久化方式有哪些?以及有什么区别?答案2023-06-07:Redis提供了两种持久化机制:RDB和AOF。RDBRDB持久化是将Redis当前进程中的数据生成快照并保存到硬盘的过程。快照指的是Redis在某一时刻的内存状态的记录,类似于拍照一样把数据保存下来,因此也被称为Redis的数据库快照(Re......