Codeforces Round 911 (Div. 2)(C~E)(DFS、数论(容斥)、SCC缩点 + DAG图上DP)



​​​​​​1900C - Anji's Binary Tree 

        题意:

凯克西奇一直被安吉冷落。通过一个共同的朋友,他发现安吉非常喜欢二叉树,于是决定解决她的问题,以引起她的注意。Anji 给了 Keksic 一棵有 n个顶点的二叉树。顶点 1 是根,没有父顶点。所有其他顶点都有一个父顶点。每个顶点最多可以有 2个子顶点、一个左子顶点和一个右子顶点。对于每个顶点,安吉都会告诉凯西奇它的左子和右子的索引,或者告诉他它们不存在。

此外,每个顶点上都有一个字母 eq?s_%7Bi%7D,即 "U"、"L "或 "R"。

克克西奇从根开始下棋,他的每一步都是这样走的:

  • 如果当前顶点上的字母是 "U",他就移动到它的父顶点。如果它不存在,他就什么也不做。
  • 如果当前顶点上的字母是 "L",则移动到其左侧子顶点。如果它不存在,则他什么也不做。
  • 如果当前顶点上的字母是 "R",则移动到其右边的子顶点。如果它不存在,则他什么也不做。

在移动之前,他可以执行以下操作:选择任意一个节点,并用另一个节点替换写在上面的字母。

我们想知道的是,当他开始旅行时,他将在某一点到达一片叶子,那么他在旅行前需要做的操作的最小数目。叶子是一个没有子顶点的顶点。他到达哪片叶子并不重要。需要注意的是,他是否会停留在叶子上并不重要,他只需要移动到叶子上。此外,他需要移动多少次才能到达一片叶子也无关紧要。

帮助 Keksic 解开安吉的树,这样他就能赢得她的芳心,让她来到恰恰克。

        思路:转化为到叶子结点最短路,若顶点字母是‘L’,则到达左孩子路径长度为0,若顶点是‘R’,则到达右边孩子长度为0,否则都是1(代表了需要修改),求到达叶子结点路径最小值。

        

// Problem: C. Anji's Binary Tree
// Contest: Codeforces - Codeforces Round 911 (Div. 2)
// URL: https://codeforces.com/contest/1900/problem/C
// Memory Limit: 256 MB
// Time Limit: 2500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
int a[N];
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}
struct Node{
	int l ,  r;
}e[N];
void solve() 
{
	cin >> n;
	string s;
	cin >> s;
	s = " " + s;
//	cout << s[1]<<endl;
	for(int i = 1 ; i <= n ; i ++){
		cin >> e[i].l >> e[i].r;	
	}
	int ans = inf;
	queue< pair<int,int>>q;
	q.push({1 , 0});
	while(!q.empty()){
		auto tmp = q.front();
		q.pop();
		int id = tmp.x , dis = tmp.y;
//		cout << id << dis << endl;
		if(e[id].l != 0){
			int nex = e[id].l;
			if(s[id] != 'L'){
				q.push({nex , dis + 1});
			}
			else{
				q.push({nex , dis});
			}
		}
		if(e[id].r != 0){
			int nex = e[id].r;
			if(s[id] != 'R'){
				q.push({nex , dis + 1});
			}
			else{
				q.push({nex , dis});
			}			
		}
		if(e[id].l == 0 && e[id].r == 0){
			ans = min(ans , dis);
		}
	}
	cout << ans << endl;
}            
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

 1900D - Small GCD 

(太菜了导致坐牢一个半小时,没想到能够预处理因子的价值,下次不会再犯了)

        题意:设 a 、 b 和 c 为整数。函数 f(a,b,c) 的定义如下:将数字 a 、 b 、 c 排序为 a≤b≤c 。然后返回 gcd(a,b) ,其中 gcd(a,b) 表示整数 a 和 b 的 最大公约数 (GCD)。给你一个由 n 个元素组成的数组 a 。计算每个 i 、 j 、 k 的 f(ai,aj,ak) 和,使得 1≤i<j<k≤n 。更正式地说,计算

