【DG 特长生2019】模拟赛赛后总结(2024.1.24)

打了330pt,订正后350pt

T1 签到

T2 dfs+剪枝(虽然我写挂了) 

T3 NOIP原题

T4 floyd

主要是想分享一下T4。

写了一种基于floyd的做法。

感觉好像和大部分人的写法不太一样。

因为看到大小关系,我就想到了传递性。

floyd是可以维护传递性的。

至此,此题的一种写法诞生了。

因为比较板子,所以比拓扑排序的要好写一点。

#include<bits/stdc++.h>
using namespace std;
int n,k;
string a[500005];
int f[30][30];//表示i是否小于j
bool vis[31];
bool know[31];
void add(string a,string b){
	int la = a.size(),lb = b.size();
	for(int i = 0;i < la;i++)vis[a[i]-'a'+1] = 1;
	for(int i = 0;i < lb;i++)vis[b[i]-'a'+1] = 1;
	for(int i = 0;i < la&&i < lb;i++){
		int aa = a[i]-'a'+1,bb = b[i]-'a'+1;
		if(aa != bb){
		//	cout<<a[i]<<" "<<b[i]<<" "<<aa<<" "<<bb<<endl;
		    f[aa][bb] = 1;
			break;
		}
	}
}
void floyd(){
	for(int k = 1;k <= 26;k++){
		for(int i = 1;i <= 26;i++){
			for(int j = 1;j <= 26;j++){
				if(f[i][k] == 1&&f[k][j] == 1){
					f[i][j] = 1;
				}
				
			}
		}
	}
}
string p;
char pr[31]; 
int tot;
int kth[31];
int main(){
	freopen("resume.in", "r", stdin);
	freopen("resume.out", "w", stdout);
	//ios::sync_with_stdio(0); 
    cin>>n>>k;
    for(int i = 1;i <= 26;i++){
    	for(int j = 1;j <= 26;j++){
    	    f[i][j] = -1;
	    }
	    
	}
    for(int i = 1;i <= k;i++){
    	cin>>a[i];
    	if(i > 1){
    		add(a[i-1],a[i]);
		}
	}
	cin>>p;
    floyd();
    //cout<<f[1][5]<<endl;
    for(int i = 1;i <= 26;i++){
    	if(vis[i]){
    		pr[++tot] = char(i+'a'-1);
		}
	}
    for(int i = 1;i <= 26;i++){
    	if(vis[i]){
    //	cout<<(char)('a'+i-1)<<":";
    	int res = 0;
    	for(int j = 1;j <= 26;j++){
    	    if(f[i][j] == 1){
    	    //	cout<<(char)('a'+j-1)<<" ";
    	    	res++;
			}
	    }
	    if(know[n-res]!=0){
	    	cout<<0;
	    	return 0;
		}
		know[n-res] = 1;
	    kth[i+'a'-1] = n-res;
	    //cout<<n-res<<endl;
	}
	}
	for(int i = 0;i < p.size();i++){
		if(kth[p[i]] == 0){
			cout<<0;
			return 0;
		}
	}
	for(int i = 0;i < p.size();i++){
	    cout<<pr[kth[p[i]]];
	}
	return 0;
} 

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

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

相关文章

端口隔离技术

概念 端口隔离可实现同一VLAN内端口之间的隔离&#xff0c;为用户提供了更安全、更灵活的组网方案。 为了实现报文之间的二层隔离&#xff0c;用户可以将不同的端口加入不同的VLAN&#xff0c;但这样会浪费有限的VLAN资源。采用端口隔离功能&#xff0c;可以实现同一VLAN内端口…

探索 XMLHttpRequest:网页与服务器的异步通信之道(下)

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

HarmonyOS鸿蒙学习基础篇 - Text文本组件

该组件从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 Text文本组件是可以显示一段文本的组件。该组件从API Version 7开始支持&#xff0c;从API version 9开始&#xff0c;该接口支持在ArkTS卡片中使用。 子组件 可…

ChromeDriver谷歌驱动最新版安装120/121/122

chromeDriver最新版本下载 最新驱动 https://googlechromelabs.github.io/chrome-for-testing/参考&#xff1a; https://blog.csdn.net/m0_57382185/article/details/134007615

Transfomer相关最新研究

文章目录 iTransformerContiFormerBasisFormerMTSTMultiResFormerFPPformerDOzerfomerCSformerMASTERPCA former **PDFPathformerVQ-TR iTransformer ContiFormer BasisFormer MTST MultiResFormer FPPformer DOzerfomer CSformer MASTER PCA former ** PDF Pathformer VQ-TR…

VG-4231CE压控晶体振荡器

随着科技的飞速发展&#xff0c;各类电子设备对于稳定且精确的信号需求越来越高。VG-4231CE压控晶体振荡器&#xff08;VCXO&#xff09;&#xff0c;它能提供稳定的工作环境和高精度信号&#xff0c;助您轻松应对各种高难度信号处理任务。3MHz至50MHz的频率范围&#xff0c;输…

云卷云舒:PostgreSQL的事儿你听说了吗?

最近&#xff0c;PostgreSQL公布了全球贡献者名单。 以上是全球贡献者主要成员&#xff0c;可以看出都是外国人&#xff0c;除了一名台湾省贡献者外&#xff0c;几乎再看不到中国贡献者的身影。 那么偌大的中国&#xff0c;为什么在PostgreSQL的全球贡献者名单里面就看不到人呢…