eq?%5Csum_%7Bi%20%3D%201%7D%5E%7Bn%7D%20%5Csum_%7Bj%20%3D%20i%20&plus;%201%7D%5E%7Bn%7D%20%5Csum_%7Bk%20%3D%20j%20&plus;%201%7D%5E%7Bn%7Df%28a_%7Bi%7D%2Ca_%7Bj%7D%2C%20a_%7Bk%7D%29

        思路:当对a数组进行排序以后会发现,原式子eq?%5Csum_%7Bi%20%3D%201%7D%5E%7Bn%7D%20%5Csum_%7Bj%20%3D%20i%20&plus;%201%7D%5E%7Bn%7D%20%5Csum_%7Bk%20%3D%20j%20&plus;%201%7D%5E%7Bn%7Df%28a_%7Bi%7D%2Ca_%7Bj%7D%2C%20a_%7Bk%7D%29的k变成了一个无效的东西(因为eq?a_%7Bi%7D%20%5Cleq%20a_%7Bj%7D%5Cleq%20a_%7Bk%7D)。原式子变为eq?%5Csum_%7Bi%20%3D%201%7D%5E%7Bn%7D%20%5Csum_%7Bj%20%3D%20i%20&plus;%201%7D%5E%7Bn%7D%20gcd%28a_%7Bi%7D%2Ca_%7Bj%7D%29*%28n%20-%20k%29

再转化一下得到eq?%5Csum_%7Bi%20%3D%201%7D%5E%7Bj%20-%201%7D%20%5Csum_%7Bj%20%3D%202%7D%5E%7Bn%7D%20gcd%28a_%7Bi%7D%2Ca_%7Bj%7D%29*%28n%20-%20j%29.。对于这种所有区间求和问题,考虑右端点递增,然后思考如何去维护左侧所有区间的信息。首先我们如果单纯的两两求gcd肯定是不行的,观察数据后发现a数组的数据很小,也就是说a的因子个数很小。而两个数的gcd也就是他们的最大公共因子。因此可以考虑统计区间内所有因子的个数,然后对于每个右端点eq?a_%7Bj%7D而言,遍历其所有因子,区间之和就是(右端点的因子大小 * 区间内该因子的个数)的总和。但是仔细想想之后发现是有重复的:假如当前因子是2,用2 * 区间内2的因子个数是不正确的,因为有2这个因子也必然会有1这个因子。gcd是两个数的最大公共因子,所以统计因子2时会把1这个因子给撤销掉,后面任意因子也是同理。也就是说,2这个因子的实际价值不是2而是1。3也是同理,3的实际价值需要减去1的实际价值, 而6的实际价值需要减去1、2、3实际价值。因此对于任意一个因子而言,其实际价值需要需要减去其所有不为他本身的因子的实际价值。

        对于每个数的因子,每个因子的实际价值都是可以预处理出来的。做的时候只需要过一下公式即可。

        

// Problem: D. Small GCD
// Contest: Codeforces - Codeforces Round 911 (Div. 2)
// URL: https://codeforces.com/contest/1900/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 1e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
int a[N];
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}
int cnt[N];
vector<int>yinzi[100010];
int val[N];
void solve() 
{
	memset(cnt , 0 , sizeof cnt);
	cin >> n;
	for(int i = 0 ; i < n ; i ++)
		cin >> a[i];
	sort(a , a + n);
	LL ans = 0;
	for(int i = 0 ; i < n - 1; i ++){
		LL sum = 0;
		for(auto it : yinzi[a[i]])
			sum += 1LL * val[it] * cnt[it];
		ans += sum * (n - i - 1);
		for(auto it : yinzi[a[i]]){
			cnt[it]++;
		}		
	}
	cout << ans <<endl;
}            
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
    int maxx = -1;
	auto cmp = [&](int x , int y){
		return x > y;
	};
	for(int i = 1 ; i <= 100000 ; i ++){
		val[i] = i;
		yinzi[i].pb(i);
	}
	for(int i = 1 ; i <= 100000; i ++){
		for(int j = i * 2; j <= 100000 ; j += i){
			yinzi[j].pb(i);
			val[j] -= val[i];
		}
	}
	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

        

E - Transitive Graph 

        (补的时候发现就是个SCC缩点 + DAG图上DP问题)

     题意:给你一个有向图 G ,其中有 n 个顶点和 m条边。

最初,图 H与图 G相同。然后,您决定执行以下操作:

  • 如果存在由顶点 a 、 b 、 c 和 H 组成的三重顶点,且存在一条从 a 到 b 的边和一条从 b 到 c 的边,但没有从 a 到 c 的边,则添加一条从 a 到 c的边。
  • 只要存在这样的三边形,就重复上一步。