linux 安装 grafana

Ubuntu 和 Debian(64 位)SHA256&#xff1a; e551434e9e3e585633f7b56a33d8f49cda138d92ad69c2c29dcec2c3ede84607 sudo apt-get install -y adduser libfontconfig1 muslwget https://dl.grafana.com/enterprise/release/grafana-enterprise_10.2.3_amd64.debsudo dpkg -i gra…

4.Hive表更新字段信息,一次讲明白

Hive表更新字段信息 一、更新表字段语句1、修改字段名称2、修改字段类型3、修改字段备注 二、总结 一、更新表字段语句 ALTER TABLE table_name [PARTITION partition_spec] CHANGE [COLUMN] col_old_name col_new_name column_type[COMMENT col_comment] [FIRST|AFTER column…

深度学习(5)--Keras实战

目录 一.Keras基础概念 二.如何跑通Keras项目 2.1.在cmd上跑通 2.2.在PyCharm上跑通 一.Keras基础概念 Keras是深度学习中的一个神经网络框架&#xff0c;是一个高级神经网络API&#xff0c;用Python编写&#xff0c;可以在TensorFlow&#xff0c;CNTK或Theano之上运行。 …

SpringCloud Alibaba Sentinel 与 SpringCloud Gateway 的限流有什么差别?(三种限流算法原理分析)

目录 一、Sentinel 与 Gateway 的限流有什么差别&#xff1f; 1.1、前置知识 - 四种常见的限流算法 1.1.1、Tips 1.1.2、计数器算法 1&#xff09;固定窗口计数器算法 2&#xff09;滑动窗口计数器算法 1.1.3、令牌桶算法 1.1.4、漏桶算法 1.2、解决问题 一、Sentinel…

如何通过 Nginx 反向代理提高网站安全性和性能?

如何通过 Nginx 反向代理提高网站安全性和性能&#xff1f; 引言Nginx 反向代理的基本原理什么是反向代理&#xff1f;反向代理的工作方式反向代理的好处 配置 Nginx 反向代理的基本步骤1. 安装 Nginx2. 编辑 Nginx 配置文件3. 设置反向代理配置4. 测试并重启 Nginx 提高安全性…

NineData支持制定安全、可靠的SQL开发规范

在和数据库打交道中&#xff0c;不管是数据库管理员&#xff08;DBA&#xff09;还是开发人员&#xff0c;经常会做一些CURD操作。因为每个人对数据库的了解程度不一样&#xff0c;所以在项目上线时&#xff0c;往往还需要专职人员对数据库的CURD操作进行审核&#xff0c;确保C…

第21课 在Android Native开发中架起java与c++互通的桥梁

在开始本节课&#xff0c;我尝试把项目拷贝到另一台电脑上以便继续工作&#xff0c;但出现了大量的“could not be resolved”问题&#xff0c;尝试包含新的include路径也无法解决该问题&#xff0c;最后删除了项目的Native Support&#xff0c;然后重新添加Native Support才解…

1.19号网络

超时检测 概念 1> 在网络通信中&#xff0c;有很多函数是阻塞函数&#xff0c;会导致进程的阻塞&#xff0c;例如&#xff1a;accept、recv、recvfrom、等等 2> 为了避免进程在阻塞函数处&#xff0c;无休止的等待&#xff0c;我们可以设置一个超时时间&#xff0c;当…

unity学习笔记----游戏练习05

一、阳光的收集和搜集动画开发 1.收集阳光的思路&#xff1a;当鼠标点击到阳光的时候&#xff0c;就可以进行收集了。可以通过为添加一个碰撞器来检测Circle Collider 2D 编写脚本&#xff1a; 在SunManager中写一个增加阳光的方法 //增加阳光 public void AddSubSun(in…

如何利用streamlit 將 gemini pro vision 進行圖片內容介紹

如何利用streamlit 將 gemini pro vision 進行圖片內容介紹 1.安裝pip install google-generativeai 2.至 gemini pro 取 api key 3.撰寫如下文章:(方法一) import json import requests import base64 import streamlit as st 讀取圖片檔案&#xff0c;並轉換成 Base64 編…

51-15 视频理解串讲—TimeSformer论文精读

今天读的论文题目是Is Space-Time Attention All You Need for Video Understanding? Facebook AI提出了一种称为TimeSformer视频理解的新架构&#xff0c;这个架构完全基于transformer&#xff0c;不使用卷积层。它通过分别对视频的时间和空间维度应用自注意力机制&#xff…

SpringBoot 3.1.7 集成Kafka 3.5.0

一、背景 写这边篇文章的目的&#xff0c;是记录我在集成kafka客户端遇到的一些问题&#xff0c;文章会记录整个接入的过程&#xff0c;其中会遇到几个坑&#xff0c;如果需要最终版本&#xff0c;直接看最后一节就行了&#xff0c;感觉Spring-Kafka的文档太少了&#xff0c;如…

linux更新内核

内核介绍 官网链接:https://kernel.org 内核下载库: https://mirrors.edge.kernel.org/pub/linux/kernel/ 更新软件源 rootcary:~# apt-get update rootcary:~# sudo apt-get install libncurses5-dev build-essential kernel-package flex bison libelf-dev libssl-dev 下…