注意,执行上述操作后, H中的边的数量最多可达 eq?n%5E2

您还在图 H的顶点上写了一些值。更确切地说,在顶点 i 上写入了 ai的值。

考虑一条由 k个顶点组成的简单路径。索引为 v1,v2,…,vk 的个不同顶点组成的简单路径。这条路径的长度为 k 。该路径的值定义为 eq?%5Csum%20_%7Bi%20%3D%201%7D%5Eka_%7Bv_%7Bi%7D%7D

如果图中没有其他更长的简单路径,那么这条简单路径就是最长的。

在 H中所有最长的简单路径中,找出数值最小的一条。

        思路:观察题目中的操作,其实就是把有向图中一条路径上的点全部两两相连,其实这样操作在求最长简单路径时没有任何意义,因为a到c增加的边在求最长路径时必然会被a到b,b到c这两条边代替。这么做保证了能从一个强连通分量上的任意一点连到其他强连通分量上的任意一点。因此本题就变成了给定一个有向图求最长简单路径中权值最小的那一条。直接强连通分量缩点 + 图上DP就行,用tarjan求出scc,然后按照逆拓扑序dp就行。

        

// Problem: E. Transitive Graph
// Contest: Codeforces - Codeforces Round 911 (Div. 2)
// URL: https://codeforces.com/contest/1900/problem/E
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
LL a[N];
vector<int>e[N];
int dfn[N] , low[N] , ins[N] , idx = 0 , cnt = 0, bel[N];//dfn : dfs的时间戳 low : 子树能跳到的最上方的点 bel : 结点位于哪块强连通分量上
stack<int>stk;
int out[N];
int x[N] , y[N] , ty[N] , ans = 0;
pair<LL,LL>dp[N];
void init(int n){
	idx = cnt = 0;
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0 , low[i] = 0 , ins[i] = 0 , bel[i] = 0 , dfn[i] = 0 , e[i].clear();
	}
}
void tarjan(int u , int fa){//无向图需要fa != u
	dfn[u] = low[u] = ++idx;//dfs序中的顺序
	ins[u] = true;//是否在栈当中
	stk.push(u);//未被切掉的点
	for(auto v : e[u]){
		if(!dfn[v]){
			tarjan(v , u);
			low[u] = min(low[u] , low[v]);
		}
		else{//被访问过了
			if(ins[v]){
				low[u] = min(low[u] , dfn[v]);
			}																																																																																																																																																																							
		}
	}
	if(dfn[u] == low[u]){
		cnt ++;
		int sz = 0;
		LL ch = 0;
		LL sum = 0;
		dp[cnt] = {0 , 0};
		while(true){
			int v = stk.top();
			bel[v] = cnt;
			ch ++;
			sum += a[v];
			ins[v] = false;
			for(int w : e[v]){
				if(bel[w] != cnt && bel[w] != 0){
					if(dp[bel[w]].x > dp[cnt].x){
						dp[cnt] = dp[bel[w]];
					}
					else if(dp[bel[w]].x == dp[cnt].x && dp[bel[w]].y < dp[cnt].y){
						dp[cnt] = dp[bel[w]];
					}
				}
			}
			stk.pop();
			if(v == u){
				break;
			}
		}
		dp[cnt].x += ch;
		dp[cnt].y += sum;
	}
}
void solve() 
{
	cin >> n >> m;
	map<pair<int,int>,int>mp;
	for(int i = 1 ; i <= n ; i ++)
		cin >> a[i];
	for(int i = 0 ; i < m ; i ++){
		int x , y;
		cin >> x >> y;
		if(mp.count({x , y}) || x == y){
			continue;
		}
		else{
			e[x].pb(y);
			mp[{x,y}] = 1;
		}
	}
	for(int i = 1 ; i <= n ; i++){
		if(!dfn[i]) tarjan(i , 0);
	}
/*	for(int i = 1 ; i <= n ; i ++){
		cout << bel[i] << endl;
	}*/
	pair<LL,LL>ans = {0 , 0};
	for(int i = 1 ; i <= cnt ; i ++){
		if(dp[i].x > ans.x){
			ans = dp[i];
		}
		else if(dp[i].x == ans.x && dp[i].y < ans.y){
			ans = dp[i];
		}
	}
	init(n);
	cout << ans.x << " " << ans.y << endl;
}            
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

        

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

[Spring] 字节一面~Spring 如何解决循环依赖问题 以及 @resource 与 @autowire 同时存在时谁生效

文章目录 Spring 如何解决循环依赖问题resource 与 autowire 同时存在时谁生效 Spring 如何解决循环依赖问题 Spring在实例化一个bean的时候&#xff0c;是首先递归实例化其所依赖的所有bean&#xff0c;直到某个bean没有依赖其他bean&#xff0c;此时就会将该实例返回&#x…

基于Java SSM框架+Vue实现大学生兼职信息网站项目【项目源码+论文说明】

基于java的SSM框架Vue实现大学生兼职信息网站演示 摘要 21世纪的今天&#xff0c;随着社会的不断发展与进步&#xff0c;人们对于信息科学化的认识&#xff0c;已由低层次向高层次发展&#xff0c;由原来的感性认识向理性认识提高&#xff0c;管理工作的重要性已逐渐被人们所认…

【GD32307E-START】开发板开箱、开发环境建立及工程模板测试

01-GD32F307E-START开箱、开发环境建立及工程模板测试&#xff08;Keil-MDK GCC Template&#xff09; 兆易GD32307E-START开发板搭载GD32 ARM Cortex-M4微控制器主流芯片GD32F307。 开箱 板子的做工还是非常精良小巧的。有两颗按键&#xff0c;一颗是复位&#xff0c;一颗是…

时间序列预测 — LSTM实现单变量风电滚动预测(Keras)

目录 1 数据处理 1.1 数据集简介 1.2 数据集处理 2 模型训练与预测 2.1 模型训练 2.2 模型滚动预测 2.3 结果可视化 1 数据处理 1.1 数据集简介 实验数据集采用数据集5&#xff1a;风电机组运行数据集&#xff08;下载链接&#xff09;&#xff0c;包括风速、风向、温…

纯新手发布鸿蒙的第一个java应用

第一个java开发鸿蒙应用 1.下载和安装华为自己的app开发软件DevEco Studio HUAWEI DevEco Studio和SDK下载和升级 | HarmonyOS开发者 2.打开IDE新建工程&#xff08;当前用的IDEA 3.1.1 Release&#xff09; 选择第一个&#xff0c;其他的默认只能用(API9)版本&#xff0c;…

居家适老化设计第三十二条---卫生间之扶手

以上产品图片均来源于淘宝 侵权联系删除 居家适老化中的扶手是指在家居环境中&#xff0c;为老年人提供支撑和帮助的装置&#xff0c;通常安装在家中的各个需要扶抓的位置&#xff0c;如楼梯、卫生间、浴室、厨房等处。扶手的设计应考虑老年人的体力、平衡和安全需求&#xf…

顶级Mac数据恢复工具—— 13个 Mac 数据恢复程序榜单

如果您点击此博客&#xff0c;首先可能是您不小心格式化了外部或内部存储&#xff0c;无论是 SD卡还是硬盘&#xff0c;其次&#xff0c;您收到了一些错误消息&#xff0c;表明您丢失了所有内容&#xff0c;现在您已经精疲力竭了的形状。原因可能有多种&#xff1a;您不小心删除…

探索 Linux vim/vi 编辑器:介绍、模式以及基本操作演示

&#x1f490;作者&#xff1a;insist-- &#x1f490;个人主页&#xff1a;insist-- 的个人主页 理想主义的花&#xff0c;最终会盛开在浪漫主义的土壤里&#xff0c;我们的热情永远不会熄灭&#xff0c;在现实平凡中&#xff0c;我们终将上岸&#xff0c;阳光万里 ❤️欢迎点…

Slf4j使用Logback时,Logback如何初始化

前言 Slf4j SLF4J&#xff0c;全称 Simple Logging Facade for Java&#xff0c;是一个用于Java编程语言的日志系统抽象层。它为多种现有日志框架&#xff08;例如Log4j、java.util.logging等&#xff09;提供了统一的接口, 但自身并不实现日志功能。 SLF4J 允许用户在部署时…

校园导游程序及通信线路设计(结尾附着总源码)

校园导游程序及通信线路设计 摘  要 新生或来访客人刚到校园&#xff0c;对校园的环境不熟悉。就需要一个导游介绍景点&#xff0c;推荐到下一个景点的最佳路径等。随着科技的发展&#xff0c;社会的进步&#xff0c;人们对便捷的追求也越来越高。为了减少人力和时间。针对对…

一起学docker系列之十一使用 Docker 安装 Redis 并配置持久化存储

目录 前言1 基本安装步骤安装Redis镜像&#xff1a;查看已下载的Redis镜像&#xff1a;运行Redis容器&#xff1a;进入Redis容器&#xff1a;使用Redis CLI进行基本操作&#xff1a; 2 配置文件同步准备配置文件&#xff1a;修改Redis配置文件 /app/redis/redis.conf&#xff1…

Project DESFT 白皮书中文版——应用于普惠金融的可信数字凭证解决方案

1. 概述 Project DESFT 是由 Solv 基金会与 zCloak Network 联合设计孵化&#xff0c;以跨境贸易和金融服务为场景的分布式可信数字凭证解决方案&#xff08;Distributed Trusted Digital Credential Solution&#xff09;&#xff0c;项目获得新加坡金管局&#xff08;Monetar…

项目实战——苍穹外卖(DAY10)

如果之前有改过端口号造成WebSocket无法连接的&#xff0c;可以看本篇文章“来单提醒”前的内容进行解决。 课程内容 Spring Task 订单状态定时处理 WebSocket 来单提醒 客户催单 功能实现&#xff1a;订单状态定时处理、来单提醒和客户催单 订单状态定时处理&#xff1a…

Python---练习:使用Python函数编写通讯录系统

预览通讯录系统最终效果 首先&#xff0c;进行需求分析&#xff0c;整个系统功能&#xff0c;分为6个板块&#xff0c;功能如下&#xff1a; ① 添加学员信息 ② 删除学员信息 ③ 修改学员信息 ④ 查询学员信息 ⑤ 遍历所有学员信息 ⑥ 退出系统 系统共6个功能&#xff…

drool 7 multiThread 测试

基本信息 通过option &#xff0c;使用如下代码进行设置 //线程数量10MaxThreadsOption optionMaxThreadsOption.get(10);kieBaseConf.setOption(option);kieBaseConf.setOption(MultithreadEvaluationOption.YES);并发是以CompositeDefaultAgenda/Rule为颗粒度来的&#xff0…

国企央企降薪20%,年终奖也没了。

* 你好&#xff0c;我是前端队长&#xff0c;在职场&#xff0c;玩副业&#xff0c;文末有福利&#xff01; 精彩回顾&#xff1a;京东内部员工&#xff0c;爆料工资与公积金收入&#xff01; 最近&#xff0c;很多国企央企也开始降薪了&#xff0c;有的甚至降幅达到 21%&#…

针对操作系统漏洞的反馈方法

一、针对操作系统漏洞的反馈方法 漏洞扫描指基于漏洞数据库&#xff0c;通过扫描等手段对指定的远程或者本地计算机系统的安全脆弱性进行检测&#xff0c;发现可利用漏洞的一种安全检测&#xff08;渗透攻击&#xff09;行为。在进行漏洞扫描后&#xff0c;需先确定哪些是业务…

2023年亚太杯数学建模C题新能源汽车成品文章(思路模型代码成品)

一、翻译 新能源汽车是指采用先进的技术原理、新技术和新结构&#xff0c;以非常规车用燃料&#xff08;非常规车用燃料是指汽油和柴油以外的燃料(非常规车用燃料是指汽油和柴油以外的燃料&#xff09;&#xff0c;并集成了汽车动力控制和驱动等先进技术的汽车。新能源汽车包括…

博物馆线上导览系统的设计与实现-计算机毕业设计源码64574

摘 要 21世纪的今天&#xff0c;随着社会的不断发展与进步&#xff0c;人们对于信息科学化的认识&#xff0c;已由低层次向高层次发展&#xff0c;由原来的感性认识向理性认识提高&#xff0c;管理工作的重要性已逐渐被人们所认识&#xff0c;科学化的管理&#xff0c;使信息存…

网络运维与网络安全 学习笔记2023.11.25

网络运维与网络安全 学习笔记 第二十六天 今日目标 ACL原理与类型、基本ACL配置、高级ACL配置 高级ACL之ICMP、高级ACL之telnet ACL原理与类型 项目背景 为了企业的业务安全&#xff0c;要求不同部门对服务器有不同的权限 PC1不能访问Server PC2允许访问Server 允许其他所…